Homework 12 Parse Trees 1 CS 341 Homework 12 Parse Trees 1. Consider the grammar G = ({+, *, (, ), id, T, F, E}, {+, *, (, ), id}, R, E}, where R = {E → E+T, E → T, T → T * F, T → F, F → (E), F → id}. Give two derivations of the string id * id + id, one of which is leftmost and one of which is not leftmost. 2. Draw parse trees for each of the following: (a) The simple grammar of English we presented in class and the string "big Jim ate green cheese." (b) The grammar of Problem 1 and the strings id + (id + id) * id and (id * id + id * id). 3. Present a context-free grammar that generates ∅, the empty language. 4. Consider the following grammar (the start symbol is S; the alphabets are implicit in the rules): S → SS | AAA | ε A → aA | Aa | b (a) Describe the language generated by this grammar. (b) Give a left-most derivation for the terminal string abbaba. (c) Show that the grammar is ambiguous by exhibiting two distinct derivation trees for some terminal string. (d) If this language is regular, give a regular (right linear) grammar generating it and construct the corresponding FSM. If the language is not regular, prove that it is not. 5. Consider the following language : L = {wRw" : w ∈ {a, b}* and w" indicates w with each occurrence of a replaced by b, and vice versa}. Give a context-free grammar G that generates L and a parse tree that shows that aababb ∈ L. 6. (a) Consider the CFG that you constructed in Homework 11, Problem 2 for {wcwR : w ∈ {a, b}*}. How many derivations are there, using that grammar, for the string aabacabaa? (b) Show parse tree(s) corresponding to your derivation(s). Is the grammar ambiguous? 7. Consider the language L = {w ∈ {a, b}* : w contains equal numbers of a's and b's} (a) Write a context-free grammar G for L. (b) Show two derivations (if possible) for the string aabbab using G. Show at least one leftmost derivation. (c) Do all your derivations result in the same parse tree? If so, see if you can find other parse trees or convince yourself there are none. (d) If G is ambiguous (i.e., you found multiple parse trees), remove the ambiguity. (Hint: look out for two recursive occurrences of the same nonterminal in the right side of a rule, e.g, X → XX) (e) See how many parse trees you get for aabbab using the grammar developed in (d). Solutions 3. G = ({S} ∪ Σ, Σ, R, S), where R is any set of rules that can't produce any strings in Σ*. So, for example, R = {S → S} does the trick. So does R = ∅.Homework 12 Parse Trees 2 4. (a) (a*ba*ba*ba*)* (b) S Þ AAA Þ aAAA Þ abAA Þ abAaA Þ abbaA Þ abbaAa Þ abbaba (c) S S A A A A A A A a b b b a A b b b (d) G = ({S, S1, B1, B2, B3, a, b}, {a, b}, R, S), where R = { S →ε S → S1 S1 → aS1 S1 → bB1 B1 → aB1 B1 → bB2 B2 → aB2 B2 → bB3 B3 → aB3 B3 → ε B3 → S1 a a S ε S1 b B1 ε ε b F ε B3 b B2 a a 5. G = ({S, a, b}, {a, b}, R, S), R = { S → aSb, S → bSa, S → ε} S a S b a S b b S a ε 6. (a) The grammar is G = (V, Σ, R, S) with V = {S, a, b, c}, Σ = {a, b, c}, R = {S → aSa, S → bSb, S → c}. There is a single derivation: S Þ aSA Þ aaSaa Þ aabSbaa Þ aabaSabaa Þ aabacabaa (b) There is a single parse tree. The grammar is unambiguous. 7. (a) G = (V, Σ, R, S) with V = {S }, Σ = {a, b }, R = { S → aSb S → bSa S → ε S → SS } (b) (i) S Þ SS Þ aSbS Þ aaSbbS Þ aabbaSb Þ aabbab /* This is the leftmost derivation of the most "sensible" parse. (ii) S Þ SS Þ SSS Þ aSbSS Þ aaSbbSS Þ aabbSS Þ aabbaSbS Þ aabbabS Þ aabbab /* This is the leftmost derivation of a parse that introduced an unnecessary S in the first step, which was then eliminated by rewriting it as ε in the final step.Homework 12 Parse Trees 3 (c) No. The two derivations shown here have different parse trees. They do, however, have the same bracketing, [a[ab]b][ab].(In other words, they have similar essential structures.) They differ only in how S is introduced and then eliminated. But there are other derivations that correspond to additional parse trees, and some of them correspond to a completely different bracketing, [a[ab][ba]b]. One derivation that does this is (ii) S Þ aSb Þ aSSb Þ aabSb Þ aabbab (d) This is tricky. Recall that we were able to eliminate ambiguity in the case of the balanced parentheses language just by getting rid of ε except at the very top to allow for the empty string. If we do the same thing here, we get R = { S → ε S → T T → ab T → aTb T → ba T → bTa T → TT But aabbab still has multiple parses in this grammar. This language is different from balanced parens since we can go back and forth between being ahead on a's and being ahead on b's (whereas, in the paren language, we must always either be even or be ahead on open paren). So the two parses correspond to the bracketings [aabb][ab] and [a [ab] [ba] b]. The trouble is the rule T → TT, which can get applied at the very top of the tree (as in the case of the first bracketing shown here), or anywhere further down (as in the case of the second one). We clearly need some capability for forming a string by concatenating a perfectly balanced string with another one, since, without that, we'll get no parse for the string abba. Just nesting won't work. We have to be able to combine nesting and concatenation, but we have to control it. It's tempting to think that maybe an unambiguous grammar doesn't exist, but it's pretty easy to see how to build a deterministic pda (with a bottom of stack symbol) to accept this language, so there must be an unambiguous grammar. What we need is the notion of an A region, in which we are currently ahead on a's, and a B region, in which we are currently ahead on b's. Then at the top level, we can allow an A region, followed by a B region, followed by an A region and so forth. Think of …
View Full Document
Unlocking...