Description
Questions:
1. (10 pt) Given a string a0b10c and the context free grammar G:
S → SA|A|SD
A → a|b|c
D → 0|1
(a) (2 pt) What are the terminals and non-terminals of the grammar?
(b) (2 pt) Give a leftmost derivation for the string
(c) (2 pt) Give a rightmost derivation for the string
(d) (2 pt) Give a parse tree for the string
(e) (2 pt) Write 3 strings using the terminals that do not belong to the language of the grammar
L(G)
2. (10 pt) Consider the following grammar:
• terminals: x, y, z, >, <, 0, 1,(,), if, then, else
Fall 2019 page 1 of 3
CS 342 Principles of Programming Languages Homework 1
• non-terminals: S, F, B, T, E, N
• start symbol: S
• production rules:
S → F|T N T
F →if B then S|if B then S else S
B → (T E T)
T → x|y|z|1|0
E →> | <
N → +| − | =
(a) (4 pt) Draw two different parse trees for the string
if (x > y) then if (x < z) then x = 1 else x = 0
(b) (2 pt) Modify the grammar to remove ambiguity.
(c) (2 pt) Draw the parse tree for the string using new grammar
(d) (2 pt) Explain how your new grammar modifies the parse trees you drew in the first step to
remove ambiguity
3. (10 pt) Consider the following grammar:
• terminals: x, y, z, +, -, *, /
• non-terminals: E, T, F, V
• start symbol: E
• production rules:
E → E + T|E − T|T
T → F ∗ T|F/T|F
F → x|y|z
(a) (4 pt) What is the associativity of the operators +, −, ∗ and /; explain why.
(b) (3 pt) What is the precedence of +,−, ∗ and /; explain why.
(c) (3 pt) Given a parse tree E
E
T
F
y
∗ T
F
x
/ T
F
z
− T
F
z
∗ T
F
z
/ T
F
y
