编译原理简明教程（第3版）-课件 第1-3章 概述、形式语言理论基础、自动机原理

新工科建设·计算机类系列教材

免费提供编译原理1基本课程信息编译原理计算机科学中发展最迅速、最成熟的分支之一编译程序计算机系统中重要的系统软件之一编译技术计算机高级语言发展的支柱编译原理计算机科学中语言处理的基石理论研究软件开发编译原理课程是计算机科学中理解语言处理内在机制、提升软件开发效率与质量、培养系统级编程思维与创新能力的核心课程。学分：编译原理简明教程（第3版）冯秀芳

崔冬华

王会青

主编电子工业出版社

2024年出版课程教材学分：参考教材“编译原理”是计算机类专业一门重要的专业课，其目的是系统地向学生讲授编译程序的基本结构，阐述编译原理的一般理论和常用的有效方法与编译技术。

引言教学目的：学习本课后，使学生掌握编译理论和方法方面的基本知识，具有设计、实现、分析和维护编译程序等方面的初步能力。主要内容：形式语言与自动机、词法分析、语法分析、语义分析、中间语言代码生成和优化、目标代码生成、存储组织与分配、程序的查错与处理等。56目录第一章概述第二章形式语言理论基础第三章自动机理论基础第四章词法分析第五章语法分析—自顶向下分析方法第六章语法分析—自底向上分析方法第七章语义分析及中间代码的生成第八章代码优化第九章目标代码的生成第十章符号表和出错处理第十一章

面向对象语言的编译第十二章

并行编译技术第十三章

软件构造62024/11/67学习目标学习编译程序的概念工作过程、体系结构语言与编译程序的关系了解开发技术1概述EINLEITUNG重点：编译程序的概念、编译程序的结构难点：编译程序的开发技术

目录1.1程序设计语言与翻译1.2编译过程概述1.3编译程序的开发1.4本章小结81.1程序设计语言与翻译计算机系统：硬件软件：应用软件、系统软件（包括OS、编译系统、诊断系统等）程序设计语言：机器、汇编、高级翻译程序：指能把A语言程序翻译成与之等价的B语言

程序的程序。B语言（目标程序）A语言（源程序）翻译程序91.1程序设计语言与翻译计算机系统：硬件软件：应用软件、系统软件（包括OS、编译系统、诊断系统等）程序设计语言：机器、汇编、高级翻译程序：指能把A语言程序翻译成与之等价的B语言

程序的程序。B语言（目标程序）A语言（源程序）翻译程序101.1.1程序设计语言机器语言高级语言11汇编语言机器语言即机器指令，能被计算机直接理解与执行是符号化的机器语言FORTRAN、ALGOL、Pascal、C、JAVA、Ada、C++、Python等1.1.2编译程序和解释程序B（机器语言）A（高级语言）编译程序12如何让计算机认识、理解、执行高级语言程序？

汇编程序B（机器语言）A（汇编语言）汇编程序13

解释程序纯粹的解释程序并不多见，通常做某种程序的结合。141.2编译过程概述阅读全文、识别单词分析句子语法结构根据句子含义初步分析修辞加工写出译文生成目标代码优化语义分析语法分析扫描源程序、词法分析分析综合翻译外文资料编译程序15一、词法分析

输入源程序，对源程序构成的字符串进行扫描和分析，识别出一个个的单词，如保留字(if、for、while等)、标识符、常数、特殊符号(标点符号、左右括号、运算符等)。例如，对于C语言的循环语句：词法分析：遵循词法规则，描述词法规则正规式和有限自动机for(i=1;i<=100;i++)

sum=sum+1;161.2.1编译程序的工作过程编译程序一般分五个部分二、语法分析

根据语言语法规则，把词法分析后的单词合成各类语法单位（语法范畴），如“短语”，“句子”，“程序段”，“程序”。例如赋值语句：Z=X+2*Y；

语法分析：遵循语法规则，采用上下文无关文法描述。17编译程序一般分五个部分三、语义分析及中间代码的生成

根据语法结构，分析其含义，并进行初步翻译（生成中间代码），或直接生成目标代码。对常用的一些语言来说，语义分析生成语法成分的含义和用途，以及应进行的运算和操作，而且要进行语义检查等。例如：

3）在过程调用中，实参和形参是否在个数、次序、种属一一对应等。2）在表达式中，是否有类型不匹配的运算对象；1）在说明语句中，是否有矛盾的类型说明；18编译程序一般分五个部分“中间代码”是一种含义明确、便于处理的记号系统。如：三元式、四元式、逆波兰式。z=(x+3)*y/w;（+，x，3，T1）例：四元式（运算符，第一运算量，第二运算量，结果）(/,T2,

w，z

)（*，T1,y,

