编译原理作业答案最终版

第一次作业答案： 3.12 词法单元描述

text 标签间的文本 Here is a photo of , my house, ; , See , More Pictures , if you liked that one. Start_tag End_tag attrbute value 开始标签 结束标签 标签内的参数 ,

,,
, , SRC,HREF 标签内的参数“house.gif” , “morePix.html” 值 assign_op 赋值号 = 3.3.5 b)a*b*……z* c) /\\*([^*”]|\\*[^/]|\\”([^”]*)\\”)*\\*/ h)b*(a|ab)* 3.7.3d

F转G错误，F跳转后的状态子集应包含9

第二次作业答案：

4.2.2 最左推导 S->SS S->S*S S->(S)*S S->(S+S)*S S->(a+S)*S S->(a+a)*S S->(a+a)*a Parse tree:

SSS*Sa(S)S+S 最右推导： S->SS S->S*a S->(S)*a

aa S->(S+S)*a S->(S+a)*a S->(a+a)*a

无二义性，只能画出一棵语法树。 4.3.2

提取左公因子： S->SS’|(S)|a S’->+S|S|* 消除左递归：

S->(S)A|aA , A->BA|? B->S|+S|*

FIRST(S) = { a , ( }

FIRST(A) = {* , a , ( , + , ?} FIRST(B) = {* , a , ( , +}

FOLLOW(S) = { ( , ) , a , * , + , $}

LL1 parse table:

转换表如下： S A B a S->aA A->BA B->S ( S->(S)A A->BA B->S ) A->? $ A->? + A->BA B->+S * A->BA B->*

match stack input action S$ (a+a)*a$

(S)A$ (a+a)*a$ S->(S)A

( S)A$ a+a)*a$ match( ( aA)A$ a+a)*a$ S->aA (a A)A$ +a)*a$ match a (a BA)A$ +a)*a$ A->BA (a +SA)A$ +a)*a$ B->+S (a+ SA)A$ a)*a$ match + (a+ aAA)A$ a)*a$ S->aA (a+a AA)A$ )*a$ match a (a+a A)A$ )*a$ A->? (a+a )A$ )*a$ A->? (a+a) A$ *a$ match ) (a+a) BA$ *a$ A->BA (a+a) *A$ *a$ B->* (a+a)* A$ a$ match * (a+a)* BA$ a$ A->BA (a+a)* SA$ a$ B- >S (a+a)* aAA$ a$ S->aA (a+a)*a AA$ $ match a (a+a)*a $ $ A->?

第三次作业答案：

文法 S—>SS+|SS*|a

p240 Ex 4.5.2 对该文法求句柄和右句型

最右句型 句柄 归约产生式 SSS+a*+ SS+ S->SS+ SSa*+ a S->a SSS*+ SS* S->SS* SS+ SS+ S->SS+

SS+a*a+ SS+ S->SS+ Sa*a+ a S->a SS*a+ SS* S->SS* Sa+ a S->a SS+ SS+ S->SS+

aaa*a++ a S->a Saa*a++ a S->a SSa*a++ a S->a SSS*a++ SS* S->SS* SSa++ a S->a SSS++ SS+ S->SS+ SS+ SS+ S->SS+

p258 Ex4.6.1 b)，求可行前缀 S—>SS+|SS*|a aa+a*

最右推导：

S->SS* ->Sa*->SS+a*->Sa+a*->aa+a* 可行前缀

a, a, S, SS, SS+, a, S, SS, SS*

p258 Ex4.6.2 求基于LR(0) item的DFA、Parsing Table，并判断是否SLR(1)，若是，Follow set也要求出

产生式 1) S->SS+ 2) S->SS* 3) S->a 需要扩展文法 Parsing table

State action GOTO a + * $ S 0 S2 1 1 S2 acc 3 2 r3 r3 r3

3 S2 S4 S5 4 3 4 r1 r1 r1 5 r2 r2 r2

是SLR Follow(s)={+,*,a}

p258 Ex4.6.3 针对输入串，模拟match的过程，包括stack、input string的每一步操作，自己画表

stack input action Goto $0 aa*a+$ S2

$0a2 a*a+$ r3 1 $0S1 a*a+$ S2

$0S1a2 *a+$ r3 3 $0S1S3 *a+$ S5

$0S1S3*5 a+$ r2 1 $0S1 a+$ S2

$0S1a2 +$ r3 3 $0S1S3 +$ S4 $0S1S3+4 $ r1 1 $0S1 $ acc

p258 Ex4.6.5 判断文法属性

FIRST(AaAb)={a} FIRST(BbBa)={b} 不存在交集，所以文法是LL（1）文法。

文法的LR(0)项目集 I0={S’->·S S->·AaAb S->·BbBa }

FOLLOW（A）={a,b} Follow(B)={a,b} 会产生归约-归约冲突，所以文法不是SLR(1)文法。

p408 Ex 6.6.1 a) S’->repeat S while B

S'.begin = newlabel(); B.true = S'.begin; B.false= S'.next;

S'.code= Label S'.begin||S.code||B.code||Label S'.next

本文来源：https://www.bwwdw.com/article/hnfa.html