编译原理试题集78677

第一章 引论

一.填空题

1. 对编译程序而言，输入数据是________________；输出数据是_____________。

2. 编译后端通常不依赖于源语言而仅仅依赖于___________________。

3. 如果不需改写编译程序中与机器无关的部分就可以把编译程序移植到另外一个目标机上 ，则称该编译程序是___________________。

4. 描述程序设计语言词法的有效工具是___________________________。

5. 编译过程的每一个阶段都能检测出错误，其中，绝大多数错误在_______________阶段检 测出来的。

6. 编译过程的每一个阶段都能检测出错误，其中，绝大多数错误在_______阶段检测出来的 。

7. 为了使编译后的Java程序从一个平台移到另外一个平台上执行，Java定义了一种称为Byt eCode的虚拟机代码。只要实际使用的操作平台上实现了执行ByteCode的Java解释器，这个

操作平台就可以执行各种Java程序。这就是所谓Java语言的________________。

8. 在一个程序设计环境中，______________起着中心作用。连接程序、调试程序、程序分 析等工具的工作直接依赖于它所产生的结果。

解答: 1. 2. 3. 4. 5. 6. 7. 8.

二.判断题

1. 在编译过程中，既可以将几个不同的阶段合为一遍，也可以把一个阶段的工作分为若干 遍。（ ）

2. 编译程序生成的目标程序都是可执行的程序。（ ）

3. 编译前端主要由与源语言和目标机相关的那些部分组成。（ ）

4. 优化的任务在于对前端编译所产生的中间代码进行加工和变换，以其能产生运行结果更

为准确的目标代码。（ ）

5. 支持程序设计人员进行程序计开发的工具，除了编译程序以外，还需要编辑程序、链接 程序和调试程序等其他一些工具。（ ）

6. 汇编器将高级语言程序翻译成汇编语言程序。（ ）

7. 许多编译程序在识别出语法单位后并不真正构造语法树。（ ）

8. 取编译程序前端改写其后端以生成不同机器上的目标代码，目前技术上还难以实现。（ ） 解答: 1. √ 2. × 3. × 4. ×

5. √ 6. × 7. 8.

三.单项选择题

1. 如果一个编译程序能产生不同于其宿主机的机器代码，则称它为：___________________ 。 a. 诊断编译程序b. 优化编译程序 c. 交叉编译程序 d. 可变目标编译程序

2. 编译程序将高级语言程序翻译成_________ 。 a. 机器语言程序或高级语言程序 b. 汇编语言或机器语言程序 c. 汇编语言程序或高级

语言程序 d. 中间语言程序或高级语言程序

3. 下面的四个选项中，__________不是编译程序的组成部分。 a. 词法分析程序 b. 代码生成程序 c. 设备管理程序 d. 语法分析程序

4. 现代多数实用编译程序所产生的目标代码都是一种可重定位的指令代码，在运行前必须

借助于一个_______把各个目标模块，包括系统提供的库模块连接在一起，确定程序变量或常

数在主存中的位置，装入内存中制定的起始地址，使之成为一个可运行的绝对指令代码的程 序。 a. 重定位程序； b. 解释程序；c. 连接装配程序；d. 诊断程序；

5. 从编译程序的角度说，源程序中的错误通常分为________两大类。 a. 词法错误和语法错误； b. 语法错误和语义错误； c. 编辑错误和诊断错误； d. 词法错误和语义错误；

6. 下面对编译原理的有关概念正确描述的是：____。 a. 目标语言只能是机器语言 b. 编译程序处理的对象是源语言。 c. Lex是语法分析自动生成器 d. 解释程序属于编译程序

7. 目标代码生成阶段所生成的目标代码的形式不可能是____。 a. 绝对指令代码 b. 可充定位的指令代码。 c. 汇编指令代码 d. 三地址代码

8. 语义错误是指源程序中不符合语义规则的错误，不包括：____ a. 非法字符错误 b. 类型不一致错误。 c. 作用域错误 d. 说明错误

解答: 1. 2. 3. 4. 5. 6. 7. 8.

四.名词解释

1. 诊断编译程序、优化编译程序；

2. 交叉编译程序、可变目标编译程序；

3. 编译程序的“遍”

4. 程序设计环境

解答:

1. 诊断编译程序：专门用于帮助程序开发和调试的编译程序。 优化编译程序：着重于提高目标代码效率的编译程序。

2. 交叉编译程序：能产生不同于其宿主机的机器代码的编译程序。 可变目标编译程序：不需重写编译程序中与机器无关的部分就能改变目标机的编译程 序。