T2）19编译程序一般分五个部分四、代码优化

优化的任务在于对前阶段产生的中间代码进行加工变换，以期在最后阶段产生出更为高效(节省时间和空间)的目标代码。优化的主要方面有：公共子表达式的提取、循环优化、删除无用代码等。有时，为了便于“并行运算”，还可以对代码进行并行优化处理。优化所依循的原则是程序的等价变换规则。

20编译程序一般分五个部分从与具体计算机的关系分与机器无关的与机器有关的从与源程序的关系分全局优化局部优化21五、目标代码生成

把中间代码变成特定机器上的机器代码。这部分涉及到硬件,如各种数据类型变量的存储空间分配，寄存器的调度等。例：尽量使用执行速度快的指令，充分利用计算机的寄存器，以节省访问内存所用时间等。22编译程序一般分五个部分1.2.2编译程序的结构231.3编译程序的开发

编译程序是一个非常复杂的软件系统，虽然编译理论和技术不断发展，开发周期缩短，但研制仍需大量时间。追求目标过程自动化。1.3.1开发步骤1.认真分析，合理分工

2.算法设计，方案确定

3.语言选择，编制程序

4.调试程序，确保质量

5.资料整理，文本形成

241.3.2开发技术一、系统程序设计语言

70年代以前，用机器语言、汇编语言，手工编写工作量大、可靠性差、难以维护。

80年代以后，高级语言如PASCAL、ADA、C，工作量大大减少，缩短开发周期。系统程序程序设计语言：编写编译程序或其它系统软件的高级语言。25二、开发技术自编译：用某一高级语言编写其自己的编译程序。交叉编译：A机器上的编译程序能产生B机器上的目标代码。自展：首先确定一个非常简单的核心语言L0，用机器的汇

编语言写其编译程序T0，扩充L0到L1，用L0写L1的T1, L1到L2……滚雪球一样，直到所需编程序。移植：将A机器上的某高级语言编译程序搬到B机器上运行。261.3.2开发技术1.3.2开发技术三、编译技术的发展面向对象的高级语言编译技术

并行计算机和并行程序编译技术27编译技术的发展过程中，有多名计算机领域的专家因在编译理论和技术相关研究方面的突出贡献获得了图灵奖，例如艾伦·佩利（AlanJ.Perlis）、高德纳·克努斯（DonaldE.Knuth）、法兰西斯·艾伦（FrancesE.Allen）、阿尔弗雷德·艾侯（AlfredVainoAho）和杰弗里·乌尔曼（JeffreyDavidUllman）如Unix下

LEX

词法分析程序自动构造软件工具

YACC

语法分析程序自动构造软件工具

Llama

编译程序生成软件工具

Occs

源语言的定义机器语言的描述翻译程序的自动生成软件编译程序281.3.3编译程序的自动生成291.4本章小结1．程序设计语言：机器语言、汇编语言、高级语言2．编译程序和解释程序都是翻译程序，但解释程序不产生完整的目标代码程序3．编译程序工作过程一般划分为：词法分析、语法分析、语义分析与中间代码的产生、优化、目标代码的生成五个阶段4．编译程序常用开发技术：自编译、交叉编译、自展和移植

30总结

本章我们学习了什么是编译程序、高级语言的编译过程、编译程序的一般结构、编译程序的开发技术等内容。

下一章将学习编译的基本理论------形式语言理论。THANKS31THANKS新工科建设·计算机类系列教材

免费提供编译原理326目录第一章概述第二章形式语言理论基础第三章自动机理论基础第四章词法分析第五章语法分析—自顶向下分析方法第六章语法分析—自底向上分析方法第七章语义分析及中间代码的生成第八章代码优化第九章目标代码的生成第十章符号表和出错处理第十一章

面向对象语言的编译第十二章

并行编译技术第十三章

软件构造33

学习形式语言基本理论和基础知识掌握程序设计语言的语法描述方法需要着重掌握的内容为：字母表、符号、符号串、符号串集合

规则（产生式）、文法推导、归约、句型、句子、语言语法树、二义性

文法的限制、文法的分类34学习目标2形式语言理论基础形式语言理论基础程序设计语言语法程序的结构形式语义语言所代表的含义语用语言的实际应用35Theoreticalbasisofformallanguage形式语言理论基础

例如：x:=a*b+c

以下非形式化的描述不够清晰明确

变量：=表达式v:=e对e求值，再赋给变量计算和保存e的值语法语义语用36Theoreticalbasisofformallanguage形式语言理论基础形式语言形式语言理论探讨形式化方法发展过程用一套带有严格规定的符号体系来描述问题的理论方法。是一种不考虑含义的符号语言（只谈语法不谈语义）。研究组成这组符号串的集合表示法、结构及特性，只能用于程序语言的语法描述和语法分析。37Theoreticalbasisofformallanguage

