CODEWITHSUNDEEP
grammaryacclalrdisambiguationambiguous-grammar
Jorge Silva
Jorge Silva

Reputation: 245

LALR grammar ambiguous

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.

Upvotes: 0

Views: 517

Answers (1)

user764754
user764754

Reputation: 4226

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.

Upvotes: 1

Related Questions