Theory of computation: Considering this grammar, construct: Consider the grammar

Question

Theory of computation: Considering this grammar, construct:

Consider the grammar: S right arrow i C t S S right arrow i C t S e S S right arrow a C right arrow b where i, t, and, e stand for if, then, and else, and C and S for "conditional" and "statement." Construct a rightmost derivation for the sentence w = i b t i b t a e a. Show the corresponding parse tree for the above sentence. Is the above grammar ambiguous? If so, prove it.

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. b) The proof that all prefixes have at least as many a's as b's follows from the given productions. It is clearly true if the length of the string is 1 (it can only be a single a) or 2 (aa or ab). Assume that it is true for all strings of length up to n. Then, using the given productions, we can construct strings of length n+1. and longer, for which the property clearly holds because we have added an a to any previous prefix. Therefore the property holds for all n. c) 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.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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