The parsing process for n+n+n Parsing Input Action stack SO n+n+ns shift 2 2|0n2 +n+ n s reduce E→n 3 S0EI +n +n s shift3 4 S0EI+3 n+n s shifty 5|s0E/+3n4 + n s reduce e→E+n 6 SOEI +n $ shift3 7 S0E1+3 n shift4 SOEl+3n4 s reduce E→E+n 9 S0EI saccept
1 2 3 4 5 6 7 8 9 Parsing stack Input Action $0 $0 n 2 $0E1 $0E1+3 $0E1+3n4 $0E1 $0E1+3 $0E1+3n4 $0E1 n + n + n $ +n + n $ +n + n $ n + n $ + n $ + n $ n $ $ $ shift 2 reduce E →n shift3 shift4 reduce E → E+n shift3 shift4 reduce E → E+n accept The parsing process for n+n+n
Example 5. 11 Consider the grammar of balanced parentheses E Follow sets computation yields Follow(s )=$ and Follow(S)($ ) S S→S (S)S S S→(·S)S (S)S S S→·(S)S S→(S)S
Example 5. 11 Consider the grammar of balanced parentheses S' → S S → (S)S|ε Follow sets computation yields: – Follow(S') = {$} and Follow(S)={$,)}. S’ →·S S →·(S)S S →· 0 S S’ →S· 1 S →(S·)S 3 S →(·S)S S →·(S)S S →· 2 ( S S →(S) ·S S →·(S)S S →· 4 ) S →(S)S· 5 S ( (
The siro parsing table is as follows, where The non -LR(O) states 0, 2, and 4 have both shifts and reductions by thea- production S→￡ State Input Goto S2 r(S→E) r(S→e)1 012345 acce ept S2 r(S→) (S→E) r(S→) r(S→c)|5 r(S→(S)S)r(S→(S)S)
• The SLR(l) parsing table is as follows, where – The non-LR(0) states 0, 2, and 4 have both shifts and – reductions by theε-production S → ε. State Input Goto 0 1 2 3 4 5 ( ) $ S S2 S2 s2 r(S → ε) r(S → ε) s4 r(S → ε) r(S → (S)S) r(S → ε) accept r(S → ε) r(S → ε) r(S → (S)S) 1 3 5
The steps to parse the string (o The stack continues to grow until the final reductions This is characteristic of bottom-up parsers in the presence of right-recursive rules such as s-S)s Thus. right recursion can cause stack overflow. and so is to be avoided if possible Parsing stack Input Action SO (Os shift 2 234 S02 )O) S S→E S0(2S3 )Os shift4 S0(2S3)4 Os shift S0(2S3)4(2 DS reduce S02S3)4(2S3 )S shift4 789 S02S3)4(2S3)4 s reduce s S02S3)4(2S3)4S5 seduces→(S)S S02S3)4S5 S reduce S→(S)S 0S0S1 s accept
• The steps to parse the string ( ) ( ) – The stack continues to grow until the final reductions – This is characteristic of bottom-up parsers in the presence of right-recursive rules such as S → (S)S – Thus, right recursion can cause stack overflow, and so is to be avoided if possible 1 2 3 4 5 6 7 8 9 10 Parsing stack Input Action $0 $0( 2 $0(2S3 $0(2S3)4 $0(2S3)4(2 $0(2S3)4(2S3 $0(2S3)4(2S3)4 $0(2S3)4(2S3)4S5 $0(2S3)4S5 $0S1 ( ) ( )$ ) ( )$ ) ( )$ ( )$ )$ ) $ $ $ $ $ shift 2 reduce S → ε shift4 shift2 reduce S → ε shift4 reduce S → ε reduce S → (S)S reduce S → (S)S accept
5.3.2 Disambiguating rules for Parsing Conflicts
5.3.2 Disambiguating Rules for Parsing Conflicts