编译原理第4章习题答案x

《编译原理第4章习题答案x》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理习题答案-第4章作业7：P1194.2.1P1204.2.2(3)4.2.3作业8：P1264.3.14.3.2(1)作业9：P1364.4.3作业10：P1364.4.1（3）P1424.5.2(3)4.5.3(2)4.2.1考虑上下文无关文法：以及串1）给出这个串的一个最左推导。2）给出这个串的一个最右推导。第四章语法分析3）给出这个串的一棵语法分析树。4）这个文法是否为二义性的？证明你的回答。该文法不是二义性的。因为对于文法产生的每一个符号串，不存在两棵不同的分析树（或两种不同的最左或最右推导）。

2、5）描述这个文法生成的语言。以a为变量，+和*为二元操作符的后缀表达式的集合4.2.23）考虑上下文无关文法：以及串　(()())。１）给出这个串的一个最左推导。２）给出这个串的一个最右推导３）给出这个串的一棵语法分析树。4）这个文法是否为二义性的？证明你的回答。该文法是二义性的文法。如串()()对应着两棵不同的语法分析树。5）描述这个文法生成的语言。括号的匹配，包括空串。4.2.3为下面的语言设计文法：1）所有由0和1组成的并且每个0之后都至少跟着一个1的串的集合。2）所有由0和1组成的回文的集合，也就是从前

3、面和从后面读结果都相同的串的集合。3）所有由0和1组成的具有相同多个0和1的串的集合。4）所有由0和1组成的并且0的个数和1的个数不同的串的集合。SA

4、BAAA

5、E0E（A是0比1多的串）BBB

6、E1E（B是1比0多的串）E0E1E

7、1E0E

8、（E是0和1的个数相等的串）5）所有由0和1组成的且其中不包含子串011的串的集合。6）所有由0和1组成的形如xy的串的集合，其中且x和y等长。SAB

9、BAAXAX

10、0（A是奇数长度，中间为0的串）BXBX

11、1（B是奇数长度，中间为1的串）X0

12、14.3

13、.1下面是一个只包含符号a和b的正则表达式的文法。它使用+替代表示并运算的字符“｜”，以避免和文法中作为元符号使用的竖线相混淆：1）对这个文法提取左公因子。２）提取左公因子的变换能使这个文法适用于自顶向下的语法分析技术吗？不可以。文法中依然存在左递归。３）提取左公因子之后，从原文法中消除左递归。４）得到的文法适用于自顶向下的语法分析吗？适用。因为文法中不存在左公因子，也不存在左递归。4.3.21)S->SS+

14、SS*

15、aa.提取左公因子：S->SSA

16、aA->+

17、*b.提取左公因子的变换能使这个文法适用于自顶向

18、下的语法分析技术吗？不可以。文法中依然存在左递归。c.消除左递归：S->aS’S’->SAS’

19、ƐA->+

20、*d.得到的文法适用于自顶向下的语法分析吗？适用。因为文法中不存在左公因子，也不存在左递归S->aS’S’->aS’AS’

21、ƐA->+

22、*代入AA

23、改写为AAAA

24、4.4.3S->SS+

25、SS*

26、aFIRST(S)={a}因为S是起始符号，把{$}加入到Follow(S)中。对于S->SS+的第一个S，把First(S+)={a}加入到Follow(S)中。对于S->SS*的第一个S

27、，把First(S*)={a}加入到Follow(S)中。对于S->SS+的第二个S，把First(+)={+}加入到Follow(S)中。对于S->SS*的第二个S，把First(*)={*}加入到Follow(S)中。所以，FOLLOW(S)={a,+,*,$}仅消除左递归后的文法：FIRST(S)={a}，FIRST(S')={a,}FOLLOW(S)=FOLLOW(S')={+,*,$}题目中并没有要求我们消除左递归，所以第一个答案才是符合要求的。下页还有内容。S->aS’S’->aS’AS’

28、ƐA-

29、>+

30、*4.3.21)中，我们先提取左公因子，然后消除左递归后，并代入，得到如下的文法，详见前两页的ppt。First(S)=First(aS’)={a}First(S’)=First(aS’AS’)∪First(Ɛ)={a}∪{Ɛ}={a,Ɛ}First(A)={+,*}Follow(S)={$}因为S->aS’，所以把Follow(S)加入到Follow(S’)中。因为S’->aS’AS’的第一个S’，所以把First(AS’)={+,*}加入到Follow(S’)中。因为S’->aS’AS’的第二个S’，

31、所以Follow(S)加入到Follow(S’)中。所以，Follow(S’)={$,+,*}对S’->aS’AS’的A，当A后面的S’推导出非空时，把First(S’)-{Ɛ}={a}加入到Follow(A)中。对S’->aS’AS’的A，当A后面的S’推导出空时，把Follow(S’)={$,+,*}加入到Follow(A)中。所以，Follow(A)={a,+,*,$}对于S’-