CODEWITHSUNDEEP
parsinggrammar
Tasbeer
Tasbeer

Reputation:

Grammar for Arithmetic Expressions

I was assigned a task for creating a parser for Arithmetic Expressions (with parenthesis and unary operators). So I just wanna know if this grammar correct or not and is it in LL(1) form and having real problems constructing the parse table for this

 S  -> TS'
 S' -> +TS' | -TS' | epsilon
 T  -> UT'
 T' -> *UT' | /UT' | epsilon
 U  -> VX
 X  -> ^U | epsilon
 V  -> (W) | -W | W | epsilon
 W  -> S | number

Precedence (high to low)

 (), unary –
 ^
 *, /
 +, -

Associativity for binary operators

 ^ = right
 +, -, *, / = left

Upvotes: 0

Views: 2938

Answers (2)

Phil Wright
Phil Wright

Reputation: 22906

You seem to be missing anything for unary plus operator. Try this instead...

V -> (W) | -W | +W | epsilon

Upvotes: 0

John Feminella
John Feminella

Reputation: 311496

Is it in LL(1) form?

To tell if the grammar is LL(1) or not, you need to expand the production rules out. If you can generate any sequence of productions which results in the left-hand-side appearing as the first thing on the right-hand-side, the grammar is not LL(1).

For example, consider this rule:

X --> X | x | epsilon

This clearly can't be part of an LL(1) grammar, since it's left-recursive if you apply the leftmost production. But what about this?

X --> Y | x
Y --> X + X

This isn't an LL(1) grammar either, but it's more subtle: first you have to apply X --> Y, then apply Y --> X + X to see that you now have X --> X + X, which is left-recursive.

Upvotes: 1

Related Questions