编译原理第六章到第十一章课后习题答案.pdf

编译原理第六章到第十一章课后习题答案

p116/1.已知文法G[S]为：

S→a|∧|(T)

T→T,S|S

(1)计算FIRSTVT--LASTVT表

(2)构造算符优先关系表（OPERATERPRIORITYRELATION

TABLE），说明是否为算符优先文法。=:#=#,(=)=:#=#,(=)

:LASTVT(S)#,LASTVT(T)),LASTVT(T),

表中无多重人口所以是算符优先（OPG）文法。

（3）计算G[S]的优先函数。

收敛

（4）对输入串（a,a）#的算符优先分析过程为

Success!

3.有文法G（S）：

s-V

v-T/ViT

T-F/T+F

F-)V*|(

(1)(+(i(的规范推导

S=V

=ViT

=ViF

=Vi(

=Ti(

=T+Fi(

=T+(i(

=F+(i(

=(+(i(

(2)F+Fi（的短语、句柄、素短语。

短语

S:F+Fi（

T1:F+F（素短语）

T2:F（句柄）

F:(（素短语）

(3)G(S)是否为OPG？若是，给出（1）中句子的分析过程！

S’-#S#S-VV-T/ViTT-F/T+FF-)V*|(

算符优先关系表（OPERATERPRIORITYRELATIONTABLE）

对输入串(+(I(的算符优先分析过程为:

p152/2

文法：

S→L.L|L

L→LB|B

B→0|1

拓广文法为G′，增加产生式S′→S

I3

若产生式排序为：

0S→S

1S→L.L

2S→L

3L→LB

4L→B

5B→0

6B→1

由产生式知：

First(S)={0,1}

First(S)={0,1}

First(L)={0,1}

First(B)={0,1}

Follow(S)={#}

Follow(S)={#}

Follow(L)={.,0,1,#}

Follow(B)={.,0,1,#}

G′的LR(0)项目集族及识别活前缀的DFA如下图所示：

I5

B→.0和B→.1为移进项目，S→L.为归约项目，存在移进-归约

冲突，因此所给文法不是LR(0)文法。

在I

2、I

8

中：

Follow(s)∩{0，1}={#}∩{0，1}=

所以在I

2、I

8

中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。

构造的SLR(1)分析表如下：

分析成功，说明输入串101.110是题目2文法的句子。

0)S’-S

1)S-a

2)S-^

3)S-(T)

4)T-T,S

5)T-S

LR(0)分析表

[8。1]写出下列各式的逆波兰表示

（1）-a-((b*c)/(c-d)+(-b)*a)

(2)-A+B*C↑(D/E)/F

栈顶运算符与当前运算符比较：

栈顶运算符当前运算符：进栈

栈顶运算符当前运算符：进行运算

解8.1：

（1）a@bc*cd-/b@a*+-

（2）A@BCDE/↑*F/+

[8。2]写出表达式

A+B*(C-D)-E/F↑G

逆波兰表示，三元组表示，四元组表示。解8.2：逆波兰表示：

ABCD-*+EFG↑/-

①(-,C,D)

②(*,B,①)

③(+,A,②)

④(↑,F,G)

⑤(/,E,④)

⑥(-，③，⑤）

四元式组：

1)（