编译原理习题答案

1、正规文法又称 D A、0型文法 B、1型文法 C、2型文法 D、3型文法 2、对于无二义性的文法，规范归约是 B A. 最左推导 B. 最右推导的逆过程 C.最左归约的逆过程 D.最右归约的逆过程。

3、扫描器的任务是从 源程序 中识别出一个个 单词符号 。

4、程序所需的数据空间在程序运行前就可确定，称为 A 管理技术。

A 静态存储 B 动态存储 C 栈式存储 D 堆式存储 5、编译过程中，语法分析器的任务是（ B）。

①分析单词是怎样构成的

②分析单词串是如何构成语句和说明的 ③分析语句和说明是如何构成程序的 ④分析程序的结构

A、②③ B、②③④ C、①②③ D、①②③④

6、文法G：E→E+T|T T→T*P|P P→ (E)| i

则句型P+T+i的句柄和最左素短语分别为 B 。

A、P+T和i B、P和P+T C、i和P+T+i D、P和P 7、四元式之间的联系是通过 B 实现的

A.指示器 B.临时变量 C.符号表 D.程序变量

8、程序语言的单词符号一般可以分为保留字、标识符、常数、运算符、界符 等等。

9、下列 B 优化方法是针对循环优化进行的。

A．删除多余运算 B．删除归纳变量 C．合并已知量 D．复写传播 10、若文法 G 定义的语言是无限集，则文法必然是 A A、递归的 B、前后文无关的 C、二义性的 D、无二义性的

11、文法 G 产生的 D 的全体是该文法描述的语言。

A、句型 B、终结符集 C、非终结符集 D、句子

12、Chomsky 定义的四种形式语言文法中， 0 型文法又称为 A 文法； 1 型文法又称为 C 文法。

A.短语文法 B.上下文无关文法 C.上下文有关文法 D.正规文法 A.短语文法 B.上下文无关文法 C.上下文有关文法 D.正规文法 13、语法分析最常用的两类方法是 自顶向下 和 自底向上 分析法。

14、一个确定的有穷自动机DFA是一个 A 。

A 五元组（K，∑，f, S, Z） B 四元组（VN，VT，P，S）

C 四元组（K，∑，f，S） D 三元组(VN,VT,P) A、语法

B、语义

C、代码

D、运行

15、 B 不属于乔姆斯基观点分类的文法。

A、上下文无关文法 B、算符优先文法 C、上下文有关文法 D、正规文法 16、一个文法所描述的语言是 A ；描述一个语言的文法是 B 。

A.唯一的 B.不唯一的 C.可能唯一,可能不唯一 A.唯一的 B.不唯一的 C.可能唯一,可能不唯一 17、语法分析是依据语言的 语法 规则进行的，中间代码产生是依据语言的 等价变换 规则进行的。

18、 B 不属于乔姆斯基观点分类的文法。

A上下文无关文法 B算符优先文法 C上下文有关文法 D正规文法 19、过程调用时参数传递方式有 A

(1)传地址 (2)传值 (3)传标识符 (4)得结果 (5)传名 (6) 返回值 可选项有：

A、(1)(2)(4)(5) B、(1)(2)(5)(6) C、(1)(2)(3) (6) D、(2)(3)(4)(6) 20、过程调用时参数传递方式有 (1)传地址 (2)传值 (3)传标识符 (4)得结果 (5)传名 (6) 返回值 可选项有：

A、(1)(2)(4)(5) B、(1)(2)(5)(6) C、(1)(2)(3) (6) D、(2)(3)(4)(6)

21、下列代码中 D 不可能是目标代码。

A、汇编指令代码 B、可重定位指令代码 C、绝对指令代码 D、中间代码 22、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。 BB 。A.正确 B.不正确

23、有限自动机能识别 C A．上下文无关文法 B．上下文有关文法 C．正规文法 D．短语文法。

24、汇编程序是将 B 程序改造成目标语言程序的翻译程序。