3. 编译程序的“遍”：就是对源程序或者中间结果从头到尾的一次扫描，并做有关的加工 处理，生成新的中间结果或者目标程序。

4. 程序设计环境：支持程序设计人员进行程序设计开发所需要的如编辑程序、编译程序、 连接程序和调试程序等软件工具，一起构成程序设计环境。

五.简答题

1. 什么是编译程序的“遍”？

2. 什么编译程序、解释程序？编译程序和解释程序有什么区别？

3. 前端编译和后端编译是如何划分的？

4. 什么是标识符，什么是名字，它们的区别是什么？

5. 如果机器A上已有一个用A机器代码实现的某高级语言L1的编译程序，则可以用L1编写另

一种高级语言L2的编译程序，画出这个实现过程的T形图表示。

6. 如何采用“移植”的办法，利用A机器上已有的高级语言L编写能够在B机器上运行的高级

语言L的编译程序？画出T形图表示。

解答:

1. 编译程序的“遍”，就是对源程序或者中间结果从头到尾的一次扫描，并做有关的加工 处理，生成新的中间结果或者目标程序。 既可以将几个不同阶段合为一遍，也可以把一个阶段的工作分为若干遍。当一遍中包含 若干阶段时，各阶段的工作是穿插进行的。 一个编译程序究竟应分为几遍、如何划分，是与源语言、设计要求、硬件设备等诸因素 有关的，难以统一规定。

2. 编译程序：把某一种高级语言源程序转换成汇编语言程序或机器语言程序的程序。

解释程序：对高级语言源程序并不生成汇编程序或机器语言程序，而是边解释边执行的 程序。 编译程序把源语言程序翻译成目标代码，然后由操作系统加载执行；而解释程序则是边 翻译边执行，不生成目标代码。

3. 前端编译和后端编译是如何划分的？ 根据编译器的工作是与源语言相关还是目标机器有关来进行划分。 编译前端：编译程序中包括词法分析、语法分析、语义分析和中间代码产生等主要与源 语言程序有关但与目标机无关的那些部分叫编译前端。 编译后端：编译程序中包括目标代码生成、目标代码优化等与目标机有关而与源语言无 关的那些部分部分叫编译后端。

4. 标识符是由字母或数字以及某些特殊符号（因不同的高级语言而不同）组成的，但是必 须以字母开头的一个字符串。 当给某标识符以确切的含义时，这个标识符就叫做名字。程序语言中的各种名字都是用 标识符表示的。 名字和标识符具有相同的形式，名字使用标识符来描述，但标识符是没有意义的字符序 列，而名字却有确切的意义和属性（即类型和作用域）。

5. 6.

六.应用题 解答:

第二章 高级语言及其语法描述

一.填空题

1. 假设G是一个文法，?是由终结符和非终结符组成的串，S是文法的开始符号，如果S=>*α

，则称α是________________________。

2. 在赋值语句中，赋值号‘：=’左右两边的变量名扮演着两种不同的角色，为了区分一个 名字的这两种特征，我们把一个名字所代表的______称为该名的左值，把一个名字的_______ _ 称为该名字的右值。

3. 对于文法G，仅含终结符号的句型称为_________________________。

4. 设有文法G[S]，其部分产生式: S－>S;T S－>T T－>if E then S T－>V:=E T－>A 则VN ={ },VT={ }。

5. 由文法产生的_______________________集合是文法产生的语言。

6. Chomsky语法定义的3型文法又可以分为__________________________________。

7. 一个上下文文法G的四个组成部分分别是：________________________________________ _。

8. 已知语言：{anbnambm|n，m≥0}，其

语法定义为：G=({a，b}，{S，A，B}，S，P)，其中P为： ________________________________________________________ 。

9. 已知某语言的语法定义为：G=({1，0}，{S，A}，S，P)，且P：S→1A0|A|ε?；A→0A1| ε，则该语言为________________________________。

10. 已知某语言为{?wcwR|?∈{a，b}*}，其语法定义为G=({a，b，c}，{S}，S， P)， 其中P为：_________________________________ 。

11. 所谓最右推导是指_________________________________________________________。

12. 已知文法G(Z): E→ET+|T T→TF*|F F→FP↑|P P→E|i 试写出其识别的一个句子：_____________________。

13. 文法G[S]：S→aA|a， A→aS为_______ 型文法，其确定的语言的为：_______ 。

14. 在一棵语法树生长过___________________________________________ _________ 就是一个句型。

程

中

的

任

何

时

刻

，

15. 我们说G=(VT，VN，S，P)是一个0型文法，如果它的每一个产生 式α→β是这样一种结构：

