编译原理课件

第一章编译概述1.1

语言处理与编译程序1.1.1程序设计语言的引入是解决人机对话鸿沟的一个里程碑语言处理程序自然语言数学概念与符号程序设计语言机器指令人类的“计算”思维形式表示方法计算机的“计算”方式**语言处理与编译程序1.1.2程序设计语言分类程序设计语言是遵守一定规范的、描述“计算”（Computing）过程的形式语言。一般可以划分：低级语言 低级语言是面向机器的语言，它是为特定的计算机系统设计的语言。如：机器指令、汇编语言是低级语言。高级语言 高级语言是与具体计算机无关的“通用”语言，它更接近于人类的自然语言和数学表示。如：FORTRAN、Pascal、C、JAVA等等高级语言。其他语言 如：控制命令语言、查询语言、脚本语言等。**语言处理与编译程序1.1.3语言处理程序翻译程序(Translator)

翻译程序是一种语言处理程序，它将输入的用程序设计语言（源语言）书写的程序（源程序）转换为等价的用另一种语言书（目标语言）写的程序（目标程序）。 若源语言是汇编语言，目标语言是机器语言，称这种翻译程序为汇编程序。 若源语言是高级语言，目标语言是低级语言，称这种翻译程序为编译程序。

若源语言是高级语言，目标语言是另一种高级语言，称这种翻译程序为转换程序。**语言处理与编译程序解释程序（Interpreter） 解释程序是一种语言处理程序，它对源程序逐个语句地进行分析，并根据每个语句的含义执行语句指定的功能。编译程序（翻译程序）与解释程序主要的不同是：编译程序将先生成目标程序，再执行目标程序，而解释程序不生成目标程序，边翻译、边执行。形象地说，这类似于自然语言中的“笔译”与“口译”。翻译与解释相结合的方法是一种不错的方法：即先将源程序翻译为中间语言表示的代码，然后再解释执行。例如，JAVA语言的源程序翻译为一种称为Bytecode的中间代码，再通过JAVA虚拟机解释执行。

**语言处理与编译程序编译程序的一个实例FACOMM-340的C语言编译器

程序名意义功能CV替换程序\、$等字符的替换CPP预处理程序#include、#define等的处理CSA词法、语法、语义分析程序生成中间代码CCG代码生成程序生成汇编指令ASM汇编程序生成二进制机器指令LINK连接装配程序生成可执行程序**语言处理与编译程序相关说明CV、CPP与语言、机器相关，ASM、LINK与机器相关，而CSA、CSG组成了编译程序的主体。称CSA为编译器的前端独立于目标语言，称CSG为编译器的后端面向目标语言。遍 在编译过程中，扫描一遍源程序（输入文件），经处理形成一个输出文件，称为一遍。 合理地决定“遍数”，可提高效率（时/空）LINK程序

linker：连接程序： 多个不同的目标文件 一个可执行文件

loader：装配程序：相对地址 绝对地址**语言处理与编译程序编译器所在的集成环境 编辑器（Editor)

调试器（Debugger)

描述器（Profiler)

项目管理器（ProjectManager)等**编译程序概貌1.2编译过程和编译程序的基本结构

抽象地看：源程序（S）编译程序（C）目标程序（T）出错信息（E）**

这是一个逻辑模型

独立于具体的语言和机器**以赋值语句pos:=init+rate*60为例来了解编译的全过程词法分析

(LexicalAnalysis)功能：a)扫描源程序的字符串，识别出意义独立的最小的词 法单位——单词（Token）。b)删除注解、空格、回车及与输入介质有关的符号。c)报告词法错误。 如上述赋值语句经过词法分析后输出为如下单词：

(ID,pos)(OP,:=)(ID,init)(OP,+)(ID,rate)(OP,*)(CONST,60)**语法分析

(SyntaxAnalysis)功能：对输入的单词串，按程序设计语言的语法规则，检查源程序句法正确性。例如某语言关于赋值语句的语法规则是：赋值语句是：ID:=EXPID、CONST是EXP若EXP1和EXP2是EXP，则EXP1+EXP2、EXP1*EXP2、(EXP1)是EXP。 可以通过自顶向下或自底向上的句法分析方法，建立分析树（又称

句法树、推导树）进行句法分析。

**对此例，分析树为：**语义分析

(SemanticAnalysis)功能：检查语义的正确性，完成语义解释及必要的转换。例如：此例中各变量的数据类型是float，由于rate与60的类型不同就应该进行转换，即将60转换为60.0。中间代码生成

（IntermediateCodeGeneration）

功能：将单词串转换为等价的中间代码串。 常见的中间代码 有：四元组、三元组、 逆波兰（后缀）表示等。上例中的赋值语句可翻译为（四元组形式）：(float，，60，t1)(*，ID.rate，t1，t2)(+，ID.init，t2，t3)(:=,t3,,ID.pos)其中t1，t2，t3是临时变量、ID.x是x在符号表中的位置。

**代码优化

(CodeOptimization)功能：以提高目标代码运行的时/空间效率为目的 的对中间代码进行等价变换。常见的方法有：删除无用赋值和多余运算、常量合并、运算强度削弱、代码外提、复写传播等等。此例中的中间代码通过优化可为：(*，ID.rate，60.0，t1)(+，ID.init，t1，t2)(:=，t2，，ID.pos)代码生成（CodeGeneration）功能：将中间代码串转换为汇编代码或机器指令。**代码生成此例中优化后的中间代码可生成如下的汇编代码：LOADR0,drate(R3)LOADR1,d60.0(R3)MULTR0,R1LOADR0,dinit(R3)ADDR0,R1STORER1,dpos(R3)其中R3是基地址寄存器，dx是x的位移（相对于R3的内容）。

**出错处理

(ErrorHandle)功能：显示出错的位置、性质，限制出错的影响，为尽可能多地发现错误做些恢复工作。符号表管理

(Symbol-TableManagement)功能：管理源程序中各种数据对象及其各种属性，提供包括生成、查询、更新等各种功能。