A机器语言 B汇编语言 C高级语言 D低级语言 25、LR(k)文法___B____二义性的。

A、都是

26、乔姆斯基方法的2型语言是这样一种语言，其产生式限制为 A 27、局部优化是局限于一个 C 范围内的一种优化。

A.循环 B.函数 C.基本块 D.整个程序

28、目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 A 。

A.正确 B.不正确

A、A→? B、A→a，A→aB C、? → β(| ? | ? | ? |) D、? → ?

B、都不是

C、不一定都是

29、乔姆斯基方法的3型语言是这样一种语言，其产生式限制为 B

A A→? B A→a或A→aB C ?→β(| ? | ? | ? |) D ? →? 30、运算符与运算对象类型不符属于 A 。

A、语法错误 B、语义错误 C、语用错误 D、规则集合

31、词法分析器的输入是 B 。

A、词法记号 B、源程序 C、语法单位 D、目标程序

32、在下述的编译方法中，自底向上的方法有 F ，自顶向下的分析方法有 A 。

①简单优先分析 ②算符优先分析 ③递归下降分析 ④预测分析技术 ⑤LR（K）分析 ⑥ SLR（k）分析 ⑦ LL（k）分析 ⑧LALR（K）分析

A.③④⑦ B. ③④⑧ C.①②⑧ D.③④⑤⑥⑦ E.①②⑤⑥⑦ F. ①②⑤⑥⑧ A.③④⑦ B. ③④⑧ C.①②⑧ D.③④⑤⑥⑦ E.①②⑤⑥⑦ F. ①②⑤⑥⑧ 33、对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。 B 。 A.正确 B.不正确

34、算符优先分析法每次都是对 C 进行归约。

A 句柄 B短语 C最左素短语 D素短语 35、编译时能进行的类型检查称为 C 。

A、错误检查 B、动态检查 C、静态检查 D、随机检查

36、规范推导的每一步总是用产生式右边符号串替换句型中 B 位置的非终结符号 A、最左 B、最右 C、最中 D、任意

37、语法分析器的输入是 单词符号流 ，其输出是 分析树的某种表示 38、每个文法都能改写为LL(1)文法。 B A.正确 B.不正确

39、对于无二义性的文法，规范推导是 C A 最左推导 B 最右推导的逆过程 C 最左归约的逆过程 D 最右归约的逆过程。 40、描述语言 L= { ambn | n≥m≥1 } 的文法为 D 。

A、Z→Abb C、Z→Ab D、Z→aAb

41、间接三元式表示法的优点为 A

A、采用间接码表，便于优化处理 B、节省存储空间，不便于表的修改

C、便于优化处理，节省存储空间 D、节省存储空间，不便于优化处理

A→aA | a

A→aAb | a A→Ab | aAb | ε

B→bB | b

B、Z→AB | b A→Aa | a

B→aBb | b

42、编译时能进行的类型检查称为 C

A错误检查 B动态检查 C静态检查 D随机检查 43、文法 G[S]：S→ xSx | y所识别的语言是 A 。 A、xnyxn(n≥0) B、(xyx)* C、xyx D、x*yx*

44、项目A→α·称为 B ，其中A∈VN，A不是开始符。

A、移进项目 B、归约项目 C、出错项目 D、接受项目

45、设有文法G[S]: S-> S*S | S+S | (S) | a, 该文法___A__二义性文法。

A、 是

46、高级语言编译程序常用的语法分析方法中，LL分析法属于 B 分析方法。

A、自左至右 B、自顶向下 C、自底向上 D、自右至左。

47、有文法G：E→E*T|T T→T＋i|i 句子2＋5*3＋3按该文法G归约，其值为 B

A 23 B 42 C 30 D 17

48、高级语言编译程序常用的语法分析方法中，LL分析法属于 B 分析方法。

A 自左至右 B 自顶向下 C 自底向上 D自右至左。 49、形如A→α·Bβ的项目为 A 项目。

