Re: 2 Yacc Qs

Dmitri Bronnikov <Bronikov@ic.net>
23 Mar 1997 23:25:14 -0500

          From comp.compilers

Related articles
2 Yacc Qs zero@istar.ca (1997-03-22)
Re: 2 Yacc Qs Bronikov@ic.net (Dmitri Bronnikov) (1997-03-23)
Re: 2 Yacc Qs brianb@microware.com (Brian Bliss) (1997-03-27)
| List of all articles for this month |

From: Dmitri Bronnikov <Bronikov@ic.net>
Newsgroups: comp.compilers
Date: 23 Mar 1997 23:25:14 -0500
Organization: None
References: 97-03-135
Keywords: yacc, parse

Barton Jaques wrote:
> I am building an expression grammar and having problems with associativity
> and shift/reduce conflicts. The language I am emulating permits a statement
> like this:
>
> set y to items 1 thru 2 of x as string
>
> which should be read as: "set y to (items 1 thru 2 of x) as string"
> and not as: "set y to items 1 thru 2 of (x as string)"
>
> My grammar always picks the 2nd path. The relevant rules look like this:
>
> statement:
> SET IDENT TO expression
>
> expression:
> object_specifier
> | IDENT
> | expression AS class
>
> object_specifier:
> object_container
> | object_container of expression
> | object_container of object_specifier
>
> object_container:
> class
> | class expression THRU expression


Your problem reminds me the if-then-else shift/reduce conflict, but
unlike the latter, shift is not the action you'd like the parser to take
if such conflict occurred.


It is not quite clear from the example whether you want leftmost
derivation, rightmost derivation or something in between.


Consider this example:


"SomeContainer OF SomeIdentifier AS class1 AS class2 AS class4 ... AS
classN"


It's valid to associate any number (0..N) of AS qualifiers with
SomeIdentifier and leave the rest as qualifiers of the expression
beginning with SomeContainer.


Things are getting more complicated if we replace SomeIndetifier with a
more sophisticated expression.


If expression following either "OF" or "THRU" can be legitimately
qualified by an "AS class" in your language, then it is a real ambiguity
and it might be reasonable to require programmer to use parenthesis to
resolve that.


If your language rules out "AS class" qualifiers in association with
expressions following "OF"/"THRU", then the conflict can be resolved as
follows:


  expression:
        as_less_expr
    | expression AS class


  as_less_expr:
        object_specifier
    | IDENT


  object_specifier:
        object_container
    | object_container of as_less_expression
    | object_container of object_specifier


  object_container:
        class
    | class expression THRU as_less_expression
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.