CODEWITHSUNDEEP
parsingcompiler-constructiongrammarcontext-free-grammarlr-grammar
Kostas Ayfantop
Kostas Ayfantop

Reputation: 53

Is these 2 grammars equal?

I have the following grammar which is ambiguous and of course not slr1:

E -> E+A+A | E+A-A | E-A+A | E-A-A | T
T -> T+A | T-A | A
A -> A*B | A/B | B
B -> (E) | x

I used the rule of transformation which is:

E -> E + T  ----->  E -> TE'
                    E' -> +TE' | ε

so the first grammar transforms into this:

E -> T E' .
E' -> + A + A E' .
E' -> + A - A E' .
E' -> - A + A E' .
E' -> - A - A E' .
E' -> .
T -> A T' .
T' -> + A T' .
T' -> - A T' .
T' -> .
A -> B A' .
A' -> * B A' .
A' -> / B A' .
A' -> .
B -> ( E ) .
B -> x .

This is solving the ambiguity but it continues not being slr1. The transformation is correct. After that I erase the T rules and I install them to E'. So the final grammar which is slr1 is the following:

E -> A E' .
E' -> + A + A E' .
E' -> + A - A E' .
E' -> - A + A E' .
E' -> - A - A E' .
E' -> + A .
E' -> - A .
E' -> .
A -> B A' .
A' -> * B A' .
A' -> / B A' .
A' -> .
B -> ( E ) .
B -> x .

Now I have 2 questions.

  1. The 2 final grammars are equal ?? I define equality by saying that these 2 grammars must accept the same sentences. It seems that they do.
  2. Is the fact that i erased the T rules correct ?? My exercise ask that I change the very first one to slr1 and all i came up with was the final one. Thx in advanced and sorry for my english.

Upvotes: 0

Views: 101

Answers (1)

rici
rici

Reputation: 241671

I hope that your assignment is marked by someone who provides good feedback. I would like to believe that higher education still works in some places, but obviously that is a bit of an illusion.

Anyway. The grammar you end up with is a valid solution to the problem as you present it, but the solution is based on a misconception and an error, which coincidentally cancel each other out to produce a valid result.

First, the misconception: left-recursion is not the same as ambiguity, and consequently left-factoring and eliminating left-recursion does not remove ambiguity. In particular, your claim that "This is solving the ambiguity but it continues not being SLR(1)" is mistaken. The transformation does not remove the ambiguity; the grammar continues to not be SLR(1) because it is still ambiguous.

E                   E
T E'                T E'
A T' E'             A T' E'
B A' T' E'          B A' T' E'
x A' T' E'          x A' T' E'
x T' E'             x T' E'
x + A T' E'         x E'
x + B A' T' E'      x + A + A E'
x + x A' T' E'      x + B A' + A E'
x + x T' E'         x + x A' + A E'
x + x + A T' E'     x + x + A E'
x + x + B A' T' E'  x + x + B A' E'
x + x + x A' T' E'  x + x + x A' E'
x + x + x T' E'     x + x + x E'
x + x + x E'        x + x + x
x + x + x

The mistake is the erasure of the T rules. You start with

E -> T E' .
T -> A T' .
T' -> + A T' .
T' -> - A T' .
T' -> .

From that, you can easily erase T, since it is only used in one place:

E -> A T' E'.
T' -> + A T' .
T' -> - A T' .
T' -> .

Erasing T' is not so simple, though, because it is recursive. And, in any event, E' does not have any production which uses T', so adding new productions to E' is not a mechanical elimination of T'.

However, the productions you choose to add to E' do, in fact, eliminate the ambiguity. So well done, in that sense. But note that you could have done this without the left-recursion elimination:

E -> E + A + A .
E -> E + A - A .
E -> E - A + A .
E -> E - A - A .
E -> A + A .
E -> A - A .
E -> A .
A -> A * B .
A -> A / B .
A -> B .
B -> ( E ) .
B -> x .

That grammar is unambiguous, for the same reason yours is: the + and - operators are decomposed into a sequence of ternary operations, possibly preceded by a single binary operation (in case the sequence of additive operators contains an odd number of operators). But it is not SLR(1). Indeed, it is not LR(k) for any k, because it is impossible to know whether the sequence of operations should start with a ternary or binary operation until we know whether there are an even or odd number of operators.

But we can solve that problem (in effect, in the same way as your grammar) by making the additive operators right-associative:

E -> A + A + E .
E -> A + A - E .
E -> A - A + E .
E -> A - A - E .
# Rest of the grammar is the same

This grammar is not LL(1), of course; it is not left-factored. But the original problem did not require an LL(1) grammar, and the above is SLR(1).

However, that is just one possible interpretation of the original ambiguous grammar, and quite possibly not the most natural one since right-associativity is not usually the natural interpretation. Unless the problem specifies a desired associativity, there is no way to know what is desired.

Upvotes: 2

Related Questions