**编译程序的生成方法1.3编译程序的生成方法1.3.1手工生成 完全由人采用低级语言开发编译程序，工作量很大。1.3.2自动生成 利用自动生成工具开发编译程序。如：

LEX词法分析程序的自动生成程序

YACC、LLgen语法分析程序的自动生成程序

GAG、CGSS代码生成程序的自动生成程序**1.3.3其他编译模式前面讨论的编译模式称为“完全编译”。其他编译模式有：交互式编译——允许通过交互方式处理源程序中的错误，及时改错。允许部分或逐步测试。增量编译——允许在修改了部分程序结构后仅对该修改部分重新编译，而不一定对整个程序进行编译。问题：如何实现？**第二章文法与语言的基本知识2.1概述程序设计语言是一种形式语言，与自然语言既有相似的性质又有本质的不同。最主要的区别是：形式语言的规则简单、严格、无例外、无二义性。编译程序的正确转换建立在对程序设计语言的精确定义和描述基础上。语法——文法是描述语言语法的形式规则语义——语言中各语句的含义语用——从使用者的角度对语言的描述本章将介绍形式语言和形式文法的基本概念，这是整个编译原理的基础。**基本概念2.2基本概念2.2.1符号与符号串用程序语言书写的程序一般由一些基本符号组成。下面是一些常见的基本符号： 字母：a,b,c,…,x,y,z

数字：0,1,…,9

其他符号：+,-,*,/,=,:，等

在这些符号的基础上，组成如if,then,else,for等关键字、程序的标识符和常量，并进一步组成用户程序。

定义1符号的非空有限集合称为字母表。常用V、

表示。

**符号与符号串例1：

1＝{0,1} 1是二进制数的字母表

2＝{a,b…….z} 2是英文小写字母

3＝{A….Z,0….9,+,-,*,/,.,(,),=,$,’,:}

3是FORTRAN4语言的字母表注意：符号可能是字符的组合如：

5＝{ASCII码}则<=为一个符号再如：pascal语言的:＝C语言的&&等等**符号与符号串

定义2：字母表(符号的非空有限集合)V上的符号 串的递归定义如下：

①空串（一个不含任何元素的符号串）是字母表 V上的符号串。空串用希腊字母

表示。

②字母表V中任何一个元素a，是字母表V上的符 号串。

③

若x，y是字母表V上的符号串，则它们的并置（将符号串y的符号依次写在符号串x后面所得的符号串）也是字母表V上的符号串，记以xy。

注意：‘’与‘’的不同！

**2.2.2符号串的运算符号串x中的元素的个数称为符号串x的长度，记以|x|。设z＝xy是字母表V上的符号串，则x是符号串z的头（或符号串z的前缀），而y是符号串z的尾（或符号串z的后缀）。若|x|＝1，则x是符号串z的头符号。同样，若|y|=1，则y是符号串z的尾符号。注意，空串

是任何一个符号串的头和尾。当y≠

称x是z的真前缀。当x≠

称y是z的真后缀。并置（连接）是一种运算，满足结合律，但不满足交换律。**例2：字母表

1＝{0,1}

，0，1，00，11，10，01，……是

1上的符号串如x=1001 y=010 则连接xy=1001010 yx=0101001 都是

1上的符号串|x|=4 |y|=3

，1，10，100，1001都是x的头，1是x的头符号

，1，01，001，1001都是x的尾，1是x的尾符号

，1，10，100，1001都是x的前缀，

，1，10，100是真前缀

1001，001，01，1，

都是x的后缀，001，01，1，

是真后缀**定义3：设A，B是二个符号串集合，定义：A∩B={a|a∈A且a∈B}A∪B={a|a∈A或者a∈B}A0＝{} An=AAn-1(n>0)A*=A0∪

A1∪A2∪…∪An

∪……

称为A的闭包A＋=A1∪A2∪…∪An∪……

称为A的正闭包

**由定义可知：A+=AA*=A*A例3：令A=

1＝{0,1}A*={，0，1，00，10，01，11…….}A+={0，1，00，10，01，11…….}令A=3

则任一FORTRAN4语言所编写的程序P，有PA***2.3文法和语言2.3.1文法形式语言是字母表V上所有符号串的集合，当该集合为有限集时可以枚举其全部句子，如为无限集则需找出句子的规律，用文法来表示。定义4：上下文无关文法G是一个四元组：

G＝（VT，VN，P，<S>）其中，VT是非空有限集合，元素称为终结符。

VN是非空有限集合，元素称为非终结符。

P是由产生式组成的非空有限集合。

<S>

VN，是文法G的开始符号。常把文法G记为G[<S>]。**产生式（又称复写/产生规则）产生式是一有序对偶（U，x），一般记以 U→x（或U::=x)

其中：U称为产生式左部，x称为产生式的右部。符号‘→’（或‘::=’）称为元符号含义为“由…..构成”或“被定义为”记V＝VN∪VT

一般要求：VN∩VT＝φ

、UV，xV*，特别：

U

VN

xV

*

且<S>至少在某产生式左部 出现一次，称文法G[<S>]为上下文无关文法。

**例4：简单算术表达式文法G[<E>]定义为：

VT＝{+，*

，(，)，i} VN＝{<E>，<T>,<F>}P:<E>→<E>+<T> <E>→<T> <T>→<T>*<F> <T>→<F> <F>→(<E>) <F>→i

文法G是上下文无关文法**扩展的BNF表示(见P59）扩展的BNF（BackusNaurForm)表示引入一些元符号‘|’ 表示‘或’ 对<U>→x <U>→y: 可表示为：<U>→x|y|…..|z:<U>→z}**‘{’

‘}’表示重复出现n次。 如：{α}表示α连续出现i次，0<=i<=n {α}表示α可连续出现n次，i<=n<=j

例5：产生式<序列>→<语句> <序列>→<序列>；<语句>

与<序列>→<语句>{；<语句>}等价‘[’‘]’表示重复出现0次或1次。

