Compiler Design and Construction - Old Questions

3.  What are the problem with top down parsers? Explain the LR parsing algorithm.

Top-down parser is the parser which generates parse for the given input string with the help of grammar productions by expanding the non-terminals i.e. it starts from the start symbol and ends on the terminals.

Problems with top-down parsers are:

• Only judges grammatically
• Stops when it finds a single derivation.
• No semantic knowledge employed.
• No way to rank the derivations.
• Problems with left-recursive rules.
• Problems with ungrammatical sentences.

LR Parsing algorithm:

An LR parser comprises of a stack, an input buffer and a parsing table that has two parts: action and goto. Its stack comprises of entries of the form s_o X₁ s₁ X₂s₂ ... X_m s_m where every s_i is called a state and every X_i is a grammar symbol(terminal or non-terminal)

If top of the stack is S_m and input symbol is a, the LR parser consults action[s_m,a] which can be one of four actions.

1. Shift s , where s is a state.

2. Reduce using production A→ b

3. Accept

4. Error

The function goto takes a state and grammar symbol as arguments and produces a state.

The configuration of the LR parser is a tuple comprising of the stack contents and the contents of the unconsumed input buffer. It is of the form

(s_o X₁ s₁ X₂s₂ ... X_m s_m , a_i a_i+1 ... a_n $)

1. If action[s_m,a_i] = shift s, the parser executes a shift move entering the configuration

    (s_o X₁ s₁ X₂s₂ ... X_m s_ma_is , a_i+1 ... a_n $) shifting both a_i and the state s onto stack.

2. If action[s_m,a_i] = reduce A→ β , the parser executes a reduce move entering the configuration

    (s_o X₁ s₁ X₂s₂ ... X_m-r s_m-r As , a_i a_i+1 ... a_n $) . Here s = goto[s_m-r,A] and r is the length of handle β.

Note: if r is the length of β then the parser pops 2r symbols from the stack and push the state as on goto[s_m-r,A] . After reduction , the parser outputs the production used on reduce operation. A→β

3. If action[s_m,a_i] = Accept, then parser accept i.e. parsing successfully complete and stop.

4. If action[s_m,a_i] = error then call the error recovery routine.