两个a或相继两个b的字。

图3.5 状态转换图

2.3.3 非确定有限自动机(NFA)

设一个确定的有限自动机（DFA）M是一个五元式M=(S,Σ,f,S0, Z)其中 1. S是一个有限集，它的每个元素称为一个状态；

2.Σ是一个有穷字母表，它的每个元素称为一个输入字符； 3. f是一个从S×Σ*到S的子集的映照，即 f：S×Σ*? 2S 4. S0?S，是非空初态集；

5. Z ?S，是一个终态集（可空）。

2.3.4 正规文法与有限自动机的等价性

对于正规文法G和有限自动机M，如果L（G）＝L（M），则称G和M是等价

的。关于正规文法和有限自动机的等价性，有以下结论： （1） 对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机

（FA）M，使得L（M）＝L（G）。

（2） 对每一个FA M，都存在一个右线性正规文法GR或左线性正规文法GL，

使得L（M）＝L（GR）＝L（GL）

2.3.5 正规式与有限自动机的等价性 我们可以证明：

（1） 对任何FA M，都存在一个正规式r，使得L（r）＝L（M）。 （2） 对任何的正规式r，都存在一个FA M，使得L（M）＝L（r）。

上述结论加上前面章节所证明的结论，说明正规文法、正规式、确定有限自动机和非确定有限自动机在接收语言的能力上是互相等价的。 2.3.6 确定有限自动机的化简 等价状态；最少化。 2.4 词法分析器的自动产生

教学目的：使用状态转换图构造词法分析程序；上机实践LEX的实现。 2.4.1 语言LEX的一般描述

一个LEX源程序主要包括两部分。一部分是正规定义式，另一个是识别规则。 产

生式(也称产生规则或简称规则)是定义语法范畴的一种书写规则。一个产生式的 形式是 A?a 其中，箭头(有时也用：：＝)左边的A是一个非终结符，称为产生式的左部符号；箭头右边的a是由终结符号或非终结符号组成的符号串，称为产生式的右部。我们有时也说，产生式A?a是关于A的一条产生规则。产生式是

9

用来定义语法范畴的。

例如，令i 代表已定义的范畴?变量?，那么，产生式 算术表达式?i 意味着把?算术表达式?这个范畴定义为?变量?。在有的书上，???也用?：：＝?表示：这种表示方法也称巴科斯范式。 2.4.2 超前搜索

在某些语言中，要识别一个单词符号必须超前看若干字符。 2.4.3 LEX的实现

LEX的编译程序旨在将一个LEX源程序改造为一个词法分析器L，这个词法分

析器L将像有限自动机那样工作。

相关介绍：人们已建立了多种编制部分编译程序或整个编译程序的有效工具。有些能用于自动产生扫描器(如LEX)，有些可用于自动产生语法分析器(如YACC)，有些甚至可用来自动产生整个的编译程序。这些构造编译程序的工具称为编译程序——编译程序、编译程序产生器或翻译程序书写系统，它们是按对源程序和目标语言(或机器)的形式描述(作为输入数据)而自动产生编译程序的。

10

授课题目（教学章、节或主题）： 第三章 语法分析-上下文无关文法、形式语言和文法 教学目的、要求（分掌握、熟悉、了解三个层次）： 课时安排 授课时间 6 第3周 第3-6节 第4周 第1、2节

理解和定义上下文无关文法，为学习和构造编译程序打下良好基础。 理解语言和文法的定义 掌握文法的等价变换及语法描述方法 了解文法的分类 教学重点和难点：文法的直观概念、文法和语言的形式定义、文法的类型、语法树和二义性、文法中的实用限制、句型的分析 授课类型（请打√）：理论课? 讨论课□ 实验课□ 练习课? 其他□ 教学方式（请打√）：讲授? 讨论□ 示教□ 指导? 其他□ 教学资源（请打√）：多媒体? 模型□ 实物□ 挂图□ 音像□ 其他□ 讨论、思考题、作业： P36：6，8，11 教学内容 3.1.1 上下文无关文法

