10/22/2019 CS536 Homework 3 Solution
CS536 Homework 3 Solution
Question 1:
CFG 1:
This CFG is ambiguous. Below are two different parse trees for the string { }. Different parse trees can also be built for expressions with operators so that one tree groups the subexpressions correctly (according to the precedence and associativeity rules) and the other does not.
exp exp /\|
{} term |
CFG 2:
factor |
set | exp /\ {}
This CFG only allows parentheses around set literals (lists of countries inside curly braces). Here are two legal set expressions that are not in the language of the CFG:
({}¡É{})
{}¡È({}+{}) CFG 3:
This CFG allows a list of countries to start with a hash. Here is a string that is not a legal set expression but is in the language of the CFG:
{ # COUNTRY }
CFG 4:
This CFG doesn’t allow parentheses around the right-hand operand of a union or intersection. Here is a legal set expression that is not in the language of the CFG:
{}¡È({}) CFG 5:
This CFG only allows parentheses around the very outside of the expression. Here are two legal set expressions that are not in the language of the CFG:
{}+({})
({})¡È({}) CFG 6:
This CFG doesn’t allow two or more intersections in a row. Here is a legal set expression that is not in the language of the CFG:
{}¡É{}¡É{}
It also doesn’t allow an itersection to the right of a union. Here is another legal set expression that is not in the language of
the CFG:
file:///Users/jasonmohoney/Downloads/h3/h3_soln.html 1/2
10/22/2019 CS536 Homework 3 Solution
{}¡È{}¡É{} Question 2:
Nonterminal X
FIRST(X)
FOLLOW(X)
program
{
EOF
stmts
ID, if, ¦Å
}
stmt
ID, if
}, ID, if
exp
ID
;,)
tail
+, -, ¦Å
;,)
file:///Users/jasonmohoney/Downloads/h3/h3_soln.html
2/2