I have attached the problem below with the answer. My problem is that I can't understand it. Can you provide an overall explanation in detail about parse trees and ETF grammar by deriving the first expression?

enter image description here

Just try to explain the first expression, a+b/c+d. I think it's not that hard, but I just haven't been able to find the right resources to understand this. Can you also provide resources that explain ETF grammar? If you don't want to give an explanation, it would be nice if at least you can point out some resource to understand this.

  • 2
    That task is extremely underspecified. Note for example that the grammar contains no productions for division /. The distinction between parse trees and ASTs is fluid – an AST is literally just a kind of parse tree that's more convenient for a compiler. It would not occur to me to draw these trees in that manner unless a similar exercise had been discussed in class.
    – amon
    Nov 2 '16 at 8:13

An Abstract Syntax Tree is a data structure that uses structure to eliminate parenthesis and other details of textual representation.

Operator precedence, a significant feature of textual representation, is, in the AST, encoded in the structure of the tree: whereas in textual form operator precedence is encoded using operator priority rules along with parenthesis to override (or even to emphasize) the standard rules.

To translate from AST back to textual representation is a form of code generation, or, some might call it pretty printing.

Naively, you'd generate all these binary operations textually enclosed within () if you didn't have proper optimization to eliminate them, or understanding of operator precedence of the textual grammar.

So, your first tree example, would naively textually generate:

( ( a + ( b / c ) ) + d )

which when optimized for common operator precedence would allow for the removal of all the parenthesis.

Most interesting of the bunch is the lower left, because it requires () in the textual representation that cannot be eliminated. However, in the tree form AST, as usual, no () are required; the precedence override by () in the textual representation to make the addition happen before the multiplication is now inherent and implicit in the structure of the tree and is thus no explicit () are required in the AST form.

Have a look at (E)BNF, which is a common way of encoding a grammar (as text). Also see ANTLR, which is a parser generator tool that can parse LL(*) grammars (which are more powerful than of LALR(1) and LL(k) grammars.

An ETF grammar is a somewhat restricted expression of grammar in which there are limited levels of operator precedence, and in particular just sufficient levels of precedence to accommodate addition being lower precedence than multiplication along with () allowed to override (or emphasize) the precedence. ETF, expression, term, factor, are effectively the three levels. Notice that F admits ( E ), which is to say F (high precedence) allows and any E (low precedence) surrounded by (), which allows the () to override (e.g. raise) the precedence of the contained expression relative to the containing expression.

Let's also distinguish between parse trees and abstract syntax trees. Parse Trees (aka concrete syntax trees) manifest more nodes that correspond to the input syntax, i.e. the actually recognized productions in the grammar for a given input text in the languge. Thus for the lower left expression, you'd have a () node in the tree immediately above the + operator (not to mention a whole lot more other stuff as well). By contrast, in AST form, these textual details are suppressed.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.