箭头‘-->’读为?定义为?，直竖‘|’读为?或?，它们是元语言符号。在后面

的讨论中，根据不同情况，我们将用大写字母A、B、C…或汉语词组(如，算术表达式)代表非终结符号，特别是用小写字母a、b、c…代表终结符，用α、β、γ等代表由终结符和非终结符组成的符号串。为简便起见，当引用具体的文法例子时，仅列出产生式和指出开始符号。 例如，下面是一个上下文无关文法：

E-->i|EAE A-->+|*

其中，E、A是非终结符，E是开始符号，而i、+和*是终结符。

一个上下文无关文法如何定义一个语言呢?其中心思想是，从文法的开始符号出发，反复连续使用产生式，对非终结符施行替换和展开。例如，我们考虑下面的文法G:

E-->E十E | E*E | (E) |i

其中，唯一的非终结符E可以看成是代表一类算术表达式。我们可以从E出发，进行一系列的推导，推出种种不同的算术表达式来。例如，根据规则E一>(E)我们可以说：从‘E’可直接(一步地)推出‘(E)’。与前面一样，我们用‘?’表示?直接推出?，这样，这句话就可表示为:E?(E)。若对‘(E)’中的E使用规则E-->E+E，就有

(E)?(E+E)。即，从‘(E)’可直接推出‘(E+E)’。把上述这两步合并起来，就有

E?(E)?(E+E)。再对‘(E+E)’中的E相继两次使用规则E-->i之后，我们就有(E) ?(E+E)?(i+E)?(i+i)。

11

我们称这样的一串替换序列是从E推出(i+i)的一个推导。这个推导提供了一个证明，证明(i+i)是文法(2.1)所定义的一个算术表达式。注意，推导每前进一步总是引用一条规则(产生式),而符号‘?’指仅推导一步的意思。

我们可以用一种图示化的方法来表示这种推导，如下图2.1，说明He gave me a book是一个语法正确的句子。这种图形表示称为语法分析树。

定义 ?he gave me a book‖这个英文句子的规则可以说就是一个上下文无关文法。其中，He，me，book，gave，a等，称为终结符号；<句子>、<主语>、<谓语>、<动词>、<代词>等，称为非终结符号；这个文法最终是要定义<句子>的语法结构，所以<句子>在这里称为开始符号；<间接宾语>--><冠词><名词>这种书写形式称为产生式。

归纳起来，一个上下文无关文法C包括四个组成部分：一组终结符号，一组非终结符号，一个开始符号，以及一组产生式。

所谓终结符号乃是组成语言的基本符号，在程序语言中就是以前屡次提到的单词符号，如基本字、标识符、常数、算符和界符等。从语法分析的角度来看，终结符号是一个语言的不可再分的基本符号。 <句子>

<主语> <形容词>

<名词>

<动词>

<谓语>

<宾语>

<

名

<形容词>

he

a boo

图2.1语法树

非终结符号(也称语法变量)用来代表语法范畴。例如，?算术表达式?、?布尔表达式?、?赋值句?、?分程序?、?过程?等，它们都是现今程序语言常见的语法范畴。我们也可以说，一个非终结符代表一个一定的语法概念。因此，一个非终结符是一个类(或集合)记号，而不是一个个体记号。例如，?算术表达式?这个非终结符乃代表一定算术式组成的类。因而，也可以说，每个非终结符号表示一定符号串的集合(由终结符号和非终结符号组成的符号串)。

开始符号是一个特殊的非终结符号，它代表所定义的语言中我们最终感兴趣的语法范畴，这个语法范畴通常称为?句子?。但在程序语言中，我们最终感兴趣的是?程序?这个语法范畴，而其它的语法范畴都只不过是构造?程序?的一块块砖石。

3.1.2 语法分析树与二义性

gave

me

12