Editing LL parser (section)

=== Parsing procedure ===

In each step, the parser reads the next-available symbol from the input stream, and the top-most symbol from the stack. If the input symbol and the stack-top symbol match, the parser discards them both, leaving only the unmatched symbols in the input stream and on the stack.

Thus, in its first step, the parser reads the input symbol '<nowiki/>'''('''<nowiki/>' and the stack-top symbol 'S'. The parsing table instruction comes from the column headed by the input symbol '<nowiki/>'''('''<nowiki/>' and the row headed by the stack-top symbol 'S'; this cell contains '2', which instructs the parser to apply rule (2).  The parser has to rewrite 'S' to '<nowiki/>'''(''' S '''+''' F ''')'''<nowiki/>' on the stack by removing 'S' from stack and pushing ')', 'F', '<nowiki/>'''+'''<nowiki/>', 'S', '<nowiki/>'''('''<nowiki/>' onto the stack, and this writes the rule number 2 to the output. The stack then becomes:

 [ '''(''', S, '''+''', F, ''')''', '''$''' ]

In the second step, the parser removes the '<nowiki/>'''('''<nowiki/>' from its input stream and from its stack, since they now match. The stack now becomes:

 [ S, '''+''', F, ''')''', '''$''' ]

Now the parser has an ''''a'''' on its input stream and an 'S' as its stack top. The parsing table instructs it to apply rule (1) from the grammar and write the rule number 1 to the output stream. The stack becomes:

 [ F, '''+''', F, ''')''', '''$''' ]

The parser now has an ''''a'''' on its input stream and an 'F' as its stack top. The parsing table instructs it to apply rule (3) from the grammar and write the rule number 3 to the output stream. The stack becomes:

 [ '''a''', '''+''', F, ''')''', '''$''' ]

The parser now has an '<nowiki/>'''a'''' on the input stream and an '<nowiki/>'''a'''<nowiki/>' at its stack top. Because they are the same, it removes it from the input stream and pops it from the top of the stack. The parser then has an '<nowiki/>'''+'''<nowiki/>' on the input stream and '<nowiki/>'''+'''<nowiki/>' is at the top of the stack meaning, like with 'a', it is popped from the stack and removed from the input stream. This results in:

 [ F, ''')''', '''$''' ]

In the next three steps the parser will replace 'F' on the stack by '<nowiki/>'''a'''<nowiki/>', write the rule number 3 to the output stream and remove the '<nowiki/>'''a'''<nowiki/>' and '<nowiki/>''')'''<nowiki/>' from both the stack and the input stream. The parser thus ends with '<nowiki/>'''$'''<nowiki/>' on both its stack and its input stream.

In this case the parser will report that it has accepted the input string and write the following list of rule numbers to the output stream:
: [ 2, 1, 3, 3 ]

This is indeed a list of rules for a [[Context-free grammar#Derivations and syntax trees|leftmost derivation]] of the input string, which is:
: S → '''(''' S '''+''' F ''')''' → '''(''' F '''+''' F ''')''' → '''(''' '''a''' '''+''' F ''')''' → '''(''' '''a''' '''+''' '''a''' ''')'''