_________________________________________________________________ 。

解答: 1. 句型；

2. 单元的地址（或者：单元、存储单元的地址），值（或者：单元的内容） 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.

二.判断题

1. 一棵语法树表示了一个句型所有的不同推导过程，包括最右推导和最左推导。 （ ）

2. 可能有两个不同的文法G和G“，期中一个是二义的而另一个是无二义的，但是却有L(G) ＝L(G“)。（ ）

3. 变量既持有左值又持有右值，而常数和带有算符的表达式一般认为只持有右值。（ ）

4. 文法G: S→bA A→aA|a 定义的语言是所有以b开头的后跟至少一个a的字符串的集合。（ ）

5. 设有文法G： S→S*S | S+S | (S) | a

该文法是二义的。( )

6. 正则文法一定不是二义的。（ ）

7. 上下文无关文法可以产生语言L={ anbnci | i>=1, n>=1 }。（ ）

8. 不存在任何正规文法能产生语言L={anbn | n>=1}。（ ）

9. 对于每一个左线性文法G1，都存在一个右线性文法G2，使得L(G

（ ） 1)=L(G2)。

10. 正规文法产生的语言都可以用上下文无关文法来描述。（ ）

11. 上下文无关文法比正规文法有更强的描述能力。（ ）

12. 文法的二义性和语言的二义性在概念上是相同的，也就是说，对于某个语言，不可能存 在两个以上的文法来描述它。（ ）

13. 二义性是可以判定的，也就是说，可以编这么一个程序，输入该文法后，该程序能确切 地给出该文法是否二义的答案。（ ）

14. 说明语句旨在定义名字的性质。编译程序把这些性质登记在符号表中，并检查程序中名 字的引用和说明是否一致。实际上，许多说明语句并不能翻译成相应的目标代码。（ ）

15. C语言是一个允许子程序嵌套定义的语言。（ ）

解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.

三.单项选择题

1. Chomsky把文法分成四种类型，0型、1型、2型和3型。3型文法也称为__________，2型文

法也称为_________ 。 a.上下文无关文法 b.上下文相关文法 c.正则文法 d.短语文法

2. 许多广为使用的语言，如Fortran、C、Pascal等，属于___________。 a. 强制式语言 b. 应用式语言 c. 基于规则的语言 d. 面向对象的语言

3. 设G是一个文法，S是开始符号。若S?*α，α∈(VT∪VN)*，则 称α是一个______ 。 a. 句子 b. 句型 c. 推导 d. 语言

4. 一个数据类型通常包括的三种要素中，没有下面的______。 a. 用于区别这种类型的数据对象的属性；b. 这种类型的数据对象可以具有的值； c. 对这种类型的数据对象的内存分配；d. 可以作用于这种类型的数据对象的操作；

5. Chomsky把文法分成四种类型，其中，______也称正规文法 a. 0型 b. 1型 c. 2型 d. 3型

6. 语言的词法规则一般用Chomsky的______ 型文法来描述： a. 0 b. 1 c. 2 d. 3

7. 文法 S→(L)|a L→L，S|S 中，下面 是该文法中的终结符号。 a. S b. ， c. L d. |

8. 文法G所描述的语言是_______ 的集合。 a. 文法G的字母表?中的所有符号组成的符号串； b. 文法G的字母表?的闭包?*中的所有符号串； c. 文法G的识别符号推出的所有符号串； d. 文法G的识别符号推出的所有终结符号串；

9. 语言L={αcα | α∈(a|b)*}，该语言是_____________语言。 a. 3型语言，b. 2型语言，c. 1型语言，d. 0型语言

10. 设有文法G： I→I1 | I0 | Ia | Ic | a | b | c | 下面符号串中不是该文法的句子是： a. ab0， b. a0c01， c. aaa， d. bc10

11. 给定文法A→bA|cc，下面的符号串中，是该文法句子的是________。 a. bcbc， b. bbbcc， c. bcbcc， d. bccbcc；

12. Chomsky定义的四种形式语言文法中，2型文法可由_______识别。 a. 图灵机；b. 确定性有限自动机；c. 下推自动机；d. 非确定性有限自动机；

13. 若文法G定义的语言是无限集，则文法必然是__________。 a. 上下文无关的 b. 递归的 c. 二义性的 d. 无二义性的

14. 文法 S→aaS|abc 定义的语言是_______。 a. {a2kbc|k>0} b. {akbc|k>0} c. {a2k-1bc|k>0} d. {akakbc|k>0}

