西理工编译原理试题集1-7

01-普通作业一（第一章）

一、选择题（从备选项中选出一个或多个正确答案）。

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. 词组

二、判断题（对于下列陈述中正确的说法选择回答“对”，否则选择回答“错”）。 1. 编译程序是一种常见的应用软件。 2. C语言的编译程序可以用C语言编写。

3. 编译方式与解释方式的区别之一在于是否生成目标程序。 4. 中间代码生成是编译程序不可或缺的部分。 5. 含有优化的编译程序执行效率高。

三、解释下列术语： （1）编译程序 （2）源程序 （3）目标程序

（4）编译程序的前端 （5）后端 （6）遍

四、 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？ 并画出编译程序的总体结构图。

五、何谓翻译程序、编译程序和解释程序？它们三者之间有何种关系？

参考答案：

一、选择题

1. D 2. A 3. AC 4. C 5. B 二、判断题

1.错 2.对 3.对 4.错 5.错 三、

(1)把用高级程序设计语言书写的源程序，翻译成等价的计算机汇编语言或机器语言书写的目标程序的翻译程序。

(2)源程序，是指未经编译的，按照一定的程序设计语言规范书写的，人类可读的文本文件。 (3)为源程序经编译可直接被计算机运行的机器码集合，在计算机文件上以.obj作扩展名。 (4)编译程序的前端通常指：词法分析、语法分析、语义分析等生成最终代码以前的一系列步骤。

(5)后端包含代码优化和目标代码生成部分。

(6)对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。

四、数据结构、分析部分、综合部分、结构。 五、

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

本章要点

1. 程序语言的定义；

2. 高级程序语言一般结构和主要共同特征； 3. 正确理解上下文无关文法基本概念，包括：

文法的定义、推导、句型、句子、语言、语法树、二义性等； 4. Chomsky文法分类；

本章目标

掌握和理解程序语言的定义、高级语言的一般特征及程序语言的语法描述。

本章重点

1. 语法，词法规则与语法规则； 2. 语义和语义规则； 3. 数据类型与操作；

4. 推导，最左推导和最右推导； 5. 语法分析树和二义性；

本章难点

1. 二义性文法；

2. Chomsky各个文法类；

作业题

一、单项选择题：

（按照组卷方案，至少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 7. 文法

S→(L)|a L→L，S|S 中，下面

是该文法中的终结符号。 b. 1

c. 2

d. 3

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型文法可由（ G ）识别。

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*

一．答案：1. c.；2. a.；3. b；4. c；5. d；6. d；7. b；8. d；9. d；10. a；11. b；12. c；13. b； 14. c；15. d；

）。

d. xnyxn（n≥0）

二、填空题：

（按照组卷方案，至少15道小题）

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

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

3. 对于文法G，仅含终结符号的句型称为 。 4. 设有文法G[S]，其部分产生式: E→E+T | T

T→T*F | F F→(E) | 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=({a},{S}S, P )，且P: S→aS | ?，则该语言为 。

