Example
A grammar that can be parsed by an SLR parser but not by an LR(0) parser is the following:
- (0) S → E
- (1) E → 1 E
- (2) E → 1
Constructing the action and goto table as is done for LR(0) parsers would give the following item sets and tables:
- Item set 0
- S → • E
- + E → • 1 E
- + E → • 1
- Item set 1
- E → 1 • E
- E → 1 •
- + E → • 1 E
- + E → • 1
- Item set 2
- S → E •
- Item set 3
- E → 1 E •
The action and goto tables:
| action | goto | ||
| state | 1 | $ | E |
| 0 | s1 | 2 | |
| 1 | s1/r2 | r2 | 3 |
| 2 | acc | ||
| 3 | r1 | r1 | |
As can be observed there is a shift-reduce conflict for state 1 and terminal '1'. This occurs because, when the action table for an LR parser is created, reduce actions are inserted on a per-row basis. However, by using a follow set, reduce actions can be added with finer granularity. The follow set for this grammar:
| symbol | S | E | 1 |
| following | $ | $ | 1,$ |
A reduce only needs to be added to a particular action column if that action is in the follow set associated with that reduce. This algorithm describes whether a reduce action must be added to an action column:
function mustBeAdded(reduceAction, action){ ruleNumber = reduceAction.value; ruleSymbol = rules.leftHandSide; return (action in followSet(ruleSymbol)) }for example, mustBeAdded(r2, "1") is false, because the left hand side of rule 2 is "E", and 1 is not in E's follow set. Contrariwise, mustBeAdded(r2, "$") is true, because "$" is in E's follow set.
By using mustBeAdded on each reduce action in the action table, the result is a conflict-free action table:
| action | goto | ||
| state | 1 | $ | E |
| 0 | s1 | 2 | |
| 1 | s1 | r2 | 3 |
| 2 | acc | ||
| 3 | r1 | ||
Read more about this topic: Simple LR Parser
Famous quotes containing the word example:
“Our intellect is not the most subtle, the most powerful, the most appropriate, instrument for revealing the truth. It is life that, little by little, example by example, permits us to see that what is most important to our heart, or to our mind, is learned not by reasoning but through other agencies. Then it is that the intellect, observing their superiority, abdicates its control to them upon reasoned grounds and agrees to become their collaborator and lackey.”
—Marcel Proust (1871–1922)