‘(’‘)’表示提取公共符号后留下的 例6：<A>→+<T>|-<T>与<A>→(+|-)<T>等价**语言2.3.2语言定义5：设G是一个文法。如果v=x<U>y，w=xuy

其中：x，y

V*，且<U>→u

P， 则称字符串v直接推导出字符串w。有时候也称为w是v的一个直接推导，或者称w直接归约为v，记为v

w。如果存在一个直接推导序列：v=u0

u1

u2

…

un=w，则称v推导出字符串w，或者称w归约为v，记为v

+w。若v=w或v

+w，则为以v

*w。**直接推导与推导例7：设有文法G1[<S>]的产生式集P为：

<S>→<N><N>→<D>|<N><D><D>→0|1|2|…|9

对如下推导：<S>

<N>

<N><D>

<N><D><D>

<D><D><D>

0<D><D>

02<D>

028

称这样的推导为最左推导。2.<S>

<N>

<N><D>

<N>8

<N><D>8

<N>28

<D>28

028

称这样的推导为最右推导。**直接推导与推导最右推导又称规范推导，记为

。规范推导的逆过程称为规范归约。R**句型、句子与语言定义6：设G[<S>]是一文法，若<S>

*w，w

(VN∪VT)*，则称w为文法G[<S>]一个句型。特别：若w