10. 已知某语言为{?cwR|?∈{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. VN={E，T，F}，VT={+，*，(，)，a}；5. 句子；6. 右线性文法和左线性文法；7. 开始符号，产生式集合，终结符集合，非终结符集合；8. S→AB；A→aAb|?；B→aBb|?；9. {an|n≥0}；10. S→aSa|bSb|?；11. 任何一步???都是对?中的最右非终结符进行替换。12. iii↑*+；13. {a2n+1|n≥0}；14. 所有那些没有后代的末端结点从左到右排列起来；15. ?∈(VN∪VT)*且至少含有一个非终结符，而?∈(VN∪VT)*。

三、判断题：

（按照组卷方案，至少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(G1)=L(G2)。（ ） 10. 正规文法产生的语言都可以用上下文无关文法来描述。（ ） 11. 上下文无关文法比正规文法有更强的描述能力。（ ）

12. 文法的二义性和语言的二义性在概念上是相同的，也就是说，对于某个语言，不可能存在两个以上的文法来描述它。（ ） 13. 二义性是可以判定的，也就是说，可以编这么一个程序，输入该文法后，该程序能确切地给出该文法是否二义的答案。（ ） 14. 说明语句旨在定义名字的性质。编译程序把这些性质登记在符号表中，并检查程序中名字的引用和说明是否一致。实际上，许多说明语句并不能翻译成相应的目标代码。（ ） 15. C语言是一个允许子程序嵌套定义的语言。（ ）

三．答案：1. √；2. √；3. √；4. √；5. √；6. ×；7. √；8. √；9. √；10. √；11. √；12. ×；13. ×；14. √；15. ×；

四、名词解释：

（按照组卷方案，至少3道小题）

1. 二义性文法；2. 推导和直接推导；3. 句型，句子和语言；4. 上下文无关文法；

5. 语法；6. 正规文法（左线性文法和右线性文法）； 四．答案：

1. 如果一个文法存在某个句子对应两棵以上不同的语法树，则称这个文法是是二义性文法。 2. 设A→?是一个产生式，且?、??(VT?VN)*，若?A?=>???，则称?A?直接推出???；或者说，???是?A?的一个直接推导。

如果?1=>?2=>……=>?n，则称这个序列是从?1到?n的一个推导。

3. 设G是一个文法，S是它的开始符号。如果S=>*?，则称?是一个句型。 仅含终结符的句型叫句子。

文法G所产生的句子的全体叫文法G的语言，记为L(G)，L(G)={?| S=>*?，?∈VT*｝。 4. 上下文无关文法G是一个四元式(VT，VN，S，P)，其中： VT是一个非空有限集合，其中的每一个元素称为终结符；

VN是一个非空有限集合，其中的每一个元素称为非终结符，VN∩VT=?； S是一个非终结符，称为开始符号；

P是一个产生式有限集合，每个产生式的形式是P→?，其中P?VN，?∈(VT?VN)*。开始符号S至少必须在某个产生式的左部出现一次。

5. 若文法G= (VT，VN，S，P)的任何产生式为A→?B或A→?，其中，??VT*，A，B∈VN，则称G是右线性文法；

若文法G= (VT，VN，S，P)的任何产生式为A→B?或A→?，其中，??VT*，A，B∈VN，则称G是左线性文法；

左线性文法和右线性文法均为正规文法。

五、简答题：

（按照组卷方案，至少3道小题）

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

第一点：文法中不含任何下面形式的产生式：P→P；

第二点：每个非终结符P都必须有用处。也就是说，必须存在含P的句型；或者说，对P不存在永不终结的回路。

2. 什么是二义性文法？从输入串abab来说明下面文法二义吗？

S→aSbS|bSaS|ε

该文法产生的语言是什么？ 答：

如果一个文法存在某个句子对应两棵以上不同的语法树，则称这个文法是二义的。 例如输入串abab，它有两棵语法树如下：

S S a S b S ? a S ? b S b S ? a S ? a S ? b S ?

所以，该文法是二义的。

此文法产生的语言是：所有a的个数与b的个数相等的由a和b组成的字符串。 3. 文法 G[S]为：

S→Ac|aB A→ab B→bc

该文法是否为二义的？为什么？ 答： 对于串 abc

(1)S=>Ac=>abc (2)S=>aB=>abc

即存在两不同的最右推导。所以，该文法是二义的。 或者：

对输入字符串 abc，能构造两棵不同的语法树，所以它是二义的。

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

此文法所表示的语言是什么？ 答：

分析文法的规则：

每使用一次Bc→Cbcc，b、c的个数各增加一个； 每使用一次aC→aaB或aC→aa, a的个数就增加一个；

产生式Bb→bB、 bC→Cb起连接转换作用。

由于A是开始符号，由产生式A→abc推导得到终结符号串abc；由产生式A→aBbc推导得到B后，每当使用产生式Bb→bB、Bc→Cbcc、bC→Cb、aC→aaB就会递归调用B一次，所产生的a、b、c的个数分别增加一个，因此推导所得的终结符号串为abc、aabbcc、aaabbbccc、?所以文法描述的语言为{ anbncn|n>0}. 5已知文法G[Z]:

Z→0U|1V U→1Z|1 V→0Z|0

（1）请写出此文法描述的只含有４个符号的全部句子。 （2）G[Z]产生的语言是什么？

（3）该文法在Chomsky文法分类中属于几型文法？ 答：

（1）0101，0110，1010， 1001

（2）分析G[Z]所推导出的句子的特点：由Z开始的推导不外乎图1所示的四种情形。

Z 0 1 U Z 0 Z U 1 1 Z V 0 Z 1 Z V 0 图 1文法G[Z]可能的几种推导 由Z推导出10或01后就终止或进入递归，而Z的每次递归将推导出相同的符号串：10或01。所以G[Z]产生的语言L(G[Z])={x|x∈(10|01)+ } (3)该文法属于3型文法。

七、应用题：

1. 试分析下面给出的if-then-else语句的文法，它的提出原本是为了矫正dangling-else(else悬挂)文法的二义性：

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，试说明此文法仍然是二义性的。 答：

1. 考虑句子if e then if e then other else if e then other else other 它具有如下所示的两种分析树 stmt expr then e if stmt if matched-stmt expr then matched-stmt e other if esle stmt matched-stmt expr then matched-stmt e other esle stmt matched-stmt other

stmt matched-stmt if expr then matched-stmt e if esle stmt esle stmt matched-stmt expr then e stmt other expr then matched-stmt e other if matched-stmt other

则上面给出的if-then-else文法仍是二义性的。 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) 试说明此文法所产生的语言是全体布尔表达式。 答：

(a) 终结符号为：{or, and, not, (, ), true, false} 非终结符号为：{bexpr, bterm, bfactor} 开始符号为：bexpr

(b) 句子not(true or false)的分析树为： (c) 用归纳法说明如下：

(1) 不含运算的布尔表达式，常数true和false由此文法产生：

bexpr => bterm => bfactor => true bexpr => bterm => bfactor => false

(2) 设结论对于少于n(n≥1)个运算的布尔表达式成立，即若be1和be2是含有少于n个运算的布尔表达式，则有：bexpr=>+be1,bexpr=>+be2。

(3) 对于含有n个运算的布尔表达式，可表示成下面三种形式：

(a) (be1) or (be2) (b) (be1) and (be2) (c) not (be1)

对于(a)：bexpr => bexpr or bterm => bterm or bterm => bfactor or bterm => (bexpr) or bterm =>+(be1) or bterm => (be1) or bfactor => (be1) or (bexpr) =>+ (be1) or (be2) 同理，有：

Bexpr=>+ (be1) and (be2) Bexpr=>+ not (be1)

综上所述，此文法所产生的语言是全体布尔表达式。 3. 已知文法G[S],其产生式为：S→(S)| ?

（a）L(G)是什么？

（b）对于(a)的结果，请给出证明。 答：

(a) 解：L(G)?{()|n?0} (b)证明：

首先证明L(G)?{()|n?0} 对推导次数进行归纳

1):当推导次数为1时，使用产生式S→?，此时左括号与右括号个数为0 2):假设推导次数为n时(a)成立,即: S?(((...S...)))?(((......)))

n?1n?1n?1n?1?nnnn则推导次数为n+1次时，多使用一次产生式S→(S)即:

S?(((...S...)))?(((...S...)))?(((......)))

n?1n?1nnnn?推导次数为n+1次时(a)成立。

根据(1)(2)可得：L(G)?{()|n?0}

nn其次证明{(n)n|n?0}?L(G) 对n进行归纳

1):当n=0时,使用产生式S→? 即可；

2):假设当n=k时,结论成立，即(k)k?L(G)，下面证n=k+1时结论成立。 由(k)k?L(G)，其推导过程如下：

S?(((...S...)))?(((......)))

kkkk?当n=k+1时，推导过程如下：

S?(((...S...)))?(((...S...)))?(((......)))

kkk?1k?1k?1k?1?故(k?1)k?1?L(G)

根据(1)(2)可得：{(n)n|n?0}?L(G) 根据1，2可知：L(G)?{(n)n|?0} 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| - 答：

（1）把anbnci分成anbn和ci两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为： S → AB A → aAb|ab B → cB|ε

（2）令S为开始符号，产生的w中a的个数恰好比b多一个，令E为一个非终结符号，产生含相同个数的a和b的所有串，则产生式如下： S → aE|Ea|bSS|SbS|SSb

E → aEbE|bEaE|ε

(3) 设文法开始符号为S，产生的w中满足|a|≤|b|≤2|a|。因此，可想到S有如下的产生式 （其中B产生1到2个b）： S → aSBS|BSaS|ε B → b|bb

5. 已知文法G[S]:

S→AB A→aA|a B→bB|b

求该文法所定义的语言。 答：

从规则2可推出: a,aa,aaa,?? 从规则3可推出: b,bb,bbb,?? 再从规则1可推出句子：

ab, aab, aabb, aaab, abbb,……

即，从S出发可推出多个a后跟多个b的字符串，且a的个数与b的个数不尽相同。 故： L(G)={ambn| m,n≥1}

6. 考虑下面上下文无关文法G[S]：

S→SS*|SS+|a

(1) 对于符号串aa+a*分别给出最左推导和最右推导过程，并为该串构造语法树。 (2)G[S]的语言是什么？ 答：

(1)此文法生成串 aa+a*的最右推导：

S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a* 此文法生成串 aa+a*的最左推导：

S=>SS*=>SS+S*=>*=>aS+S*=>aa+S*=>aa+a*

(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。

7 令文法G为 N→ D | ND

D→ 0 | 1 | 2 | 3 | 4 | 5 | 6| 7 | 8 | 9 (1) G的语言L（G）是什么？

(2) 给出句子0127、34和568的最左推导和最右推导。 答： （1）

∵N N?ND?NDD?NDDD?NDDDD……?DD……D ∴L(G)=｛d(n+1)|n≥0, d∈{0, 1, …, 9}｝

允许以0开头的自然数（十进制无符号整数）； （2）

0127最左推导：N?ND?NDD?NDDD?DDDD?0DDD?01DD?012D?0127 0127最右推导：N?ND?N7?ND7?N27?ND27?N127?D127?0127 8 写一个文法，使其语言是奇数集，且每个奇数不以0开头。

答：（首先分析题意，本题是希望构造一个文法，由它产生的句子是奇数，并且不以0开头，也就是说它的每个句子都是以1、3、5、7、9中的某个数结尾。如果数字只有一位，则1、3、5、7、9就满足要求，如果有多位，则要求第1位不能是0，而中间有多少位，每位是什么数字（必须是数字）则没什么要求，因此，我们可以把这个文法分3部分来完成。分别用3个非终结符来产生句子的第1位、中间部分和最后一位。

引入几个非终结符，其中，一个用作产生句子的开头，可以是1－9之间的数，不包括0；一个用来产生句子的结尾，为奇数；另一个则用来产生以非0整数开头后面跟任意多个数字的数字串，进行分解之后，这个文法就很好写了。）

令S表示不以0开始的奇数集合。

S → 〈奇数头〉〈整数〉〈奇数尾〉|〈奇数头〉〈奇数尾〉|〈奇数尾〉 〈奇数尾〉→ 1|3|5|7|9

〈奇数头〉→ 2|4|6|8|〈奇数尾〉 〈整数〉→ 〈整数〉〈数字〉|〈数字〉 〈数字〉→ 0|〈奇数头〉

9写一个上下文无关文法CFG，使其语言是能被5整除且不以0开头的无符号整数的集合。（如｛5,10,15，?.｝） 答：

能被5整除的数从形式上看，是以0和5结尾的数字串。题目要求的不以0开头，并要注意0不是该语言的句子。所求文法为： G(S)：S→MF｜5

F→5｜0

M→MD｜N D→N｜0

N→1｜2｜3｜4｜5｜6｜7｜8｜9 10证明下面的文法是二义的：

S→iSeS｜iS｜i

答：（根据文法的二义性的定义，如果要证明该文法是二义的，必须找到一个句子，使得该句子具有两个不同的最右推导或两个不同的语法树。我们首先分析这个文法，根据我们对程序语言的了解，不难发现，这个文法应该是用来表示if?.else?.结构的（用“i”代表“if”或语句集，“e”代表“else”）。因此我们就要到if?.else?结构中去找二义性。我们知道，程序语言一般都规定else部分是和它前面离它最近的没有被匹配的的if语句进行匹配。而上面的这个文法体现不出这种限制，因此我们可以找这样一个句子，在else前面有两个if（如句子iiiei），else和不同的if进行匹配时就会产生不同的语义。） 解答：

考虑句子iiiei，存在如下两个最右推导： S => iSeS => iSei => iiSei => iiiei S => iS => iiSeS => iiSei => iiiei

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 答：

（对于一个包含运算符的语言，运算符的结合顺序、运算符的优先级在文法中反映为递归的方向和推导（或规约）的先后，左递归表明左边的运算先处理，对应的运算符左结合；右递归表明右边的运算先处理，对应的运算符右结合。两个运算符连续出现，后推导出（或先被规约）的，表明其运算先被处理，因此优先级高；反之，先推导出（或后被规约）的，表明其运算后被处理，因此优先级低。） 题意要求：θ1和θ2的优先级相同，θ3的优先级低于θ1、θ2的优先级，因此θ3比θ1、θ2先推导出来，即应为图3所示的四种情形。

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

U U V θ 1θ 3V (1) U U U θ 3V (2) U U θ 1V V U θ 2θ 3V (3) U U U θ 3V (4) U θ 2V 图3可能的文法推导顺序 因此a和b不成立。

又因为优先级相同的运算符从右往左计算，应采用右递归，即应为图4所示的情形。

U U θ 1W (1) U V θ 1V U θ 2W (2 U V θ 2V U θ 3W (3) V θ 3V

图4可能的文法递归结构 故c不成立,应为d。

第三章 词法分析

本章要点

１．词法分析器设计， ２．正规表达式与有限自动机， ３．词法分析器自动生成。

本章目标：

１．理解对词法分析器的任务，掌握词法分析器的设计； ２．掌握正规表达式与有限自动机； ３．掌握词法分析器的自动产生。

本章重点：

1．词法分析器的作用和接口，用高级语言编写词法分析器等内容，它们与词法分析器的实现有关。应重点掌握词法分析器的任务与设计，状态转换图等内容。 2．掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法。 （1）非形式描述的语言 ? 正规式

（2）正规式 ? NFA（非确定的有限自动机） （3）NFA ? DFA（确定的有限自动机） （4）DFA ? 最简DFA 本章难点

（1） 非形式描述的语言 ? 正规式

（2） 正规式 ? NFA（非确定的有限自动机） （3） NFA ? DFA（确定的有限自动机） （4） DFA ? 最简DFA

作业题 一、单项选择题

（按照组卷方案，至少15道）

1. 程序语言下面的单词符号中， 一般不需要超前搜索

a. 关键字 b. 标识符 c. 常数 d. 算符和界符 2. 在状态转换图的实现中， 一般对应一个循环语句

a. 不含回路的分叉结点 b. 含回路的状态结点 c. 终态结点 d. 都不是 3. 用了表示字母，d表示数字，?={l，d}，则定义标识符的正则表达式可以是： 。

(a)ld* (b)ll* (c)l(l | d)* (d)ll* | d* 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、单词在符号表中的位置 D、单词的种别编码和自身值

C、单词的种别编码

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)等价的正规式是 。

A. a*| b* B. (ab)*(a|b)* C. (a|b)(a|b)* D. (a|b)* 19.无符号常数的识别和拼数工作通常都在 阶段完成。

Ａ．词法分析 Ｂ．语法分析 Ｃ．语义分析 Ｄ．代码生成

一．答案：1. b；2. b；3. c；4. d；5.②；6. ②，7.④；8. b；9. ①；10. B；11. A； 12. B；13. d；14. d；15.d；16.d；17.c；18. C；19. A

二、填空题：

（按照组卷方案，至少15道）

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. L(M)=L(M')；3. 单词种别，单词符号的属性值；4. 初态，终态；5. 由while和if语句构成的；6. 源程序，单词；7. 种别编码；8. 存放它的有关信息的符号表项的指针；9. 存放它的常数表项的指针；10. 单词符号的属性信息（属性值）；11. 两个正规式所表示的正规集相同；12. 这条通路上所有弧的标记符号连接起来形成的符号串等于?；13. 正规定义式，识别规则；14. 状态，输入字符，转换函数（或?(s, a)）的值；15. 将搜索器回退一个位置，并令下一个状态图开始工作。

三、判断题：

（按照组卷方案，至少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. ×；

四、名词解释：

（按照组卷方案，至少5道） 1. 状态转换图；

2. 正规式（正规表达式、正则表达式）的形式化定义； 3. 给出确定性有限状态自动机的形式化定义； 4. 给出非确定性有限状态自动机的形式化定义； 5. DFA状态最小化。 四．答案

1. 状态转换图是一张有限方向图，用于识别（或接受）一定的字符串。

在图中，结点代表状态，用圆圈表示；状态之间用箭弧连结；箭弧上的标记（字符）代表在射出结点（即箭弧的始结点）状态下可能出现的字符或字符类。

一张状态转换图只包含有限个状态（即有限个结点），其中一个被认为是初态，而且实际上至少要有一个终态（用双圈表示）。 2. 正规式是采用递归方式来定义的。 （1）?和?都是正规式；

（2）任何a∈?，a是?上的一个正规式；

（3）假定r和s都是?上的正规式，则r|s、r?s、和r*也都是正规式。

3. 一个确定有限自动机（DFA）M是一个五元式：M=(S，?，?，s0，F)，其中：

（1）S是一个有限集合，它的每一个元素称为一个状态； （2）?是一个有限字母表，它的每一个元素称为一个输入字符；

（3）?是一个从S×?到S的单值部分映射。?(s，a)=s'，意思是：当前状态是s，输入字符为a时，自动机将转入下一个状态s'。 s'称为s的后继状态；

（4）s0∈S，是自动机的惟一初态； （5）F?S，是一个终态集合。

一个非确定有限自动机（NFA）M是一个五元式：M=(S，?，?，s0，F)，其中：

（1）S是一个有限集合，它的每一个元素称为一个状态； （2）?是一个有限字母表，它的每一个元素称为一个输入字符；

（3）?是一个从S×?到S的子集的映射。?(s，a)={s1，s2，……，sm}，意思是：当前状态是s，输入字符为a时，自动机将转入的下一个状态可能是s1，或者s2，……，或者sm；

（4）s0∈S，是自动机的惟一初态； （5）F?S，是一个终态集合。

五、简答题：

（按照组卷方案，至少5道）

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

letter?A ?B ?... Z ? a ?b ?... ?z digit ?0 ?1 ?... ?9 id ? letter(letter?digit)*

2. 词法分析器对程序语言的单词符号一般如何分类？ 答：程序语言的单词符号一般可以分为下列五种：

（1）关键字：是有程序语言所定义的具有固定意义的标识符，有时也称保留字或基本字； （2）标识符：用来表示变量名、数组名和过程名等各种名字；

（3）常数：一般有整型、实型、布尔型和文字型等各种类型，是程序执行过程中不变的量； （4）运算符：如＋、－、*、/等各种进行算术逻辑运算的符号； （5）界符：如逗号、分号、括号等。

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

3. 先写出渡河的方法，串中对象顺序为人来回渡河时所运的货物的顺序： ①羊空菜羊狼空羊；②羊空狼羊菜空羊

现给出一个NFA: M=(Σ，Q，0，{9}，δ)

其中Σ=,羊，空，菜，狼}，Q={0，1，2，3，4，5，6，7，8，9}，转形函数： δ(0，羊)=1，δ(1，空)=2，δ(2，菜)=3，δ(2，狼)=5 δ(3，羊)=4，δ(5，羊)=6，δ(4，狼)=7，δ(6，菜)=7 δ(7，空)=8，δ(8，羊)=9

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

digit ?0 ?1 ?... ?9 digits ?digit(digit)* fraction ? . digits

exponent ?E (+ ?- ??) digits )

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

