Top Down Parsing
Question 1: 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 2: What are the levels of precedence for standard algebraic expressions?
- Parentheses
- Multiplication and Division
- Addition and Subtraction
Question 3: When writing the rules of a grammar where should the highest precedence rules be placed?
At the last
Question 4: 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 5: Comment on the recognition power of top-down vs bottom-up parsers
Bottom up parsers can recognize more grammars than top-down parsers
Question 6: 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 7: 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 8: 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 9: 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