A、待约 B、移进 C、接受 D、规约

50、活动记录的连接数据不包括 A 。

A、形参单元 B、动态链（老SP） C、返回地址 D、全局Display地址 51、高级语言编译程序常用的语法分析方法中，lALR分析法属于 C 分析方法。

A、 自左至右 B、 自上而下 C、 自下而上 D、自右至左

52、设a、b、c是文法的终结符，且满足优先关系a=?b和b=?c，则 D 。

A.必有a=?c B.必有c=?a C 必有b=?a D 答案A~C都不一定成立 53、词法分析器的输出是 A 。

A、词法记号流 B、源程序 C、语法单位 D、目标程序

54、对一个基本块来说， A 是正确的。

A、只有一个入口语句和一个出口语句 B、有一个入口语句和多个出口语句 C、有多个入口语句和一个出口语句 D、有多个入口语句和多个出口语句

55、词法分析所依据的是 B 。

A 语义规则 B 构词规则 C 语法规则 D 等价变换规则 56、句型是由 D 推导出的符号串。

A、非终结符 B、终结符 C、任何符号 D、开始符号

B、不是

C、不一定

57、如果文法G是无二义的，则它的任何句子α A 。 A、最左推导和最右推导对应的语法树必定相同 B、最左推导和最右推导对应的语法树可能不同 C、最左推导和最右推导必定相同

D、可能存在两个不同的最左推导，但它们对应的语法树相同 58、算符优先文法与算符优先函数的关系的描述中正确的是（B）。

A、一个算符优先文法一定存在优先函数与之对应 B、一个算符优先文法可能存在多个优先函数与之对应 C、一个算符优先文法一定存在多个优先函数与之对应 D、一个算符优先文法一定存在有限对优先函数与之对应

59、一个句型中称为句柄的是该句型的最左 D 。 A 非终结符 B 短语 C 句子 D 直接短语 60、描述一个语言的文法是（B ）

A、唯一的 B、不唯一的 C、可能唯一，也可能不唯一

61、下列 C 优化方法不是针对循环优化进行的。

A、强度削弱 B、删除归纳变量 C、删除多余运算 D、代码外提

62、更动一张 A 表很困难。

A 三元式 B 间接三元式 C 四元式 D 三元式和四元式 63、栈式存储分配申请和释放存储空间遵守 BC 原则。

A、先申请先释放 B、先申请后释放 C、后申请先释放 D、任意

64、所谓自上而下分析法是指 。 65、所谓语法制导翻译方法是 。

66、确定的有穷自动机是一个 五元组 ，通常表示为 M=(S , ∑,f,s0,Z ) 。

67、规范归约中的可归约串是指 句柄 ；算符优先分析中的可归约串是指最最左左素素短短语语 。

68、编译程序在逻辑上由 词法分析 、 语语法法分分析析 、语义分析、中间代码生成、代码优化和目标代码生成六部分组成。 69、 D 不可能是目标程序。

A、汇编语言模块 B、可重定位目标模块 C、可执行目标模块 D、中间代码 70、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是 二义的 。

71、一个名字的属性包括 继承属性 和 综合属性 。 72、正规式的“*”读作 星闭包 。

73、编译程序在逻辑上由 、 、语义分析、中间代码生成、代码优化和目标代码生成六部分组成。

74、编译程序的各个阶段的工作都涉及到 符号表管理 和 错误处理 75、文法用来描述语言的语法结构，它由如下4个部分组成：文法终结符集合、文法非终结符集合、 D 和文法开始符号。

A、单词集合 B、字母数字串

C、文法句子集合 D、文法产生式的集合

76、确定的有穷自动机是一个 元组，通常表示为 。 77、已知文法G[E]：

E→E + T | T T→T * F | F F→（E）| id

该文法终结符集合VT= ， 文法非终结符集合VN= ，该文法在乔姆斯基（Chomsky）文法分类属于 2 文法。