目录2.1形式语言的基本概念2.2文法和语言的形式定义2.3语法树和二义性2.4文法的限制2.5文法和语言的Chomsky分类2.6本章小结382.1形式语言的基本概念

2.1.1符号和符号串形式语言和编译技术中两个主要概念任何一种语言都是由该语言的基本符号组成的基本符号串的集合。英文：26个字母、数字、标点符号等

中文：汉字、数字、标点符号等

C、JAVA、PASCAL：

字母、数字、关键字、专用符号等

392.1.1符号和符号串是一个非空的有限集合。用Σ表示。例：Σ={a，b，c}a,b,c均为字符或符号，是字母表中的元素字母表字母表上若干符号串/字符串组成的集合。用大写字母表示。例：A={a，ab，bc}符号串集合/字符串集合符号/字符的有限序列。小写希腊字母表示。如：ω，φ，λ，a，b，ab，abc等。ε表示空字符串，不包含任何符号的符号串。ε≠空格ab≠ba符号串/字符串402.1.1符号和符号串例：Σ={a}，L={a2k|k≥0}Σ={0，1}，L1={(01)n|n≥0}={ε，01，0101，……}L2={0n1n|n≥0}={ε，01，0011,……}

ф空集或者空语言，不含任何符号串的语言。ф≠{ε}

语言/形式语言412.1.2符号串的运算符号串相等：同一字母表的两个符号串所有

符号依次相等。如Σ={a，b，c}，ω=abc，ψ=abc，则ω=ψ；若ω=abc，ψ=cba，则ω≠ψ字符串的长度：符号串中包含的字符的个数。

记|ω|。例|abc|=3，|ε|=0,|aω|=|ωa|=1+|ω|，a∈Σ422.1.2符号串的运算符号串的连接:

把符号串ψ的所有符号相继写在ω之后，记ωψ或ω·ψω=ab，ψ=bc，则ωψ=abbc符号串的逆：符号串ω的倒置，记ω-1如ω=abc则ω-1=cbaε-1=ε（ω-1）-1=ω（ωψ）-1=ψ-1ω-1432.1.2符号串的运算前缀：ε，a，ab，abc后缀：ε，c,bc，abc子串：ε，a，b，c，ab，bc，abc例：abc符号串的前缀、后缀和子串：设ω，ψ，β是字母表Σ上的字符串，则ω为符号ωψ的前缀，ψ为字符串ωψ的后缀，ψ是字符串ωψβ的子串。前缀和后缀都是子串，但子串不一定是前缀或者后缀。

442.1.2符号串的运算符号串的幂：一个符号串与它自己的n次连接。ω0=ε；ω1=ω；ω2=ωω；……；ωn=ωn-1ωω=abω0=εω1=abω2=abab……ωn=abab……ab452.1.3符号串集合的运算符号串集合的乘积:A·B={ωψ|ω∈A，ψ∈B}例：A={ab,ba}B={bc,b}则AB={abbc,abb,babc,bab}特别：{ε}A=A{ε}=A46符号串集合的幂：A0={ε}；A1=A；……；An=An-1A=AAn-1

(n>0)例：A={ab,c}A0={ε}A1={ab,c}A2={abc,cab,abab,cc}……472.1.3符号串集合的运算集合A的闭包和正闭包：星闭包A*=A0∪

A1∪

……A+=AA*=A*A正闭包A+=A1∪

A2∪

……A*=A0∪

A+

Σ字母表Σ*：Σ上所有符号串的集合

Σ+：Σ上所有非空符号串的集合A={0，1}则A1={0，1}A0={ε}A2={00，01，10，11}……A*={ε，0，1，00，01，10，11，000，……}A+={0，1，00，01，10，11，000，……}482.1.3符号串集合的运算2.2文法和语言的形式定义语言L可抽象地看成是所有句子组成的集合（有限集：用枚举；无限集：文法）句子可抽象地看成是某个有限字母表Σ上的符号串。例：英语Σ={26个字母，数字，标点符号，……}文法在形式上用以描述和规定语言结构的方法，是用有限的手段描述无限的句子集合的方法之一。492.2文法和语言的形式定义例：“Thebigcatateamouse.”

<句子>→<主语><谓语><主语>→<冠词><形容词><名词><冠词>→the<名词>→cat<形容词>→big<谓语>→<动词><直接宾语><动词>→ate<直接宾语>→<冠词><名词><冠词>→a<名词>→mouse502.2文法和语言的形式定义例：我爱祖国。

从结构上看符合中文文法，是中文句子。

又如：（1）〈无符号整数〉→〈数字串〉（2）〈数字串〉→〈数字串〉〈数字〉（3）〈数字串〉→〈数字〉（4）〈数字〉→2（5）〈数字〉→5（6）〈数字〉→6256是一个句子。51