15. 文法：G：S→xSx | y所识别的语言是________。 a. xyx b. (xyx)* c. x*yx* d. xnyxn（n≥0）

解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.

四.名词解释 1. 二义性文法；

2. 推导和直接推导；

3. 句型，句子和语言；

4. 上下文无关文法；

5. 语法；

6. 正规文法（左线性文法和右线性文法）； 解答: 1. 2. 3. 4. 5. 6.

五.简答题

1. 作为描述程序语言的上下文无关文法，对它有哪些限制？

2. 什么是二义性文法？从输入串abab来说明下面文法二义吗？ S→aSbS|bSaS|ε 该文法产生的语言是什么？

3. 文法 G[S]为： S→Ac|aB A→ab B→bc 该文法是否为二义的？为什么？

4. 已知文法G=({A,B,C}，{a,b,c}，P，A), P由以下产生式组成: A→abc A→aBbc Bb→bB Bc→Cbcc bC→Cb aC→aaB aC→aa 此文法所表示的语言是什么？

5. 已知文法G[Z]:

Z→0U|1V U→1Z|1 V→0Z|0 （1）请写出此文法描述的只含有４个符号的全部句子。 （2）G[Z]产生的语言是什么？ （3）该文法在Chomsky文法分类中属于几型文法？

解答: 1. 2. 3. 4. 5.

六.应用题

1. 试分析下面给出的if-then-else语句的文法，它的提出原本是为了矫正dangling-else(e lse悬挂)文法的二义性： stmt → if expr then stmt | matched-stmt matched-stmt→ if expr then matched-stmt else stmt | other expr→e 考虑句子if e then if e then other else if e then other else other，试说明此文 法仍然是二义性的。

2. 考虑文法G[bexpr]： bexpr→bexpr or bterm | bterm bterm→bterm and bfactor | bfactor bfactor→not bfactor| ( bexpr ) | true | false (a) 请指出此文法的终结符号、非终结符号和开始符号。 (b) 试对于句子not(true or false)构造一棵分析树。 (c) 试说明此文法所产生的语言是全体布尔表达式。

3. 已知文法G[S],其产生式为：S→(S)| ε? （a）L(G)是什么？ （b）对于(a)的结果，请给出证明。

4. 试构造生成下列语言的上下文无关文法： (1) { anbnci | n≥1, i≥0 } (2) { w | w∈{a,b}+，且w中a的个数恰好比b多1 } (3) { w | w∈{a,b}+，且|a|≤|b|≤2|a| } (4) { w | w是不以0开始的奇数集 }

5. 已知文法G[S]: S→AB A→aA|a B→bB|b 求该文法所定义的语言。

6. 考虑下面上下文无关文法G[S]： S→SS*|SS+|a (1) 对于符号串aa+a*分别给出最左推导和最右推导过程，并为该串构造语法树。 (2)G[S]的语言是什么？

7. 令文法G为 N→ D | ND D→ 0 | 1 | 2 | 3 | 4 | 5 | 6| 7 | 8 | 9 (1) G的语言L（G）是什么？ (2) 给出句子0127、34和568的最左推导和最右推导。

8. 写一个文法，使其语言是奇数集，且每个奇数不以0开头。

9. 写一个上下文无关文法CFG，使其语言是能被5整除且不以0开头的无符号整数的集合。（

如｛5,10,15，?.｝）

10. 证明下面的文法是二义的： S→ｉSｅS |ｉS | ｉ 11. 某程序设计语言的表达式由运算符θ1、θ2、θ3、 标识符、（、）组成，其中θ1和θ2的优先级相同，θ3

的优先级低于θ1、θ2的优先级，优先级相同的运算符从右往左 计算，可以用括号改变运算的顺序，则下述四种文法中哪一个可以描述上述的表达式文法？ 设E为识别符号，终结符号集={θ1、θ2、θ3、 （、）、I}，非终结符号集={E、T、F}。 a. E→T|Eθ1T|Eθ2T T→F|Tθ3F F→(E)|I b. E→T|Tθ1E|Tθ2E T→F|Fθ3T

F→(E)|I

c. E→T|Eθ3T

T→F|Tθ1F|Tθ2F F→(E)|I

d. E→T|Tθ3 E

T→F|Fθ1T|Fθ2T F→(E)|I

解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.

第三章 词法分析

一.填空题

1. 词法分析器对扫描缓冲区进行扫描时一般用两个指示器，一个_______________________ __________；另一个_____________________________________。 ————————————————————————————；————————— —————————————————___________________________;

2. 一个确定性有限自动机DFA M的化简是指：寻找一个状态数比M少的DFA M’，使得______

__________。