答：(1) ,α|α∈{0，1}*，α中有偶数个0和偶数个1}，即由偶数个0和偶数个1构成的串。

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

答：扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析，识别出一个个的单词符号，其输出结果是单词符号，供语法分析器使用。

一般把词法分析器安排成一个子程序，每当语法分析器需要一个单词符号时就调用这个子程序。每一次调用，词法分析器就从输入串中识别出一个单词符号，把它交给语法分析器。 词法分析器工作的第一步是输入源程序文本。输入串中一般都包含一些没有意义的字符，如：空白符、跳格符、回车符和换行符等编辑性字符除了出现在文字常数中之外，在别处的任何出现都没有意义，而注解部分几乎允许出现在程序中的任何地方。它们不是程序的必要组成部分，预处理时可以将其剔掉。词法分析器一般会构造一个预处理子程序来处理上述任务。

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

答：．∑上的非确定有限自动机M所能识别字的全体L(M)是∑上的一个正规集；同时，对于∑上的每个正规集V，存在一个∑上的确定有限自动机M，使得V=L(M)。

六、应用题：

1. 有一个语言，它接收Σ=,0，1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。

（１）给出该语言的正规式 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化 解法1：

（１）按题意相应的正规表达式是0*(0 | 10)*0*或0*( 100*)*0*。 （２）构造NFA为 0*的NFA为：