文法G[A]：

A→B

B→BC|CC→2|5|6

2.2文法和语言的形式定义定义2.5：文法是一个四元组：G=（VN，VT，S，P）记为G[S]。V是字汇表，V=VT∪VN，S∈VN,VT∩VN=ΦU->X或U::=XVN大写字母，一般出现在左部，不属于字母表VT句子中的字母终结符号集非终结符号集文法规则集合52VN--非终结符集合，VT--终结符集合，S--开始符号，P--规则2.2文法和语言的形式定义例2-1

例2-2

VN={A}，VT={a，b，c}，S=A，P={A→aAb，A→c}。构成文法G=（{A}，{a，b，c}，A，P）G=（{〈标识符〉，〈字母〉，〈数字〉}，{0，1，2，…….9，a，b，c}，〈标识符〉，P）532.2文法和语言的形式定义引进BNF（巴科斯范式）

G[I]:I→L|IL|INL→a|b|cN→0|1|……|9定义2.6：句型

文法G[S]，G=（VN，VT，S，P）由S推出的符号串X∈(VT∪VN)*称为句型。

542.2文法和语言的形式定义b.推导、归约、推导长度(n≥1)

文法G，存在一直接推导序列，ω0

ω1

ω2……

ωn

(ω0ω1……ωn是句型)则称ω0推导出ωn或ωn归约到ω0记作ω0

ωn，ωn

ω0

++文法G，A→α是一条规则，ω1=φ1Aφ2ω2=φ1αφ2

（其中ω1，ω2，φ1，φ2∈(VT∪VN)*）

则称ω1直接推导出ω2，记作

反之，ω2直接归约到ω1，记作

ω1ω2ω2ω1

a.直接推导、直接归约(长度=1)552.2文法和语言的形式定义c.若ω1

ω2或ω1=ω2

则称ω1广义推导ω2，记作ω1

ω2

ω2广义归约到ω1记作ω2

ω1

长度≥0

+**例：1.文法G[E]：E→E+T|TT→T*F|FE

i+i*i(n=8)F→(E)|i2.G[<无符号整数>]推出256+562.2文法和语言的形式定义例：1.文法G[E]：E→E+T|TT→T*F|FE

i+i*i(n=8)F→(E)|i2.G[<无符号整数>]推出256+57例：1.文法G[E]：E

E+T

E+T*F

E+T*iE+F*i

E+i*iT+i*iF+i*ii+i*i

2.G[<无符号整数>]ABBCBCCCCC2CC25C2562.2文法和语言的形式定义结论:给定一个文法,就能从结构上唯一地确定其语言。

给定一个语言，能确定相应文法,但不唯一。

定义2.7：语言、句子文法G=（VN，VT，S，P）所产生的语言L(G)

L(G)={ω|S

ω,ω∈VT*}其中ω称为句子.空语言:由文法开始符号推不出任何句子.

+

d.规范推导（最右推导，也称为最左归约）

每次替换最右边非终结符的直接推导。记作ω1

ω2

r+58例:G1:S→0S1S→01L(G1)={0n1n|n≥1}G2:S→1S→1AL(G2)={(10)n1|n≥0}A→0S

G3:S→1S→A1L(G3)={1(01)n|n≥0}A→S0

59L(G2)=L(G3),所以，G2和G3为等价文法2.2文法和语言的形式定义2.2文法和语言的形式定义又如：已知语言L(G[Z])={abna|n≥1}

则：G1：Z→aBaG2：Z→aBG3：Z→BaB→b|BbB→ba|bBB→ab|Bb例2-3G=（VN，VT，S，P）

VN={S，B，C}VT={a，b，c}P：（1）S→aSBC（5）bB→bb

（2）S→aBC（6）bC→bc

（3）CB→BC（7）cC→cc

（4）aB→ab602.2文法和语言的形式定义解：1)SaBCabCabc

（2）

（4）

（6）2）SaSBCaaBCBCaabCBCaabBCC(1)(2)(4)(3)aabbCCaabbcCaabbcc…………

所以,L(G)={anbncn|n=1，2，……}612.2文法和语言的形式定义例G=（VN，VT，S，P）

VN={A，B，S}VT={0，1}

P：S→0BS→1A

A→0B→1A→0SB→1S

A→1AAB→0BB

所以，L(G)由相同个数的0和1所组成的VT+中所有符号串的集合.

解：S

0B

01

S

1A

10

010B

0101S

0B

01S

011A

0110

S

0B

00BB

0011

……

62

2.3语法树和二义性2.3.1语法树和推导