3. 词法分析器所的输出常表示成如下形式的二元式：（______________，_______________ __）。

4. 一个状态转换图只包含有限个状态，其中有一个被认为是________，而且实际上至少有 一个________。

5. 把状态转换图用程序实现时，对于含有回路的状态结点来说，可以让它对应一个_______ ______________________________程序段。

6. 词法分析阶段的任务式从左到右扫描_____________，从而逐个识别______________ 。

7. 如果一个种别只含有一个单词符号，那么，对于这个单词符号，__________就可以完全 代表它自身了。

8. 单词符号的属性值是指单词符号的特性或特征，其属性值则是反映特性或特征的值。比 如，对于某个标识符，常将_________________________________________________作为其属 性值。

9. 单词符号的属性值是指单词符号的特性或特征，其属性值则是反映特性或特征的值。比 如，对于常数，常将__________________________________________作为其属性值。

10. 如果一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给出种别编码以 外，还应给出有关__________________________ 。

11. 如果_______________________________，则认为这两个正规式等价。

12. 对于?*中的任何符号串?，如果存在一条从初态结点到某一终态结点的通路，且________ ___________________________，则称?被该自动机所接受（识别）。

13. 一个Lex源程序主要包括两部分，一部分是___________________________，另一部分是_

______________________________ 。

14. 一个DFA可用一个矩阵表示，该矩阵的行表示______________，列表示_______________ ，矩阵元素表示_____________ 。这个矩阵叫状态转换矩阵。

15. 对于词法分析程序来说，当程序到达“错误处理”时，意味着现行状态i和当前所面临的

输入串不匹配。如果后面还有状态图，出现在这个地方的代码应该为： _____________________________________________________________________________

______________。

9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19.

四.名词解释 1. 状态转换图；

2. 正规式（正规表达式、正则表达式）的形式化定义；

3. 给出确定性有限状态自动机的形式化定义；

4. 给出非确定性有限状态自动机的形式化定义；

5. DFA状态最小化。

解答: 1. 2. 3. 4. 5.

五.简答题

1. 写出标识符（以字母打头，由字母和数字组成的符号串）的正则表达式。

2. 词法分析器对程序语言的单词符号一般如何分类？

3. 人运狼、羊、菜过河，一次运一件，不让羊吃掉菜，也不让狼吃掉羊，画出渡河的状态 转换图。可否将其抽象为一个有限自动机？

4. C语言无符号实数用正则表达式怎么定义？

5. 分析下面各正规表达式所表示的语言。 (00|11)*((01|10)(00|11)*(01|10)(00|11)*)*

6. 何谓扫描器？扫描器的功能是什么？

7. 试简述有穷状态自动机与正则表达式的等价性概念。

解答: 1. 2. 3. 4. 5. 6. 7.

六.应用题

1. 有一个语言，它接收Σ={0，1}上所有满足如下条件的字符串：每个1都有0直接跟在右边 。 （１）给出该语言的正规式 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化

2. 已知字母表? = {a， b}上语言L = {w | w中a的个数是偶数}。 （１）给出该语言的正规式 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化

3. 有一个语言，它接收Σ={0，1}上的含奇数个1的所有串。 （１）给出该语言的正规式 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化 提示：正则表达式为0*1 (0|10*1)*。

4. 已知Σ={0，1}上正则表达式为0(0|1)*0， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化

5. 已知Σ={0，1}上正则表达式为(0|1)*0(0|1)(0|1)， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA

（３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化

6. 已知Σ={0，1}上正则表达式为0*10*10*10*， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化

7. 有一个语言，它接收Σ={a，b}上所有满足如下条件的字符串：不含子串abb的由a和b组

成的符号串的全体。 （１）给出该语言的正规式 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化

8. 已知Σ={0，1}上正则表达式为((ε|0)1*)*， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化

9. 已知Σ={0，1}上正则表达式为(a*|b*)*， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化

10. 已知语言为Σ={a，b}上的、由a和b组成的但是不以bb结束的所有符号串的集合。 （１）写出定义该语言的正则表达式。 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化

11. 已知Σ={a，b}上正则表达式为(aa|b)*(a|bb)*， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA

（３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化

12. 已知语言为Σ={0，1}上所有由0和1组成的二进制数串的集合，这些串从数值上可以看作

是4的倍数。 （１）写出定义该语言的正则表达式。 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化

13. 已知语言为Σ={0，1}上所有由0和1组成的二进制串的集合，这些串都是以0打头以0结尾 的。 （１）写出定义该语言的正则表达式。 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化

14. 已知Σ={0，1}上正则表达式为1(0|1)*101， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化

