Error Detection
Correct Inputs
- Both the CLR and LALR parsers perform the same moves (shift/reduce) on correct inputs although the name of the states on the stack may differ
- For example, the above designed LALR parser puts I89 onto the stack whenever CLR parser puts I8 or I9 on to the stack
- Similarly, LALR parser places I36 whenever CLR parser places I3 or I6 on the stack
Incorrect Inputs:
- There will be some delay in announcing error by LALR parser when compared to CLR parser
- After CLR parser has announced an error
- The LALR parser may perform some reductions but never shifts a symbol before announcing the error
Example: Consider the input ccd$ on both the parsers for the
grammar S → CC C →
cC | d
CLR
|
LALR
|
0 c 3 c d 4
|
0 c 36 c 36 d 48
|
Now, state 4 on $ discovers
|
Now, state 48 on $ has a reduction producing
|
Error
|
0 c 36 c 36 c 89
|
Now, state 89 on $ has a reduction producing
|
|
0 c 36 c 89
|
|
Now, state 89 on $ has a reduction producing
|
|
0 C 2
|
|
Now state 2 on $ discover error.
|
Conflicts: Shift/Reduce Conflict:
This conflict never occurs due to merging.
Example:
- Consider LR(1) grammar. After merge of LR(1) items, the items in a set are [A → α., a] and [B →β.aγ, b]. These have shift/reduce conflict on input symbol ‘a’
- This won’t be possible because items are merged with the same core from the given LR(1) items
- Then the two items [A → α., a] and [B →β.aγ, c] for some ‘c’ must be present in a state of LR(1) items. That means the given LR(1) items has this problem and the given grammar is not LR(1) as we assumed
Conflicts: Reduce/Reduce Conflict
This conflict may occur due to
merging.
Example:
- Consider the LR(1) grammar S → aAd | bBd | aBe |bAd A →c B →c
- After constructing LR(1) items for the grammar and merging, one state with the following items, [A → c., d/e] and [B → c., d/e] are obtained which results in a reduce/reduce conflict