LL Parser - General Case

General Case

The parser works on strings from a particular context-free grammar.

The parser consists of

  • an input buffer, holding the input string (built from the grammar)
  • a stack on which to store the terminals and non-terminals from the grammar yet to be parsed
  • a parsing table which tells it what (if any) grammar rule to apply given the symbols on top of its stack and the next input token

The parser applies the rule found in the table by matching the top-most symbol on the stack (row) with the current symbol in the input stream (column).

When the parser starts, the stack already contains two symbols:

where '$' is a special terminal to indicate the bottom of the stack and the end of the input stream, and 'S' is the start symbol of the grammar. The parser will attempt to rewrite the contents of this stack to what it sees on the input stream. However, it only keeps on the stack what still needs to be rewritten.

Read more about this topic:  LL Parser

Famous quotes containing the words general and/or case:

    [The Republican Party] consists of those who, believing in the doctrine that mankind are capable of governing themselves and hating hereditary power as an insult to the reason and an outrage to the rights of men, are naturally offended at every public measure that does not appeal to the understanding and to the general interest of the community.
    James Madison (1751–1836)

    I’m a very smart guy. I haven’t a feeling or a scruple in the world. All I have the itch for is money. I am so money greedy that for twenty-five bucks a day and expenses, mostly gasoline and whisky, I do my thinking myself, what there is of it; I risk my whole future, the hatred of the cops ... I dodge bullets and eat saps, and say thank you very much, if you have any more trouble, I hope you’ll think of me, I’ll just leave one of my cards in case anything comes up.
    Raymond Chandler (1888–1959)