VT*，称w是文法G[<S>]一个句子。文法G[<S>]句子的全体所组成的集合称为该文法所产生的语言，记以L（G[<S>]）。即L(G[<S>]）={w|<S>

*w，且w

VT*}。例8：对例7的G1[<S>]

<S>

、<N><D>、0<D><D>、028是文法的句型

028是G1的一个句子。语言L(G1[<S>])是什么？如何表示一个语言？**语言语言L(G1[<S>])是一个具有无限多句子的集合，称为无限语言。可以用有限的集合的形式来定义一个无限多句子的语言。给定一个文法，就能唯一确定其语言。给定一种语言，能确定其对应的文法，但文法不唯一。对给定的文法G及任意的符号串w，能否用有限的方法来判定w是否是G的一个句子（句型）？**语言语言L(G)有无限多个句子，这与G的产生式集合P中某些产生式的递归性有关：1.

若<U>→<U>……

P称为直接左递归若<U>→……<U>……

P称为直接递归若<U>→………<U>

P称为直接右递归2.

若<U>

+<U>………

称为左递归若<U>

+…<U>……

称为递归若<U>

+………<U>

称为右递归对文法G1、G2，如L(G1)=L(G2)

称文法G1、G2等价**短语与句柄2.3.3短语与句柄定义7：设G[<S>]是一个文法，并设w=xuy是该文法的一个句型。若<S>

*x<U>y且<U>

+u，则称u为句型w=xuy对非终结符<U>的一个短语。若<S>

*x<U>y且<U>

u，则称u为句型w=xuy相对于非终结符<U>的一个简单(直接）短语。任何一个句型的最左简单短语称为柄短语（句柄）。含有终结符的短语，并且不存在也具有这种性质真子串的短语称为素短语。**P30习题22.12.22.32.42.72.10补充题： 试为如下的语言构造二个（或二个以上的）等价文法，它们接受相同的语言。

①L1={a2n

b|n≥1}②L2={aibjck|i,j,k≥1}习题**语法树（推导树）2.4语法树与二义性2.4.1语法树（又称推导树、分析树）用特殊的树的形式来表示推导一个推导 一棵推导树注意：这是一种专为推导的表示而设计的特 殊的树 **推导树的构造与表示方法：对文法G=（VT，VN，P，<S>）树的每个结点对应一个文法符号，vV∪{}根结点是文法开始符号<S>对<A>VN为标记的结点，其所有的子结点（若有的话）则从左至右标记为x1,x2,…xn,且<A>→x1,x2,…xn

P若某结点标记为

，则必为叶结点，且为其 父结点的唯一子结点。**例1：表达式文法G[<E>]：

<E>→<E>+<T>|<T> <T>→<T>*<F>|<F> <F>→(<E>)|i对句型i*(<E>)的推导为：

<E>

<T><T>*<F><F>*<F>i*<F> i*(<E>)**对应的推导树为：

注意推导树的特殊性**语法树与短语使用推导树计算句型（句子）的短语简单、明了推导<S>

*x<U>y <U>

+u等价于： 等价于：

<S> <U> x<U>y u**因此称u是句型xuy(对<U>)的一个短语等价于：

<S> x<U>y u以为子树根的叶结点的全体<U>**若子树高度为1，则u还是简单短语，最左简单短语为句柄。若u是含有终结符的最小的短语，则为素短语，句型最左边的素短语称为最左素短语（P72）。例2：例1的文法G[<E>]和句型i*(<E>)容易从推导树中看出：短语：i,i*(<E>),(<E>)简单短语：i，(<E>)句柄：i素短语：i，(<E>)**文法的二义性2.4.2文法的二义性定义8：若文法G的一个句子有两棵（或两棵以上）的分析树，则称该句子是二义性的。若文法含有二义性句子，称该文法是二义性文法，否则称该文法是无二义的。例3：文法G1[<E>] <E>→<E>+<E>|<E>*<E>|(<E>)|i

对句子i+i*i有两棵不同的推导树**文法的二义性<E><E><E>*<E><E>+iii表示先‘＋’后‘*’表示先‘*’后‘＋’<E><E><E>+<E><E>*iii**对文法的二义性讨论一个句子有两棵不同的推导树，说明其含义（语义）是不唯一的，这给编译带来问题（不确定）。对某些二义性文法，如果确定其中一种含义（语义）而排除另一种（或多种）含义（称为消除二义性规则），则可将其改造成等价的无二义性文法。例4：若规定先‘*’后‘＋’及‘＋’、‘*’都是左结合 的。则文法G1[<E>]可改造为算术表达式 文法G[<E>]。这样句子i+i*i只能有一棵推 导树。**对文法的二义性讨论（续）对二义性文法所产生的语言，有的可找到等价的无二义性文法，因此只说文法的二义性，而不说语言的二义性。当然存在这样的语言，不存在它们的无二义性文法。例如：L={aibjck|i=j或j=k,i,j,k

1}。文法的二义性是不可判定的，即不存在一种算法能在有限步内判定该文法是否是二义性的。通常的做法是：找出无二义性文法的一个充分条件，即满足条件的一定是无二义性文法。**形式语言分类2.5形式语言分类1956年Chomsky将文法分成四类：0型、1型、2型和3型文法G＝（VT，VN，P，<S>）

VN∪VT＝

V

、

VN∩VT＝φ

P中产生式的一般形式是α→β，α

V+,α至少含有一个非终结符，β

V*，β可以是空串。 称文法G为

0型文法（短语结构文法）**形式语言分类在0型文法的基础上，再规定：|α|<=|β|

∵

α中至少含有一个非终结符

β不能为

称文法G为1型文法（上下文有关文法）等价定义：

wαz→wβzw,z

V*

α

VN，β

V＋

**形式语言分类在0型文法的基础上，再规定：

<A>→α，其中<A>

VN，α

V*

称文法是2型文法（上下文无关文法）任何含有<U>→ε的产生式（称为ε产生式）的文法不是1型文法。但是含有ε产生式的2型文法可以转化为不含ε产生式的2型文法，转化前后的两个文法所生成的语言至多相差一个ε。**例1：试将如下的含有

产生式的上下文无关文法 （2型文法）G[<S>]转换成等价的不含

产生式的 上下文无关文法。

①<S>

a<A><S> ②<S>

b ③<A>

c<S> ④<A>

解：引入非终结符<AN>与<AY>,<AN>表示不可空， 而<AY>表示可空。随后消除可空的产生式以及 在产生式的右部去除非终结符<AY>即可，因此 G[<S>]可等价表示为：①<S>

a<AN><S> ①’<S>

a<AY><S>②<S>

b ③<AN>

c<S>④<AY>

**最后得到等价的无

产生式的文法G1[<S>]为：①<S>

a<AN><S> ②<S>

a<S>③<S>

b ④<AN>

c<S>注意：两文法不同，但等价！∵语言相同。问题：什么情况下转换前后的二个文法的语言 会 相差

呢？**在2型文法的基础上，再规定：

产生式形式是<A>→x，<A>→x<B>，

<A>,<B>

VN，x

VT*

则称文法是右线性文法。 若规定：x

VT

即<A>→a，<A>→b<B>， <A>,<B>

VN，a,b

VT

则称文法是3型文法（正则文法）。正则文法也可以是左线性文法的特例。适当地引入新的非终结符可以把一个右线性文法转换为等价的正则文法。**例2：试将如下文法G[<S>]转换为等价的正则文法（3型文法）：

①<S>

a<A> ②<S>

<A> ③<A>

abb<S> ④A>

c<A> ⑤<A>

a解：按正则文法的定义，只需对产生式②、③进行等价变换。对产生式③用<A>

a<bbS> <bbS>

b<bS><bS>

b<S>来替代。**对产生式②则用<S>

a<bbS><S>

c<A><S>

a来替代。 因此与G[<S>]等价的正则文法G1[<S>]为：

<S>

a<A>|a<bbS>|c<A>|a <A>

a<bbS>|c<A>|a <bbS>

b<bS> <bS>

b<S>

其中<bbS>,<bS>是新引入的非终结符。**实用限制文法的实用限制 从实用的角度一般规定：文法中不含任何如下形式的产生式：<U>→<U>。<U>是可达的，即从开始符号<S>出发，存在推导<S>

*α<U>β,α、β

V*<U>是有用的，即存在终结符号串γ

VT*，使得<U>

*γ。

**文法与模型文法与模型每一类文法都对应数学模型（识别系统）——自动机。 有限状态自动机 3型文法 下推自动机 2型文法 线性界限图灵机 1型文法 图灵机（Turing） 0型文法编译程序的词法分析程序使用3型文法及其数学模型有限状态自动机。在句法分析中使用2型文法及其数学模型下推自动机。**习题P30习题22.52.62.82.92.11补充题考察如下的文法G[<S>]：

<S>→abcd<A> <A>→a

试将其转换成等价的正则文法。**考察如下的文法G[<S>]： <S>→<A>a<B>|a <A>→<A><B>|b|

<B>→b<B>|

试重写G[<S>]，以便消去

产生式。**第三章词法分析与有限状态自动机词法分析程序的主要功能是识别单词，这将涉及3型文法、正则表达式和有限状态自动机。本章将讨论这三者间的关系。3.1有限状态自动机(Finite-stateAutomate machineFA)**有限状态自动机3.1.1基本概念FA的非形式描述有限状态自动机由3部分组成：

⑴一根输入带：输入带可以理解成由一系列带块组成，每个带块上只含有一个输入符号（终结符号），其全体构成集合VT，特殊符号“

”表示输入符号串的结束，

VT。

⑵一个输入头：初始时，输入头指向第一个带块（即指向输入带最左端的带块），输入头每次将输入头下方带块上的输入符号读入，然后输入头向右移动一个带块。**基本概念 ⑶

一个有限状态控制器：有限状态控制器所能处于的状态的全体组成状态集合Q，Q中有若干特殊状态：一个初始状态q0和若干最终状态qf。开始时有限状态控制器处于初始状态，以后有限状态控制器所处状态由状态转换函数

决定。**基本概念例1令VT={0,1,2,3} Q={S,A,B}2030

S是初态用‘-’表示A是终态用‘+’表示有向弧表示转换**FA的工作过程初始时，FA处于初态，输入头指向第一个输入符，随着带上符号的读入，FA从一个状态转向另一个状态。若遇到如下情况，FA结束工作：输入头指向‘’、FA处于终态。称输入串被FA接受。（如2030）输入头指向‘’、FA不在终态。称输入串不被FA接受。（如203）FA无法转换。称输入串不被FA接受。（如1031）**FA的形式描述定义1：有限状态自动机M是一个五元组：

M＝(VT,Q,

,q0,Qf)，其中：

VT：有限非空终结符集合

Q：有限非空状态集合

：从Q×VT到Q的幂集2Q上的状态转换函数

q0：初始状态，q0

Q Qf：最终状态集，Qf

Q|Qf|≥1

**FA的形式描述对q,q1

Q aVT(q,a)={q1}的含义为：当前状态为q，若输入头所指符号为a，则转向下一状态q1，输入头右移。∵

是Q×VT 2Q上的一个单射

一般地(q,a)={q1,q2,……qn}qiQi=1,2,…n

因此称FAM为不确定的FA，记为NFA。若映射

是Q×VT Q，即对任何q

Q，ai

VT，

(q,ai)至多只有一个元素q’，称FAM是确定性的FA，记为DFA。**FA的形式描述对FA的拓展Q0

Q|Q0|≥1即初态可以是一个集合

：从Q×VT*到2Q上的单值映射，即输入符可以是一个串，包括

称M为一个传递图或转换系统或NFA。例1：M1＝(VT,Q,

,q0,F)VT={a,b}, Q={q0,q1,q2} F={q2}:(q0,a)=q1 (q0,b)=q2(q1,a)=q1(q1,b)=q1 (q2,a)=q2 (q2,b)=q1M1是一个DFA。 **FA的表示3.1.2状态转换图和状态转换表状态转换图：q

Q若q，q’

Q，a

VT，且q’

(q,a)，初态用‘－’标记、终态用‘+’标记qqq’a**状态转换图例2：例1的DFAM1可表示为：—＋q0q2q1abbaa,b**状态转换表状态转换表（矩阵）表的列对应输入符号及特殊符号‘’，行和M的状态q相对应。状态转换表的qi行aj列中填以

(qi,aj)中的状态。表的第一行和M的初始状态q0相对应；‘’这一列和最终状态qf行的元素标以A，以表示该状态是最终状态。**状态转换表例3：例1的DFAM1可表示为：Mab

q0q1q2q1q1q1q2q2q1A**示例例4：设计一个接受以a为头符号和尾符号，中间可出现任意多个a,b的符号串的FAM。解：令：VT={a,b} Q={q0,q1,q2}a—＋q0q2q1aaa,baM是NFA**FA识别的语言格局

FAM的一个格局是二元组（q,w)qQ，w

VT*动作 对q’

(q,a)则FAM的动作记为：

(q,aw) (q’,w) a

VT w

VT*对w

VT*，q0是初态，称w被FAM所接受，表示为：

(q0,w) (qf,) qfF***FA识别的语言定义2：设M是一个FA，w

VT*若：

(q0,w) (qf,) qfF q0是初态 称w是M的一个句子。

M句子的全体称为M的语言，记为：

L(M)={w|(q0,w) (qf,) ,w

VT*}

例5：对例4的NFAM，输入串abba

有：

(q0,abba) (q1,bba)(q1,ba) (q1,a) (q2,) ∵q2

FabbaL(M) L(M)=a|a(a|b)*a****FA的确定化定义3：对FAM与FAM’，若L(M)=L(M’)则称M与M’等价。3.1.4FA的确定化定理3.1对任一给定的NFAM存在一个DFAM’使L(M)=L(M’)。分析： 由定理3.1L(DFA)L(NFA)

由FA的定义L(DFA)L(NFA)

得到 L(DFA)＝L(NFA)**FA的确定化证明：“构造性证明” 对给定的NFAM＝(VT,Q,

,q0,F)

构造一个DFAM’＝(VT’,Q’,’,q0’,F’)令VT＝

VT’Q’＝2Q 即Q’的元素是Q的子集，Q’也是有限集，|Q|=2|Q| 对aVT若({qi1,….qin},a)={qj1,…qjm}令’([qi1,….qin],a)=[qj1,…qjm]Q’M’的初态q0’=[q0]QF’中的元素由Q’中那些至少含有F中一个元素的状态组成，即[qj1,…qjm]F’则qjkF1kn

M’是DFA**FA的确定化再证：L(M’)=L(M)，即要证xVT*

’(q0,x) [qi1,…qik,…qim]F’

(q0,x) {qi1,…qik,…qim}qikF

证明：对x的长度|x|作归纳法

1.当|x|=0时，结论成立

2.假定|x|<n，结论成立

3.当|x|=n, 由’的定义，结论成立****FA的确定化例6：例4的M是NFA可用表的形式表示为：Mab

q0{q1,q2}q1{q1,q2}{q1}q2{q2}AM’ab

[q0][q1,q2][q1,q2][q1,q2][q1]A[q1][q1,q2][q1]确定化**FA的最小化3.1.3FA的最小化一般地说，对给定的一个FAM，可以找到任意多个不同的FAM’，有L(M)=L(M’)，因此得到最小的FA是有意义的。定义4：若FA的二个状态q与q’，对任意一个长度为k或小于k的符号串w，q接受w当且仅当q’接受w，称q与q’是k等价的，否则称q与q’是k可区分的。q与q’等价的充要条件是对k0，q与q’是k等价的。**FA的最小化状态分离法基本思想：对DFA的状态集Q进行k等价类划分，即将Q划分成Qk1,….Qkn的n个子集，子集中的状态是k等价的。然后进行k+1的等价类划分……直至无法进一步划分为止。 则得到的等价子集中各状态等价，可合并为一个状态。**状态分离法具体做法：0等价类划分：将Q划分成F与Q-F二个0等价类。若已经进行了k等价类划分，Q已经被划分成Q1，…，Qn（n2)n个子集，进行k+1等价类划分。对Qi(i=1…n)q,q’Qi，若有aVT，

