Programming Languages and Paradigms hw

1. Using the grammar below:

=

A | B | C

+ |

* |

() |

show a parse tree and a leftmost derivation for each of the following statements:

1. A = (A + B) * C
2. A = B + C + A
3. A = A * (B + C)
4. A = B * (C * (A + B))

2. Prove that the following grammar is ambiguous:

+ |

a | b | c

3. Modify the grammar of Example 3.4 to add a unary minus operator that has higher precedence than either + or *.

=

A | B | C

+ |

* |

() |

4. Describe, in English, the language defined by the following grammar:

a | a

b | b

e

5. Consider the following grammar:

a b

b | b

b

Which of the following sentences are in the language generated by this grammar?

1. babb
2. bbbabb
3. bbaaaaabc
4. aaaaaa

6. Consider the following grammar:

a c |

c | c

d

Which of the following sentences are in the language generated by this grammar?

1. abcd
2. acccbd c. acccbcc d. accd
3. ccc