LALR grammar ambiguous

0
votes

I have made a grammar for boolean and arithmetic expressions. I want to handle arithmetic expressions like:

(1+5)+(-3)

I'm done with that work: I can handle all the expressions I want.

My problem is that a boolean expression can be something like:

( ( (2+2==4) or (3>2) ) and 2==2)

so at some point my boolean rules have to refer to my arithmetic expression rules. I can't use parentheses () in my boolean rules because it'll cause my grammar to be ambiguous. I understand why but I can't figure out a solution for this problem.

1
grammaryacclalrdisambiguationambiguous-grammar
What have you tried so far? Show your code and provide details of the conflicts that yacc identifies. - David Gorsline
There is nothing inherently ambiguous in having parenthesis in both boolean and arithmetic expressions (the simple ways of doing it will make the grammar not-LL, but are just fine with LR). What have you tried? - Chris Dodd
possible duplicate of Simple ambiguous grammer with reduce-reduce conflict - Chris Dodd

1 Answers

1
votes

This LALR grammar written for GOLD should get you started:

<Formula>     ::= <BoolConcat> <Formula> | <BoolConcat> 

<BoolConcat> ::= <BoolConcat> 'and' <Comparison> | <Comparison>

<Comparison> ::=  <Comparison> '>' <Expression> | <Expression> 

<Expression> ::= <Expression> '+' <Term> | <Term>

<Term> ::= <Term> '*' <Fact> | <Fact>

<Fact> ::= Integer | '(' <BoolConcat> ')'

For the bool part the typical concepts for arithmetic grammar are reused. Nothing new, only new levels of precedence for the different kinds of bool operators.

Just add '==' to Comparison, 'or' to BoolConcat and so on.