? ? 0 ? ?

0 | 10的NFA为：

? ? 1 0 ? 0 ? ?

(0 | 10)*的NFA为：

? ? ? ? 0 ? ? ? 1 ? 0 ?

0*(0 | 10)*0*的NFA为（给各个结点标上序号）

? ? 0 1 ? ? ? 0 2 ? 3 ? 4 5 ? ? 6 1 9 10 0 7 ? 11 ? 0 ? 8 ? 12 ? 13 ? ? ? 14 15 ? 0 16 ? 17

（３）用子集法确定化 I I0 I1 {0，1，3，4，5，——————————————————————{2，7，16}={1，2，3，4，5，6，9，13，14，15，{10}6，9，13，14，15，17} 17}∪{5，7，8，9，13，14，15，17}∪{15，16，17}＝={10，11} {1，2，3，4，5，6，7，8，9，13，14，15，16，17} {1，2，3，4，5，————————————————{2，7，16}，同上 6，7，8，9，13，14，15，16，17} {10，11} ————————————{10}同上 ? {12}＝{5，6，8，9，12，13，14，15，17} {5，6，8，9，12，——————————————————{7，16}＝{5，6，7，8，9，13，14，15，16，17} {10}旧13，14，15，17} 态 {5，6，7，8，9，————————————{7，16}旧态 13，14，15，16，17}

令：{0，1，3，4，5，6，9，13，14，15，17}＝A； {1，2，3，4，5，6，7，8，9，13，14，15，16，17}＝B； {10，11}＝C；

——————{10}旧态 {5，6，8，9，12，13，14，15，17}＝D； {5，6，7，8，9，13，14，15，16，17}＝E； 画出DFA如图所示： 0 0 A 1 B 1 C 0 1 1 D 0 0 E

（４）对该DFA进行状态最小化

?＝{I(1)，I(2)}＝{{C}，{A，B，D，E}} I(1)＝{C}不可再分； 看I(2)＝{A，B，D，E}：

{A，B，D，E}0＝{B，E}，落入了I(2)； {A，B，D，E}1＝{C}，落入了I(1)；

所以，{A，B，D，E}是等价状态，不再分；

因此，从{A，B，D，E}中抽取一个状态作为代表，C不变，得到简化了的DFA如图所示：

0 1 A C 0

解法2：

（２）构造NFA为

0 0 0 ε X 0 ε 1 1 1 0 2 ε 3 ε Y

（3）用子集法确定化 I I0 I1 S 0 1 {X，0，1，3，Y} {0，1，3，Y} {2} 1 2 3 {0，1，3，Y} {2} {1，3，Y} DFA为： 0 0 1 0 1 0 D {0，1，3，Y} {2} 2 2 3 {1，3，Y} {1，3，Y} / 3 4 {2} 4 4 3 A 1 C B

（４）可最小化，终态组为{A，B，D}，非终态组为{C}； {A，B，D}0?{A，B，D}， {A，B，D}1?{C}，

所以A，B，D为等价状态，可合并。

0 1 A C 0

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

（１） 语言L的正规式是：

(a b*a | b)* 或 b*(a b*a b*)*

（２）画出接收该语言的NFA

? ? ? 1 2 ? 3 a 4 ? b 13 ? 14 ? 5 ? 6 ? ? b 7 ? 8 ? 9 a 10 ? 11 ? 12 （3）NFA转换成DFA I {1，2，3，12，13} Ia ————Ib ————S a B A B C {4}={4，5，6，8，9} {14}＝{2，3，11，12，13，14} {4，5，6，8，9} ————{10}＝{2，3，10，11，12，————{7}＝{6，7，8，9} B D E 13} {2，3，11，12，13，14} ————{4}={4，5，6，8，9} ————{14}＝{2，3，11，12，13，C B C 14} {2，3，10，11，12，13} ————{4}={4，5，6，8，9} ————{14}＝{2，3，11，12，13，D B C 14} {6，7，8，9} ————{10}＝{2，3，10，11，12，————{7}＝{6，7，8，9} E D E 13} 得到的DFA为： A b a a b B a a a D b E C b b

（４）对该DFA进行状态最小化

?＝{I(1)，I(2)}＝{{ B，E }，{A，C，D }}

∵{ B，E }a＝{D}，落入I(2)中；{ B，E }b＝{E}；落入I(1)中； ∴I(1)＝{ B，E }不必再分。

∵I(2)}＝{A，C，D }a＝{B}，落入I(1)中；I(2)}＝{A，C，D }b＝{C}，落入I(2)中； ∴I(2)}＝{A，C，D }不必再分。

故，得到的接受该语言的最简DFA是：

b start a A a B

b 解法2

（２）画出接收该语言的NFA

? b a 1 2 b ? a 3

（3）NFA转换成DFA

I {1，3} Ia ————Ib ————S A a B B A {2}={2} {3}＝{1，3} {2} ————{3}＝{1，3} ————{2}={2} B A B 得到的DFA如下：

b start a A a B

b （４）对该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进行状态最小化

提示：(1) 以0开头并且以0结尾的，由0和1组成的符号串。

5已知Σ=,0，1}上正则表达式为(0|1)*0(0|1)(0|1)， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA

（４）对该DFA进行状态最小化

提示：(1) 由0和1组成的符号串，且从右边开始数第3位为0。

6已知Σ=,0，1}上正则表达式为0*10*10*10*， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA

（４）对该DFA进行状态最小化

提示：(1) 含3个1的由0和1组成的符号串。 ,α|α∈{0，1}+，且α中含有3个1 }。

7有一个语言，它接收Σ=,a，b}上所有满足如下条件的字符串：不含子串abb的由a和b组成的符号串的全体。 （１）给出该语言的正规式 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化 提示：正则表达式为：b*(a*|(ba)*)*。

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

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

10. 已知语言为Σ=,a，b}上的、由a和b组成的但是不以bb结束的所有符号串的集合。

（１）写出定义该语言的正则表达式。 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA

（４）对该DFA进行状态最小化

