编译原理 龙书答案(5)

编译原理 龙书答案

正规式：1*(0 | 01)*

e) 具有形式xy的二进制串，x≠y S→ A | B | A B | B A A→ D A D | 0 B→ D B D | 1 D→ 0 | 1

A、B分别表示中心符号为0、1的长度为奇数的二进制串

将AB串接，长度为偶数，将它从中间分为长度相等的两部分，x、y

虽然A、B长度可能不一样，但容易得到，A的中心0在x中的位置，与B的中心1在y中的位置是相同的，因此x≠y BA的情况类似

f) 形如xx的0、1串

解：此语言无法用上下文无关文法描述

（Aho）4.11 对习题4.1中文法 a) 消除左递归 S→( L ) | a L→S L’ L’→, S L’ |

b) 构造预测分析表，对4.1(b)中句子，给出预测分析器的运行过程 FIRST(S) = { (, a ) FIRST(L) = { (, a } FIRST(L’) = { ‘,’, } FOLLOW(S) = {‘,’, ), $} FOLLOW(L) = { ) } FOLLOW(L’) = { ) } 预测分析表：

编译原理 龙书答案

其他两个句子的分析过程类似

（Aho）4.13 下面文法产生除

外所有长度为偶数的a的串

S → a S a | a a

a）试为该文法构造一个带回溯的递归下降语法分析器，对S的两个候选式首先考虑aSa。证明：S所对应的过程可以成功分析2、4、8个a的串，但6个a的串不行。

解：aa的分析过程，其中√表示匹配成功，×表示匹配失败，匹配失败则尝试下个候选式

aaaa分析过程：

aaaaaa分析过程：

aaaaaaaa分析过程：

编译原理 龙书答案

b）此语法分析器能识别什么样的语言？

解：由a）的解可以看出，2N个a的串分析过程中，步骤如下

1） 产生2N+1个S的语法树，对第2N+1个S进行扩展时输入缓冲已空，失败 2） 对第2N个S尝试候选式aa，第二个a匹配失败

3） 对第2N-1个S尝试候选式aa，左边N-1个a匹配，右边最后一个a匹配，倒数第二个

a失败

4） 对第2N-2个S尝试候选式aa，左边N-2个a匹配，右边最后一个a和倒数第二个a匹

配，倒数第三个a失败

5） 对第2N-4个S尝试候选式aa，左边N-4个a匹配，右边最后一个a～倒数第四个a匹

配，倒数第五个a失败

6） 对第2N-8个S尝试候选式aa，…

最后正确识别的情况必然是：对第N个S尝试aa，左边N个a和右边N个a恰与输入匹配 显然，可以正确识别的符号串的N满足 2N – 1 – 1 – 2 – 4 - … = N N=2i

（Aho）4.25 试给出图4－60中的优先关系表对应的优先级函数 解：有向图如下

优先级函数为

（Aho）4.26 对习题4.1中文法，利用讲义中给出的算法计算终结符之间的优先关系 解： S → ( L ) | a L → L, S | S 由于S → ( L )，因此 ( )

S → ( L )，而L L , S，L S ( L )，L S a 因此 ( , ，( (，( a；, )，) )，a )

由于L → L, S，而L L , S，L S ( L )，L S a，因此 , ,，) ,，a ,