15. 已知Σ={a，b}上正则表达式为(a|b)*abb(a|b)*， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化 解答: 1. 2. 3. 4. 5. 6. 7. 8.

9. 10. 11. 12. 13. 14. 15.

第四章 语法分析—自上而下分析

一.填空题

1. 语法分析器的工作本质上就是按____________________，识别输入符号串是否为一个句 子。这里所说的输入串是指由____________________ 组成的有限序列。

2. 自顶向下分析会遇到的主要问题是____________________和__________________。

3. 自上而下地为输入串建立一棵语法树，就是为输入串寻找一个______________。

4. 在扩充的巴科斯范式中，用______________表示符号或串α的出现可有可无。

5. 对于一个文法，当给出一串符号时，怎么能知道它是不是该文法的一个句子呢？这就要 判断，

看是否能___________________________________________。

6. 文法exp → exp addop term | term 消除左递归的结果为__________________________ _______。

7. 写出E→T | E+T的EBNF范式为__________________________。

8. 扩展的巴克斯范式描述语法的好处是，直观易懂，便于表示_________________________ _____。

解答: 1. 2. 3. 4. 5. 6. 7. 8.

二.判断题

1. LL(k)文法都不是二义性的。（ ）

A→SB B→ab

(1) 改写文法以消除左递归，若有左因子则提取之；

(2)计算改写后文法中各非终结符的 FIRST 集和 FOLLOW 集； (3)构造改写后文法的预测分析表；该文法是 LL(1) 文法吗?。

15. 文法： S→MH|a H→LSo|ε K→dML|ε L→eHf M→K|bLM (1)消除左递归； (2)计算改写后文法中各非终结符的 FIRST 集和 FOLLOW 集； (3)构造改写后文法的预测分析表；该文法是 LL(1) 文法吗?。

16. 对下面文法 Expr→-Expr Expr→ (Expr)|Var ExprTail ExprTail→-Expr | ε? Var→id VarTail VarTail→ (Expr) | ε? (1) 构造LL（1）分析表。 (2) 给出对句子id--id((id))的分析过程。

17. 把下面文法改写为LL（1）的： Declist→Declist; Decl | Decl Decl→idList:Type IdList→Idlist, id | id Type→ScalarType | array (ScalarTypeList) of Type ScalarType→id | Bound..Bound Bound→Sign IntLiteral | id Sign→+ | - | e ScalarTypeList→ScalarTypeList, ScalarType | ScalarType

解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17.

第五章 语法分析—自下而上分析

一.填空题

1. 规范归约的关键问题是_______________________。

2. LR(k)分析法中，L的含义是____________________，

R的含义是_______________________，

k的含义是_______________________。

3. 移进一归约分析对符号串的使用有四类操作：移进、__________、_________和出错处理 。 4. 设文法G（E为其开始符号）产生式如下：

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

则句型E+T*F+i的句柄是_________________。

5. 自下而上分析方法的基本思想是：从输入符号串开始，利用文法规则逐步进行归约，直 至归约到文法的_________________________ 。

6. 在算符优先分析中，用_____________来刻画“可归约串”；在规范归约分析中，用____ ___________ 来刻画“可归约串”。

7. 在LR(0)分析中，相容的项目集，必须满足的条件是_______，_______。

8. LR语法分析栈中存放的状态是识别_______的DFA状态。

9. 在LR分析过程中的任何时候，栈里的文法符号从下往上应该构成______________，把输 入串的剩余部分配上之后应成为__________________。

10. 对于LR(0)分析法来说，项目A→β1β2对活前缀αβ1是 有效的，其条件是存在规范推导_________________________。

11. 形式上我们说一个LR(1)项目[A→α?β，a]对于活前缀γ是有效的，如果存在规范推导 _____________________。

12. LR(k)分析方法中项目类型可分为四类_____________、______________ 、____________ ___ 和_______________。

13. 所谓算符优先分析法就是仿照算术四则运算的运算过程设计的一种语法分析方法。它首 先要规定________________，然后利用这种关系确定__________________，并进行_________ ________。

14. 如图所示的语法树中，a，b不在同一句柄中，____先归约，所以____的优先级高于 。

15. 对于句型η的语法树，若它的一棵子树的根标记为A，且将此子树的末端结点标记从左至

右排列起来所形成的符号串为β，则β是____________________________；此时文法中必有 推导____________________________。

16. LR(0)每个项目中圆点的左部表示在分析过程中，要用该产生式归约时，______________ ___________，右部表示_______________________。

17. 根据项目的定义，可给出文法中所有产生式的项目，而每个项目都为识别_____________ _____的NFA的一个状态。

解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17.

二.判断题

1. 一个二义性文法可以是SLR文法或LALR文法。（ ）

2. LL(1)文法不能用LR（1）分析器来分析。（ ）

3. LR分析器在自左至右扫描输入串时就能发现其中的任何错误，并能准确地指出出错地点 。( ）

4. 在归约过程的任一时刻，一个上下文无关文法的任何句型的直接短语一般都不是唯一的 。( )

5. 算符优先分析法不是一种规范规约法。 ( )

6. 存在有左递归规则的文法是LL(1)的。 ( )

7. 任何算符优先文法的句型中不会有两个相邻的非终结符号。 ( )

8. 算符优先文法中任何两个相邻的终结符号之间至少满足三种关系(＜?，?＞，＝?)之 一。 ( )

9. 任何LL(1)文法都是无二义性的。 ( )

10. 每一个SLR(1)文法也都是LR(1)文法。 ( )

11. 存在一种算法，能判定任何上下文无关文法是否是LL(1)的。 ( )

12. 任何一个LL(1)文法都是一个LR(1)文法，反之亦然。 ( )

13. LR(1)分析中括号中的1是指，在选用产生式A→α进行分析，看当前读入符号是否在FIRS T(α)中。 ( )

14. 若某一个句型中出现了某一产生式的右部，则此右部不一定是该句型的句柄。（ ）

15. 算符优先关系表不一定存在对应的优先函数。 （ ）

16. 简单优先文法允许任意两个产生式具有相同右部。 （ ）

17. 一个句型的句柄一定是文法某产生式的右部。 （ ）

18. 若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。 （ ）

19. 根据项目的定义，可给出文法中所有产生式的项目，而每个项目都为识别活前缀的DFA的

一个状态。 （ ） 解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18.

a. 综合属性， b. 继承属性， c. L-属性， d. R-属性

8. 考虑非终结符A、B和C，其中A有一个继承属性a和一个综合属性b，B有综合属性c，C有继

承属性d。产生式A→BC可能的属性计算规则中，_______属性要在其它地方计算，不是在本产

生式的属性计算规则中计算的。 a. C.d和A.b；b. A.a和A.b；c. A.a和B.c；d. C.d和A.a

9. 通常使用________ 的方法在每一个结点处使用语义规则计算综合属性的值。 a. 自顶向下，b. 自底向上，c. 从左到右，d. 从右到左；

10. S-属性文法的计算中，设当前的栈顶由指针top指示，假设综合属性刚好在每次归约前计

算的。假定产生式为A→XYZ，相应的语义规则为A.a:=f(X.x, Y.y，Z.z)。 在把XYZ归约成A 以前，属性Z.z的值放在val[top]中，Y.y的值放在val[top-1]中， X.x的值放在val[top-2] 中。归约以后，A的状态存放在 中（即X的位置）。综合属性A.a的值存放在 中。 a. state[top]，val[top]； b. state[top-1]，val[top-1]； c. state[top-2]，val[top-2]； d. state[top-3]，val[top-3]；

11. 一个简单的翻译模式 E→TR R→addop T {print(addop.lexeme)} R1|ε T→num {print(num.val)} addop→+|- 该文法的作用是 。 a. 把一个带加号和减号的前缀表达式翻译成相应的后缀表达式 b. 把一个带加号和减号的后缀表达式翻译成相应的前缀表达式 c. 把一个带加号和减号的后缀表达式翻译成相应的中缀表达式； d. 把一个带加号和减号的中缀表达式翻译成相应的后缀表达式；

12. 有一语法制导翻译如下所示:（第8章） S→bAb {print “1” } A→(B {print “2” } A→a {print “3” } B→Aa) {print “4” } 若输入序列为b(((aa)a)a)b，则采用自下而上的分析方法，则输出是_________。 a. 32224441 b. 34242421 c. 12424243 d. 34442212

13. 在属性文法中，终结符只具有________ 属性。 a. 传递 b. 继承 c. 抽象 d. 综合

14. 设，有以下左递归翻译模式 A→A1Y {A.a:=g(A1.a,Y.y)} A→X {A.a:=f(X.x)} 它的每一个文法符号都有一个综合属性，用相应的小写字母表示，g和f是任意函数。消

除左递归，再考虑语义动作，翻译模式变为： A→X { R.i:=f(X.x) } R { A.a:=R.s }

R→Y { R1.i:=g(R.i, Y.y) }

R1_____________________

R→ε ______________________ a. { R.s:=R1.s } ，{ R.s:=R.i }；b. { R.s:=R.i }，{ R.s:=R1 .s }； c. { R.s:=R1.i } ，{ R.s:=R.s }；d. { R.s:=R.s }，{ R.s:=R1.i }；

15. ________________可用于一遍扫描的自上而下分析，而________________则适合于一遍

扫描的自下而上分析。 a. S-属性文法，L-属性文法； b. 继承属性文法，综合属性文法； c. L-属性文法，S-属性文法； d. 综合属性文法，继承属性文法；

解答: 1. 2. 3. 4. 5. 6. 7. 8. 9.

10. 11. 12. 13. 14. 15.

四.名词解释

1. 属性，属性文法，综合属性，继承属性；

2. 语法制导翻译法；

3. 属性依赖图；

4. S－属性文法，L－属性文法；

5. 翻译模式；

解答: 1. 2. 3. 4. 5.

五.简答题

1. 一般情况下，为什么语义分析部分仅产生中间代码？

2. 什么是语法制导翻译？为什么把这种方法叫语法制导翻译？

3. 给定一个L－属性文法，建立翻译模式要满足哪些条件？

解答: 1. 2. 3.

六.应用题

1. 欲打印表达式(4*7+1)*2的值。写出属性文法，根据该属性文法建立一棵带注释的分析树 ，并在该分析树上用箭头标出属性计算次序。

2. 已知上下文无关文法： E→E+T E→E-T E→T T→(E) T→id

T→num 已知表达式((a)+(b))。不对文法进行修改，写出为表达式建立抽象语法树的属性文法； 并画出带注释的语法分析树来描绘抽象语法树的构造。

3. 已知上下文无关文法： E→E+T E→E-T E→T T→(E) T→id T→num 已知表达式((a)+(b))。采用自顶向下的翻译模式，写出构造抽象语法树的、消除了左递 归的翻译模式，并画出带注释的语法分析树来描绘抽象语法树的构造。

4. 试给出把中缀表达式转换成没有多余括号的中缀表达式的语法制导定义。例如，由于+和 *都是左结合的，((a*(b+c))*(d))可以写成a*(b+c)*d。

5. 下面文法产生的表达式是对整型和实型常数应用算符+形成的。当两个整数相加时,结果 为整数，否则为实数。 E→E+T | T T→num.num | num （1）给出语法制导定义确定每个子表达式的类型 （2）扩充（1）中的语法制导定义把表达式翻译成前缀形式，并且决定类型。试用一元 运算符inttoreal把整型值转换为相等的实型值，以使得前缀表达式中两个运算对象是同类型 的。

6. 令综合属性val给出在下面的文法中的S产生的二进制数的值(如，对于输入101.101，S.v al=5.625)； S→L.L | L L→LB | B B→0 | 1 （1）试用各有关综合属性决定S.val； （2）试用一个语法制导定义来决定S.val,在这个定义中仅有B的综合属性，设为c，它给

出由B 生的位对于最后的数值的分担额。例如，在101.101中的第一位和最后一位对于值5.62

5的分担额分别为4和0.125。

7. 已知变量声明语句的上下文无关文法： D→TL T→int

T→real L→L1，id L→id 定义一个继承属性来完成类型信息的传递，已知输入串real id1,id2, id3，给出带注释的语法分析树，画出属性依赖图，并给出属性计算过程。

8. 已知变量声明语句的上下文无关文法： D→TL T→int T→real L→L1，id L→id 定义一个综合属性来完成类型信息的传递，已知输入串real id1,id2, id3，给出带注释的语法分析树，画出属性依赖图，并给出属性计算过程。

9. 下面文法产生的表达式是对整型和实型常数应用算符+形成的。当两个整数相加时,结果 为整数，否则为实数。 E→E+T | T T→num.num | num （1）给出语法制导定义确定每个子表达式的类型，并消除属性文法的左递归； （2）扩充（1）中的语法制导定义把表达式翻译成前缀形式，并且决定类型。试用一元 运算符inttoreal把整型值转换为相等的实型值，以使得前缀表达式中两个运算对象是同类型 的。并消除文法左递归。

10. 给出一个检查同一个标识符不在标识符表中出现两次的翻译模式。

11. 假设说明是由下列文法产生的： D→id L L→,id L|:T T→ingeger |real （1）建立一个翻译模式，把每一个标识符的类型加入到符号表中。 （2）从（1）中的翻译模式构造一个预翻译程序。 12. 已知关于盒子大小和高度的属性文法如下： 产生式 语义规则 S→B B.ps:=10 S.ht:=B.ht

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