78、编译程序的各个阶段的工作都涉及到 和 。 79、假设G是一个文法，S是文法开始符号，如果S?*>x，则称x是该文法的一 。

80、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是 。 81、优化时，节省一条指令MOV Ri，M，节省的指令代价为 C

A、0 B、1 C、2 D、3

82、采用 LL(1) 语法分析时，必须消除文法的左递归。

83、在状态转换图中，结点代表 状态 ，用圆圈表示。

84、若源程序是高级语言编写的，目标程序是 机器语言或汇编 语言的程序，则相应的翻译程序称为编译程序。

85、常用的两种动态存贮分配办法是 栈式 分配和 堆式 分配。

86、翻译方案和语法制导定义不同的是它的 语义动作 （而不叫语义规则）放在括号{ }内，并且可以插在产生式 右部 的任何地方

87、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是 。

88、所谓最左推导是指： 。

89、上下文无关文法的可以用 四元组 表示，其形式为 G=(VN,VT,S,P) 。

90、后缀式 ab+c+d*e- 所表达的式子为 （a+b+c）*d-e 。

91、常用的两种动态存贮分配办法是 分配和 分配。

92、LL(K)文法中，第一个L表示 从左到右扫描输入串 ，第二个L表示 产生最左推导 ，K表示 在决定语法分析器每步动作时向前看K

个输入符 。

93、一个上下文无关文法所含四个组成部分是 文法终结符集合 文法非终结符集合 开始符号 产生式有限集合 。

94、对于文法G，仅含终结符号的句型称为 句子 。 95、设有文法G[E]： E→E + T | E – T | T T→T * F | T/F | F F→（E）| i

该文法句型E + T * F 的句柄是 T * F 。

96、后缀式 ab+c+d*e- 所表达的式子为 。

97、文法符号的属性有两种，一种称为 继承 属性，另一种称为 综合 属性，S属性定义是指仅使用 综合 属性的语法制导定义。

98、LR(0)项目和LR(1)项目的区别在于 是否有搜索符 。

99、紧跟在条件转移语句后面的语句是基本块的 入口 语句。

100、若二个正规式所表示的 DFA（或正规集） 相同，则认为二者是等价的。

101、仅含终结符的句型称为 。

( F )

103、规范归约和规范推导是互逆的两个过程。 ( T )

104、一个上下文无关文法的开始符号可以是终结符或非终结符。 ( F )

102、编译方式与解析程序的根本区别在于是否生成目标代码。

105、逆波兰表示法表示表达式时无需使用括号。 ( T )

106、符号表由词法分析程序建立，由语法分析程序使用。 ( F )

107、逆波兰法表示的表达式亦称前缀式。 ( F )

108、代码生成器的输入包括中间代码和符号表中的信息。 ( T )

109、孤立地考虑一个基本块常常不能确定一个赋值是否真是无用的。 ( T )

110、目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( T )

111、无左递归的文法是LL(1)文法。 ( F )

112、一个句型的直接短语语是唯一的。 ( F )

113、正规文法产生的语言都可以用上下文无关文法来描述。 (F )

114、对任何一个编译程序来说，产生中间代码是不可缺少的一部分。 ( F )

115、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。( F )

116、一个上下文无关文法的开始符号可以是终结符或非终结符。 ( F )

117、一个文法所有句子的集合构成该文法定义的语言。 ( T )

118、优化实质上是对代码进行等价变换，变换后的代码结构不同但运行结果相同。 ( T )

119、算符优先分析法是一种规范归约分析法。 ( F )

120、非终结符可以有综合属性，但不能有继承属性。 ( F )

121、所有LR分析器的总控程序都是一样的，只是分析表各有不同。 ( T )

122、因名字都是用标识符表示的，故名字与标识符没有区别 (F )

123、空符号串的集合{ε}={}=?。 ( F )

124、非终结符可以有综合属性，但不能有继承属性。 ( F )

125、终结符可以有综合属性，也可以有继承属性。 ( F )

126、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。( )