1.语法树的概念：定义2.8（用直观方法描述句型或句子的语法结构）已知文法G[S],满足下列条件的树称为G的语法树.a.结点：终结符or非终结符b.树根:Sc.分枝:非终结符d.若结点A有B1B2…Bn分枝，则A→B1B2…Bn是G的一个规则。

63例：G[S]：S→aABSSA→Ba|aaABaABB→bdBaBabdbd642.3.1语法树和推导例：G[<无符号整数>]G[A]：A→BB→BC|CC→0|1|2……|9

推导：

A

BBCB6BC6B56C56256ABBCBCCCCC2CC25C256A

BBC

BC6C522.由推导生成语法树:

句型or句子的推导用图解表示→语法树生成652.3.1语法树和推导3.由语法树构造推导

上一步的逆过程.由分枝建立直接推导,然后剪去分枝,直到无分枝可剪.A

BBCBCC

CCC

2CC

25C256或先进行归约,再倒过来.

662.3.1语法树和推导4.子树和短语定义:子树----某个结点与它的分枝结点.BB

CC5简单子树----单层分枝的子树.BCC5672.3.1语法树和推导设S

aBc,B

b,则S

aBc

abc

S则b称为句型abc相对于B的短语.

a

B

c

b*+*+结论:(1)子树的末端结点组成的符号串是相对于子树根的短语.(2)简单子树的末端结点组成的符号串是相对于简单子树根的简单短语.(3)最左简单子树的末端结点组成的符号串为句柄.

682.3.1语法树和推导例：E句型：

短语：E

+

T

简单短语：

句柄：T

F

iT+iT+i,T,iT,iT692.3.1语法树和推导2.3.2文法的二义性

1.二义性的概念

定义:如果一个文法所定义的句子中,有某个句子存在两棵不

同的语法树,则称文法是二义性的。

或:若文法所定义的某个句子,有两种不同的最左(or最右)

推导。或:若文法所定义的某个句子,有两种不同的最左(or最右)

归约。70

例:G[E]：E→E+E|E*E|(E)|iEEE+EE*EiE*EE+Eiiiii

E

E+E

E+E*E

i+i*iE

E*EE+E*E

i+i*i++

文法的二义性产生句子语义上的不确定性712.3.2文法的二义性例：G[s]：S→ifBthenS|ifBthenSelseS|A

S：语句B：布尔表达式A：其它语句

句型：ifBthenifBthenSelseSS

ifBthenS

ifBthenifBthenSelseSS

ifBthenSelseS

ifBthenifBthenSelseS722.3.2文法的二义性

S

SifB

then

Sif

Bthen

S

elseS

if

Bthen

S

else

S

ifB

then

S

732.3.2文法的二义性

例:G[E]：E→E+E|E*E|(E)|i在编译方法中规定运算之间的优先级。

如:①*,/高于+,-

②同级先左后右2.二义性解决方法（1）修改编译算法742.3.2文法的二义性（2）修改文法

G[E]：E→E+T|E-T|TT→T*F|T/F|FF→(E)|iG[S]：S→C|UC:完全语句U:不完全语句C→ifBthenCelseS|AU→ifBthenS

752.3.2文法的二义性

注：规则左部的符号在右部同时出现两次or两次以上，导致二义性。先天二义性文法：不存在等价的非二义性文法。二义性问题是不可判定的，即不存在一种算法在有限步内判断二义性762.3.2文法的二义性2.4文法的限制文法的实用限制主要是限制文法中不能存在有害规则和多余规则，这两种规则如果出现会导致文法的二义性和错误。77定义2.14:如果文法G[S]中所有规则均满足下列实用限制条件：①没有有害规则；②没有多余规则。则称该文法G[S]是压缩或化简过的。2.4.1文法的实用限制2.4.1文法的实用限制定义2.15:文法中形如A→A的规则，称为有害规则。

N

例:N→NNNN→ND|DNND→0|1|……|9

N

DN

D78定义2.17:

对于文法G，在某句型中出现的符号称为可推出符号。例:G[E]：{E,T,F,+,-,*,/,(,),i}

例:S→aAB|aA→aAb|b{S,A,B,a,b,d}B→dC→aBf定义2.16:G[S],若A∈VN，存在α,β∈V*有S

*

αAβ，则称A为活的非终结符。792.4.1文法的实用限制定义2.18

多余规则：左部符号为A的规则,若不满足条件

①A为可推出符号

②从A能推出句子

例:G[S]:S→Be①D不是可推出符号A→Ae|e∴D→f多余B→Ce|Af②B→CeC→Cf

C→Cf多余D→f在程序设计语言中若包含多余规则，必定有错误句子。802.4.1文法的实用限制a.A为可推出符号：即S

αAβ;α,β∈V*；

b.必须能从A推出句子，即：A

ω,ω∈VT+

