LR(0) Parsing for Grammar and String abab Grammar
( S \to AA \mid AB ) ( A \to aA \mid b ) ( B \to BB \mid b )
Step 1: Augment the Grammar
Add ( S' \to S ) Terminals: ( {a, b, $ } ), Non-terminals: ( {S', S, A, B} )
Step 2: LR(0) States
State 0: ( S' \to \cdot S ), ( S \to \cdot AA ), ( S \to \cdot AB ), ( A \to \cdot aA ), ( A \to \cdot b ) ( a \to ) State 3, ( b \to ) State 4, ( S \to ) State 1, ( A \to ) State 2
State 1: ( S' \to S \cdot ) ( $ \to ) Accept
State 2: ( S \to A \cdot A ), ( S \to A \cdot B ), ( A \to \cdot aA ), ( A \to \cdot b ), ( B \to \cdot BB ), ( B \to \cdot b ) ( a \to ) State 3, ( b \to ) State 4, ( A \to ) State 5, ( B \to ) State 6
State 3: ( A \to a \cdot A ), ( A \to \cdot aA ), ( A \to \cdot b ) ( a \to ) State 3, ( b \to ) State 4, ( A \to ) State 7
State 4: ( A \to b \cdot ), ( B \to b \cdot ) ( a, b, $ \to ) Reduce ( A \to b )
State 5: ( S \to AA \cdot ) ( a, b, $ \to ) Reduce ( S \to AA )
State 6: ( S \to AB \cdot ) ( a, b, $ \to ) Reduce ( S \to AB )
State 7: ( A \to aA \cdot ) ( a, b, $ \to ) Reduce ( A \to aA )
State 8: ( B \to \cdot BB ), ( B \to \cdot b ) ( b \to ) State 4, ( B \to ) State 9
State 9: ( B \to B \cdot B ), ( B \to \cdot BB ), ( B \to \cdot b ) ( b \to ) State 4, ( B \to ) State 10
State 10: ( B \to BB \cdot ) ( a, b, $ \to ) Reduce ( B \to BB )
Step 3: Parse abab
Stack: ( [0] ), Input: ( abab$ ) Shift ( a ): Stack: ( [0, a, 3] ), Input: ( bab$ ) Shift ( b ): Stack: ( [0, a, 3, b, 4] ), Input: ( ab$ ) Reduce ( A \to b ): Stack: ( [0, a, 3, A, 7] ), Input: ( ab$ ) Reduce ( A \to aA ): Stack: ( [0, A, 2] ), Input: ( ab$ ) Shift ( a ): Stack: ( [0, A, 2, a, 3] ), Input: ( b$ ) Shift ( b ): Stack: ( [0, A, 2, a, 3, b, 4] ), Input: ( $ ) Reduce ( A \to b ): Stack: ( [0, A, 2, a, 3, A, 7] ), Input: ( $ ) Reduce ( A \to aA ): Stack: ( [0, A, 2, A, 5] ), Input: ( $ ) Reduce ( S \to AA ): Stack: ( [0, S, 1] ), Input: ( $ ) Accept
Note
State 4 has a conflict (( A \to b ) vs. ( B \to b )). Resolved by choosing ( A \to b ) for parsing, but the grammar is not strictly LR(0).