Re: Ambiguous Grammar

[Ramaswamy]

    Hi,     Thanks first. It is a  mistake if I mentioned that A, B, C are
tokens. They are productions and  effectively A B = C, in terms of the
tokens.       If I were to use  non-glr it would probably work. But since
GLR does both the shift and reduce by  splitting the stack I get an
ambiguity. And since A, B & C are not tokens I  cannot use the precedence
for the same. The problem I am facing is that I dont  seem to get where to
add the %dprec to get it working. Observe the following  ambiguity that the
parser prints -
  Ambiguity detected.
Option 1,
   DefinedSyntaxTokenList -> <Rule 354, tokens 49 ..  66>
    DefinedSyntaxTokenList -> <Rule 354, tokens  49 .. 63>
      DefinedSyntaxTokenList <tokens  49 .. 62>
      DefinedSyntaxToken -> <Rule  356, tokens 63 .. 63>
        Setting  -> <Rule 340, tokens 63 ..  63>
          Type ->  <Rule 70, tokens 63 ..  63>
             ReferencedType -> <Rule 250, tokens 63 ..  63>
               DefinedType -> <Rule 254, tokens 63 ..  63>
                 DefinedObjectSet -> <Rule 269, tokens 63 ..  63>
                   UC_IDENTIFIER <tokens 63 .. 63>
    DefinedSyntaxToken  -> <Rule 356, tokens 64 .. 66>
       Setting -> <Rule 341, tokens 64 ..  66>
        Value -> <Rule 130,  tokens 64 .. 66>
           BuiltinValue -> <Rule 132, tokens 64 ..  66>
             BitStringValue -> <Rule 146, tokens 64 ..  66>
               '{' <tokens 64 ..  64>
               IdentifierList -> <Rule 147, tokens 65 ..  65>
                 LC_IDENTIFIER <tokens 65 ..  65>
               '}' <tokens 66 .. 66>     Option 2,
   DefinedSyntaxTokenList -> <Rule 354, tokens 49 ..  66>
    DefinedSyntaxTokenList <tokens 49 ..  62>
    DefinedSyntaxToken -> <Rule 356, tokens 63 ..  66>
      Setting -> <Rule 340, tokens 63  .. 66>
        Type -> <Rule 70,  tokens 63 .. 66>
           ReferencedType -> <Rule 250, tokens 63 ..  66>
             DefinedType -> <Rule 255, tokens 63 ..  66>
               ParameterizedType -> <Rule 259, tokens 63 ..  66>
                 SimpleDefinedType -> <Rule 257, tokens 63 ..  63>
                   UC_IDENTIFIER <tokens 63 ..  63>
                 ActualParameterList -> <Rule 61, tokens 64 ..  66>
                   '{' <tokens 64 ..  64>
                   ActualParameterListPlus -> <Rule 62, tokens 65 ..  65>
                     ActualParameter -> <Rule 66, tokens 65 ..  65>
                       Value -> <Rule 131, tokens 65 ..  65>
                         ReferencedValue -> <Rule 158, tokens 65 ..  65>
                           DefinedValueOrObject -> <Rule 57, tokens 65 ..  65>
                             LC_IDENTIFIER <tokens 65 ..  65>
                   '}' <tokens 66 .. 66>

        As u might be observing the  production Setting is the culprit
having the A | B and the A B form. I'm still  working on where to put the
%dprec. In case there are any ue in this regard, do  send it across. Bye.  
Regds Ram   ----- Original Message -----   From: "Hans Aberg"
<address@hidden> To: "Ramaswamy" <address@hidden> Cc:
<address@hidden> Sent: Monday, May 26, 2003 10:43 PM Subject: Re:
Ambiguous Grammar
> 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
>
>
>