# Ullman (Compiler Design) Edition 2 Exercise 4.4 Question 10 (Page No. 233)

25 views
Show how, having filled in the table as in Question $4.4.9$, we can in $O(n)$ time recover a parse tree for $a_{1}a_{2}\cdot\cdot\cdot a_{n}$. Hint: modify the table so it records, for each nonterminal $A$ in each table entry $T_{ij}$,  some pair of nonterminals in other table entries that justified putting $A$ in  $T_{ij}$.

## Related questions

1
48 views
In Fig. 4.24 is a grammar for certain statements. You may take $e$ and $s$ to be terminals standing for conditional expressions and "other statements," respectively. If we resolve the conflict regarding expansion of the optional "else" (nonterminal stmtTail) by preferring to consume an else from the input whenever ... $s$ ; if $e$ then $s$ end while $e$ do begin $s$ ; if $e$ then $s$ ; end
Modify your algorithm of Question $4.4.9$ so that it will find, for any string, the smallest number of insert, delete, and mutate errors (each error a single character) needed to turn the string into a string in the language of the underlying grammar.
Every language that has a context-free grammar can be recognized in at most $O(n^{3})$ time for strings of length $n$ ... n_{3})$time. Having filled in the table, how do you determine whether$a_{l}a_{2}\cdot\cdot\cdot a_{n} is in the language?
Design grammars for the following languages: The set of all strings of $0's$ and $1's$ such that every $0$ is immediately followed by at least one $1$. The set of all strings of $0's$ and $1's$ that are palindromes; that is, the string reads the same backward as forward. The set of all ... of all strings of $0's$ and $1's$ of the form $xy$, where $x\neq y$ and $x$ and $y$ are of the same length.