*+定理1:如果一个文法G[S]中所有规则均满足下列两个条件，则该文法不包含多余规则（设：A为任一规则的左部符号）。812.4.1文法的实用限制

G[S]:S→Be多余规则①D→fA→Ae|e②B→CeB→Ce|AfC→CfC→CfD→f822.4.1文法的实用限制

832.4.1文法的实用限制

842.4.1文法的实用限制算法2.2:使文法的每个非终结符均出现在某个句型中

*852.4.2文法的实用限制2.4.2文法的等价变换

在语法分析中,各种分析方法都有一定的局限性，对文法进行种种限制,为了使某一语言能用某一种分析方法,常常根据限制条件对文法进行变换.

86

872.4.2文法的等价变换2.4.3扩充的BNF表示法在BNF上发展起来,相同表达效力,结构上更简单，清晰.一.专用符号{t}--t可重复任意次[t]--t可出现0次或1次

()--提因子例:G[N]:N

→ND|DN→D{D}D→0|1|…|9D→0|1|…|9例:G[E]:E→T|T+EE→T[+E]T→F|F*TT→F[*T]F→i|(E)F→i|(E)例:A→αβ1|αβ2|…|αβnA→α(β1|β2|…|βn)88二.扩充BNF表示法的用途.

消除左递归,使文法在自顶向下分析过程中，能进行分析处理.

例:G[E]:E→T{+T}T→F{*F}F→i|(E)892.4.3扩充的BNF表示法2.5文法和语言的Chomsky分类如果对某文法G[S]，P中的每个规则具有下列形式：α→β,α∈V+,β∈V*,V=(VN∪VT)则称该文法G为Chomsky0型文法或无限制性文法或短语结构文法(Phrase

StructureGrammar)，记为PSG。0型文法产生的相应语言称为0型语言(无限制性语言或短语结构语言)，记为L0(G)。四类文法对应四类语言.2.5.10型文法与0型语言(图灵机)

定义2.19:90例[2-13]:P={S→ACaB,Ca→aaC,CB→DBCB→E,aD→Da,AD→AC,aE→Ea,AE→ε}SACaBAaaCBAaaEAaEaAEaaaa,SaaaaL0(G)={a2n|n>0}+

尽管0型文法不足以描述自然语言，但对程序设计语言的描述而言又太一般化,所以须对规则的形式加以限制.912.5.10型文法与0型语言(图灵机)2.5.21型文法与1型语言（线性界限自动机）

在自然语言中，一个句子或一个单词的语法性质往往和它所处的上下文有密切的关系，所以描述自然语言的文法一定是上下文有关文法。定义2.20：文法G[S]中每个规则即为：

αWβ→αωβ,W∈VN，α，β∈V*,ω∈V+

则称G为1型文法（或上下文有关文法)→CSG产生的语言称为1型语言L1（G）（或上下文有关语言，前后文有关语言）。92例：G[S]：S→aSBC|aBCG[S]是1型文法CB→DBDB→DCDC→BCaB→abbB→bbbC→bccC→ccS⇒aBC⇒abC⇒abcS⇒aSBC⇒aaBCBC⇒aabCBC⇒aabDBC⇒aabDCC⇒aabBCC⇒aabbcC⇒aabbcc……L1(G)={anbncn|n≥1}932.5.21型文法与1型语言（线性界限自动机）2.5.32型文法和2型语言（下推自动机）例：G[S]：S→aSbL2(G)={anbn|n≥1}S→abG[S]:S→Ac|ScL2(G)={anbncm|n,m≥1}A→ab|aAb

定义2.21:

文法G[S]中每一个规则形如：A→α，A∈VN，α∈V+,V=(VN∪VT)则称G为2型文法，产生的语言称为2型语言(CFG)，或上下文无关语言、前后文无关语言

L2（G）。注:

有些书中α∈V*，即允许出现A→ε的规则。大部分程序设计语言的文法近似于2型文法，所以是我们主要研究对象942.5.43型文法和3型语言（有限自动机）注:1.左线性文法A→Ba或A→a

右线性文法A→aB或A→a2.一般形式a∈VT*,定义中的是简单形式，可以替换3.对于每一个左(右)线性文法，都存在一个与某等价

的右(左)线性文法.

定义2.22:文法G[S]中每个规则形如:A→Ba(A→aB)或A→aA，B∈VN，a∈VT

则称G为3型文法(或正则文法)→RG产生的语言为3型语言(或正则语言)L3(G)95例:G[S]:S→Bc|ScB→Ab|Bb左线性A→Aa|aL3(G)={ambnck|m,n,k≥1}G[S]:S→aS|aAA→bA|bB右线性B→c|cB

962.5.43型文法和3型语言（有限自动机）

