When and how to generate parse tree while top down parsing

Question

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.

Grammar

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

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.