17.7 LR(1) PARSING CONFLICTS

Given a context-free grammar G, if you can build the LR(1) Parse Table that uses one lookahead, and the resulting table has no conflicts in any entries, then G is an LR(1) grammar. If the grammar is not LR(1), then in at least one entry in the table, there would be more than one action.

A shift-reduce error means that for the same lookahead there is a shift operation and also a reduce operation. For example, in Figure 17.10(a), q1 or 1 is the state. Then LR[1, c] has a shift operation for the item A → c · cA. If c ∈ FOLLOW(A), then LR[1, c] also has a reduce by item A → c·, resulting in a shift-reduce conflict.

L R (1) parsing conflicts. State s showing shift-reduce conflict. This state has 2 items. Capital A derives c dot. Capital A derives dot c capital A c. State s showing reduce-reduce conflict. This state has 2 items. Capital S derives b dot. Capital A derives a b dot.

Get An Introduction to Formal Languages and Automata, 7th Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial