Is an abstract syntax tree identical to a parse tree? Explain.
If a compiler uses abstract syntax trees, does it build them as explicit data structures or does it, instead, traverse them implicitly during the parsing process.
Show a parse tree for string cccdd using the following grammar. There is only one nonterminal, S, and it is the start nonterminal.
| S → c S d |
| S → c |
Show a parse tree for string aacacab using the following grammar. The start nonterminal is S.
| S → F a S |
| S → b |
| F → a F |
| F → c |
Show that the following grammar is ambiguous. There is only one nonterminal, S.
| S → S c S |
| S → d |
Show that the following grammar is ambiguous. Nonterminal S is the start nonterminal.
| S → if ( E ) S else S |
| S → if ( E ) S |
| S → x |
| E → true |
| E → false |
A convenient notation for writing an abstract syntax tree is to write the root label followed by its subtrees, separated by commas, in parentheses.
For example, tail(t) is a tree whose root is labeled tail and that has one subtree, t. Similarly, times(s, t) would be a tree whose root is labeled times and that has two subtrees, s and t. It represents the product of s and t.
Some trees have extra integer parmeters. Write function:1(t) for a function labeled 1 with one subtree, t. num:n() is a tree representing number n, with no subtrees.
Explain the steps that an interpreter would take to simplify tail(t), representing the tail of the value of subtree t.
Using the notation above, explain how to simplify tree if(x, y, z), which stands for an expression whose value is y if x has value true, and is z if x has value false.