Lecture Notes 18 Bottom Up Parsing 1 Bottom Up Parsing Read Supplementary Materials: Context-Free Languages and Pushdown Automata: Parsing, Section 3. Bottom Up Parsing An Example: [1] E → E + T [2] E → T [3] T → T * F [4] T → F [5] F → (E) [6] F → id id + id * id $ Creating a Bottom Up PDA There are two basic actions: 1. Shift an input symbol onto the stack 2. Reduce a string of stack symbols to a nonterminal M 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 2 M for Expressions 0 (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 stack p 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 Tree E E T T T F F F id + id * id $ Producing the Rightmost Derivation We can reconstruct the derivation that we found by reading the results of the parse bottom to top, producing: E Þ E+ T Þ E+ T* FÞ E+ T* idÞ E+ F* idÞ E+ id* idÞ T+ id*idÞ F+ id*idÞ id+ id*id This is exactly the rightmost derivation of the input string.Lecture Notes 18 Bottom Up Parsing 3 Possible 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 parser 3) Modify the grammar • Left factor • Get rid of left recursion Solving the Shift vs. Reduce Ambiguity With a Precedence Relation Let'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 symbol If (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 contains βγabx Ý corresponding to a rule A →γa and not some rule X → ab βAbx Ý* 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 4 Example T*F Ý corresponding to a rule T→T*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 • • • • + * E T • • • F • • • • A Different Example E+T Ý* corresponding to a rule E→E+T E We want to undo rule E if the input is E + T $ or E + T + id but not E + T * id The top of the stack is T + E The precedence relation for expressions: V\Σ ( ) id + * $ ( ) • • • • id • • • • + * E T • • • F • • • •Lecture Notes 18 Bottom Up Parsing 5 What About If Then Else? ST → if C then ST else ST ST → if C then ST What if the input is if C1 then if C2 then ST1 else ST2 1 2 Which 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 2 else ST1 1 then C2 if then C1 if Resolving Reduce vs. Reduce Ambiguities 0 (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 stack p id + id * id$ ε 0 (shift) p + id * id$ id 6 (reduce F → id) p +
View Full Document
Unlocking...