编译原理第4章习题答案.pptx

1、编译原理习题答案-第4章,作业7： P119 4.2.1 P120 4.2.2(3) 4.2.3 作业8： P126 4.3.1 4.3.2(1) 作业9： P136 4.4.3 作业10： P136 4.4.1（3） P142 4.5.2(3) 4.5.3(2),4.2.1 考虑上下文无关文法： 以及串 1）给出这个串的一个最左推导。 2）给出这个串的一个最右推导。,第四章 语法分析,3）给出这个串的一棵语法分析树。 4）这个文法是否为二义性的？证明你的回答。 该文法不是二义性的。因为对于文法产生的每一个符号串，不存在两棵不同的分析树（或两种不同的最左或最右推导）。 5）描述这个文法生成的语

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

3、合。,4）所有由0和1组成的并且0的个数和1的个数不同的串的集合。 S A| B A AA | E0E （A是0比1多的串） B BB | E1E （B是1比0多的串） E 0E1E | 1E0E | （E是0和1的个数相等的串） 5）所有由0和1组成的且其中不包含子串011的串的集合。 6）所有由0和1组成的形如xy的串的集合，其中 且x和y等长。 S AB | BA A XAX | 0 （A是奇数长度，中间为0的串） B XBX | 1 （B是奇数长度，中间为1的串） X 0 | 1,4.3.1 下面是一个只包含符号a和b的正则表达式的文法。它使用+替代表示并运算的字符“”，以避免和文法中

4、作为元符号使用的竖线相混淆： 1）对这个文法提取左公因子。,）提取左公因子的变换能使这个文法适用于自顶向下的语法分析技术吗？ 不可以。文法中依然存在左递归。 ）提取左公因子之后，从原文法中消除左递归。 ）得到的文法适用于自顶向下的语法分析吗？ 适用。因为文法中不存在左公因子，也不存在左递归。,4.3.2 1) S- SS+|SS*|a a.提取左公因子：S-SSA|a A-+|* b.提取左公因子的变换能使这个文法适用于自顶向下的语法分析技术吗？ 不可以。文法中依然存在左递归。 c.消除左递归：S-aS S-SAS| A-+|* d.得到的文法适用于自顶向下的语法分析吗？ 适用。因为文法中不存

5、在左公因子，也不存在左递归,S-aS S-aSAS| A-+|*,代入,A A | 改写为 A A A A | ,4.4.3 S-SS+|SS*|a FIRST(S)=a 因为S是起始符号，把$加入到Follow(S)中。 对于S-SS+的第一个S，把First(S+) = a加入到Follow(S)中。 对于S-SS*的第一个S，把First(S*) = a加入到Follow(S)中。 对于S-SS+的第二个S，把First(+) = +加入到Follow(S)中。 对于S-SS*的第二个S，把First(*) = *加入到Follow(S)中。 所以，FOLLOW(S)=a,+,*,$ 仅

6、消除左递归后的文法： FIRST(S)=a ，FIRST(S)=a, FOLLOW(S)=FOLLOW(S)=+,*,$,题目中并没有要求我们消除左递归，所以第一个答案才是符合要求的。,下页还有内容。,S-aS S-aSAS| A-+|*,4.3.2 1)中，我们先提取左公因子， 然后消除左递归后，并代入，得到如下的文法，详见前两页的ppt。,First(S) = First(aS)=a First(S)= First(aSAS) First()= a = a, First(A) = +,* Follow(S) =$ 因为 S-aS，所以把Follow(S)加入到Follow(S)中。 因为

7、S-aSAS的第一个S ，所以把First(AS)=+,*加入到Follow(S)中。 因为 S-aSAS的第二个S ，所以Follow(S)加入到Follow(S)中。 所以，Follow(S)= $, +,* 对 S-aSAS的A ，当A后面的S推导出非空时，把First(S)-=a加入到Follow(A)中。 对 S-aSAS的A ，当A后面的S推导出空时，把Follow(S)=$,+,*加入到Follow(A)中。 所以，Follow(A)= a, +,*,$ 对于S-aSAS|，因为First(aSAS) Follow(S)=a $,+,*=空集,所以没有冲突。 对于A-+|*，因为

8、First(+) First(*)=+ *=空集,所以没有冲突。 所以该文法是LL(1)文法。,A A | 改写为 A A A A | ,此时， =(S)S = ,4.4.1 3) S-S(S)S| 消除左递归：S- S S-(S)SS| 即 S- S S-(S)SS| ,First(S)= (, First(S) = First(S)= (, 因为S是起始符号，所以把$加入到Follow(S)中。 由S-(S)SS的第一个S，将)加入到Follow(S)中。 由S-(S)SS的第二个S，将First(S)- 加入到Follow(S) 将Follow(S)加入到Follow(S) 由S-S，将

9、Follow(S)加入到Follow(S)中。 所以，Follow(S)=Follow(S)= (, ),$ 但是，First( (S)SS) Follow(S) = ( ,所以不是LL(1)文法。,预测分析表,冲突,Follow(S)=Follow(S)= (, ),$ ,First( (S)SS) = （ ,S- S S-(S)SS| ,仔细分析后，发现该文法 S-S(S)S| 是二义性文法。 二义性文法不可能是LL(1)文法。 例如：( ) ( ),S,S,(,S,),S,S,S,(,S,),S,S,(,S,),S,S,(,S,),S,对于改造后的文法 S- S S-(S)SS| 也可以画出两棵句法分析树。,“句柄”是和某个产生式 体匹配的子串，对它的 归约代表了相应的最右 推导的一个反向步骤。,4.5.2 2）对文法 和