127、若一个句型中出现了某一产生式的右部，则此右部一定是该句型的句柄。 ( F )

129、DAG是一个可带环路的有向图。 ( F )

130、设有符号串x和y，把y的符号写在x的符号之后所得的符号串，叫做x与y的连接，记为xy。 ( T ) 131、对任何一个编译程序来说，产生中间代码是不可缺少的一部分。 ( F ) 132、对任何正规表达式e，都存在一个DFA M，满足L(M)＝L(e)。 ( T)

133、 运行时的DISPLAY表的内容是什么？它的作用是什么？

答：内容：1、过程R的现行活动记录的地址（sp的现值）2、R的外层Q的最新活动记录的地址3、Q的外层即主程序P的活动记录的地址 作用：跟踪每个外层的最新活动记录的位置

134、何谓局部优化、循环优化和全局优化？优化工作在编译的哪个阶段进行？

答：局部优化：在基本快内的优化。循环优化：对循环中的代码进行优化。全局优化：整个程序范围内的优化。 在 中间代码优化阶段。

135、常见的存储分配策略有几种？它们都适合于什么性质的语言？

答：1、静态分配策略 适用于无动态申请内存、无可变体积数组、无递归调用的程序语言（ 如 Fortran） 2、动态分配策略 2.1栈式动态分配 2.1.1简单栈式分配 适用于没有分程序结构、不允许程序嵌套定义但允许过程递归调用、允许过程含可变数组的语言 2.1.2嵌套过程语言的栈式分配 适用于没有分程序结构、允许程序嵌套定义和过程递归调用、允许过程含可变数组的语言 2.2堆式动态分配 适用于允许程序为变量在运行时动态申请和释放存储空间的语言

136、下面文法是否是二义文法？试说明理由。 G[S]： S → SaS | ? 答：二义

137、已知文法G(E) E→T|E＋T T→F|T * F F→(E)|i

(1) 给出句型(T * F＋i)的最右推导及画出语法树； (2) 给出句型(T * F＋i)的短语、素短语。 1）E→E＋T→E+i→T+i→T*F+I 树略 2）短语：T*F+i T*F i 素短语：T*F i

138、把算术表达式－(a+b)*(b+c)翻译成：

(a) 后缀表示 ab+bc+*@ (b) 语法树 图略 (c) 有向无环图 图略 (d) 四元式三地址代码 四地址代码： （+, a ，b，t1） （+，b，c，t2） （*，t1，t2，t3） （@，t3，-，t4）

139、DFA与NFA的区别？

答：1、DFA弧上不允许有ε出现，NFA允许 2、DFA中每个状态S和输入符号a最多有一条边离开S，NFA有多条 3、NFA可以有多个初态，DFA只有一个

140、设已构造出文法G(S)： S?S(S) S??

的LR分析表如下

状态 0 1 2 3 4 5 6 7 ACTION ( r2 S2 r2 S4 r2 r1 S4 r1 ) r2 S5 r2 S7 r1 # r2 Acc r1 GOTO S 1 3 6 假定输入串为( )( )，请给出LR分析过程(即状态，符号，输入串的变化过程)。

步骤 状态 符号 输入串 步骤 1 2 3 4 5 6 7 8 9 10

141、对符号表的基本操作有几种，分别是什么？

答：5类。1、填写名称2、查找名字3、访问信息4、填写修改信息5、删除 （或者：4类。建立、插入、查找、删除）

142、给定代码段如下，求出按四种不同方式进行参数传递后，变量a的值 …

procedure P(w,x,y,z); begin

y := y*w; z := z+x; end begin

a := 5; b := 3; P(a+b,a-b,a,a); write(a); end

