tags: compiler design, systems
SLR(1) parsing is similar to the LR(0), but it uses a single look-ahead to token to direct its actions. This allows the presence of two different complete items in a state, and also allows the presence of a shift and complete items to be together.
The Algorithm
When to do reduction
If the algorithm is currently in a complete state, it looks at the Follow set of the grammar rule that is inside this state, and for every symbol in the Follow set a reduction action is entered in the table at the place of the symbol.
The usage of the Follow set has a a good meaning since, if the next token is in the follow set of the rule, then it means that this grammar is completely in the parsing stack and it is ok to reduce now.
Conflicts
Conflicts can still happen, there is two types of conflicts, reduce/reduce conflicts and this happens when the follow sets of the grammar rules have an intersection and when this happens we say the grammar has a design problem. (The doctor said the sentence before this I don’t really know the meaning of a grammar design problem).
There is also shift-reduce conflicts, this happens when the next terminal token in a grammar rule in a state is in the follow set of a complete item in the same state.
A thought I had in mind is: why there is no conflict if the first of non-terminal is in the follow of a complete item in the same state, the reason is that when the transition to the next state has a non-terminal on the arrow this indicates a reduction not that the next token is a terminal of a non-terminal.
Shift-reduce conflicts can be fixed with a disambiguiting rule that prefers the shift over the reduce.
Questions that can come:
- Say why did you choose SLR(1) in the final and state the conditions of the SLR(1) parser and explain the two algorithms.
NOTE: maybe increasing the look-ahead number can fix some issues but they are not in the syllabus.
A complete example can be found in the slide 8 and 9. Slide 19 is also a really good example.