CODEWITHSUNDEEP
parsingrecursive-descent
user1072706
user1072706

Reputation: 573

Unambiguous Grammar

I want to create an unambiguous grammar for arithmetic expressions. Now the exponentiation should be of higher precedence and associate to the right. All other operations associate to the left. This is what I have so far but I don't know if the exponentiation is correct 

E -> E+T | E-T | T
T -> T*F | T/F | L
L ->  F^ L|F
F -> i | (E)

Upvotes: 0

Views: 776

Answers (2)

Austin Henley
Austin Henley

Reputation: 4633

Based on your grammar, here is a more readable version of what you want. It is unambiguous and correctly captures associativity.

expr -> term | expr add term
term -> factor | term mult factor
factor -> number | - factor | ( expr )
add -> + | -
mult -> * | /

This example should be much more readable so that you can apply this to your homework. I did leave out the ^ operator but you should be able to figure it out from the example. If you care to buy [another] textbook, Programming Language Pragmatics is of great help.

Upvotes: 0

ccoakley
ccoakley

Reputation: 3255

I am curious, because this is tagged recursive-descent, which makes me think LL.

When creating a grammar for an LL parser, remember these rules.

Repetition is used for left associativity:

Foo -> Bar (op Bar)*

Tail recursion is used for right associativity:

Foo -> Bar (op Foo)?

Now, you don't have an LL-parser-friendly grammar because you have left recursion:

E -> E+T

On the other hand, if it were LL, your exponentiation uses tail recursion, so that would work.

I suggest wikipedia's Top Down Parsing and Left-Recursion articles (these are easier reads than the LL parser article). And note, LR parsers work different, and result in different grammars for left and right associativity.

Oh, and your rule ordering is correct for what LL parsers need for precedence. Your lower-precedence operator rules come first in the production rule chain.

Upvotes: 3

Related Questions