提示：(1) (a|b)*a(a|b|ε)。All the strings of a’s and b’s that end with a, ab or aa. Or：All the strings of a’s and b’s that do not end with bb.。

11已知Σ=,a，b}上正则表达式为(aa|b)*(a|bb)*， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA

（４）对该DFA进行状态最小化 提示：（1）All the strings of a’s and b’s that can be divided into two substings, where in the left substring, the even number of consecutive a’s are separated by b’s while in the right substring, the even number of consecutive b’ are separated by a’s.

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

（１）写出定义该语言的正则表达式。 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化 提示：(0|1)*00。

13已知语言为Σ=,0，1}上所有由0和1组成的二进制串的集合，这些串都是以0打头以0结尾的。

（１）写出定义该语言的正则表达式。 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化 提示：0(0|1)*0。

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. 自上而下分析方法，LL(1)文法 3. 递归下降分析程序构造；

4. 预测分析表的构造及预测分析过程； 5. LL(1)分析中的错误处理。

本章目标

理解和掌握语法分析器的功能、自上而下分析所面临的问题、LL（1）分析法、递归下降分析的构造过程、预测分析程序等内容。

本章重点

1．语法分析器的功能，自上而下的基本概念

2．LL（1）文法的条件及其判别，计算first集和follow集 3．递归下降分析方法、预测分析表的构造及其预测过程。

本章难点

1. 非终结符的First集合，产生式候选的First集合，非终结符的follow集合的求解； 2. 左递归消除；

3. 递归下降分析程序的编写；

作业题

一、单项选择题：

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表示成扩展的巴克斯范式以后，画出它的语法图应该是 。 T F F * 图a T T F * F 图b F * F 图c T F * F 图d

7. 下列文法中，_______是LL(1)文法。

a. S→aSb|ab 8. 设有文法G： S→Ap|Bq A→a|cA

B→b|dB

b. S→ab|Sab c. S→aS|b d. S→aS|a

则，First(Ap)={_______________} a. a,c b. b,d c. p, q d. A, p

一．答案：1. b；2. c；3. d；4. c；5. d；6. 图a；

二、填空题：

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

2. 自顶向下分析会遇到的主要问题是____________________和__________________。 3. 自上而下地为输入串建立一棵语法树，就是为输入串寻找一个______________。 4. 在扩充的巴科斯范式中，用______________表示符号或串α的出现可有可无。

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

6. 文法exp → exp addop term | term 消除左递归的结果为 。 7. 写出E→T | E+T的EBNF范式为 。 8. 扩展的巴克斯范式描述语法的好处是，直观易懂，便于表示 。

二．答案：1. 文法的产生式，单词符号（文法的终结符）2. 左递归，回溯；3.最左推导；4. 方括号（或[?]）；5. 从文法的开始符号出发推导出这个输入串。（或：能否建立一棵与输入串相匹配的语法分析树。）6. exp → term exp′；exp′→ addop term exp′| ?；7. E→T{+T}；8. 左递归消去和左因子提取。

三、判断题：

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

2. 存在一种算法，能判定任何上下文无关文法是否是LL(1)的。 ( ) 3. 一个文法是含有左递归的，如果存在非终结符P，使得P?*?P。（ ） 4. 提取公共左因子的副产品是引进了大量的非终结符和ε产生式。 ( )

5. 把一个文法改造成任何非终结符的所有后选终结首符集两两不相交的办法是消除左递归。( )

6. 若X∈VT，则FIRST(X)={ X }。 ( )

7. 一个文法的预测分析表含有多重定义入口，说明该文法是LL(1)的。（ ） 8. 自上而下分析及自下而上分析中的“下”是指被分析的源程序串。（ ） 三．答案：1. ?；2. ?；3. ×；4. ?；5. ×；6. ?；7. ×；8. ?；

四、名词解释：

1. 左递归；

2. 递归下降分析器； 3. LL(1)文法； 4. 预测分析表 5. 自上而下分析

四．答案：

1.一个文法如果存在非终结符P，P=>+P?，则称该文法是左递归的。

2. 当一个文法满足LL(1)条件时，可以为它构造一个不带回溯的的自上而下分析程序，该程序是由一组递归过程组成的，每个过程对应文法的一个非终结符。这样的分析程序称为递归下降分析器。

3. 一个文法G，如果满足以下条件，则称为LL(1)文法： （1）文法不含左递归；

（2）对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交； （3）对文法中的每个非终结符A，若它存在某个候选首符集包含?，则A的First集合和Follow集合的交集为空。

4. 预测分析表是一个M[A, a]形式的矩阵。其中A为非终结符，a是终结符或“#”。矩阵元素M[A, a]中存放着一条关于A的产生式，指出当A面临输入符号a时所应采取的候选。M[A, a]中也可能存放一个“出错标志”，指出A根本不该面临输入符号a。

5. 自上而下分析是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结点）出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。

五、简答题：

1. 词法分析和语法分析都是对字符串进行识别的，二者有何区别？ 2. 试说明没有一个左递归文法是LL(1)的。 3. 试说明没有一个LL(1)文法是二义性的。 4. 为什么要消除回溯？ 5. 为什么要提取左因子？

6. 下面文法是有左递归吗？若有，提取左递归。 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. 对于任一个左递归文法来说，存在一个A?VN，有A规则序列：

A → A1... A1 → A2... ..................... An→ Aα|β Aα

β。显然，FIRST(Aα)∩FIRST(β)≠Φ。因此，没有一个左递归文法是LL(1)的。

A...，因此，在文法中必有如下的

3. 解：

设有一个LL(1)文法G是二义性的，那么，一定存在一个W∈L(G)，W=a1, a2......, an，有两棵不同的分析树。如果按最左推导构造这两棵分析树，按么，一定有两个最左推导序列，这来年改革最左推导序列的不同在于，于对某一个A∈VN和当前要匹配的ai(1≤i≤n)，分别使用A的两个不同的候选式A→α和A→β进行推导以匹配ai (i) 若α

ε且β

ε，则必有

ai∈FIRST(α)且ai∈FIRST(β)，FIRST(α)∩FIRST(β)≠Φ (ii) 若α和β有一个能推导出ε，比如β

ε，则

ai∈FIRST(α)且ai∈FOLLOW(A)显然，FIRST(α)∩FOLLOW(A)≠Φ 无论(i)还是(ii)，都和G是LL(1)文法矛盾。

