CODEWITHSUNDEEP
grammarantlr4ambiguityambiguous-grammar
Andromeda
Andromeda

Reputation: 49

Why is this grammar ambiguous?

I'm using Antlr4. Here is my grammar:

assign : id '=' expr ;
    id : 'A' | 'B' | 'C' ;
  expr : expr '+' term
       | expr '-' term
       | term ;
  term : term '*' factor
       | term '/' factor
       | factor ;
factor : expr '**' factor
       | '(' expr ')'
       | id ;
    WS : [ \t\r\n]+ -> skip ;

I know this grammar is ambiguous and also I know I should add an element to the grammar but I don't know how to make the grammar unambiguous.

Upvotes: 1

Views: 88

Answers (1)

rici
rici

Reputation: 241691

factor : expr '**' factor

Consider the input

A + B ** C

A + B is an expr so we could analyse that as a factor, semantically (A+B)C

But the other, more conventional interpretation (A + (BC)) is also possible:

<expr>                   => 
<expr> + <term>          =>
<term> + <term>          =>
<factor> + <term>        =>
A        + <term>        =>
A        + <factor>      =>
A + <expr> ** <factor>   =>
A + <term> ** <factor>   =>
A + <factor> ** <factor> =>
A + B ** <factor>        =>
A + B ** C

Upvotes: 1

Related Questions