状态 0 01 012 0123 01235 01 012 0123 01235 01 符号 S S( S( S() S S( S(S S(S) S 输入串 （）（）$ （）（）$ ）（）$ )（）$ （）$ （）$ ）$ ）$ $ $

传值: 5 传地址: 42 得结果: 7 传名: 77

143、目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？

答：1、汇编语言2、机器语言 又可分为a可立即执行的机器语言b可重定位的机器语言 需要考虑：1.、如何使生成的目标代码最短2、如何分配寄存器的使用

144、下面的推导S ?rm … ? rm ? A b w ? rm ? l ? b w中，最后一步用的是A? l?，分别指出LL（1）方法和LR（1）方法在扫描到此句型的什么位置决定用此产生式？(5分) P79 答： LL(1)扫描到l的时候决定用此产生式；LR(1)扫描到b的时候决定使用次产生式

145、构造一个最简DFA，它接受正规式ab (a|b)*。

给出文法G[S]：S→SaA|A A→AbB|B B→cSd|e

(1)证实AacAbcBaAdbed是文法G[S]的一个句型； (2)请写出该句型的所有短语、素短语以及句柄。

答：1）这里用最右推导表示，省略树S→SaA→SaB→SacSd→SacAd→SacAbBd→SacAbed→SacAbBbed→SacAbcSdbed →SacAbcSaAdbed→SacAbcAaAdbed→SacAbcBaAdbed →AacAbcBaAdbed 2）短语：AacAbcBaAdbed cAbcBaAdbed AbcBaAdbe AbcBaAd cBaAd BaA e A 素短语：BaA e 句柄：A

146、写出表达式a+b*(c-d)对应的逆波兰表示、三元式三地址代码序列和抽象语法树。

147、什么是活动记录？它主要由哪些内容构成？ 148、对下列四元式序列生成目标代码 (10分) T=A-B S=C+D W=E-F U=W/T V=U*S

其中，V是基本块出口的活跃变量，R0和R1是可用寄存器。 答 MOV R0 ，A SUB R0 ，B MOV R1 ，A ADD R1 ，D MOV S ，R1 MOv R1 ，E SUB R1 ，F DIV R1 ，R0 MUL R1 ，S

149、设有如下的三地址码(四元式)序列：

Read N I∶=N J∶=2

———————— L1：if I≤J goto L3 ———————— L2：I∶=I-J

if I>J goto L2

————————

if I=0 goto L4

————————

J∶=J+1 I∶=N goto L1

———————— L3：Print ′YES′

Return

————————

L4：Print ′NO′

Return （1）、对题中代码划分基本块，并给每个基本块一个序号 （2）、画出基本块集合的控制流图，每个基本块就用（1）小题中的序号表示。 （3）、若有循环的话，列出构成每个循环的结点。 150、已知文法G(V)： V →N | N [E]

E →V | V+E

N→i (1)给出与G(V)等价的LL(1)文法G'(V)；

V →NV’ V’ →[E]| ε E →VE’ E’ →+E|ε N→i (2)求文法G'(V)的每个非终结符的FIRST集合和FOLLOW集合； First(V)={i} First(V’)={[ , ε}

First(E)={i} First(E’)={ + , ε} First(N)={i}

Follow(V)={$,+,]} Follow(V’)={$,+,]} Follow(E)={]} Follow(E’)={]} Follow(N)={[ , $ , + }

(3)构造文法G'(V)的LL(1)分析表。 V V’ + V’ →ε [ V’ →[E] ] V’ →ε i V →NV’ $ V’ →ε E E’ N

E’ →+E E’ →ε E →VE’ N→i

151、考虑下面的三地址语句序列： b := 1 b := 2 if w <= x goto L2 ———————— e := b goto L2 ———————— L1: goto L3 ———————— L2: c := 3 b := 4 c := 6

———————— L3: if y <= z goto L4 ———————— goto L5 ———————— L4: g := g + 1 h := 8 goto L1 ———————— L5: h := 9

（1）、在该代码中用水平的横线将代码分成基本块，并给每个基本块一个序号。 （2）、画出该代码的控制流图，每个基本块就用（1）小题中的序号表示。 （3）、若有循环的话，列出构成每个循环的结点。

152、对于文法G(S)：

S ?bMbM ?(L|a L ?Ma)(1) 写出句型b(Ma)b的最右推导并画出分析树。 S→bMb→b(Lb→b(Ma)b

(2) 写出上述句型的短语，直接短语和句柄。 短语：b(Ma)b (Ma) Ma) 句柄：Ma) 153、LL(1)分析法对文法有哪些要求？

