Problem 4 consider the grammar S arrow aS|aSbS|e This grammar is ambiguous. Show

Question

Problem 4 consider the grammar S arrow aS|aSbS|e This grammar is ambiguous. Show in particular that the string aab has two: a) Parse trees b) Leftmost derivations e) Rightmost derivations Find an unambiguous grammar.

Explanation / Answer

The ambiguity is easy to show: you can derive the string aab as follows: (at every step we expand the leftmost non-terminal); S -> aSbS -> aaSbS -> aabS -> aab S -> aS -> aaSbS -> aabS -> aab These two parses correspond to associating the b with the first or the second a. This is somewhat analogous to the problem of the dangling else, where the last else may be associated with the previous then or with an earlier one. unambiguous grammar We can disambiguate by using a similar approach to the dangling else, and decide that each b should be associated with the nearest a. This means that the expansion within an ab pair should always be balanced. This leads to the following grammar: S -> a S | S1 S | epsilon S1 -> a S1 S1 b | epsilon It is easy to verify that this generates the same strings as the original grammar, and the parse tree is always unique, because one b is always associated with the most recent a. Note that the answer is not necessarily unique. If the grammar is ambiguous, it means that we get to choose between possible parses, and each choice is in a sense a different language. For example, given the ambiguous grammar for expressions: E -> E + E | E * E | id We say that the unambiguous grammar we want is: E -> E + T | T, T -> T * T | id because it gives us the proper precedence between the two operators. But that choice is in no way mandated by the grammar. We could just as well choose: E -> E * T | T , T -> T + T | id which generates the same strings, but gives the opposite precedence to operators.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.