《编译原理》复习题

语义处理部分：

1．文法符号的属性有两种，一种称为 继承属性 ，另一种称为 综合属性 。

2．编译过程中，常见的中间语言形式有 逆波兰表示法 、 抽象语法树 、 三元式 、 四元式 。 3．语法制导翻译的方法就是为每个产生式配上一个 翻译子程序（语义动作或语义子程序） ，并在语法分析的同时执行它们。

4．编译过程中，常见的中间语言形式有 逆波兰表示法 、 抽象语法树 、 三元式 、 四元式 。 5．词法分析器的输入是 源程序字符串 ，输出结构是 二元式（单词种别， 单词自身的值） 。 6．文法符号的属性有两种，一种称为 继承属性 ，另一种称为 综合属性 。 7．四元式之间的联系是通过 临时变量 实现的。 8．在属性文法中，终结符只有____综合 属性。

9．编译过程中，常见的中间语言形式 有 逆波兰式 、 抽象语法树 、 三元式 、 四元式 。 10．语法制导翻译的方法就是为每个产生式配上一个 翻译子程序（语义动作或语义子程序） ，并在语法分析的同时执行它们。

11．目前较常见的语言语义的描述形式是__属性文法______，并使用__语法制导翻译 方法完成对语法成分的翻译。 三、判断题

1．设r和s分别为正规式，则有L(r|s) = L(r) | L(s).。( × ) 2．一个文法的所有句型的集合形成该文法所能接受的语言。( × ) 3．语法分析之所以采用上下文无关文法是因为它的描述能力最强。( × )

4．由于LR(0)分析表构造简单，所以它的描述能力强，适用面宽；LR(1)分析表因构造复杂而描述能力弱，适用面窄。( × )

5．逆波兰表示法表示表达式时无需使用括号。( √ ) 6．自动机M和M’的状态个数不同，则二者必不等价。( × ) 7．LL(1)文法一定不含左递归和二义性。( √ )

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

9．无论是三元式表示还是间接三元式表示的中间代码，其三元式在三元式表中的位置一旦确定就很难改变。( √ )

13

《编译原理》复习题

10．三地址语句类似于汇编语言代码，可以看成中间代码的一种抽象形式。( √ ) 11．最左推导也被称为规范推导。（× ）

12．运算对象排列的先后顺序在后缀式和中缀式中不同。（ × ） 13．出现在移进-归约分析器栈中的内容被称为文法G的活前缀。（ √ ） 14．LR方法可以分析含有左递归的文法。（ √ ）

15．三元式的编号具有双重含义，既代表此三元式，又代表三元式存放的结果。（ √ ） 16．语义规则中的属性有两种：综合属性与继承属性。（ √ ）

17．移进-归约分析器的格局中栈的内容一般是文法符号与状态。（ √ ）

18．由于递归下降子程序方法较LL（1）方法简单，因此它要求文法不必是LL（1）文法。（ ×19．四元式的编号具有双重含义，既代表此四元式，又代表四元式存放的结果。（ × ） 20．用高级语言编写的源程序必须经过编译，产生目标程序后才能运行。（ × ） 21．源程序到目标程序的变换是等价变换，即两者结构不同，但语义是一致的。（ √ ） 22．对于任何一个正规式e，都存在一个DFA A，使得L（e）=L（A）。（ √ ） 23．最小化的DFA，它的状态数最小。（ √ ） 24．NFA的确定化算法具有消除ε边的功能。（ √ ）

25．每个非终结符产生的终结符号串都是该语言的子集。（ × ） 26．一个语言的文法是不唯一的。（ √ ）

27．语法错误校正的目的是为了把错误改正过来。（ × ） 28．源程序和目标程序是等价关系。（ √ ）

29．编译程序中错误处理的任务是对检查出的错误进行修改。（ × ） 30．使用有限自动机可以实现单词的识别。（ √ ）

31．一个非确定的有限自动机NFA可以通过多条路径识别同一个符号串。（ √ ） 32．最小化的DFA所识别接受的正规集最小。（ × ） 33．一个语言（如C语言）的句子是有穷的。（ × ） 34．LL（1）方法又称为预测分析方法。（ √ ） 35．一个LL（1）文法是无二义和无回溯方法。（ √ ） 36．语法分析器可以检查出程序中的所有错误。（ × ） 37．LR分析法是自上而下的语法分析方法。（ × ） 三、多项选择题

