Description
Learning Objectives:
In this homework, we are going to exercise the following key knowledge points on the topic of
context-free grammar (CFG)
1. understanding the relations of strings and grammars
2. performing derivations and constructing parse trees
3. determining and resolving ambiguity
4. designing a grammar to describe given string patterns
Instructions:
1. Total points: 40 pt
2. Early deadline: Sept 11 (Wed) 11:59 pm, Regular deadline Sept 13 (Fri) 11:59 pm (you can continue
working on the homework till TA starts to grade the homework)
3. How to submit:
• Submit your document to Canvas under Assignments, Homework 1
• Please provide the complete solutions in one pdf file
• You can write your solutions in latex or word and then convert it to pdf; or you can submit a
scanned document with legible handwritten solutions
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
Fall 2019 page 2 of 3
CS 342 Principles of Programming Languages Homework 1
Explain how the value of the string is generated.
4. (10 pt) Design CFGs for the given languages:
(a) (2 pt) Write a grammar that describes the strings 0∗1
+2
∗
.
(b) (3 pt) Write a grammar that describes the strings 0n1
m, where n > m.
(c) (5 pt) Given a graph below, where 1 is an entry and 7 is an exit, we can generate paths like 127,
1234627, 1235627, 12356234627 … Write a grammar that describes these paths.
1
2
7 3
4 5
6
Fall 2019 page 3 of 3