I'm reading through the book : "Compiler Construction: Principles and Practice". In chapter 6 : semantic analysis, an example about attribute grammars is given. The example is of a simple integer arithmetic expressions (I posted a picture because different fonts means different things as you may know):

enter image description here

where the bold Courier font is a token and the Times New Roman is grammar.

Now this parse tree represents the expression: (34-3)*42 which is 1302. I know that every attribute rule corresponds with a grammar rule, and we're actually starting with the rule exp->term because it is what it fits the given expression, but I just don't understand how did the compiler know the value in the first place? When was the value computed? How does the compiler start implementing the semantic analysis? did it start from the bottom where the number token is? I hope I made it clear.

enter image description here

  • $\begingroup$ If this helps: this was a two-staged process. In the first stage the compiler generated the graph and in the second stage the compiler (or rather the interpreter, a virtual machine etc, compilers don't normally do this) computed the value. While the parsing was top-down, the evaluation was bottom-up. $\endgroup$
    – wvxvw
    Feb 26 '16 at 14:14
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael
    Feb 26 '16 at 14:28

The computer is using the rules in the left-hand column of your table. This amounts to a bottom up approach: to compute the value of a node you first compute (recursively) the values of all its children, and then you use the given rule to compute the value of the node itself.


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.