11

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.

Community
  • 1
  • 1
Ani
  • 1,448
  • 1
  • 16
  • 38
  • 1
    I retagged from `flex` to `gnu-flex` despite the counter-advice here: http://meta.stackexchange.com/questions/26460/tag-for-two-flexes/26708#26708 simply because it's confusing to many visitors to the site to see the Adobe icon on the tag. Hopefully this will get sorted soon. Best of luck getting an answer to your question. – mechanical_meat Jun 30 '10 at 06:03
  • 5
    You hardly need flex or bison to parse simple S-expressions. You should be able to code this as a simple recursive descent parser with a hand-rolled lexer for atoms, parentheses and a white-space skipper in something like a hundred lines of C or less. The original LISP interpreters certainly did this with only a tiny bit of code. – Ira Baxter Jun 30 '10 at 06:13
  • 2
    Ira: True about no need for a parser, but "hand-rolled lexer" works only for the usual toy subsets that people usually end up with. Some Lisps/Schemes have tokens that can get *very* hairy. For your entertainment, here's an example for a valid numeric constant in [Racket](http://racket-lang.org/): `#e#x+e#s+e@-e#l-e`. – Eli Barzilay Jun 30 '10 at 07:08
  • @Ira: yes, I could code the parser in pure C (I have mentioned this in my question). But I wanted to know how *real* parsers are built from flex/bison. – Ani Jul 05 '10 at 07:37
  • @Eli Barzley: Maybe you need a lexer for a full up modern lisp like Racket. The OP said, "Simple". – Ira Baxter Jul 05 '10 at 08:22
  • @vyom Yes, you could carry through using bison, and as a pure learning experience that would be fine. If the question is, "How do I use Bison to do this?" the correct answer is, "Know when you should use a tool, and when you should not". When the parsing is simple, you don't need and shouldn't use a big hammer. As part of the pure education idea, I think you'd find it valuable to code the pure C version building your trees, as well as the bison version, so you understand how using something like bison biases the way you build your trees. And I'd do it first. – Ira Baxter Jul 05 '10 at 08:27
  • Ira: There is no modern non-toy lisp that is "simple" to this point. – Eli Barzilay Jul 05 '10 at 15:50

1 Answers1

3

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.

Andrew
  • 2,943
  • 18
  • 23