Top Down Parsing
[!question]- How to add precedence to a grammar?
- Determine the number of levels of precedence
- Assign a non terminal for each level
- Add rules in the order of precedence
- Force the compiler to choose the higher precedence productions first
[!question]- What are the levels of precedence for standard algebraic expressions?
- Parentheses
- Multiplication and Division
- Addition and Subtraction
[!question]- When writing the rules of a grammar where should the highest precedence rules be placed? At the last
[!question]- Explain why the highest precedence rules have to be placed at the last Usually the order of evaluation is a Post order walk of the parse tree That means that we have to have the highest precedence things at the last or as the leaves
[!question]- Comment on the recognition power of top-down vs bottom-up parsers Bottom up parsers can recognize more grammars than top-down parsers
[!question]- Why can’t top down parsers handle left recursion? Top down parser build left derivations. If there is left recursion then it will lead to non-termination As we can always expand the left most NT to it recursive counterpart infinite times
[!question]- Formally define left recursion For a grammar $G$ if there exists an $A \in N$ such that $A \Rightarrow^+ A\alpha, \alpha \in (N \cup T)^+$
[!question]- How do you remove direct left recursion? $A \rightarrow A \alpha | \beta$ $\alpha, \beta \in (N \cup T)^+$ and $\alpha, \beta$ doesn’t start with $A$ $A \rightarrow \beta A’$ $A’ \rightarrow \alpha A’ | \varepsilon$
[!question]- Suppose you have a grammar production of the form $E \rightarrow E + T$. Why can’t we just write it as $E \rightarrow T + E$ to eliminate right recursion? It will remove right recursion. But it will also change the associativity of the grammar