SLR Parsing Example and Improvements
- The example in video itself is sufficient for SLR.
- Problem in SLR parsing: It has to re-run the viable prefix automata many times for the stack as at every transition it reads the stack.
Solution: The state of the stack can be remembered. Now stack stores items in this format:<symi, DFA statei>
and statei is the DFA state after sym1sym2…symi is processed. For the start symbol <dummy, startState> is added to the stack.
A GOTO table is made showing the transition from statei to a statej on input A, GOTO[i,A]=j
1. SHIFT x: PUSH <a, x> in stack where a is next input and x is the state;
2. REDUCE would be the same,
An ACTION table is made showing the action to be taken when stack at the statei and a is the next input: ACTION[i,a]=action
if X → α.aβ and GOTO[i,a]=j then ACTION[i, a]=SHIFT to j
if X → α. and a ∈ FOLLOW(X) then ACTION[i,a]=REDUCE X → α
if X → S. then ACTION[i,a]=ACCEPT
- Algorithm for SLR parsing:
LET I=W$ is the input and j=0 LET DFA state 1 has item S' → S INSERT <dummy, 1> in STACK REPEAT CASE action[top_state of stack, input a] of SHIFT to k: PUSH <I[j++] ,k> into the STACK REDUCE X → α: POP α and PUSH <X, goto[top_state of the STACK, X]> ACCEPT: Halt normally ERROR: Abort with a error message
- SLR is very simple and LR(1) is generally used in bottom-up parser. In LR(1) grammar, an item is actually a pair like: T → [T → . int*T, $] means if T → int*T. is read then reduce if next symbol us $. This method is actually is better then searching in follow sets.
- Left-recursion is okay for LR grammars.
- The improved SLR example is here.