SLR Parser Actions

SLR (simple LR) is like LR(0) but reduces on (X::=p.) only if additionally:

  • t $\in$ follow(X) where $t$ is current token

Otherwise, same as LR(0) Parser Actions

Here is then the algorithm:

Let K be parser state at the end of stack and t current token:

  • if there is a transition $(K,t,I)$ for $I$ non-empty
    • shift: push t onto stack
    • if t is EOF, then accept
  • reduce: if item $(X::=p.) \in$ K and t $\in$ follow(X) then
    • pop p from stack
    • push X onto stack
  • if none possible, report syntax error
  • if both possible, shift-reduce conflict: grammar not SLR

Note: SLR uses lookahead in a simpler way than (LR(1)), but it is useful

Example 1: Parsing our example using the automaton we constructed

Example 2: Consider the ambiguous grammar

D' ::= E eof
E ::= E - E
E ::= ID

How does the automaton look like? Compute


where I0 is the initial state.