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:

    Women born at the turn of the century have been conditioned not to speak openly of their wedding nights. Of other nights in bed with other men they speak not at all. Today a woman having bedded with a great general feels free to tell us that in bed the general could not present arms. Women of my generation would have spared the great general the revelation of this failure.
    Jessamyn West (1907–1984)

    A new talker will often call her caregiver “mommy,” which makes parents worry that the child is confused about who is who. She isn’t. This is a case of limited vocabulary rather than mixed-up identities. When a child has only one word for the female person who takes care of her, calling both of them “mommy” is understandable.
    Amy Laura Dombro (20th century)