1. 编译器的各个阶段的工作都涉及到（AE ）

A. 表格处理 B. 词法分析 C. 语法分析 D. 语义分析

14

）《编译原理》复习题

E. 出错处理

2. 令?＝{a,b}，则?上的符号串的全体可用下面的正规式表示。（ABE ）

A. (a|b)* B. (a*|b*)* C. (a|b)+ D. (ab)* E. (a*b*)*

3. 自上而下的分析方法有：（AD ）

A. 递归下降分析法 B. LR（0）分析法 C. LALR（1）分析法 D. LL（1）分析法 E. SLR（1）分析法 4. 文法G：G[S]：S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD 是（ABE ）。

A. 0型文法 B. 1型文法 C. 2型文法 D. 3型文法 E. 上下文有关文法

5. 对LR分析表的构造，有可能存在的动作冲突有：（AD ）

A. 移进/归约冲突 B. 移进/移进冲突 C. 归约冲突 D. 归约/归约冲突 E. 移进冲突

6. 一个编译器可能有的阶段为（ABCDE ）

A. 词法分析 B. 语法分析 C. 语义分析 D. 中间代码生成 E. 目标代码生成

7 令?＝{a,b}，则?上的所有以b开头，后跟若干个（可为0个）ab的符号串的全体可用下面的正规式表示。（AB ）

A.b (ab)* B. (ba)*b C. b(a|b)+ D. (ba)+b E. b (a|b)*

8. 自下而上的分析方法有：（BCE ）

A. 递归下降分析法 B. LR（0）分析法 C. LALR（1）分析法 D. LL（1）分析法 E. SLR（1）分析法

9. 一般来说，编译器可分为前端和后端，下列编译阶段可被划分为编译的前端的有：（ABCDE ）

A. 词法分析 B. 语法分析

C. 语义分析 D. 中间代码生成 E. 中间代码优化

10．令?＝{a,b}，则?上的符号串的全体可用下面的正规式表示。（ABE ）

A. (a|b)* B. (a*|b*)*

C. (a|b)+ D. (ab)* E. (a*b*)*

11．下列符号串是符号集?＝{a,b}上的正规式的有：（ ABCDE）

A. ε B. a C. ab D. (ab｜a) (ab｜a) E. ab｜ab

12．正规式服从的代数规律有：（ABDE ）

15

《编译原理》复习题

A. “或”运算服从交换律 B. “或”运算服从结合律 C. “连接”运算服从交换律 D. “连接”运算服从结合律 E. “连接”运算可对“或”运算进行分配

13． 令?＝{a,b}，则?上的所有以b开头，后跟若干个（可为0个）ab的符号串的全体可用下面的正规式表示。（AB ）

A.b (ab)* B. (ba)*b C. b(a|b)+ D. (ba)+b E. b (a|b)* 14． 一个LR分析器包括：（ADE ）

A. 一个总控程序 B. 一个项目集 C. 一个活前缀 D. 一个分析栈 E. 一张分析表

15． LR分析器的核心部分是一张分析表，该表包括（DE ）等子表。

A. LL（1）分析表 B. LR（1）分析表 C. SLR（1）分析表 D. Action表 E. goto表

16． Action表中的每一项Action[S,a]所表示的动作可能为：（ABCD ）

A. 移进 B. 接受 C. 归约 D. 出错 E. 待约 五．简答题

1．构造正规表达式a(aa)*bb(bb)*a(aa)* 的NFA。 解：

256aabbaaXa1b3b4aY

2．构造正规表达式((a|b)*|aa)*b的NFA。 解：

3aaX?1?2bY??a4b

2．令文法G[N]为 G[N]: N→D|ND

D→0|1|2|3|4|5|6|7|8|9

给出句子568的最左、最右推导。

解：最左推导：N ? ND ? NDD ? DDD ? 5DD ? 56D ? 568

最右推导：N ? ND ? N8 ? ND8? N68 ? D68 ? 568

16