Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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: Lisp grammar in yacc the grammar is correct and can recognize the code.

like image 934
vyom Avatar asked Jun 30 '10 05:06

vyom


People also ask

Is bison A parser?

Bison is a general-purpose parser generator that converts an annotated context-free grammar into a deterministic LR or generalized LR (GLR) parser employing LALR (1) parser tables. As an experimental feature, Bison can also generate IELR (1) or canonical LR(1) parser tables.

What is Flex and Bison used for?

Flex and Bison are tools for building programs that handle structured input. They were originally tools for building compilers, but they have proven to be useful in many other areas.

What parser does bison use?

Bison by default generates LALR(1) parsers but it can also generate canonical LR, IELR(1) and GLR parsers. Flex, an automatic lexical analyser, is often used with Bison, to tokenise input data and provide Bison with tokens. Bison was originally written by Robert Corbett in 1985.

What do you mean by Flex lex Yacc and bison?

Lex and Yacc were the first popular and efficient lexers and parsers generators, flex and Bison were the first widespread open-source versions compatible with the original software. Each of these software has more than 30 years of history, which is an achievement in itself.


1 Answers

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.

like image 54
Andrew Avatar answered Oct 29 '22 16:10

Andrew