|
Yacc/Bison question
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?
|