4. 假定当前轮到非终结符A去执行匹配任务，A共有n个候选?1、?2、……?n，这时候该用哪一个候选去替换A，原始的办法是采用对所有候选采取“试探”的方法。如果某个候选不成功就需要“回退”。这个回退的过程会导致前次匹配的许多工作推到重来，效率低。而且，最终匹配不成功的时候，难以直到输入串中出错的确切位置。

5. 假定当前轮到非终结符A去执行匹配任务，A共有n个候选?1、?2、……?n，即A→?1|?2|……|?n。A面临的第一个输入符号为a，如果a属于某个First(?i)，则用该?i来匹配A。但是，若a既属于某个First(?i)，又属于某个First(?j)，则说明?i和?i存在共同的左部，也就是说，有共同的左因子。此时无法确定到底是用?i还是用?j来匹配A。所以要消除左因子。

六、应用题

1. 已知文法G[S]：

S → (L) | a

L → L,S | S

ⅰ.消除左递归，若有左因子则提取之；

ⅱ.对（1）中得到的文法求First集合和Follow集合 ⅲ.对（1）中得到的文法构造一个预测分析表； ⅳ.给出对句子(a,(a,a))上的分析动作

1.答案：将所给文法消除左递归得G′： S → (L) | a L → SL′

L′ → ,SL′ |?

实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制，下面构造预测分析表：

根据文法G′有

