程序代写代做代考 CS314 Fall 2018 Assignment3 Solution

CS314 Fall 2018 Assignment3 Solution

September 2018

1 (a)

FIRST sets for left hand sides:
FIRST()={def}

FIRST()={(}

FIRST()={f,g}

FIRST()={,,�}
FIRST()=FIRST()={ }

FIRST()={
,�}
FIRST()={FIRST(), FIRST(), FIRST()} ={a,b,c,if,return}

FIRST()=FIRST()={a,b,c}

FIRST()=FIRST()={a,b,c}

FIRST()={if}

FIRST()={return}

FIRST()=FIRST()={a,b,c,0,1,2}

FIRST()={FIRST(), FIRST()}={a,b,c,0,1,2}

FIRST()={a,b,c}

FIRST()={0,1,2}

FIRST sets for right hand sides:
FIRST(def :
EOF)={def}

FIRST(f)={f}

FIRST(g)={g}

FIRST(( ))={(}

FIRST(, )={,}

FIRST( )={ }

FIRST(
)={
}

FIRST(if:
else :)={if}

FIRST(return)={return}

FIRST(a)={a}

FIRST(b)={b}

FIRST(c)={c}

FIRST(0)={0}

FIRST(1)={1}

FIRST(2)={2}

FOLLOW sets:
FOLLOW()=FIRST()={(}

FOLLOW()={:}

FOLLOW()={)}

FOLLOW()={EOF}

FOLLOW()=FOLLOW()={EOF}

FOLLOW()=FOLLOW()={EOF}

FOLLOW()={FIRST(), FOLLOW()}={
, EOF}

FOLLOW()=FOLLOW()={
, EOF}

1

FOLLOW()={:}

FOLLOW()=FOLLOW()={
, EOF}

FOLLOW()=FOLLOW()={
, EOF}

FOLLOW()={FOLLOW(), FOLLOW()}={
, EOF, :}

FOLLOW()={+, FOLLOW()}={+,
, EOF, :}

FOLLOW()=

{=, <=, FOLLOW(), FIRST()-�, FOLLOW(, FOLLOW())}
={=, <= , +, , EOF, :, , , )} FOLLOW()={FOLLOW()}={+,
, EOF, :}

PREDICT sets:
(1)PREDICT(::=def :
EOF)={def}
(2)PREDICT(::=f)={f}
(3)PREDICT(::=g)={g}
(4)PREDICT(::=( ))={(}
(5)PREDICT(::=, )={,}
(6)PREDICT(::=�)=FOLLOW()={)}
(7)PREDICT(::=)=FIRST()={ }
(8)PREDICT(::= )={ }
(9)PREDICT(::=
)={
}
(10)PREDICT(::=�)=FOLLOW()={EOF}
(11)PREDICT(::=)=FIRST()={a, b, c}
(12)PREDICT(::=)=FIRST()={if}
(13)PREDICT(::=)=FIRST()={return}
(14)PREDICT(::==)=FIRST()={a,b,c}
(15)PREDICT(::= <=)=FIRST()={a,b,c}
(16)PREDICT(::=if:
else :)={if}
(17)PREDICT(::=return)={return}
(18)PREDICT(::=+)=FIRST()={a, b, c, 0, 1, 2}
(19)PREDICT(::=)=FIRST()={a,b,c}
(20)PREDICT(::=)=FIRST()={0,1,2}
(21)PREDICT(::=a)={a}
(22)PREDICT(::=b)={b}
(23)PREDICT(::=c)={c}
(24)PREDICT(::=0)={0}
(25)PREDICT(::=1)={1}
(26)PREDICT(::=2)={2}
45pt: 15pts for FIRST of non-terminal symbols, 1pt for each; 4pts for FOLLOW() and FOLLOW() , 2pt for each;

26pts for PREDICT, 1pt for each

2 (b)

def :
EOF f g ( ) , = <= if else return + a b c 0 1 2 (1)
(2) (3)
(4)
(6) (5)
(7)

(8)
(9) (10)

(12) (13) (11) (11) (11)
(14) (14) (14)

(15) (15) (15)
(16)

(17)
(18) (18) (18) (18) (18) (18)
(19) (19) (19) (20) (20) (20)

(21) (22) (23)
(24) (25) (26)

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 !=
)

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 == )

return stmtlist();

else

return false;

}

bool stmtlist() {

if (token != )

return false;

token = next_token();

if (!stmt())

return false;

if (!morestmts())

return false;

return true;

}

bool morestmts() {

switch(token) {

case
:

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 != ) return false; token = next_token(); if (token != ) 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