Re: Odd parser behaviour

[Heiko Wundram]

Am Freitag, 22. September 2006 15:26 schrieb Tim Van Holder:
> I would expect this to accept any input starting with A(B|C?D?E)+,
> but in practice, it only accepts input starting with A(B|CDE)+,
> because for the xyzzy nterm, it always tries to reduce the opt_C.
>
> >From the .output:
>
> state 1
>
>     2 bar: A . plus_xyzzy
>     3 plus_xyzzy: . xyzzy
>     4           | . plus_xyzzy xyzzy
>     5 xyzzy: . B
>     6      | . opt_C opt_D E
>     7 opt_C: .  [D, E]
>     8      | . C
>
>     B  shift, and go to state 4
>     C  shift, and go to state 5
>
>     $default  reduce using rule 7 (opt_C)
>
>     plus_xyzzy  go to state 6
>     xyzzy       go to state 7
>     opt_C       go to state 8

But, all of this looks okay? On B or C, a shift occurs, on any other 
lookahead, $default, in this case [ADE], a reduce (on opt_C) takes place, 
which should be the behaviour you expect. In case there's another A in the 
input, rule 12 should find that for you, and abort there; otherwise, an E 
will be matched and reduced to a xyzzy by rule 13. A B is reduced to xyzzy in 
rule 4 immediately.

I haven't had the time to write a lexer for this grammar to test for the 
behaviour you mention when you use bison's lalr-engine, but the 
bison-generated LR-sets seem to represent A(B|C?D?E)+ properly, at least 
AFAICT from a quick glance, and the tables produced by bison when used in 
PyBison work properly (PyBison implements the standard bison LALR-parser in 
Python, using the tabular output of bison).

-- 
--- Heiko Wundram.

  ____      _          _                    ___ _____
 / ___| ___| |__  _ __| | _____ _ __  ___  |_ _|_   _|
| |  _ / _ \ '_ \| '__| |/ / _ \ '_ \/ __|  | |  | |
| |_| |  __/ | | | |  |   <  __/ | | \__ \_ | |  | |
 \____|\___|_| |_|_|  |_|\_\___|_| |_|___(_)___| |_|

FON 0511-59027954
FAX 0511-59027957
Gehrkens.IT GmbH
Mailänder Strasse 2
http://www.gehrkens.it
http://www.xencon.net