FIRST(S) = { ( , a } FOLLOW(S) = {#, ) , ′,′- FIRST(L) = { ( , a } FOLLOW(S) = { ) } FIRST(L′) = ,′,′ , ?} FOLLOW(L′) = , ) } 按以上结果，构造预测分析表M如下： 非终结符号 S L L′ 输入符号 ( ) , a S → a # S →( L ) L → SL′ L →SL′ L′ →? L′ → ,SL′ 文法G′是LL(1)的，因为它的分析表不含多重定义入口。 预测分析器对输入符号串(a, (a, a))做出的分析动作如下： 栈 $S $)L( $)L $)L′S $)L′a $)L′ $)L′S, $)L′S $)L′)L( $)L′)L $)L′)L′S $)L′)L′a $)L′)L′ $)L′)L′S, $)L′)L′S $)L′)L′a $)L′)L′ $)L′) 输入 (a, (a, a)) (a, (a, a))$ a, (a, a))$ a, (a, a))$ a, (a, a))$ , (a, a))$ , (a, a))$ (a, a))$ (a, a))$ a, a))$ a, a))$ a, a))$ , a))$ , a))$ a))$ a))$ ))$ ))$ 输出 $ S → (L) L → SL′ S → a L′ → , SL′ S → (L) L → SL′ S → a L′ → ,SL′ S → a L′ →? $)L′ $) $ )$ )$ $ L′ →?

2. 考查文法G(s):

S→( T ) | a + S | a T→T, S | S

ⅰ. 消除文法的左递归，提取公共左因子 ⅱ. 改造后的文法是LL(1)的吗？为什么？

ⅲ. 如果是LL(1)文法，对每个非终结符，写出不带回朔的递归子程序。

2.答案：

ⅰ.消除文法的左递归G ( s )：

S→ ( T ) | a + S | a T→ S T′ T`→ , S T′| ?

再提取公共左因子，最后得到改造后的文法G[S]:

①S→( T ) | a S′ ②S′→ + S | ? ③T→ S T′ ④T′→, S T′ | ? ⅱ.

First(S)={(，a }； Follow(S)={#，‘,’}； First(S’)={＋，ε}； Follow(S’)= {#，‘,’}； First(T)={(，a }； Follow(T)={ ) }； First(T’)=,‘,’ ，ε}; Follow(T’) ={ ) }；

产生式①的两个候选的First集合： Fist(（T）)=｛（｝，First(aS’)={a} 不相交，满足条件。

产生式②，First(S’)∩ Follow(S’)=?； 产生式④，First(T’)∩ Follow(T’)=?；

所以，改造后的文法是LL(1)的， ⅲ.

我们构造不带回溯的递归子程序如下： ①S→( T ) | a S′

PROCEDURE S; DEGIN

IF SYM=′( ′THEN BEGIN

ADVANCE T;

IF SYM=′ ) ′THEN ADVANCE ELSE ERROR END

ELSE IF SYM=′a′ THEN BEGIN

ADVANCE; END

ELSE ERROR END;

②S′→ + S | ? PROCEDURE S′; BEGIN

IF SYM=′ + ′THEN BEGIN ADVANCE;S END END;

③T→ S T′ PROCEDURE T; BEGIIN S; T ′ END;

④T′→, S T′ | ? PROCEDURE T′; BEGIN

IF SYM=′ , ′ THEN BEGIN

ADVANCE; S; T′ END END;

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)文法. 3. 答案：

(a) FIRST(S) = { u } FOLLOW(S) = {#} FIRST(B) = {w } FOLLOW(B) = { r, z } FIRST(D) = { x, y, ?} FOLLOW(D) = { z }

FIRST(E) = { y, ?} FOLLOW(E) = { x, z } FIRST(F) = { x, ? } FOLLOW(F) = { z }

(b) 该文法的LL(1)分析表为：

非终结符 u S B D E F

(c) 因为M[B, w]有两个产生式 B→Bv, B→w 且FIRST(Bv)=FIRST(w) = { w } 所以不是LL(1)的。

(d) 消除左递归即可。 S→uBDz B→wB′ B′→rB′ | ? D → EF

E = y | ? F = x | ?

4. 已知文法如下： E→T | E+T T→F | T*F F→i | (E)

构造预测分析表，并给出对输入串i*i+i的分析过程。

4.答案：

首先消除左递归，得到新文法如下： E→TE′ E′→+TE′|ε T→FT′ T′→*FT′|ε F→(E)|i

对每个非终结符构造First和Follow集合：

FIRST(E) = FIRST(T) = FIRST(F) = { ( , i }；FIRST(E′) = , + , ε-；FIRST(T′) = , * , ε- FOLLOW(E) = FOLLOW(E′) = , ) , # -；FOLLOW(T) = FOLLOW(T′) = , + ，) ，# } FOLLOW(F) = { * , + , ) , # }

再通过对文法的每个非终结符的任意候选都构造出First集合：

FIRST(TE′)= ,(,i-； FIRST(+TE′)=,+- ；FIRST(FT′)=,(,i-；FIRST(*FT′)=,*-； FIRST(（E）)={(} 得到预测分析表如下：

z r w x y # S→uBDz B→Br B→w E→y F→x D→EF D→EF E→? F→? D→EF D→EF E→?

E E→TE′ E→TE′

E′ E′→+TE′ E′→ ? E′→ ?

T T→FT′ T→FT′

T′ T′→ ? T′→*FT′ T′→ ? T′→ ? F F→i F→(E) i + * ( ) # 对输入串的分析过程如下：

5. 文法G1：

S→a|^|(T) T→T,S|S

(1) 证明文法G是LL(1)文法。 (2) 构造LL(1)分析表。

(3) 写出句子（a,a）#的分析过程。

5. 答案：

（1）先消除左递归，得到文法G2： 0) S→a 1) S→^ 2) S→( T ) 3) T→S N2 4) N2→, S N2 5) N2→ε

求非终结符的First和Follow集合：

S T N2

FIRST { a，^，( } { a，^，( } { ,，ε -

FOLLOW { #，,，) } { ) } { ) }

对左部为N2的产生式可知： FIRST （, S N2）={，} FIRST （ε）=,ε-

FIRST(, S N2) ∩ FIRST(ε)=?;

且：FIRST(N2) ∩ FOLLOW(N2)= ? 所以文法是LL(1)的。

得到预测分析表 ： a ^ ( ) , # S S→a S→^ S→( T ) T T→SN2 T→SN2 T→SN2 N2 N2→ε N2→,SN2

也可由预测分析表中无多重入口判定文法是LL(1)的。 对输入串（a,a）#的分析过程为： 分析栈 输入串 所用产生式 #S a,a)# #)T( #)T #)N2S #)N2a #)N2 #)N2S, #)N2S #)N2a #)N2 #) # a,a)# ,a)# ,a)# ,a)# a)# a)# )# )# # # # S→(T) T→SN2 S→a N2→,SN2 S→a N2→ε 可见输入串（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 构造一个预测分析器(表)。

答案：

消除左递归和提取左因子

bexpr → bterm bexpr′

bexpr′ → or bterm bexpr′ | ? bterm → bfactor bterm′

bterm′ → and bfactor bterm′ | ?

bfactor→ not bfactor | (bexpr) | true | false

First(bexpr)=First(bterm)=First(bfactor)={ not, (, true,false } First(bexpr′)=, or , ? } First(bterm′)=, and, ? }

Follow(bexpr)=Follow(bexpr′)=, ) , $ - Follow(bterm)=Follow(bterm′)=,or , ) , $- Follow(bfactor)={and , or, ) , $}

8. 已知G[R]的产生式如下: R → R′ | ′T | T T → TF | F F → F* | C C → (R) | a | b

构造它的LL(1)分析表，并写出对输入串a|ba*的分析过程。

答案：

①消除上面文法中的左递归

R → TR′

R′ → ′|′ TR′ | ε T → FT′ T′ → FT′ | ε F → CF′ F → *F′ | ε C → (R) | a | b

②计算FIRST(α)和FOLLOW(A)

③构造LL(1)分析表。

9. 已知文法如下：

S→S*T | S/T | T T→T+F | T-F | F F →(S) | i | i e i

构造预测分析表，并给出对输入串i/i*i+i的分析过程。

10. 已知文法：

S→Ac|c A→Bb|b B→Sa|a 构造预测分析表，给出对输入串cabc的分析过程。

11. 已知文法G： S → ( L | a L → S , L | )

（1）构造文法 G 的预测分析表。 （2）若输入串为“（ａ，）”，请给出语法分析过程。

解（１）

1）求各非终结符的 FISRT 集和 FOLLOW 集： FIRST(S) = { (, a ) FIRST(L) = { a }? FIRST(S) = { (, ), a }

FOLLOW(S) = , ′,′, # - FOLLOW(L) = FOLLOW(S) =, ′,′, # - 2）预测分析表： ( a , } # S S→ ( L S→ a L L→ S , L L→ S , L L → ) （２）对输入串 “（ａ，）”的分析处理过程如表1所示。 表1 对输入串 “（ａ，）”的分析过程

步骤 分析栈 输入串 ０ １ ２ ３ ４ ５ ６ ７ ８ ＃Ｓ ＃L( ＃L ＃L, a ＃L, ＃L ＃） ＃ 所用产生式 （ａ，）＃ （ａ，）＃ S → ( L ａ，）＃ ａ，）＃ ，）＃ ）＃ ）＃ ＃ L → S , L S→a L → ) ＃L, S ａ，）＃

12. 给定文法

Ｇ＝({ i，d，′(′，′)′ }，{Ｅ，Ａ}，Ｅ，Ｐ) 其中 Ｐ：

E →iA E →EA A → i A →d A → (E)

(1)消除左递归；

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

(1)消除左递归后的文法为: E → iAE′

Ｅ′→ ? | AE′ A → i A →d A → ( E )

(2)各非终结符的 FISRT集和FOLLOW集 FIRST( E ) ={i}

FIRST(E′) = ,i, d, (, ?) FIRST( A ) ={i, d, () FOLLOW( E ) ={?, # } FOLLOW(E′) =, -, # -

FOLLOW( A ) ={i, d, (, ), # }

(3)改写后文法的预测分析表： E i d ( ) # E→iAE′ A→d E′ E′→AE′ E′→AE′ E′→AE′ E →? E→ ? A A→i A→ (E) 预测分析表中无多重入口,因此该文法是 LL(1) 文法.

13. 已知文法： A→aABe|a B→Bb|d

ⅰ.消除左递归，若有左因子则提取之；

ⅱ.对（1）中得到的文法求First集合和Follow集合 ⅲ.对（1）中得到的文法构造一个预测分析表； ⅳ.给出对句子aadb上的分析动作

答案：

改写文法为： 0) A→a N3 1) N3→A B e 2) N3→ε 3) B→d N2 4) N2→b N2 5) N2→ε

A B FIRST FOLLOW {a} {d} {#,d} {e} {e} {#,d} N2 {b,ε} N3 {ε,a}

Predicting Analysis Table

A B a A→a N3 e b d # N3→ε B→d N2 N3→ε N2 N2→ε N2→b N2 N3 N3→A B e

由预测分析表中无多重入口判定文法是LL(1)的。

14. 已知文法：

S→Aa|b A→SB

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