Ply(LALR) and Yacc behaving differently
- From: Åsmund Grammeltvedt <asmundg@xxxxxxxxxxxxxx>
- Date: Thu, 7 Apr 2005 20:51:21 +0200 (CEST)
I am trying to implement a small compiler in python and, trying to use
something a bit more pythonic than lex/yacc, ended up with ply
(http://systems.cs.uchicago.edu/ply/). The only problem is that whereas
yacc accepts the grammar and appears to parse it correctly, ply does not.
Perhaps this belongs on some compiler list, but I couldn't decide if it
was a compiler or a python problem, so bear with me.
This smaller grammar illustrates the problem:
Goal ::= (+|+-)*;
The yacc grammar goes:
: Block ';'
| Block T
| Block S
: /* empty */
: '+' '-'
Translated to ply:
Goal : Block SEMI
Block : Empty
| Block T
| Block S
S : PLUS
T : PLUS MINUS
Now, looking at the state machines that yacc and ply produces, the
difference show up.
0 $accept: . Goal $end
$default reduce using rule 5 (Empty)
Goal go to state 1
Block go to state 2
Empty go to state 3
1 Goal: Block . ';'
3 Block: Block . T
4 | Block . S
';' shift, and go to state 5
'+' shift, and go to state 6
S go to state 7
T go to state 8
2 Block: Empty .
$default reduce using rule 2 (Block)
(0) S' -> . Goal
(1) Goal -> . Block SEMI
(2) Block -> . Empty
(3) Block -> . Block T
(4) Block -> . Block S
(5) Empty -> .
SEMI reduce using rule 5 (Empty -> .)
Empty shift and go to state 3
Goal shift and go to state 2
Block shift and go to state 1
OK, I believe those are the interesting parts. Appearently, ply doesn't
want to shift anything other than a ';' and thereby produces an error if
it encounters '+'. This only occurs in LALR mode, though. SLR handles
correctly, but my larger grammar isn't SLR, sigh.
So, any ideas? Have I completely messed up how to handle empty productions
or should I switch to another lexer/parser?
All these moments will be lost in time, like tears in the rain.
- Prev by Date: Re: sorting a list and counting interchanges
- Next by Date: Re: Lambda: the Ultimate Design Flaw
- Previous by thread: Use string in URLs
- Next by thread: Re: Ply(LALR) and Yacc behaving differently