inherent ambiguity issue

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

inherent ambiguity issue

Ram Marzin
 
Hello,
My name is Ram and I use grammatica SW as a part of my acadmic project in the university.
I use grammatica to help me develop c parser (an important part of my project).
 
I get an inherent ambiguity error which I cannot solve,
The code is:
/* Expression */
Expression = Term [ExpressionRest] ;
ExpressionRest = "+" Expression
                         | "-" Expression ;
Term = Factor [TermRest] ;
TermRest = "*" Term
                   | "/" Term
                   | "%" Term ;
Factor = Atom
                   | "(" Expression ")" ;
Atom = Number
                   | STRING_DATA
                   | VARIABLE_NAME
                   | FunctionCall  
                   | Casting;
 
Number = INT_NUMBER | FLOAT_NUMBER;

/* Condition Statement */
Condition = ConditionTerm [ConditionRest] ;
ConditionRest = AND Condition
                       | OR Condition ;
ConditionTerm = ConditionAtom
                       | "(" Condition ")" ;     
ConditionAtom = Value ConditionOperator Value ;
ConditionOperator = "==" | "!=" | ">" | "<" | "<=" | ">=";
Value = Expression;
 
The error is:
Error: in pt.grammar: lines 163-164:
    inherent ambiguity in production 'ConditionTerm' starting with
    token "("
ConditionTerm = ConditionAtom
                           | "(" Condition ")" ;
 
I understand why it happens, there is unlimit look ahead option but how can I solve it ?
 
Thanks,
Ram.

_______________________________________________
Grammatica-users mailing list
[hidden email]
http://lists.nongnu.org/mailman/listinfo/grammatica-users
Reply | Threaded
Open this post in threaded view
|

Re: inherent ambiguity issue

Oliver Gramberg

Hi Ram,

I think the error message appears because the second alternative for "ConditionTerm" start with an "(", and the first derives (via "Value") a string that can also start with "(" because of the second alternative in "Factor".

One solution is to allow those parentheses in only one place. Here's an example (grammar for a different language):

---------------------------------------------------------------------------------
expression = xor_expression {'OR' xor_expression} ;
xor_expression = and_expression {'XOR' and_expression} ;
and_expression = comparison {('&' | 'AND') comparison} ;
comparison = equ_expression {('=' | '<>') equ_expression} ;
equ_expression = add_expression {comparison_operator add_expression} ;
comparison_operator = '<'
        | '>'
        | '<='
        | '>=' ;
add_expression = term {add_operator term} ;
add_operator = '+'
        | '-' ;
term = unary_expression {multiply_operator unary_expression} ;
multiply_operator = '*'
        | '/'
        | 'MOD' ;
unary_expression = {unary_operator} primary_expression ;
unary_operator = '-'
        | '+'
        | 'NOT' ;
primary_expression = constant
        | variable
        | '(' expression ')'
              ...
               ;
---------------------------------------------------------------------------------

It seems you are trying with your grammar to force the condition of an if(...) to be a comparison. The above approach would allow anything derivable from "expression" to appear there, so you would have to check during semantic analysis that your restriction is adhered to. On the other hand, if I'm not mistaken standard C allows if(1)...

Regards
Oliver Gramberg



Ram Marzin <[hidden email]>
Sent by: grammatica-users-bounces+oliver.gramberg=[hidden email]

28.11.2010 18:45

Please respond to
[hidden email]

To
[hidden email]
cc
Subject
[Grammatica-users] inherent ambiguity issue





 
Hello,
My name is Ram and I use grammatica SW as a part of my acadmic project in the university.
I use grammatica to help me develop c parser (an important part of my project).
 
I get an inherent ambiguity error which I cannot solve,
The code is:
/* Expression */
Expression = Term [ExpressionRest] ;
ExpressionRest = "+" Expression
                        | "-" Expression ;
Term = Factor [TermRest] ;
TermRest = "*" Term
                  | "/" Term
                  | "%" Term ;
Factor = Atom
                  | "(" Expression ")" ;
Atom = Number
                  | STRING_DATA
                  | VARIABLE_NAME
                  | FunctionCall  
                  | Casting;
 
Number = INT_NUMBER | FLOAT_NUMBER;


/* Condition Statement */
Condition = ConditionTerm [ConditionRest] ;
ConditionRest = AND Condition
                      | OR Condition ;
ConditionTerm = ConditionAtom
                      | "(" Condition ")" ;      
ConditionAtom = Value ConditionOperator Value ;
ConditionOperator = "==" | "!=" | ">" | "<" | "<=" | ">=";
Value = Expression;

 
The error is:
Error: in pt.grammar: lines 163-164:
   inherent ambiguity in production 'ConditionTerm' starting with
   token "("

ConditionTerm = ConditionAtom
                          | "(" Condition ")" ;

 
I understand why it happens, there is unlimit look ahead option but how can I solve it ?
 
Thanks,
Ram.
_______________________________________________
Grammatica-users mailing list
[hidden email]
http://lists.nongnu.org/mailman/listinfo/grammatica-users


_______________________________________________
Grammatica-users mailing list
[hidden email]
http://lists.nongnu.org/mailman/listinfo/grammatica-users
Reply | Threaded
Open this post in threaded view
|

Re: inherent ambiguity issue

Per Cederberg
In reply to this post by Ram Marzin
The easiest approach would be to violate the grammar a bit, by changing:

Factor = Atom
                   | "(" Expression ")" ;

ConditionTerm = ConditionAtom
                       | "(" Condition ")" ;

Into this:

Factor = Atom
                   | "(" Condition ")" ;

ConditionTerm = ConditionAtom ;

And add semantic checks in the analyzer to look for expressions
containing conditionals.

Cheers,

/Per

On Sun, Nov 28, 2010 at 18:45, Ram Marzin <[hidden email]> wrote:

>
> Hello,
> My name is Ram and I use grammatica SW as a part of my acadmic project in
> the university.
> I use grammatica to help me develop c parser (an important part of my
> project).
>
> I get an inherent ambiguity error which I cannot solve,
> The code is:
> /* Expression */
> Expression = Term [ExpressionRest] ;
> ExpressionRest = "+" Expression
>                          | "-" Expression ;
> Term = Factor [TermRest] ;
> TermRest = "*" Term
>                    | "/" Term
>                    | "%" Term ;
> Factor = Atom
>                    | "(" Expression ")" ;
> Atom = Number
>                    | STRING_DATA
>                    | VARIABLE_NAME
>                    | FunctionCall
>                    | Casting;
>
> Number = INT_NUMBER | FLOAT_NUMBER;
> /* Condition Statement */
> Condition = ConditionTerm [ConditionRest] ;
> ConditionRest = AND Condition
>                        | OR Condition ;
> ConditionTerm = ConditionAtom
>                        | "(" Condition ")" ;
> ConditionAtom = Value ConditionOperator Value ;
> ConditionOperator = "==" | "!=" | ">" | "<" | "<=" | ">=";
> Value = Expression;
>
> The error is:
> Error: in pt.grammar: lines 163-164:
>     inherent ambiguity in production 'ConditionTerm' starting with
>     token "("
> ConditionTerm = ConditionAtom
>                            | "(" Condition ")" ;
>
> I understand why it happens, there is unlimit look ahead option but how
> can I solve it ?
>
> Thanks,
> Ram.
> ‎
> _______________________________________________
> Grammatica-users mailing list
> [hidden email]
> http://lists.nongnu.org/mailman/listinfo/grammatica-users
>
>

_______________________________________________
Grammatica-users mailing list
[hidden email]
http://lists.nongnu.org/mailman/listinfo/grammatica-users