Building Lisp/Scheme-like parse tree with flex/bison

Question

Hello,

I was trying to parse simple Lisp/scheme-like code

E.g. (func a (b c d) )

and build a tree from it, I could do the parsing in C without using bison (i.e, using only flex to return tokens and building the tree with recursion). But, with bison grammar, I am not sure where to add the code to build the list (i.e, which rule to associate with accumulating terminal symbols and where to link a built list to parent node).

My grammar is similar to the one here: http://stackoverflow.com/questions/517113/lisp-grammar-in-yacc the grammar is correct and can recognize the code.

Answer 1

Have you tried placing the code to add an element to the current list in each atom, and code to manage a tree of lists when you process the brackets? It seems the easiest way unless you run into other problems:

listend: members ')'        { cur = cur->parent; }
       | ')'                { cur = cur->parent; }
       ;

list: '(' listend           { cur = newList(cur);}
    ;

atom: ID                    { appendAtom(cur, "ID"); }
    | NUM                   { appendAtom(cur, "NUM");}
    | STR                   { appendAtom(cur, "STR");}
    ;

This assumes that you are keep a parent point in each list struct.