Help with Bison recursion.. =>

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

Posts: 10
Joined: Sun Mar 02, 2008 10:42 pm UTC

Help with Bison recursion.. =>

Postby Meeples » Sun Apr 06, 2008 10:38 pm UTC

I've recently been thrown into the worked of working with Flex and Bison rather unarmed, and there's a thing or two that I'm having difficulties understanding. One of the smaller things we need do is work with making calculators for Infix/Postfix/Prefix notation...the first of which I managed to do, eventually. With the latter two, however, I'm stumped over a thing or two. Such as...when it comes to evaluating something along the lines of (+ 1 2 3 4). I'm not certain how to get it to work with X amount of numbers...only specific quantities.

Code: Select all
expr: '+' expr expr { $$ = $2 * $3; }

Such as that...with a simple + A B. I understand the exceedingly simple concepts of how to make it so it can do specifically/only + A B C. But I don't know how to get it to do such as + A B...n. I've perused the Bison manual extensively, but not seen any examples or other things that help me out overly much...the examples for recursion seem near non-existent, at least in showing results and such to help me understand it.. Could somebody help me out here, be it with a mere hint or more? I hope I explained it well enough; if not, do pester me, and I shall attempt again. <3 Any help'd be much appreciated..! Mostly, some sort've example of Bison recursion wuold do me wonders, I imagine. I'm looking such up myself, and just trying random things as well in the meanwhile to see if I can get this working.. =>

Edit: Ah...after suddenly feeling foolish, I got the gist of Bison recursion quite easily. Still, I cannot figure out how to do something such as the + 1 2 3 4 above. I have issues getting such as that to work..but I'll keep trying. =3

Posts: 117
Joined: Mon Feb 04, 2008 6:04 am UTC

Re: Help with Bison recursion.. =>

Postby coppro » Mon Apr 07, 2008 4:23 am UTC

Probably something along the lines of:

plus-expr: "+" | plus-expr expr

That's usually how operators are chained for binary notation, so I would expect it works for prefix (haven't tested it though).

User avatar
Poster with most posts but no title.
Posts: 11116
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Help with Bison recursion.. =>

Postby Yakk » Mon Apr 07, 2008 4:35 am UTC

I forgot how the grammer rules of Bison prefer things. There is:

expr-> plus-expr | mult-expr | div-expr | sub-expr | ...
plus-expr -> "(" "+" expr expr opt-many-expr ")"
opt-many-expr -> nothing | expr opt-many-expr

And there is:
expr-> plus-expr | mult-expr | div-expr | sub-expr | ...
plus-expr -> "(""+" expr many-expr ")"
opt-many-expr -> expr | expr many-expr

and there is:
plus-expr -> "(""+" expr expr many-with-end-expr
many-with-end-expr -> ")" | expr many-with-end-expr

or even:
expr -> literal | "(" forumla
formula -> plus-expr | mult-expr | ...
plus-expr -> "+" expr expr long-expr-tail
long-expr-tail -> ")" | expr long-expr-tail

the goal, of course, is to get things to clump right.

I think the right choice might be the many-with-end-expr, or long-expr-tail, but it has been a while since I wrote a parse tree for a compiler.

The long-expr-tail one has the nice property that each derivation rule you should follow can be determined by the leftmost token.

at expr, if you see "(", follow right rule. Otherwise, it is a literal.
at formula, "+" means plus-expr, "*" means mult-expr, etc.
at plus-expr, there is only one rule. Get a "+", then an expr, then an expr.
at long-expr-tail, if you see a ")" you know what to do. Otherwise, you will be following the right rule.

I believe that is known as an LL(1) grammar -- left lookahead, left expansion first grammar. I can't remember if that is the kind of things Bison wants or not, off the top of my head. :)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Posts: 1460
Joined: Wed Mar 21, 2007 4:07 am UTC

Re: Help with Bison recursion.. =>

Postby Rysto » Mon Apr 07, 2008 6:37 am UTC

Bison wants LR, but all LL languages are LR.

Posts: 10
Joined: Sun Mar 02, 2008 10:42 pm UTC

Re: Help with Bison recursion.. =>

Postby Meeples » Mon Apr 07, 2008 10:58 pm UTC

Ah, thank you very much..! That certainly led to me working out how to do things properly, and all is working quite well, now. Thankee very, very much. <3

Return to “Coding”

Who is online

Users browsing this forum: No registered users and 9 guests