Im trying to draw an annotated parse tree for 3*5+4n, the text book shows the following:

enter image description here
[Compilers - Principles, techniques and tools (Dragon Book) by Aho, p308]

I have a few questions regarding this

  1. Why is 3*5+4 considered as a single string? Can't I draw a parse tree something like for the same string ie:with operator at the node enter image description here

  2. What is the need for giving T.VAL=3 and then giving another child F.VAL=3. (I understand that the integer attribute for digit needs to be supplied by the lexical analyzer)

  • 1
    $\begingroup$ I don't understand your question 1; the string you state is clearly decomposed in the syntax tree? Also, the tree you give seems to belong to an entirely different string. $\endgroup$ – Raphael Jan 30 '14 at 11:15
  • $\begingroup$ @Raphael The second figure is not of the string which i have stated earlier.I wanted to ask why is the parse tree drawn as in figure 1 rather than using the approach shown in figure 2 $\endgroup$ – techno Jan 30 '14 at 12:17
  • $\begingroup$ I don't know how you can expect us to answer the question without showing us the corresponding context-free grammar. I suggest you edit your question to make it self-contained (i.e., provide this information, and everything else needed to understand the situation). $\endgroup$ – D.W. Jan 31 '14 at 4:12
  • $\begingroup$ @D.W. see this link to get all details books.google.com/… $\endgroup$ – techno Jan 31 '14 at 7:08
  • $\begingroup$ @techno, please add all relevant information to the question (and not just a link, but the grammar itself). The question needs to be self-contained, without reading/following other links, resources, books, etc. It's your job to make the question self-contained. Yes, sometimes this takes work: our expectation is that you will put in a serious effort to make your question clear and thorough. The purpose of this site is to generate an archive of high-quality questions and answers that will be useful to others. $\endgroup$ – D.W. Jan 31 '14 at 7:47

The Dragon book style starts with the parse tree of the expression, i.e., the root (I think the very top is a mistake, the expression is an error as written) is the step $E \Rightarrow E + T$. The tree is then decorated giving the attributes their value (like $E.val = 19$). In an attributed grammar you give the grammar and the attributes, so that the grammar looks in part as (subindices mark diferent uses of the same symbol, left to right): \begin{eqnarray} E \rightarrow T \quad E.val \leftarrow T.val \\ E \rightarrow E + T \quad E_0.val \leftarrow E_1.val + T.val \end{eqnarray} You see that the answer to your second question is that the value of the child $F$ is used to compute the value of $T$.

  • $\begingroup$ Okay,I get it.Just follow the semantic rules given in the previous page right? $\endgroup$ – techno Jan 30 '14 at 12:20
  • $\begingroup$ I don't get the error part you have said -everything seems right to me. $\endgroup$ – techno Jan 30 '14 at 12:21

I would say, yes, you may draw the parse tree as you have presented it. Your presentation is more abstract than the one from the textbook.

On one hand, this means that it will be easier to manipulate. But it does also mean that things like generating accurate and useful error messages will be much more difficult, depending of course on what sort of information has been abstracted away.

Beyond this, I cannot answer the remainder of your question. I don't even know what textbook you are talking about – that is, you've copied the page without proper citation.

  • $\begingroup$ And be more careful with you punctuation. $\endgroup$ – Dave Clarke Jan 30 '14 at 9:48

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