编译原理作业答案最终版

( 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