Issues of Interest After Merging in LALR Parsing

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

Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.
    Blogger Comment
    Facebook Comment

0 comments:

Post a Comment