How to get the AST from YACC?

Question

I know how to make YACC generate an AST, but how do you actaully get it? I mean, how do you actaully get the value of the root node from YACC?

Answer 1

This is how I did it:

in the yacc file (your_grammar.y):

%parse-param {AstNode **pproot}
%parse-param {char **errmsg}

in the calling program (your_program.c):

res = yyparse(&pAst, &errmsg);

AST nodes are allocated and linked as a tree inside yyparse() (you make the logic) and the address of root node is passed back in the pAst pointer.

Answer 2

Yacc only gives you back one node at a time, and it's always something that you just gave yacc at some earlier time, i.e., whatever you wanted to return from a reduced production or whatever you wanted to return from a terminal symbol. (Sorry, you said you knew that, but some people reading this might not.)

So, take whatever you woud have returned from the root or top rule, and save it (in your attached C reduction code) any way you like.

Answer 3

What Yacc gives you is a parse tree, which is different than an AST. You'd need to construct your AST by yourselves while going through each node of the parse tree (through yacc).

Answer 4

It's not as elegant as having the parser return an AST directly, but the best way that I've come up with to do this is to have a global data structure (e.g. a vector or linked list), with threadsafe insertion methods if thread safety is needed, and have the top-level yacc rule add its result (a.k.a. $$) to that data structure. Then you can access this result in other functions. Of course, if you're only going to output a single AST, it's probably only necessary to have a single global pointer to that AST, rather than a data structure full of them.