例:<标识符>→<字母>|<标识符><字母>|<标识符><数字><无符号整数>→<数字>|<无符号整数><数字>

在程序设计语言中，与词法有关的文法(单词的语法规则）一般属于3型文法.972.5.43型文法和3型语言（有限自动机）2.5.5四类文法的关系1.0型→3型,限制逐渐增加,描述语言的能力逐渐减弱。L0⊃L1⊃L2⊃L3

注:1型不允许A→ε,但2,3型允许.

文法文法名称语言自动机0短语结构文法短语结构图灵机(TM)1上下文有关文法上下文有关线性界限自动机(LBA)2上下文无关文法上下文无关下推自动机(PDA)3正则文法正则语言有限自动机(FA)2.四种语言可分别被四种自动机所接收.98992.6本章小结

1．形式语言是编译技术的重要理论基础，文法是形式语言最重要的概念之一2．文法是在形式上用以描述和规定语言结构的方法，是用有限的手段描述无限的句子集合的方法之一3．二义性文法，产生句子语义上的不确定性，通过句子的不同语法树可以判断二义性问题4．文法的限制有两方面，文法的实用限制、文法的等价变换5．Chomsky将文法分为四类(0型、1型、2型、3型)，四类文法对应四类语言，与四类自动机相对应。100总结

本章我们学习了形式语言的基本概念、文法和形式语言的定义、语法树和二义性、文法的实用限制、文法和语言的Chomsky分类等内容。下一章将学习编译的另一个基本理论----自动机理论基础。THANKS101THANKS新工科建设·计算机类系列教材

免费提供编译原理1026目录第一章引言第二章形式语言理论基础第三章自动机理论基础第四章词法分析第五章语法分析—自顶向下分析方法第六章语法分析—自底向上分析方法第七章语义分析及中间代码的生成第八章代码优化第九章目标代码的生成第十章符号表和出错处理第十一章

面向对象语言的编译第十二章

并行编译技术第十三章

软件构造1033自动机理论基础本章主要介绍状态转换图定义、有限自动机的理论及下推自动机的的理论。着重需要掌握以下内容：确定的有限自动机DFA非确定的有限自动机NFANFA到DFA的转换DFA的最小化下推自动机PDA104学习目标

目录3.1有限自动机的基本概念3.2确定有限自动机DFA的化简3.3正则表达式形式定义3.4下推自动机PDA3.5本章小结1053.1有限自动机的基础106定义3.1：有限自动机定义为一个五元组：D=(K,Σ,δ,S,F)。K是有穷的非空状态集合；Σ是有穷的输入字母表；δ是从K×Σ到K的映射，表示状态的转换（状态转换函数）；S是初始状态；F是终止状态。确定有限自动机

(DFA)：每次转换的后继状态都是唯一的不确定有限自动机(NFA)：转换的后继状态不是唯一的3.1.1有限自动机的定义和表达式1.状态转换图的引进和构造定义3.2：状态转换图是定义在字母表上的有向图，满足以下三个条件：

至少存在一个初始结点

存在一些终止状态结点（也可为空）

每条边上标有字母表∑上的符号（也可为空串ε）107例：TG接收（or识别）的符号串：从某一初始结点到某一终止结

点的序列。TG所接收的符号串集合：L（TG）={ab，bab，abbb，……}状态转换图：结点------状态------文法的非终结符

初始结点--初始状态

终止结点--终止状态--开始符号

边--------转换关系--终结符号∑={a，b}1080S1S2Sbbbba算法3.1

正则文法构造状态转换图算法

将S设为初始状态（假定文法的字母表中不含符号S）以每一个非终结符号作为其它状态对于形如A→b

的每个规则，引一条从初始状态S到状态A的边，其标记为b；

而对于形如A→Bc

的规则，引一条从状态B到A的边，其标

记为c（其中A、B为非终结符号，b、c为终结符号）。④以文法开始符号作为终止状态。

特别地，一个状态转换图可以不止一个初始状态，也可以有不止一个终止状态。109

例3.1：文法G[Z]，其中，VN=｛Z,A,B｝，VT=｛a,b｝。Z→Za|Aa|BbA→Ba|aB→Ab|b1102.应用状态转换图识别句子识别句子：从开始状态到终止状态经过的边上的符号序列。识别句子（α）的步骤：111定理3.1当识别一个符号串α时，如果能从转换图的初始状态出发行进达到α的右端，那么，α为句子的充要条件是：最后的当前状态为终止状态。用状态转换图识别句子的过程，称为运行状态转换图。1121从开始状态出发，以它作为当前状态，并从α的最左字符开始，重复第二步到达α的最右端为止2扫描α的下一个字符（当前字符），在当前状态射出的各条边中找出标有该字符的边并沿此边前进，以所达到的状态作为下一个当前状态。例3.2：对句子ababaaa进行分析并生成语法树

当前状态输入串的其余部分语法树SababaaaAbabaaaBabaaaAbaaaBaaaAaaZaZ

1133.应用状态转换图为正则语言构造正则文法状态转换正则文法正则语言

ε

a

ab

a|b

114b115正则文法：

A→CbC→Bb|bB→AbA→Ba|a例3.3正则语言{|n≥0}1163.1.2有限自动机的机器模型

有限自动机（FA，FiniteAutomata）可看作一个机器模型，由一个带读头的有限控制器和一条字符输入带组成。工作原理：读头从左到右扫描输入带，读到一个字符，状态改变，同时读头右移一个字符，…，直到读头读到“#”，状态进入终止状态。控制器中包括有限个状态，读入一个字符形成状态转换。

后继状态为自身状态转换后继状态为一个DFA后继状态为多个NFA

输入带ababa…#控制器1173.1.3

确定有限自动机（DFA）

定义3.3：DFA是一个五元组

D=(Κ,Σ,,Ѕ,F)

其中：Κ是状态的非空有限集

Σ有穷的输入字母表

是从ΚXΣ到Κ的映射，且为单值，即如果有转换函数(,a)=,、∈Κ表示当前状态为，输入符号为a时，转换到

Ѕ初始状态Ѕ∈Κ

F非空的终止状态集FΚDFA----DeterministicFiniteAotomaton118例3.4：由例3.1的状态转换图构造DFA如下

D1=

({S,Z,A,B},{a,b},,S,{Z})

其中：(S,a)=A,(S,b)=B

(A,a)=Z,(A,b)=B

(B,a)=A,(B,b)=Z

(Z,a)=Z

同理，由例3.3中的状态转换图构造确定有限自动机如下：D2=({S,A,B

,C,Z},{a,b},,S,{Z})

119(S,a)=A

(S,a)=C(A,b)=

(B,a)=

(B,b)=C(C,b)=

120定义3.5

由有限自动机接受的符号串集合称为正则集，记为L（D）。121定义3.4对于某个DFAD=(K,Σ,δ,S,F)，如果δ(S,α)=P，P∈F，则称字符串α可被该DFAD所接受(识别)。3.1.4有限自动机在计算机内的表示

1、矩阵表示

例3.6

或

或

注：

S0表示初始状态，0表示无后继状态

输入状态abS0=SAB

S1=AZB

S2=BAZ

S3=ZZ0ABZZZAB0122上例：

输入状态abc1232.表结构表示状态名射出边数标记1指向下一状态……标记k指向下一状态k1243.1.5不确定有限自动机（NFA）定义3.6

NFA是一个五元组，=(Κ,Σ,,Ѕ,F)其中：Κ是状态的非空有限集Σ有穷的输入字母表是从ΚXΣ到Κ的子集的映射Ѕ开始状态ЅΚF终止状态FΚ125例：=(Κ,Σ,,Ѕ,F)其中

Κ={,,

}Σ={a,b}Ѕ={,}F={}(,a)={}(,b)={,}(,a)=Φ(,b)={}(,a)=Φ(,b)={}126

得出：

输入状态ab

127例3.7由正则文法G[Z]=(VN,VT,S,P)构造NFA其中VN={Z,A,B}VT={a,b}P集为Z→Za|Aa|BbA→Ba|Za|aB→Ab|Ba|b128步骤当前状态输入串余留部分可能的后继状态选择状态

1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZ8.

例3.8对于输入符号串babbabb运行过程:129

由此可见，在NFA中由于某些状态的转换需从若干个可能的后继状态中进行选择，这种不确定性给识别过程带来反复，影响了工作效率。

解决这一问题的一个方法就是下面将介绍的使NFA转换成等价的DFA。1303.1.6NFA到DFA的等价转换定理3.3：设L是一个为某NFA所接受的符号串集合，则存在一个接受L的DFA，即L(D)=L(N)。

算法3.2:NFAN=

(Κ,Σ,,Ѕ,F)DFAN’=(,,,,)

1、若NFA中全部初始状态为,,…,

则令DFA的初始状态=[,,…,]

[]表示由若干状态构成的某一状态1312、设Q=[,,…,]是DFA的一个状态

在NFA中，({,,…,},a)={,,…,}

则令([,,…,],a)=[,,…,]。3、重复第2步，直到不出现新的状态为止。4、上面得到DFA的状态集，映射,Σ不变。5、在DFA中，含有NFA终止状态的状态均为DFA的终止状态。132例3.9=(Κ,Σ,,Ѕ,F)其中S={,}K={,,}Σ={a,b}F={}133

转换：①=[,]②({,},a)={}({,},b)={,}∴([,],a)=[]([,],b)=[,]③({