LL(1) Parsing

tags: compiler design, systems

LL(1) parsing uses a stack instead of recursive calling like recursive descent parsing, it stands for “left-to-right, leftmost derivation” and the 1 stands for only 1 look-ahead token. “Left-to-right” means that it parses the input from left to right.

How parsing happens

To parse we start by building the following table, we use two stacks, a parsing stack and an input stack. There is some variations with value stack or syntax tree stack. A dollar sign marks the start of the parsing stack, and dollar sign to mark the end of the input string.

We have two actions:

1. Generate, when we have non-terminal on the parsing stack and a terminal in the input stack. We do so by indexing the parsing table
2. Match, when we have non-terminals in the both stacks Last action is the accept action and happens when the both stacks have $ only.

Parsing table

To make choices for which grammar rule to choose we have to index a parsing table. A parsing table is indexed by the current non-terminal at the top of the parsing stack and the terminal at the top of our input stack including the $ sign. We only index when we have a non-terminal in the parsing stack and a terminal in the input. When we select a grammar rule we push it in reverse order to parsing stack during parsing, so we can correctly match the tokens.

The DR said that we can use disambiguiting rules, and this causes the removal of an entry if we have to entries at the same index. While I don’t believe that because the grammar in this way is not LL(1) grammar. See slide 28

Pseudo-code of LL(1) parsing algorithm

NOTE: This algorithm is really important and the DR said it can come in the finals.

LL(1) Grammar

NOTE: LL(1) Grammar can not be ambiguous.

Top down parsers and LL(1) parsing algorithm cant work properly with left recursion, this is because we only use a single look-ahead token to “predict” the grammar rule, this is what the 1 in LL(1) stands for, and when we have a left recursion grammar I can’t be sure which choice is the correct choice to use. I also can only have only one entry in each index of the table. So to use the LL(1) we will have to remove the left-recursion.

You can also think of it another way, if we have left recursion this will lead to an infinite loop in the parsing stack. Section 8, 33:30

Checking if LL(1) from the first and follow sets

Also, you can check if the grammar is LL(1) before doing left-factoring and stuff by looking at each production rule and if the first set of the choices intersect then this is not LL(1), and if a follow and first set of a rule that can produce epsilon intersect, then also this is not LL(1). This is the TA’s answer

Left-recursion removal

1. Simple Immediate left recursion

If i have a grammar with the following form: $A\to A\alpha |\beta$ And alpha and beta are to terminals, I transform my grammar to the following: Example is in slide 32

2. General immediate left recursion

It looks like the same as 1. Example in slide 34

3. General left recursion

This is a bit more hard but is used to remove left recursion in general grammars. It only works of there is no infinite loops or and no $ϵ$ productions. In general left recursion, we take rules and substitute the non-terminals in this production rule by their definition and then apply left recursion removal. We usually don’t have to do this except if there is inherent left recursion that is not noticed.

There is a really good example in slide 37.

NOTE: Left recursion removal does not change the language being recognized, but it changes the grammar and the parse tree, the parse tree will look like it is not left associative but getting the syntax tree will show that it actually is. See slide 41-42

Left factoring

The same problem arises again, due to LL(1) only can choose or predict the grammar rule from 1 look-ahead token only. When a grammar rule has the same prefix token in both of the grammar choices.

Look here why we do common prefix factoring.

If we had a grammar rule that was right recursive and had a common prefix string between the choices and another grammar that gives the same production but was left recursive, doing left refactoring to one and left recursion removal to one will give the same grammar rule. Proof:

Another really good example

Syntax Tree construction

The parsing stack kind of represents what is predicted to be in the input and not what the input really is, we are not sure yet if we will get correct number, and for that the construction of the nodes of the parse tree are delayed until matching happens, a node is created for every match i.e when a structure is removed from the parse stack.

We will have to create action markers like # to represent that an action like addition should happen. While this symbol will be not matched by the grammar it still must be added to perform the operation when it is found in the parsing stack. We also should add a value stack to save the current matched numbers and the operation that will happen on the values. Maybe if we had different operations we would have to push the operator also to track which operation should be done.

*NOTE: Modifications on the LL(1) may be in the final, modifications like to do syntax tree or calculate the value of the algorithm. Most modifications are done with stacks

Questions that can come

1. Show the action stack if it is used to evaluate the expression
2. Modify the algorithm for evaluation
3. Show the action for building the syntax tree (the left on the left child and the right number is the right child because it is the olden, and then do operation when # is found i.e form node and it becomes the left child)
4. Modify the algorithm as before but for syntax tree