[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: TODO update
From: |
Akim Demaille |
Subject: |
Re: TODO update |
Date: |
26 Jul 2002 09:40:49 +0200 |
User-agent: |
Gnus/5.0808 (Gnus v5.8.8) XEmacs/21.4 (Honest Recruiter) |
| > I fail to see why $default exists here: the two valid lookaheads are $
| > and + (as denoted by [$, '+']. So it seems to me that this state has
| > no default, and ought to trigger an error *now*, now after reduction.
I think I now perfectly understand what bugs me: Bison is
`unfaithful' when it displays reductions in output. I completely
forgot that fact.
What bugged me is that $default in LALR1 and GLR do not designate the
same people. But since output is independent of GLR or not, something
was wrong. But now I remeber: when there are conflicts, Bison *lies*
precisely to exhibit the conflicted rules. Compare its output on your
glorp/gleep grammar (I'm learning new technical words! :), with that
of its twin, BYacc:
Bison:
state 5
5 glorp: 'X' . [')']
6 gleep: 'X' . [')']
')' reduce using rule 5 (glorp)
')' [reduce using rule 6 (gleep)]
$default reduce using rule 5 (glorp)
BYacc:
5: reduce/reduce conflict (reduce 5, reduce 6) on ')'
state 5
glorp : 'X' . (5)
gleep : 'X' . (6)
. reduce 5
BYacc's output is the Truth. Bison's output is more informative, but
somewhat incorrect wrt LALR1. But it turns out that the way it tweaks
the .output is precisely what you do in case of conflicts.
So indeed, everybody is happy :)
| The $default reduction is actually used, by the way, but not in any
| valid program. If your input were
|
| (XX
|
| for example, you'd get the following trace
|
| ----------------------------------------------------------------------
| Starting parse
| Entering state 0
| Reading a token: Next token is token '(' ()
| Shifting token 40 ('('), Entering state 1
| Reading a token: Next token is token 'X' ()
| Shifting token 88 ('X'), Entering state 5
| Reducing via rule 5 (line 9), 'X' -> glorp <<< NOTE <<<
| state stack now 0 1
| Entering state 6
| Reading a token: Next token is token 'X' ()
| Err: parse error
| Error: popping nterm glorp ()
| Error: state stack now 0 1
| Error: popping token '(' ()
| Error: state stack now 0
| ----------------------------------------------------------------------
|
| The marked line shows where the default reduction is used (the next
| token is 'X', which is invalid).
Yes, but as you can see, it didn't even look at the lookahead. My
point was that even in (X) it is the default action which is used. My
point is that the automaton in state 5 has a single action, attached
to $default.
As a matter of fact, yesterday I fell on words I wrote in the test
suite (conflicts.at):
## -------------------------------- ##
## Defaulted Conflicted Reduction. ##
## -------------------------------- ##
# When there are RR conflicts, some rules are disabled. Usually it is
# simply displayed as:
#
# $ reduce using rule 3 (num)
# $ [reduce using rule 4 (id)]
#
# But when `reduce 3' is the default action, we'd produce:
#
# $ [reduce using rule 4 (id)]
# $default reduce using rule 3 (num)
#
# In this precise case (a reduction is masked by the default
# reduction), we make the `reduce 3' explicit:
#
# $ reduce using rule 3 (num)
# $ [reduce using rule 4 (id)]
# $default reduce using rule 3 (num)
#
# Maybe that's not the best display, but then, please propose something
# else.
AT_SETUP([Defaulted Conflicted Reduction])
AT_KEYWORDS([report])
AT_DATA([input.y],
[[%%
exp: num | id;
num: '0';
id : '0';
%%
]])
AT_CHECK([bison input.y -o input.c --report=all], 0, [],
[input.y contains 1 reduce/reduce conflict.
])
# Check the contents of the report.
AT_CHECK([cat input.output], [],
[[State 1 contains 1 reduce/reduce conflict.
Grammar
0 $axiom: exp $
1 exp: num
2 | id
3 num: '0'
4 id: '0'
Terminals, with rules where they appear
$ (0) 0
'0' (48) 3 4
error (256)
Nonterminals, with rules where they appear
$axiom (4)
on left: 0
exp (5)
on left: 1 2, on right: 0
num (6)
on left: 3, on right: 1
id (7)
on left: 4, on right: 2
state 0
0 $axiom: . exp $
1 exp: . num
2 | . id
3 num: . '0'
4 id: . '0'
'0' shift, and go to state 1
exp go to state 2
num go to state 3
id go to state 4
state 1
3 num: '0' . [$]
4 id: '0' . [$]
$ reduce using rule 3 (num)
$ [reduce using rule 4 (id)]
$default reduce using rule 3 (num)
state 2
0 $axiom: exp . $
$ shift, and go to state 5
state 3
1 exp: num .
$default reduce using rule 1 (exp)
state 4
2 exp: id .
$default reduce using rule 2 (exp)
state 5
0 $axiom: exp $ .
$default accept
]])
AT_CLEANUP
- TODO update, Akim Demaille, 2002/07/09
- Re: TODO update, Paul Hilfinger, 2002/07/21
- Re: TODO update, Akim Demaille, 2002/07/22
- Re: TODO update, Paul Hilfinger, 2002/07/22
- Re: TODO update, Akim Demaille, 2002/07/23
- Re: TODO update, Paul Hilfinger, 2002/07/23
- Re: TODO update, Akim Demaille, 2002/07/24
- Re: TODO update, Paul Hilfinger, 2002/07/24
- Re: TODO update, Akim Demaille, 2002/07/25
- Re: TODO update, Paul Hilfinger, 2002/07/25
- Re: TODO update,
Akim Demaille <=
- Re: TODO update, Paul Hilfinger, 2002/07/28