Second attempt
Let's try to fix what we had in our first attempt by making CONCAT left associative.| Fragment of bison file pat.ypp | Result | Parse tree |
%nonassoc STOP LB FOLD RB POP COLON NAME
/* tokens I care about for now */
%left CONCAT
%nonassoc ATOM
%%
S: seq STOP { YYACCEPT; }
| { done = true; }
seq: seq seq %prec CONCAT {$$ = NonTerm::next("seq",$1,$2); }
| ATOM {$$ = NonTerm::next("seq",$1); }
%% |
$ make bison -v -d pat.ypp flex -o pat.yy.c pat.lpp g++ -g -o pat pat.yy.c pat.tab.cpp sym.cpp bison -v -d pati.ypp flex -o pati.yy.c pati.lpp g++ -g -o pati pati.yy.c pati.tab.cpp helper.cpp $ ./pat a b c ; |
 |
Now the parse succeeds, but it gives us right associativity instead of the left associativity we asked for! So what went wrong this time? If we trace the CFSM in pat.ypp as we attempt to parse "a b c ;", we arrive at the same stack, though with different rules in State 6 because we changed the precedence/associativity declarations:
| Stack | State 6 |
6
seq[b]
3
seq[a]
0
-------
STACK |
State 6
3 seq: seq . seq
3 | seq seq .
ATOM shift, and go to state 1
$default reduce using rule 3 (seq)
seq go to state 6
|
So the lookahead is the ATOM c, and in this state we can either
reduce the two sequences we have on the stack or shift
c. Bison's disambiguation rule is to shift the ATOM c, which
isn't what we need to happen. We need the seq[a] and seq[b]
that are on the stack to be reduced, since that will join them
to seq[a b] and give us the parse tree we want. The question
is, why does Bison shift in this case? The answer is that ATOM
has higher precedence than CONCAT. So the action "shift ATOM"
has higher precedence than "reduce seq seq to seq" (remember, we
assigned the rule seq -> seq seq the precedence
of CONCAT).
So ... don't be lulled into thinking that putting "%left CONCAT" is enough to guarantee that concatenations will actually be left-associative. You have to understand what Bison is actually doing with those precedence/associativity declarations!
