flex and bison recursion issue

Question

I'm new to flex and bison and I'm trying to parse a file with flex and bison but there is an issue with one of the recursions that maybe someone can help me with, it looks a little like this:

details : empty | details detail ;
detail:
TOKEN
string
string
nestedDetails
integer ;

whereby:

nestedDetails : empty 
|
string
integer
integerPairs ;

and:

integerPairs : integer integer | integerPairs integer integer ;

My problem is this:

when parsing the file, bison goes through "nestedDetails" and never reaches the final integer call (presumably, when he finds the final integer he is looking for another integer because he thinks it is the first of a pair defined in "nestedDetails") and thus leaves me with a syntax error because the next thing he finds is not relevant for him.

Is there any clever way of letting bison know that he has actually reached the final integer, and he can move on to the next section? Preferably without having to define new tokens in flex, that has already let to some unpleasant surprises.

thank you in advance.

rici rici · Accepted Answer · 2015-02-27T15:32:33

There is a simple solution, but it changes the parse tree slightly. (It's easy to recover, though. See below.)

nestedDetails must always be followed by an integer but as the question indicates, it is not clear whether an integer should be shifted or trigger a reduce until the token following the integer is encountered. So the simple solution is to delay the decision:

details : %empty | details detail ;
detail  : TOKEN string string nestedDetailsPlusInteger ;
nestedDetailsPlusInteger
        : integer
        | string integer integerPairs integer ;
integerPairs
        : integer integer
        | integerPairs integer integer ;

To recover the original parse tree, nestedDetailsPlusInteger needs to have a semantic value which consists of the nestedDetails plus an integer; in the action associated with detail, these two parts can be used to construct an appropriate object. Pseudo-code:

details : %empty             { $$ = make_details(); } 
        | details detail     { append_detail($1, $2); $$ = $1; }
detail  : TOKEN string string nestedDetailsPlusInteger 
                             { $$ = make_detail($1, $2, $3,
                                                $4.first, $4.second);
nestedDetailsPlusInteger
        : integer            { $$ = make_pair(NULL, $1); }
        | string integer integerPairs integer 
                             { $$ = make_pair(make_nested($1, $2, $3),
                                              $4);

flex and bison recursion issue

1 Answers