Re: Ambiguous Grammar

[Hans Aberg]

At 14:45 +0530 2003/05/26, Ramaswamy wrote:
>    Hi,     I am working on a very ambiguous  language. The language is
>ambiguous due to the support for complete forward  referencing. Worst yet
>its meant to be user friendly which means its a headache  for the compiler
>designers. Considering so many factorts and limited time  available I
>choose to use the GLR parsing scheme provided by bison. On most  ambiguous
>situations I am able to parse the input excepting on when the parser
>finds and ambiguity. Anyway this is as follows -        Withing enclosed
>braces the  following language is permitted -    TokenList:       Token
>    | TokenList Token     ;   And the token is unfortunately as  follows:
>  Token:       A     | B     | C     | and a lot more which r out of
>scope of the prblm     ;   C: A B       The actual grammar is not this
>elementary but I prefer presenting the base problem rather that giving
>other  unwanted details. The language permits the tokens A & B
>in TokenList without any other tokens in b/w as in production C. The
>language specification says that there is no ambiguity, but due to forward
>referencing I face this problem.
<<<<

Have your computer run out of linefeeds? :-)

Are you sure the idea is not to resolve the stuff in the lexer? A Flex
generated lexer seeks out the longets match, and therfore there is no
ambiguity. If you for example have in your .l file:
%%
A   { return A; }
B   { reeturn B; }
AB  { return C; }
...

Then you can have your unambiguous .y grammar:
%token A B AB
%%
TokenList:  Token | TokenList Token;
Token:      A | B | AB;
...

Bison does not do that matching for the longest rule, so you end up with an
grammar ambiguity. If one writes it like you did, you will end up with a
state
  Token -> A .
  C     -> A . B
That is, a shift/reduce conflict. If you want to have the longest match,
you should shift here, which Bison does by default, so you can ask it to
ignore the conflict by %expect.

You might also try a precedence declaration like
  %nonassoc A
  %nonassoc B
to see if the shift/reduce conflict is resolved.

The stuff above applies to a non-GLR parser.

  Hans Aberg