According to my naive understanding of the Yacc/Bison algorithm (derived from a cursory reading of the "dragon book"), I would expect the parser generated from the grammar
p: a; p: 'b'; a: p; to execute an infinite loop on the following input: b b This conjecture is supported by the "output" file that my version of Bison writes for this grammar, which lists the following states and transitions: state 0 'b' shift, and go to state 1 p go to state 2 a go to state 3 state 1 p -> 'b' . (rule 2) $default reduce using rule 2 (p) state 2 a -> p . (rule 3) $ go to state 4 $ [reduce using rule 3 (a)] $default reduce using rule 3 (a) state 3 p -> a . (rule 1) $default reduce using rule 1 (p) state 4 $ go to state 5 state 5 $default accept However, it turns out that this is not an accurate description of the state machine that Bison actually produces. According to what I see in the "tab.c" file, the default in state 2 is an error (instead of a reduction), and the loop is thereby broken. This is confirmed by execution: Starting parse Entering state 0 Reading a token: Next token is 98 ('b') Shifting token 98 ('b'), Entering state 1 Reducing via rule 2 (line 36), 'b' -> p state stack now 0 Entering state 2 Reading a token: Next token is 98 ('b') (line 1) parse error Apparently, Bison has some method more avoiding loops of this sort, which is not discussed in the dragon book and not reflected in the output file. Can anyone tell me exactly how this works? _______________________________________________ help-bison@gnu.org http://lists.gnu.org/mailman/listinfo/help-bison