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.