（q，a）Qj和

（q’，a）Ql，j≠l或

（q，a）存在而

（q’，a）不存在或反之。则将Qi划分为二个子集Qi1，Qi2，使qQi1，q’Qi2

。重复2直至无法进一步划分为止。**状态分离法对每一个子集Qi(i=1…n)，任选一个代表qi，并修改

，修改方法为： 转向Qi中任何一个状态改成转向qi

。若一个状态子集中某一状态是原来的开始状态，则该状态子集的代表就是新的有限状态自动机的开始状态。同理，若一个状态子集中的状态均是最终状态，则该状态子集的代表就是新的有限状态自动机的最终状态。抹去可能存在的无用状态与不可及状态。则DFAM是最小的（或简化的）。**状态分离法例7：试将下图中所示的有限状态自动机M最 小化。**例7续一解：最小化的过程为：初始时的划分由2个子集组成，即：（{A,B,C},{D,E,F,G}）集合{D,E,F,G}不需要进一步划分，考察子集{A,B,C}。由于

（B,a）=D

{D,E,F,G}，而

（A,a）＝

（C,a）＝B

{A,BC}，因此Q可进一步划分为：（{A,C},{B},{D,E,F,G}）。由于

（A,b）＝C

{A,C}， 而

（C，b）＝E

