CODEWITHSUNDEEP
ambiguousll-grammarcompiler-constructiondangling-else
CSharpFiasco
CSharpFiasco

Reputation: 254

Removing Ambiguity Caused By Dangling Else For LL(1) Grammars

In the case of the dangling else problem for compiler design, is there a reason to left factor it before removing ambiguity?

We are transforming a CFG into an LL(1) grammar so my professor is asking us to first eliminate recursion, then left factor, then remove ambiguity from our grammar. But, from what I've read, ambiguity is usually eliminated first. I'm not sure how to remove ambiguity after left factoring.

This is how what I got after left factoring it:

S -> i E t S S' | other
S' -> e S | epsilon

However, as I understand it, removing ambiguity requires a rewrite of the grammar so the grammar will always result similar to this right?

S -> U | M
M -> i E t M e M | other
U -> i E t U'
U' -> M e U | S

Or is there another way to do it? As far as I can see, this is the only way to remove ambiguity from the dangling else.

Upvotes: 2

Views: 1285

Answers (2)

PraveenCv
PraveenCv

Reputation: 1

I think this can be a possible answer:

[After left factoring and making it unambiguous]

Let other = a

S -> iEtT | a

T -> S | aeS

I am generating all if's first and associating the else with the recent unassociated if . If I have to get an else, I should be eliminating the possibility of getting a new if between the current unassociated if and corresponding else.
However I am allowing the possibility of getting an if after generating the corresponding else.

Point out if there are any errors.

Thank you.

Upvotes: 0

CSharpFiasco
CSharpFiasco

Reputation: 254

As it turns out, a good way to deal with ambiguity caused by a dangling else in an LL(1) is to handle it in the parser. Rewriting the grammar is also another way to handle it, as is adding 'begin' and 'end' in the grammar like so:

S -> i E t a S z S' | other
S' -> e S | epsilon

Although it might be intuitive for some, for other beginners, this is what the symbols mean:

S: Statement

i: if

E: Expression

t: then

a: begin

z: end

S': Statement'

e: else

other: any other productions

Note: lower case letters represent terminals; Uppercase letters represent variables.

If anything is wrong, please let me know and I'll correct it.

Upvotes: 0

Related Questions