I am trying to build a parser that will eventually output a 3 address code.

My question is, how do I build the parser to go from parsing in a table driven top down parsing to then give me a parse tree?

I am looking for more psudo code than anything. Not anything concrete. For example, I have a table with the first and follow sets of all non-terminal. I take this non terminal and do the standard parsing technique for table driven parsing.

When and how do I take those choices for the parsing to create the parse tree?

Below is the grammar I am trying to parse out, I take the corresponding first and follow sets to the grammar and the parse out the input using the table driven parsing technique.


expr ::= term {addop term}
term ::= factor {mulop factor}
factor ::= variable| unsigned-number| ( expr)
variable ::= identifier
addop ::= + | -
mulop ::= * | /


1 Answer 1


As the name indicates, the parse tree is generated top-down. Specifically, you start with a place-holder node for the start symbol. Each time you predict a production, you fill in the placeholder with the right-hand side of the production, where each symbol is represented by a placeholder. Each time you shift over a token, you fill in the placeholder with the token's semantic value.

Since parsing nodes are expanded into the tree before their children, it's not possible to compute synthesized attributes with this algorithm, although inherited attributes can be computed when the node is predicted. You can slightly modify the algorithm to allow the computation of synthesized attributes by adding an "end production" pseudo-token at the end of every production. When a such a token is encountered, instead of shifting a token from the input, the code associated with the production is executed to fill in the synthesized attributes. However, it might be easier to compute attributes post-parse by performing one or more traverses over the parse tree.

  • $\begingroup$ So, what you are saying is that i will not be able to generate a intermediate code while using a top down parsing method? I have to use a bottom up parsing method such as shift reduce parsing? $\endgroup$
    – Fel
    Nov 14, 2019 at 21:20
  • $\begingroup$ @fel: that's not what you asked and it's not what I said. You asked how to produce a parse tree, and that's what the answer is about. If you want to generate a one-pass compiler which goes directly to three-address code, that's a different question. Certainly, it can be done; think of the TAC as synthesized attributes of the parse tree. Any good compiler textbook will provide more details. $\endgroup$
    – rici
    Nov 14, 2019 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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