{D,E,F,G}。因此Q可进一步划分为：（{A},{C},{B},{D,E,F,G}）**例7续二这时不能再划分了，得到的最小化的有限状态自动机如下表所示：

Mab

ABCCBDBDCDDDF**习题P55习题31.3.22.3.33.补充题将如下所示的非确定有限状态自动机M确定化和最小化。

**试给出下述每个有限状态自动机所识别的语言

a)b)**c)**正则表达式（REX)3.2正则表达式（RegularExpression）、有限状态自动机、3型文法及其相互间的关系正则表达式又称正规式有限状态自动机(FA)是正则文法（3型文法）的数学模型，正则表达式（REX）所表示的值，即为FA所能接收的语言的全体，因此这三者的关系可用下图表示：FA3型文法REX**正则表达式通常称有限状态自动机和三型文法所接受的语言为正则语言。REX在词法分析中有很重要的作用，它可以精确地表示单词符号的组成，定义单词符号集。3.2.1正规式与正规集如程序设计语言中的标识符（ID）可以用REX表示为：Let(let|Dig)*

其中Let是字母、Dig是数字**正则表达式定义1：设

是字母表。

上的REX及其值——REX所表示的符号串集合（正规集）递归定义如下：

⑴ф、ε是正则表达式，其值表示空集和{ε}；⑵对

中每一字母ai

，ai是正则表达式，其值表 示集合{ai}；

⑶若p,q是REX，值分别为L(p)和L(q)， 则p|q，p·q和p*也是

上的REX， 其值分别是：L(p)∪L(q)，L(p)·

L(q)，

L(p)*。

⑷有限次使用上述规则得到的仍是

上的REX。**正则表达式规则：优先级由高到低为：*，·,|。可用‘（’，‘）’改变优先级。记R*R为R+

值L(R+)=L(R*)L(R)。性质交换律 R|S=S|R结合律 R|(S|T)=(R|S)|TR(ST)=(RS)T分配律 R(S|T)=RS|RT (R|S)T=RT|ST同一律 εR=Rε=R**正则表达式例1．试写出

＝{0，1}上下述集合的REX：

⑴所有以1开始和结束的符号串。

⑵恰含有3个1的所有符号所组成的集合。

⑶集合{01，1}。

⑷所有以111结束的符号串。 解答：

⑴1(0|1)*1|1 ⑵0*10*10*10* ⑶01|1 ⑷(0|1)*111**正则表达式与有限状态自动机3.2.2REX和FA定理3.2（Kleene)设R是

上的一个REX，则存在一个FAM，有L(M)=L(R)。反之亦然。证：1.对给定的REX到FA从REX构造FA可以分两步进行。从REXR到传递图T

XYR－＋**Kleene定理

反复应用下述替代规则，直至所有有向弧都以

中的符号或标记

为止。

A|B

**Kleene定理②消除应用①所得到的传递图中的ε弧，可以分为两步：首先消除ε环路，其次消除其他ε弧。a)ε环路的消除方法：

i．将ε环路的诸项合并为一个顶点。

ii．修改各个相关的有向弧。

iii．若ε环路中某一状态是最终（或初始）状 态，则新顶点是最终（或初始）状态。b）其它ε弧的消除有两种方法：1）子集法：即计算ε-Closure（T），其表示从状态集T中任何一状态沿ε弧可以到达的状态全体。

**Kleene定理

其要点是：从初始状态q0的X=ε-Closure（q0）开始，按如下方法构造状态集：i．令Set＝{X}；ii．若Set中还有未考察过的状态子集Xi，则对于每一输入符号a

VT，计算：

T=ε-Closure（move（Xi,a）），Set=Set∪{T}（其中move(Xi,a)={q|q

δ(p,a),p

Xi}）。重复执行（ii），直至不存在这样的Xi。这样得到的Set即为消除ε弧后的DFA。DFA的初始状态就是ε-Closure（q0），最终状态由那些至少含有一个最终状态的状态子集组成。**Kleene定理2）逐步消除法： 其要点是找到类似于下图所示，但从B再无ε弧引出的ε弧。 删除状态A到状态B的ε弧，对每一条从状态B到状态C标记为ai的弧，增加1条从状态A到状态C标记为ai的弧。若B是最终状态，则让A为最终状态。重复上述过程直至消除全部的ε弧，这样得到的一般是NFA。

**Kleene定理例2：试给出与下图所示的传递图等价的、确定的、最小的有限状态自动机。

**例2（续一）解法一子集法：

M的初始状态为D，而ε–Closure(D)={D，E，G}

令A={D，E，G}，B={D，E，F，G} ∵VT={0，1} ∴ε–Closure(move(A，1))={D，E，F，G} ε–Closure(move(A，0))={F} ε–Closure(move(F，1))={G} ε–Closure(move(G，1))={D，E，G} ε–Closure(move(B，1))={D，E，F，G} ε–Closure(move(B，0))={F}**例2（续二）所以，DFAM如下表所示： 其中A={D,E,F,G}、B={D,E,G}。

