[racket] why shift/reduce conflict?

From: Dmitry Pavlov (dpavlov at ipa.nw.ru)
Date: Tue Jan 17 06:54:18 EST 2012

Hello Veer,

> I think the conflict may be here(I may be wrong) :
> When parser encounter C , it can reduce to y or it can shift i.e it
> think there is A waiting to be read, hence shift/reduce conflict

Thanks. I think you are right: while this grammar is
not ambiguous per se, it confuses LALR parser.

I should have educated myself on the subject earlier:
http://www.cs.man.ac.uk/~pjj/cs212/ho/node7.html

So to make that conflict gone, I had to convert my
grammar to something like

(x
   ((C A B)   'cab))
   ((C A A B) 'caab)))


Best regards,

Dmitry




> On Mon, Jan 16, 2012 at 2:49 PM, Dmitry Pavlov <dpavlov at ipa.nw.ru
> <mailto:dpavlov at ipa.nw.ru>> wrote:
>
>     Hello all,
>
>     I am having trouble with yacc parser giving shift/reduce
>     conflict, while I do not see where the conflict can be.
>     I have simplified the grammar to the following one:
>
>
>     #lang racket
>
>     (require parser-tools/yacc
>              parser-tools/lex)
>
>     (define-empty-tokens my-tokens (EOF A B C))
>
>     (define (my-parser source-name)
>       (parser
>        (start start)
>        (end EOF)
>        (tokens my-tokens)
>        (error #f)
>        (grammar
>         (start ((x) $1))
>         (x
>          ((y A B) (list $1 'ab)))
>         (y
>          ((C) 'c)
>          ((C A) 'ca)))))
>
>
>     It reports "1 shift/reduce conflict".
>     But from my primitive point of view, the parser should
>     accept only "CAB" and "CAAB" inputs, so there is no chance
>     for a conflict here. Could please anybody point me on what
>     is not correct with my understanding?
>
>
>     Best regards,
>
>     Dmitry
>     ____________________
>       Racket Users list:
>     http://lists.racket-lang.org/__users
>     <http://lists.racket-lang.org/users>
>
>



Posted on the users mailing list.