对文法中任意A→α|β型产生式需满足： First(α)∩First(β)=空集

若β=>ε 则First(α)∩Follow(A)=空集

154、写出语句a:=b*(-c)+b*(-c)的后缀式、抽象语法树、DAG图、四元式三地址代码和三元式三地址代码。

155、设有文法G[A]： A → iB*e B → SB | ε S → [eC] | . i C → eC | ε

判定该文法是否为LL(1)文法？若是则给出它的LL(1)分析表，否则说明理由。 (20分) First(A)={i} First(B)={[ , ε , . } First(S)={ [ , . } First(C)={e, ε}

Follow(A)={$} Follow(B)={*} Follow(S)={*} Follow(C)={]} 对产生式B → SB | ε

First(SB)=First(S)= { [ , . } First(ε)={ ε} 所以First(SB)∩First(ε)=空集 First(SB)∩Follow(B)=空集 对产生式S → [eC] | . i

First([eC])= { [} First(. i)={ . i } 所以First([eC])∩First(. i)=空集 对产生式C → eC | ε

First(eC) { e } First(ε)={ ε} 所以First(eC)∩First(ε)=空集 First(eC)∩Follow(C)=空集 所以此文法是LL(1)文法 A B S C . S →. i * i [ ] e C → eC $ A→ iB*e B → SB B → ε B → SB S→ [eC] C →| ε

156、构造一个DFA，它接受∑={0，1}上能被5整除的二进制数。

157、正规式 (0 | 1)* 和 ( (? | 0) 1* )*是否等价，说明理由。

158、写出字母表? = {a, b}上语言L = {w | w的最后两个字母是aa或bb}的正规式，并画出接受该语言的最简DFA。 (a|b)*aa|bb 159、文法G(S)及其LR分析表如下，请给出串baba$的分析过程。

(1) S → DbB (4) B → a

(2) D → d

(3) D → ε (6) B → ε

(5) B → Bba

LR分析表

0 1 2 3 4 5 6 7 8 ACTION b r3 s4 r2 r6 r4 s7 r5 d s3 a S5 S8 $ acc r6 r4 r1 r5 GOTO S 1 B 6 D 2

(注：答案格式为 步骤 栈 步骤 1 2 3 4 5 6 7 8 9 栈 0 0D2 0D2b4 0D2b4a5 0D2b4B6 0D2b4B6b7 0D2b4B6b7a8 0D2b4B6 0S1 输入串 动作) 输入串 动作) 按B → ε规约 移进 移进 按B → a规约 移进 移进 按B → Bba规约 按S → DbB规约 接受 baba$ baba$ aba$ ba$ ba$ a$ $ $ $

160、已知文法G(A)： A → aABl | a

B → Bb | d

(1)消除文法中的左递归，提取公共左因子，给出与G(A)等价的LL(1)文法G'(A)； (2)求文法G'(A)的每个非终结符的FIRST集合和FOLLOW集合； (3)构造文法G'(A)的LL(1)分析表。

答：1）A →aA’ A’→ABl|ε B → dB’ B’ →bB’ |ε

2) First(A)={a} First(B)={d} First(A’)={a, ε} First(B’)={b, ε} Follow(A)={$,d} Follow(B)={l} Follow(A’)={$,d} Follow(B’)={l} 3) a b l d $ A A →aA’ A’→ABl A’→ε A’→ε A’ B B’ →bB’ B’ →ε B’ 161、设文法G(S)：

S→S+aF | aF | +aF F→*aF | *a

本文来源：https://www.bwwdw.com/article/ws6t.html