Bottom Up ParsingM for ExpressionsThe Longest Prefix HeuristicBottom Up ParsingRead Supplementary Materials: Context-Free Languages and Pushdown Automata: Parsing, Section 3.Bottom Up ParsingAn Example:[1] E E + T[2] E T[3] T T * F[4] T F[5] F (E)[6] F idid + id * id $Creating a Bottom Up PDAThere are two basic actions:1. Shift an input symbol onto the stack2. Reduce a string of stack symbols to a nonterminalM will be: $/S/p q So, to construct M from a grammar G, we need the following transitions:(1) The shift transitions: ((p, a, ), (p, a)), for each a (2) The reduce transitions:((p, , R), (p, A)), for each rule A in G.(3) The finish up transition (accept):((p, $, S), (q, ))(This is the “bottom-up” CFG to PDA conversion algorithm.)Lecture Notes 18 Bottom Up Parsing 1M for Expressions0 (p, a, ), (p, a) for each a 1 (p, , T + E), (p, E)2 (p, , T), (p, E)3 (p, , F * T), (p, T)4 (p, , F), (p, T)5 (p, , “)”E”(“ ), (p, F)6 (p, , id), (p, F)7 (p, $, E), (q, )trans (action) state unread input stackp id + id * id$ 0 (shift) p + id * id$ id 6 (reduce F id) p + id * id$ F 4 (reduce T F) p + id * id$ T 2 (reduce E T) p + id * id$ E 0 (shift) p id * id$ +E 0 (shift) p * id$ id+E 6 (reduce F id) p * id$ F+E 4 (reduce T F) p * id$ T+E (could also reduce) 0 (shift) p id$ *T+E 0 (shift) p $ id*T+E 6 (reduce F id) p $ F*T+E (could also reduce T F) 3 (reduce T T * F) p $ T+E 1 (reduce E E + T) p $ E 7 (accept) q $ The Parse TreeEE TT T FF Fid + id * id $Producing the Rightmost DerivationWe can reconstruct the derivation that we found by reading the results of the parse bottom to top, producing:E E+ T E+ T* FE+ T* idE+ F* idE+ id* idT+ id*idF+ id*idid+ id*idThis is exactly the rightmost derivation of the input string.Lecture Notes 18 Bottom Up Parsing 2Possible Solutions to the Nondeterminism Problem 1) Modify the language Add a terminator $2) Change the parsing algorithm- Add one character look ahead- Use a parsing table- Tailor parsing table entries by hand- Switch to a bottom-up parser3) Modify the grammar- Left factor- Get rid of left recursionSolving the Shift vs. Reduce Ambiguity With a Precedence RelationLet's return to the problem of deciding when to shift and when to reduce (as in our example).We chose, correctly, to shift * onto the stack, instead of reducing T+E to E.This corresponds to knowing that “+” has low precedence, so if there are any other operations, we need to do them first.Solution:1. Add a one character lookahead capability.2. Define the precedence relation P ( V { $} ) top next stack input symbol symbolIf (a,b) is in P, we reduce (without consuming the input) . Otherwise we shift (consuming the input).How Does It Work?We're reconstructing rightmost derivations backwards. So suppose a rightmost derivation containsabx corresponding to a rule A a and not some rule X abAbx *S We want to undo rule A. So if the top of the stack is a and the next input character is b, we reduce now, before we put the b on the stack.To make this happen, we put (a, b) in P. That means we'll try to reduce if a is on top of the stack and b is the next character. We will actually succeed if the next part of the stack is .Lecture Notes 18 Bottom Up Parsing 3ExampleT*F corresponding to a rule TT*F T * Input: id * id * id E We want to undo rule T. So if the top of the stack is F * and the next input character is anything legal, we reduce. T The precedence relation for expressions:V\( ) id + * $() id +*ET F A Different ExampleE+T * corresponding to a rule EE+T E We want to undo rule E if the input is E + T $or E + T + idbut not E + T * idThe top of the stack is T + E The precedence relation for expressions:V\( ) id + * $() id +*ET F Lecture Notes 18 Bottom Up Parsing 4What About If Then Else?ST if C then ST else STST if C then STWhat if the input isif C1 then if C2 then ST1 else ST2 1 2Which bracketing (rule) should we choose?We don't put (ST, else) in the precedence relation, so we will not reduce at 1. At 2, we reduce: ST2 2elseST1 1then C2ifthenC1ifResolving Reduce vs. Reduce Ambiguities0 (p, a, ), (p, a) for each a 1 (p, , T + E), (p, E)2 (p, , T), (p, E)3 (p, , F * T), (p, T)4 (p, , F), (p, T)5 (p, , “)” E “(“ ), (p, F)6 (p, , id), (p, F)7 (p, $, E), (q, )trans (action) state unread input stackp id + id * id$ 0 (shift) p + id * id$ id 6 (reduce F id) p + id * id$ F 4 (reduce T F) p + id * id$ T 2 (reduce E T) p + id * id$ E 0 (shift) p id * id$ +E 0 (shift) p * id$ id+E 6 (reduce F id) p * id$ F+E 4 (reduce T F) p * id$ T+E (could also reduce) 0 (shift) p id$ *T+E 0 (shift) p $ id*T+E 6 (reduce F id) p $ F*T+E (could also reduce T - F) 3 (reduce T T * F) p $ T+E 1 (reduce E E + T) p $ E 7 (accept) q $ Lecture Notes 18 Bottom Up Parsing 5The Longest Prefix HeuristicA simple to implement heuristic rule, when faced with competing reductions, is:Choose the longest possible stack string to reduce.Example:TSuppose the stack has F * T + E TWe call grammars that become unambiguous with the addition of a precedence relation and the longest string reduction heuristic weak precedence grammars.Possible Solutions to the Nondeterminism Problem in a Bottom Up Parser1) Modify the language Add a terminator $2) Change the parsing algorithm Add one character lookahead Use a precedence table Add the longest first
View Full Document
Unlocking...