编译原理试题集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)文法都不是二义性的。（ ）

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

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 。

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