注意：状态F与表示该状态是最终状态的标记F的不同。

**例2（续三）解法二逐步消除法：

a)消除状态E到G的ε弧：

**例2（续四）b)消除状态D到E的ε弧：

**例2（续五）消除所有ε弧后得到的状态表

**例2（续六）c)确定化的DFA如下表所示：

**Kleene定理从传递图T到REX设传递图T为：逐步消除个状态或弧得到只剩状态X、Y，消除方法为：略。得到：—εSabc…………dfεεf1f2XY+—RXY＋**正则表达式与有限状态自动机例3：设V={a,b},V上的正则表达式R={ba|a}+

：试设计接收R所表示的符号串集合的确定的，最小的有限状态自动机M。

解：正则表达式R可等价地改写为：R=(ba|a)*(ba|a)或R=(ba|a)(ba|a)*。有限状态自动机M=(V,Q,δ,q0,Qf)，其中V={a,b},Q={S,A,B}，q0=S，Qf={B}，

δ如下图所示,显然M是确定的和最小的。

****3.2.3有限状态自动机与3型文法定理3.3对任一正则文法G，存在有限自动机M，使得L(M)=L(G)。反之亦然。 证：1.设G[<S>]=（VN，VT，p，<S>），令与其对应的M＝（VT，Q，

，<S>，Qf)其中：

①VT，<S>相同，即<S>作为M的开始状态。

②令Q＝VN∪{F}，F

VN ③若<A>→a<B>

P，让

（<A>,a）中含有<B>

若<A>→a

P，让

（<A>,a）中含有F

a

VT，令

（F，a）＝φ ④

令Qf＝{F}

容易证明L(M)=L(G)。(例见P47）**设M是DFAM＝（VT，Q，

，<S>，Qf），令与其对应的G[<S>]=（VN，VT，p，<S>），其中：

①VT，<S>相同，VN＝Q ②若

（<B>,a）＝C，<B>

Q，C

Qf， 让<B>→a<C>

P

若

（<B>,a）＝C，<B>

Q，C

Qf，让 <B>→a

P或<B>→a<C>

P

容易证明L(M)=L(G)。 （例见P49）**3.2.4正则表达式与正则文法定理3.4对任一正则文法G，存在REXR，使得L(R)=L(G)。反之亦然。 证：一、从正则文法G到REXR 1.将G中每个非终结符表示为关于它的正则式方程，得到一个联立方程组。 即对<A>→a<B>|b为：<A>＝a<B>＋b2.如<A>＝a<A>＋b则解为：<A>＝a*＋b3.利用REX的分配律、结合率和交换律求正则式方程组的解R。容易证明L(R)=L(G)。 （例见P36）**二、从REXR到正则文法G对V上的REXR及正则文法G=（VN，VT

，p，<S>）VT=

V。

R让<S>→R。如a，b是REX，则对形如<A>→ab的产生式转换为<A>→a<B>及<B>→b，<B>

VN

。对形如<A>→a*b转换为<A>→a<A>|b。重复使用规则3.和4.，直至每个产生式至多含有一个非终结符。容易证明L(R)=L(G)。（例见P37）**例4：对例3的REXR=(ba|a)*(ba|a)，试设计接收R所表示的符号串集合的正则文法G。

解：正则文法G={VT,VN,P,<S>}，其中 VT={a,b}，VN={<S>,<A>,<B>}先让<S>

(ba|a)(ba|a)*并转换为：<S>

(ba|a)<A><S>

ba<A>|a<A><A>

(ba|a)*<A>

ba<A>|a<A>|ε<S>

ba<A>| <S>

b<B> <B>a<A><A>

ba<A>| <A>

b<C> <C>a<A>注意：<C>可以改为<B>以及消除ε的方法，得：**P为：

<S>

a<A>|b<B>|a<A>

a<A>|b<B>|a <B>

a<A>|a

**习题P55习题33.13.43.53.63.73.83.93.103.11**§3.3词法分析程序的设计和实现词法分析程序从输入串中识别单词。单词的构词规则可由状态转换图（FA）或REX表示。将FA确定化、最小化即得到识别单词的FA。编程实现FA，即得到词法分析程序。**1.词法分析程序的任务及环境词法分析程序的任务是：a)识别源程序组成的输入符号中语义独立的最小的词法单位—单词（token）。b)删除注解和其他与输入介质相关的符号（如空格、回车等）。c)报告各种不符合程序设计语言规定的词法错误。d)符号表的维护（插入、查找…)**单词符号的种类单词是程序语言最基本的语法单位,通常有五种:(1) 基本字：有的称关键字或保留字,如if、while、for、do、goto等(2) 标识符：用户定义各种变量、数组、函数、过程等的名字，以字母打头后接若干个字母、数字。如X2、Len、getword……(3) 常数：如216、31.4……(4) 运算符：如+、=、*、/等；(5) 界限符：如;、:、(、)及双字符界符:=、/*、*/及空白符等。（1）、（4）、（5）常可合为一，分为单、双字符界限符。**单词的编码 词法分析程序输出的是统一格式的单词，形式为：(type,value,lineNo,columnNo)

一般可分为三类：标识符：表示为（ID,addr)，addr是标识符在符号表的位置。常数：表示为（N,addr）addr是常数在常数表的位置。界限符：表示为（DEL,code)，将关键字、运算符、单（双）界限符统一预先编号，则code为界限符的内部码。 **词法分析程序的实现可以有两种方案：把词法分析程序视为语法分析部分的一个子程序，每调用一次词法分析程序就扫描一个单词。把词法分析程序视为编译程序的一个独立模块，词法分析程序一次扫描全部的输入符号。常用的方法是a），优点是不用形成中间文件，直接生成符号表。**2. 词法分析程序的设计识别单词的FA的设计：0137空白字母|数字字母非字母与数字＋＋数字数字非数字界限符非法字符

2456＋＋＋**状态2的处理流程：

