CS314 Fall 2018 Assignment3 Solution
September 2018
1 (a)
FIRST sets for left hand sides:
FIRST(
FIRST(
FIRST(
FIRST(
FIRST(
FIRST(
FIRST(
FIRST(
FIRST(
FIRST(
FIRST(
FIRST(
FIRST(
FIRST(
FIRST(
FIRST sets for right hand sides:
FIRST(def
FIRST(f)={f}
FIRST(g)={g}
FIRST((
FIRST(,
FIRST(\t
FIRST(\n
FIRST(if
FIRST(return
FIRST(a)={a}
FIRST(b)={b}
FIRST(c)={c}
FIRST(0)={0}
FIRST(1)={1}
FIRST(2)={2}
FOLLOW sets:
FOLLOW(
FOLLOW(
FOLLOW(
FOLLOW(
FOLLOW(
FOLLOW(
FOLLOW(
FOLLOW(
1
FOLLOW(
FOLLOW(
FOLLOW(
FOLLOW(
FOLLOW(
FOLLOW(
{=, <=, FOLLOW(
={=, <= , +, \n, EOF, :, , , )}
FOLLOW(
PREDICT sets:
(1)PREDICT(
(2)PREDICT(
(3)PREDICT(
(4)PREDICT(
(5)PREDICT(
(6)PREDICT(
(7)PREDICT(
(8)PREDICT(
(9)PREDICT(
(10)PREDICT(
(11)PREDICT(
(12)PREDICT(
(13)PREDICT(
(14)PREDICT(
(15)PREDICT(
(16)PREDICT(
(17)PREDICT(
(18)PREDICT(
(19)PREDICT(
(20)PREDICT(
(21)PREDICT(
(22)PREDICT(
(23)PREDICT(
(24)PREDICT(
(25)PREDICT(
(26)PREDICT(
45pt: 15pts for FIRST of non-terminal symbols, 1pt for each; 4pts for FOLLOW(
26pts for PREDICT, 1pt for each
2 (b)
def : \n EOF f g ( ) , \t = <= if else return + a b c 0 1 2
2
Empty entities in the table imply error.
21pt: 1pt each row, additionally, a missed column should be penalized with 1pt, except columns without any entities
3 (c)
void main(){
token = next_token();
if (program()) {
print(“accept”)
} else {
print(“error”);
}
}
bool program() {
if (token != def)
return false;
token = next_token();
if (!funcname())
return false;
if (!arguments())
return false;
if (token != 🙂
return false;
token = next_token();
if (token != \n)
return false;
token = next_token();
if (!block())
return false;
if (token != EOF)
return false;
token = next_token();
return true;
}
bool funcname() {
switch(token) {
case f:
case g:
token = next_token();
return true;
default:
return false;
}
}
bool arguments() {
if (token != ()
return false;
token = next_token();
if (!variable())
return false;
3
if (!morevars())
return false;
if (token != ))
return false;
token = next_token();
return true;
}
bool morevars() {
switch(token) {
case ):
return true;
case ,:
token = next_token();
if (!variable())
return false;
return morevars()
default:
return false;
}
}
bool block() {
if (token == \t)
return stmtlist();
else
return false;
}
bool stmtlist() {
if (token != \t)
return false;
token = next_token();
if (!stmt())
return false;
if (!morestmts())
return false;
return true;
}
bool morestmts() {
switch(token) {
case \n:
token = next_token();
return stmtlist();
case EOF:
return true;
default:
return false;
}
}
bool stmt() {
switch(token) {
4
case if:
return ifstmt();
case return:
return returnstmt();
case a:
case b:
case c:
return assign();
default:
return false;
}
}
bool assign() {
switch(token) {
case a:
case b:
case c:
if (!variable())
return false;
if (token != =)
return false;
token = next_token();
if (!expr())
return false;
return true;
default:
return false;
}
}
bool condition() {
switch(token) {
case a:
case b:
case c:
if (!variable())
return false;
if (token != <=) return false; token = next_token(); if (!expr()) return false; return true; default: return false; } } bool ifstmt() { if (token != if) return false; token = next_token(); if (!condition()) 5 return false; if (token != 🙂 return false; token = next_token(); if (!assign()) return false; if (token != \n) return false; token = next_token(); if (token != \t) return false; token = next_token(); if (token != else) return false; token = next_token(); if (token != 🙂 return false; token = next_token(); return assign() } bool returnstmt() { if (token != return) return false; token = next_token(); return variable(); } bool expr() { switch(token) { case a: case b: case c: case 0: case 1: case 2: if (!term()) return false; if (token != +) return false; token = next_token(); return term(); default: return false; } } bool term() { switch(token) { case a: case b: case c: return variable(); case 0: 6 case 1: case 2: return digit(); default: return false; } } bool variable() { switch(token) { case a: case b: case c: token = next_token(); return true; default: return false; } } bool digit() { switch(token) { case 0: case 1: case 2: token = next_token(); return true; default: return false; } } 34pt: 2pt for each function 7