Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] eliminating shift/reduce conflicts
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2003-09-12 (14:56)
From: Eric C. Cooper <ecc@c...>
Subject: Re: [Caml-list] eliminating shift/reduce conflicts
On Fri, Sep 12, 2003 at 04:26:32PM +0800, Rafael 'Dido' Sevilla wrote:
> I have an ocamlyacc grammar that contains productions that look like:
> foo_list: FOO { [$1] }
>   | foo_list COMMA FOO { $3 :: $1 }
>   ;
> which creates a list of FOO objects.  I however have some rules that
> need to be prefixed by either a single FOO or a foo_list, like so:
> bar: foo_list COLON xyzzy { ... }
> and
> baz: FOO COLON yzzyx { ... }
> This of course produces a shift/reduce conflict, and shifting fails to
> parse the 'bar' correctly.  Perhaps I need to read a compiler
> construction textbook more thoroughly to figure out this answer, but any
> hints out there on getting rid of this shift/reduce.

Here are two approaches.  If the grammar is simple enough, you can
split the bar rule (and other similar ones) into two productions:

    bar: FOO COLON xyzzy | foo_list COLON xyzzy

and require foo_list to have at least two members:

    foo_list: FOO COMMA FOO | foo_list COMMA FOO

Of course, now you have duplicated semantic actions for the two cases,
and it can make the grammar pretty ugly.

Another approach is to accept a more liberal language in the parser,
and do more checking in the semantic action:

    bar: foo_list COLON xyzzy { ... }
    baz: foo_list COLON yzzyx { check_single_foo $1; ... }

Hope this helps.

Eric C. Cooper          e c c @ c m u . e d u

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: