第一章 引论
一.填空题
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和当前所面临的
输入串不匹配。如果后面还有状态图，出现在这个地方的代码应该为： _____________________________________________________________________________
______________。
解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.
二.判断题
1. NFA M的非确定性表现在它有多个终态。 （ ）
2. 有穷自动机接受的语言是正则语言。 （ ）
3. 若r1和r2是Σ上的正规式，则r1|r2也 是。 （ ）
4. 设M是一个NFA，并且L(M)＝{x， y， z}，则M的状态数至少为4个。 （ ）
5. 令Σ＝{a， b}，则Σ上所有以b为首的字符构成的正规集的正规式为b*(a|b)*。 （ ）
6. 对任何一个NFA M，都存在一个DFA M'，使得L(M')=L(M)。 （ ）
7. 对一个右线性文法G，必存在一个左线性文法G'，使得L(G)=L(G')，反之亦然。（ ）
8. 对任意一个右线性文法G，都存在一个NFA M，满足L(G)=L(M)。 ( )
9. 对任意一个右线性文法G，都存在一个DFA M，满足L(G)=L(M)。 ( )
10. 对任何正则表达式r，都存在一个NFA M，满足L(M)=L(r)。 ( )
11. 对任何正则表达式r，都存在一个DFA M，满足L(M)=L(r)。 ( )
12. 一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。（ ）
13. 一个正规式只能对应一个有限状态自动机； （ ）
14. 在词法分析的状态转换图中，有些结点是带星号的，这些结点肯定是终态结点。（ ）
15. 适当设置扫描缓冲区的大小（比如容纳256个字符）可以保证单词符号不会被它的边界所 打断。（ ） 解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.
三.单项选择题
1. 程序语言下面的单词符号中，____一般不需要超前搜索 a. 关键字 b. 标识符 c. 常数 d. 算符和界符
2. 在状态转换图的实现中，____ 一般对应一个循环语句 a. 不含回路的分叉结点 b. 含回路的状态结点 c. 终态结点 d. 都不是
3. 从左线性文法构造有限自动机时，通常自动机状态个数比文法非终结符号数多____个。 (a)4 (b)2 (c)0 (d)1
4. 正规表达式(ε|a|b)2表示的集合是 _____。 (a){ε，ab，ba，aa，bb} (b){ab，ba，aa，bb} (c){a，b，ab，aa，ba，bb} (d){ε，a，b，aa，bb，ab，ba}
5. 有限状态自动机可用五元组（VT，Q，δ，q0，Qf）
来描述，设有一有限状态自动机M的定义如下： VT={0， 1}，Q={q0， q1， q2}，Qf ={q2}，δ的定义为： δ（q0，0）=q1 δ（q1，0）=q2 δ（q2，1）=q2 δ（q2，0）=q2 M所对应的状态转换图为____ 。
6. 有限状态自动机可用五元组（VT，Q，δ，q0，Qf） 来描述，设有一有限状态自动机M的定义如下： VT={0， 1}，Q={q0， q1， q2}，Qf= {q2}，δ的定义为： δ（q0，0）=q1 δ（q1，0）=q2 δ（q2，1）=q2 δ（q2，0）=q2 M所能接受的语言可以用正则表达式表示为____。 ①(0|1)* ②00(0|1)* ③(0|1)*00 ④0(0|1)*0
7. 有限状态自动机可用五元组（VT，Q，δ，q0，Qf） 来描述，设有一有限状态自动机M的定义如下： VT={0， 1}，Q={q0， q1， q2}，Qf ={q2}，δ的定义为： δ（q0，0）=q1 δ（q1，0）=q2 δ（q2，1）=q2 δ（q2，0）=q2 M所能接受的语言为____。 ①由0和1所组成的符号串的集合 ②以0为头符号和尾符号、由0和1所组成的符号串的集合 ③以两个0结束的，由0和1所组成的符号串的集合 ④以两个0开始的，由0和1所组成的符号串的集合
8. 从接受语言的能力上来说，非确定型有穷自动机和________是等价的。 a. ⅰ.正规式；ⅱ.上下文无关文法；ⅲ.确定性有穷自动机； b. ⅰ.左线性正规文法；ⅱ.右线性正规文法；ⅲ.确定性有穷自动机； c. ⅰ.正规式；ⅱ.上下文无关文法；ⅲ.正规文法； d. ⅰ.正规式；ⅱ.确定性有穷自动机；ⅲ.下推自动机；
9. 下面四个选项中，关于编译过程中扫描器的任务的叙述，________是不正确的。 ①组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输 出；删除注释；删除空格和无用字符；行计数、列计数；发现并定位词法错误；建立符号表 。 ②按词法规则分割出单词，识别其属性，并转换成属性字的形式输出；发现并定位词法 错误；建立符号表；输出状态转换图。 ③组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输 出。 ④组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输 出；行计数、列计数；发现并定位词法错误；建立符号表；输出状态转换图。
10. ______不是NFA的成分。 A.有穷字母表 B.初始状态集合 C.终止状态集合 D.有限状态集合
11. 词法分析的常用方法有____。 A.有穷自动机理论 B.图灵机 Ｃ.图论 Ｄ.无穷自动机理论
12. 设有两个状态S和T，如果从S出发能读出某个字w而停于终态，那么从T出发也能读出同样
的字而停于终态；反之，果从T出发能读出某个字w而停于终态，那么从S出发也能读出同样的
字而停于终态。则我们称状态S和状态T是____。 A. 可区分的；B. 等价的；C. 多余的；D. 无用的。
13. 词法分析器的输出结果是____。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值
14. 编译过程中扫描器的任务包括______。
①组织源程序的输入
②按词法规则分割出单词，识别出其属性，并转换成属性字的形式输出 ⑧删除注解
④删除空格及无用字符 ⑤行计数、列计数 ⑥发现并定位词法错误 ⑦建立符号表
a．②③④⑦ b．②③④⑥⑦ c．①②③④⑥⑦ d．①②③④⑤⑥⑦
15. 下述正则表达式中______与(a*+b)*(c+d)等价(即有相同符号串集)。(x+y亦可写作x|y) ①a*(c+d)+b(c+d) ②a*(c+d)*+b(c+d)* ③a*(c+d)+b(c+d) ④(a+b)*c+(a+b)*d ⑤(a*+b)*c+(a*+b)*d a.①③ b. ③④⑤ c.③ d.④⑤
16. 正则式的“*”读作______。 a，并且 L或者 c．连接 d．闭包
17. 在状态转换图中，结点代表____，用圆圈表示。 a.输入缓冲区 b.向前搜索 c.状态 d.字符串
18. 与(a|b)*(a|b)等价的正规式是____。(第4章) A. a*| b* B. (ab)*(a|b)* C. (a|b)(a|b)* D. (a|b)*
19. 无符号常数的识别和拼数工作通常都在____ 阶段完成。 Ａ．词法分析 Ｂ．语法分析 Ｃ．语义分析 Ｄ．代码生成 解答: 1. 2. 3. 4. 5. 6. 7. 8.
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)文法都不是二义性的。（ ）
2. 存在一种算法，能判定任何上下文无关文法是否是LL(1)的。 ( )
3. 一个文法是含有左递归的，如果存在非终结符P，使得P?*α。（ ）
4. 提取公共左因子的副产品是引进了大量的非终结符和ε产生式。 ( )
5. 把一个文法改造成任何非终结符的所有后选终结首符集两两不相交的办法是消除左递归 。( )
6. 若X∈VT，则FIRST(X)={ X }。 ( )
7. 一个文法的预测分析表含有多重定义入口，说明该文法是LL(1)的。（ ）
8. 自上而下分析及自下而上分析中的“下”是指被分析的源程序串。（ ）
解答: 1. 2. 3. 4. 5. 6. 7. 8.
三.单项选择题
1. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于____ 分析法。 a. 自左至右 b. 自顶向下 c. 自底向上 d. 自右向左
2. 上下文无关文法可以用____来描述。 a. 正则表达式 b. 正规文法 c. 扩展的BNF d. 翻译模式
3. 自上而下分析面临的四个问题中，不包括____ a. 需消除左递归；b. 存在回朔；c. 虚假匹配；d. 寻找可归约串
4. 语法分析器接收以________为单位的输入，并产生有关信息供以后各阶段使用。 a. 表达式；b. 产生式； c. 单词；d. 语句；
5. 自上而下分析的主旨是，对任何单词符号串，试图用一切可能的办法，从文法开始符号 （根结点）出发，________。 a. 为输入串寻找最右推导； b. 为输入串寻找最左直接子树； c. 为输入串建立最右直接子树；d. 为输入串寻找最左推导；
6. 把规则T→F | T*F表示成扩展的巴克斯范式以后，画出它的语法图应该是____。
7. 下列文法中，_______是LL(1)文法。 a. S→aSb|ab b. S→ab|Sab c. S→aS|b d. S→aS|a
8. 设有文法G： S→Ap|Bq A→a|cA B→b|dB 则，First(Ap)={_______________} a. a,c b. b,d c. p, q d. A, p
解答: 1. 2. 3. 4. 5. 6. 7. 8.
四.名词解释 1. 左递归；
2. 递归下降分析器；
3. LL(1)文法； 解答: 1. 2. 3.
五.简答题
1. 词法分析和语法分析都是对字符串进行识别的，二者有何区别？
2. 试说明没有一个左递归文法是LL(1)的。
3. 试说明没有一个LL(1)文法是二义性的。 解答: 1. 2. 3.
六.应用题
1. 已知文法G[S]： S → (L) | a L → L,S | S ⅰ.消除左递归，若有左因子则提取之； ⅱ.对ⅰ中得到的文法求First集合和Follow集合 ⅲ.对ⅰ中得到的文法构造一个预测分析表； ⅳ.给出对句子(a,(a,a))上的分析动作
2. 考查文法G(s): S→( T ) | a + S | a T→T, S | S ⅰ.消除文法的左递归，提取公共左因子 ⅱ. 改造后的文法是LL(1)的吗？为什么？ ⅲ. 如果是LL(1)文法，对每个非终结符，写出不带回朔的递归子程序。
3. 已知文法G[S]： S → uBDz B → Br | w D → EF E → y | ε? F → x | ε?
(a) 求每个非终结符的FIRST和Follow集。 (b) 构造这个文法的LL(1)分析表 (c) 说明这个文法不是LL(1)的; (d) 尽可能少地修改此文法,使其成为能产生相同语言的LL(1)文法.
4. 已知文法如下： E→T | E+T T→F | T*F F→i | (E) 构造预测分析表，并给出对输入串i*i+i的分析过程。
5. 文法G1： S→a|^|(T) T→T,S|S (1) 证明文法G是LL(1)文法。 (2) 构造LL(1)分析表。 (3) 写出句子（a,a）#的分析过程。
6. 设文法G(S)： S→(L)|aS|a L→L,S|S (1)消除左递归和回溯； (2)计算每个非终结符的FIRST和FOLLOW； (3)构造预测分析表。 (4)已知输入串(aa,a)a，该输入串是否文法的句子？给出分析过程。
7. 对于文法 bexpr → bexpr or bterm | bterm bterm → bterm and bfactor | bfactor bfactor→ not bfactor | (bexpr) | true | false 构造一个预测分析器。
8. 已知G[R]的产生式如下: R → R“ | “T | T T → TF | F F → F* | C C → (R) | a | b 构造它的LL(1)分析表，并写出对输入串的分析过程。
9. 已知文法如下： S→S*T | S/T | T T→T+F | T-F | F
F →(S) | i | i e i
构造预测分析表，并给出对输入串的分析过程。
10. 已知文法： S→Ac|c A→Bb|b B→Sa|a 构造预测分析表，给出对输入串的分析过程。
11. 已知文法G：
S → ( L | a
L → S , L | )
（1）构造文法 G 的预测分析表。 （2）若输入串为“（ａ，）”，请给出语法分析过程。
12. 给定文法 Ｇ＝({ i，d，“(“，“)“ }，{Ｅ，Ａ}，Ｅ，Ｐ) 其中 Ｐ： E →iA E →EA A → i A →d A → (E) (1)消除左递归； (2)计算改写后文法中各非终结符的 FIRST 集和 FOLLOW 集； (3)构造改写后文法的预测分析表；该文法是 LL(1) 文法吗?。
13. 已知文法： A→aABe|a B→Bb|d ⅰ.消除左递归，若有左因子则提取之； ⅱ.对（1）中得到的文法求First集合和Follow集合 ⅲ.对（1）中得到的文法构造一个预测分析表； ⅳ.给出对句子aadb上的分析动作
14. 已知文法： S→Aa|b
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.
19.
三.单项选择题
1. LR语法分析栈中存放的状态是识别________的DFA状态。 a. 前缀；b. 可归前缀；c. 项目；d. 句柄；
2. 算符优先分析法每次都是对________进行归约： (a)句柄 （b）最左素短语 (c)素短语 (d)简单短语
3. 有文法G＝（｛S｝，｛a｝，｛S→SaS，S→ε｝，S），该文法是________。 a. LL(1)文法；b.二义性文法；c.算符优先文法；d.SLR(1)文法；
4. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，_____ 和LL(1)分析法 属于自顶向下分析； a. 深度分析法 b. 宽度优先分析法 c. 算符优先分析法 d. 递归下降子程序分析法
5. 自底向上语法分析采用____ 分析法，常用的是自底向上语法分析有算符优先分析法和LR 分析法。 a. 递归 b. 回溯 c. 枚举 d. 移进－归约
6. 一个LR(k)文法，无论k取多大，____。 a. 都是无二义性的；b. 都是二义性的；c. 一部分是二义性的；d. 无法判定二义性；
7. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，____和LR分析法属于 自底向上分析。 a. 深度分析法 b. 宽度优先分析法 c. 算符优先分析法 d. 递归下降子程序分析法
8. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，自顶向下分析试图为 输入符号串构造一个____； a. 语法树 b. 有向无环图 c. 最左推导 d. 最右推导
9. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，自底向上分析试图为 输入符号串构造一个____ 。 a. 语法树 b. 有向无环图 c. 最左推导 d. 最右推导
10. 采用自顶向下分析方法时，要求文法中不含有____。
a. 右递归 b. 左递归 c. 直接右递归 d. 直接左递归
11. LR分析是寻找右句型的____；而算符优先分析是寻找右句型的____。 a. 短语； b. 素短语； c. 最左素短语； d. 句柄
12. LR分析法中分析能力最强的是____；分析能力最弱的是_____。 a. SLR(1)； b. LR(0)； c. LR(1)； d. LALR(1)
13. 设有文法G： T->T*F | F
F->F↑P | P P->(T) | a
该文法句型T*P?(T*F)的最左直接短语是下列符号串________。 a. (T*F)， b. T*F， c. P， d. P↑(T*F)
14. 在通常的语法分析方法中，（ ）特别适用于表达式的分析。 a．算符优先分析法 b．LR分析法 c．递归下降分析法 d．LL(1)分析法
15. 运算符的优先数之间有几种关系____ 。 a.3种 b. 2种 c. 4种 d. 1种
16. 算符优先法属于（ ） a.自上而下分析法 b.LR分析法 c.ＳLR分析法 d.自下而上分析法
17. 在LR分析法中，分析栈中存放的状态是识别规范句型____ 的DFA状态。 a.句柄 b. 前缀 c. 活前缀 d. LR(0)项目
解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
11. 12. 13. 14. 15. 16. 17.
四.名词解释
1. 短语，直接短语，句柄；
2. 规范归约，规范推导；
3. 算符文法，算符优先文法；
4. 素短语，最左素短语；
5. 前缀，活前缀；
6. LR(0)项目，LR(0)项目集规范族； 解答: 1. 2. 3. 4. 5. 6.
五.简答题
1. 说明任何SLR(1)文法都是LR(1)文法。
2. 为什么移进－归约法不是一种语法分析方法？
3. LR(k)分析法是如何做到严格地自左向右进行分析的？
4. 使用状态有限的识别可归前缀的有穷自动机，为什么可以识别语言的无穷多个句子？
5. LR项目的含义是什么？
解答: 1. 2. 3. 4. 5.
六.应用题
1. 文法如下： S→a | L | (T) T→T, S | S (1) 计算该文法的Firstvt和Lastvt； (2) 构造算符优先关系表,并说明该文法是否是OPG文法； (3) 计算优先函数； (4) 给出串(a,a)#和(a,(a,a)) #的算符优先分析过程。
2. 下列文法是否为SLR(1)文法？若是，请构造相应的分析表。若不是，请说明理由。 S→Sab | bR R→S | a
3. 证明下面文法是SLR(1)文法，并构造其SLR分析表。 E→E+T|T T→TF|F F→F*|a|b 输入串b+ab*是该文法的句子吗？给出对该串的分析过程。
4. 下面文法属于哪类LR文法？试构造其分析表。 S→(SR|a R→,SR|) 输入串（a,a）是文法的句子吗？给出分析过程。
5. 设文法G为 S → A A → BA | ε B → aB | b （1）证明它是LR(1)文法； （2）构造它的LR(1)分析表； （3）给出输入符号串abab的分析过程。
6. 为下面的文法构造LALR(1)分析表 S→E E→E+T | T T→(E) | a 并给出对输入串(a+a)的分析过程。
7. 已知文法 S →L.L S →L L →LB L →B B →0 B →1 用LR分析法说明符号串101.110是否文法的句子。
8. 对于文法 S→AB A→aB B→b (1) 构造LR(1)分析表； (2) 给出用LR(1)分析表对输入符号串abab的分析过程。
9. 给定文法G[Z]： ①Z→C S ②C→if E then ③S→A＝E ④E→E∨A ⑤E→A ⑥A→i 其中：Z、C、S、A、E∈VN ；if、then、＝、∨、i∈VT a) 构造此文法的LR(0)项目集规范族，并给出识别活前缀的DFA。 b) 构造其SLR（1）分析表。
10. 设有文法G[S]： S→aA A→Ab A→b 求识别该文法所有活前缀的DFA；构造合适的LR分析表，并给出对输入串abb的分析过程 。
11. 给定文法 G[S] ： S → SaA|a A → AbS|b ⑴请构造该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 。
⑵请构造该文法的 LR(0) 分析表。
⑶什么是 LR(0) 文法？该文法是 LR(0) 文法吗？为什么？ ⑷什么是 SLR(1) 文法？该文法是 SLR(1) 文法吗？为什么？
12. 下面文法属于哪类LR文法？试构造其分析表。 S→aSAB | BA A→aA | B B→ b 输入串abababb是文法的句子吗？给出分析过程。
13. 文法 S→(L) | a L→L, S | S (1) 计算该文法的Firstvt和Lastvt； (2) 构造算符优先关系表,并说明该文法是否是OPG文法； (3) 计算优先函数； (4) 给出串(a, (a, a))的算符优先分析过程。
14. 设已给文法G1［S］： S→Aa|bAc|dc|bda A→d 构造其LALR(1)文法，并分析输入串bdc是否文法的句子；
15. 下面是一个描述∑={a b}上的正规式的LALR文法（实际上也是SLR文法），只不过用‘＋ ’代替‘|’，用∧代替?（空字）。 E→E+T | T T→TF | F F→F* | (E) | a | b | ∧ 构造这个文法的LALR项目集和分析表。
解答: 1. 2. 3. 4. 5. 6. 7. 8. 9.
10. 11. 12. 13. 14. 15.
第六章 属性文法和语法制导翻译
一.填空题
1. ________属性用于“自下而上”传递信息；而________属性用于“自上而下”传递信息 。
2. 如果一属性文法不存在属性之间的________，那么称该文法为良定义的。
3. 按照________________的编译程序模型来理解语法制导翻译方法，所谓的语法制导翻译 ，直观上说，就是为文法中每个_____________配上一组语义规则，并在________________的
同时执行这些语义规则。
4. 下面语义规则： T→T1*F T.val:=T1 .val*F.val ，改写成翻译模式为：_________________________。
5. S－属性文法中的每个文法符号，只含有________属性。
6. 与树遍历的属性计算方法不同，一遍扫描的处理方法是在语法分析的同时计算属性值， 而不是语法 分析构造语法树之后进行属性计算。 ________________可用于一遍扫描的自上 而下分析，而________________则适合于一遍扫描的自下而上分析。
7. 已知表达式文法的一条语法规则E→E1+T，对每个文法符号引入nptr属性， 可以写出为该文法建立抽象语法树的、对应于这条规则的语义规则为：___________________ ______________。
8. 在S-属性文法的基础上，LR分析器可以改造为一个翻译器，在对输入串进行语法分析的 同时___________________________。
9. 通过在基础文法中新引入非终结符M，加入形式为____________的新的产生式，可以使嵌
入的语义动作出现在产生式的末尾。
10. 属性计算规则中只能使用相应产生式中的文法符号的属性，这有助于在产生式范围内“ 封装”属性的依赖性。然而，出现在产生式左边的______________ 和出现在产生式右边的__
_________________不由所给的产生式的属性计算规则进行计算，它们由其他产生式的属性 规则计算或者由属性计算器的参数提供。
11. 语义规则可能产生副作用（如产生代码），也可能不是变元的严格函数（入某个规则给 出可用的下一个数据单元的地址）。这样的语义规则通常写成___________________________ ___。
12. 我们可以用一个_________________________来跟踪一个标识符，看它是出现在赋值号的
左边还是右边，以确定是需要这个标识符的地址还是值。
13. 在自下而上语法分析中，若一个产生式匹配输入串成功，或者，在自下而上分析中，当 一个产生式被用于进行归约时，__________________________________________________， 完成相关的语义分析和代码产生工作。
14. S-属性文法自下而上计算属性时，在分析栈中使用一个附加的域val来存放综合属性值。 文法符号是隐含在state中而不是存储在栈中。当把文法符号放入栈中时，那么当第i个state 对应符号为A时，val[i]中就存放____________________________________________________ _。
15. 对于一个属性文法，?A→X1X2…Xn∈P, 其每个语
义规则中的每个属性都是一个综合属性;或者，Xj(1≤j ≤ n)是一个继承属性， 这个继承属性仅依赖于: ①__________________________________________________________ ②__________________________________________________________ 则，该属性文法是L-属性文法。
解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.
13. 14. 15.
二.判断题
1. 非终结符只有综合属性，由词法分析器提供。（ ）
2. S—属性文法一定是L—属性文法。（ ）
3. 只含有综合属性的属性文法是S-属性文法。（ ）
4. 只含有继承属性的属性文法称为-L属性文法。( )
5. 语法制导翻译可以基于语法分析树，也可以基于抽象语法树，两种情况所采用的基本方 法是一样的。（ ）
6. 翻译模式既适于自顶向下分析，又适于自底向上分析。（ ）
7. 用于自顶向下分析的翻译模式，其基础文法中不能含有左递归。（ ）
8. 在基础文法中增加标记非终结符不会导致新的语法分析冲突。（ ）
9. 对L－属性文法，不用显式构造语法树就可以实现翻译。（ ）
10. 在翻译模式中，和文法符号相关的属性和语义规则（语义动作），用花括号括起来，插 入到产生式右部或左部的合适位置上。（ ）
11. 语法制导定义中文法符号的一个属性，既可以是综合属性，同时又可以是继承属性。（ ）
12. 在抽象语法树中，操作符和关键字都不作为叶子结点出现，而是把它们作为内部结点。 （ ）
13. 一般来说，语法制导翻译是基于语法分析树的，基于抽象语法树无法进行语法制导翻译 。（ ）
14. 在必要的时候引进标记非终结符，可以实现LR分析过程中对L-属性文法进行计算。虽然
任何LL(1)文法也是LR(1)文法，但是，当标记非终结符加入到LL(1)文法时可能会引起分析冲 突。（ ）
15. 尽管把和文法符号相关的属性和语义动作用花括号括起来插入到了产生式右部的合适位
置上，翻译模式还是不能给出使用语义规则进行计算的顺序。( )
解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.
三.单项选择题
1. 文法开始符号的所有________作为属性计算前的初始值。 a. 综合属性 b. 继承属性 c. 继承属性和综合属性 d. 都不是
2. 对应于产生式A→XY继承属性Y.y的属性计算，可能正确的语义规则是________。 a. A.a:=f(X.x，Y.y)；b. )Y.y:=f(A.a，Y.y)；c. Y.y:=f(X.x)；d. A.a:=f(Y.y)；
3. 描述文法符号语义的属性有两种，一种称为_____，另一种称为______。 a. L-属性 b. R-属性 c. 综合属性 d. 继承属性
4. 出现在产生式________和出现在产生式________不由所给的产生式的属性计算规则进行 计算，而是由其他产生式的属性规则计算或者由属性计算器的参数提供。 a. 左边的继承属性；b. 左边的综合属性；c. 右边的综合属性；d. 右边的继承属性
5. 描述文法符号语义的属性，综合属性值的计算依赖于分析树中它的________的属性值； a. 父结点 b. 子结点 c. 兄弟结点 d. 父结点与子结点 e. 父结点与兄弟结点
6. 描述文法符号语义的属性，继承属性值的计算依赖于分析树中它的______的属性值。 a. 父结点 b. 子结点 c. 兄弟结点 d. 父结点与子结点 e. 父结点与兄弟结点
7. 一般来说，对出现在产生式右边的__________ 和出现在产生式左边的_______ 都必须提 供一个计算规则。
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