查保留字得内部码，输出（DEL，code） 查或送符号表 得到addr,输出（ID,addr)状态4的处理流程： 检查前一单词，决定正负号 转换相应的常数表示（二、八、十六进制） 查或送常数表得到addr，输出（N,addr)YN**状态5的处理流程：

若为‘.’ 按小数点处理，转状态4

取下一字符 是否为双字符界限符 查表得到内部码， 输出（DEL，code)

回送，查表得到内部码，输出（DEL，code)状态6的处理流程：报错Y

Y

N

N

**说明上述的FA只是一个粗框架，具体实现时应根据不同语言的词法规则，作必要的改进和相应的处理。特定要求的处理：如true、false表示真、假常数：NOT、IN等是运算符；.EQ.表示逻辑相等；允许0x1f、35L等作常数等等。无符号数的识别： 如无符号数用REX表示为：

(D+E|D+.D+E|E|.D+E)((+|-)D|D)D*|D+|D*.D+

其中D表示数字0，1，……，9，则相应的最小的DFA为：**0213456－EE+DD－DD.D.E+D+＋D**超前搜索 在FORTRAN语言中，关键字不是保留字，空格不是分隔符。因此：对语句

100DO110I=1，10

（循环语句，DO是关键字）

100DO110I=1.10

（赋值语句，DO110I是标识符）拼字与缓冲区的组织P22的左、右两区的缓冲区组织形式。用getline();读入一行，如:char*fgets(char*S,intn,FILE*fp)

这样拼字时只需移动缓冲区指针即可。

while(*chp==‘’)chp++; **3.词法分析程序的实现FA的状态转换图可以视为一个程序的粗框图：

FA 程序 状态 子程序（程序段） 状态转换 程序的控制流

**§3.4词法分析程序的自动生成

见P181附录A**第四章语法分析§4.1概述§4.1.1语法分析方法 语法（句法）分析的任务是根据程序设计语言的语法规定，对输入的单词流进行分析，判定是否构成了合法的句子，并尽可能多的找出语法错误。句法分析方法可分两大类：**句法分析方法分类自顶向下（Top-Down)分析方法 以文法的开始符号为分析树的根，向下逐步构造分析树，每次以树中最左非终结符为子树的根向下形成新的子树（最左推导），直至分析树的叶结点形成输入串。此时称输入串是合法的句子，否则输入串非法（报错）。自底向上（Bottom-Up)分析方法 从输入串出发，向上逐步构造分析树，每次寻找当前句型的句柄（或最左素短语）进行归约（最右推导的逆），直至归约出文法的开始符号。此时称输入串是合法的句子，否则输入串非法（报错）。**下推自动机（PDA）与2型文法§4.1.2下推自动机(Push-DownAutomation)与2型文法3型文法及其数学模型FA由于其本身的局限性不能胜任句法分析。例如：判定表达式中的括号配对问题：L={anbn|n0}引入2型文法和PDA <A>→ (VN∪VT)*

在FA中增加一个下推栈并要求控制器能控制栈的操作，这就是PDA。 **下推自动机定义1：非确定的PDAM是一个七元组： M＝（VT，Q，

，

，q0，Z0，QF），其中，VT是有限的输入字母表； Q是有限的状态集合；

是有限的栈字母表； q0是初始状态，q0

Q； Z0

，是栈底符号；

是一个从Q×

×（VT∪{

}） 到Q×

*的幂集上的映射； QF是最终状态集，QF

Q。

**下推自动机下推自动机有两类动作。 第一类动作每一步决定于三个信息：

⑴有限控制器所处的状态qi，qi

Q；

⑵下推栈的栈顶符号A，A

；

⑶当前输入符号a，a

VT。这类动作表示成：

（qi，a，A）={(qi1,α1),…,(qik,αk)}， 它表示：当下推自动机处于状态qi、 当前输入符号为a、 下推栈栈顶符号是A时， 下推自动机可以进入状态qij，且αj代替栈顶符号是A（j＝1，2，…,k），然后输入头向右移动一个带块。**下推自动机第二类动作为：

（qi，

，A）={(qi1,α1),…,(qik,αk)}， 称为

动作。表示：PDA处于状态qi，不论当前输入符是什么，只要栈顶符号为A，则下一状态可以是qij中的任意一个，且用αj替代A，输入头不动。注意：由αj

*而αj可以为

这表示让A出栈。问题：1.为什么不定义

（qi，a，

）？

2.若不让A出栈，而只让αj进栈，如何表 示？

**确定的下推自动机PDAM是确定性的，当且仅当：

⑴对于任何q

Q，a

VT∪{

}及A

，

（q，a，A）只含有一个元素。

⑵

对于q

Q，A

，当

（q，

，A）非空， 则对于任何一个a

VT，

（q，a，A）为空。**下推自动机的格局下推自动机的当前格局是一个三元组 （q，w，α），q

Q、w

VT*、α

*。格局变换记为： （q，aw，XαZ0） （qi，w，αiαZ0）

（q，a，X）＝{（q1，α1），…，（qm，αm）}q,qi

Q、a

VT、w

VT*、x,Z0

、α,αi

***下推自动机接受的语言PDAM接收输入字符串w可以采用两种方式：i）空栈接收：（q0，w，Z0）（q，

，Z0）ii）最终状态接收：（q0，w，Z0）（qf，

，α），qf

Qf，α

*。一般采用空栈方法来定义输入串w为下推自动机M所接收。即先下推一个栈底符号Z0，一旦输入头所遇到的符号是输入串的结束符号‘

’，栈顶符号是‘Z0’，则表示输入串w为下推自动机所接收。可以证明（Chomsky)空栈接收与最终状态接收是等价的。（接受的语言集合相同）****下推自动机在确定的句法分析中（无论是自顶向下还是自底向上），由于采用的是单状态的下推自动机，因此状态变换可省略，下推自动机的控制器可简化为图或表的形式，主要描述入栈和出栈的控制。(见P66图4.3）例1：试设计能检查左右括号是否配对的PDA。

L={anbn|n>=0}<A>

a