编译原理第5版-课件汇 刘铭 第1-3章 编译概述-词法分析与有穷自动机

第1章编译概述

—编译程序的基础知识编译原理（第5版）课程说明教材:《编译原理》（第5版），电子工业出版社，2024年其他参考书:

[1]AlfredAhoect.，Compilers:Principles,Techniques,andTools，北京：人民邮电出版社，PearsonEducation出版集团，2002.2.[2]许畅等.编译原理实践与指导教程.北京：机械工业出版社2学时参考内容讲课学时1编译概述22文法和语言的基本知识63词法分析与有穷自动机74语法分析155语法制导翻译技术和中间代码生成7内容讲课学时6符号表的组织与管理17代码优化48运行时的存储组织与管理29目标代码生成210并行编译技术基本常识23评分参考评分项目占比考试70%平时成绩30%4第1章编译概述编译原理这门课程主要介绍设计和构造编译程序的基本原理和常用的技术和方法。本章重点介绍编译程序的基本概念编译的过程编译程序的结构5第1章编译概述编译器与解释器6CompilersInterpretersProgram+DataInterpreterOutput第1章编译概述1954IBM704Software>Hardwareprice如何提高软件的产量？JohnBackus1924‐2007

Speedcoding1953(10-20slower,解释执行300bytes=30%memory)

FORTRAN1(FormulasTranslation)1954-1957195850%()FORTRAN1第一个编译器意义重大诞生大量理论+实践现代编译器仍遵循781.1翻译程序与编译程序

翻译程序：将一种语言所写的程序译成等价的另一种语言的程序。

源语言源程序目标语言目标程序高级语言程序机器语言程序翻译程序#include<stdio.h>intmain(void){printf(“hello,world！\n");

return0;}00001010…..91.1翻译程序与编译程序

编译程序：是一种翻译程序，它将高级语言所写的源程序翻译成等价的机器语言或汇编语言的目标程序。

源程序高级语言程序编译程序目标程序汇编语言或者机器语言程序1.1翻译程序与编译程序程序运行阶段第一种情况：源程序编译程序机器语言目标程序初始数据运行系统结果编译阶段运行阶段高级语言程序101.1翻译程序与编译程序源程序编译程序机器语言目标程序初始数据运行系统结果编译阶段运行阶段汇编程序汇编语言目标程序汇编阶段高级语言程序11程序运行阶段第二种情况：1.2编译过程与编译程序的基本结构自然语言翻译Thisisasentence.Isthisasentence12

词法分析

语法分析

语义分析

修饰工作

翻译成文

编译过程编译过程一般可划分为五个阶段：13

词法分析

语法分析

语义分析和中间代码生成

代码优化

目标代码生成编译过程例如：程序片段14floatr,h,s；s=2*3.1416*r*(r＋h);或Ifx==ythenz=5;elsez=10;1）词法分析词法分析：是对构成源程序的字符串从左到右进行扫描和分解，根据语言的词法规则，识别出具有独立意义的单词(也称单词符号、符号

)。15词法规则词法规则：是单词符号的形成规则,它规定了字符串如何构成一个单词符号。16

例子：

floatr,h,s;

s=2*3.1416*r*(h＋r);基本字float 标识符r、h、s常数3.1416、2 算符*、＋

界符（、）、;、,、=id1=2*3.1416*id2

*(id2

＋id3);2）语法分析语法分析：在词法分析的基础上,根据语言的语法规则从单词符号串中识别出各种语法单位(如表达式、说明、语句等),并进行语法检查,即检查各种语法单位在语法结构上的正确性；产生形成语法树。17自然语言语法树Thislineis

alongersentence18Articlenounverbaritcleadjectivenounsubjectobjectsentence语法树ifX==ythen

Z=5;elseZ=10;19relationassignassignpredicateElse-stmtThen-stmtIf-then-elseX==yZ

5Z10语法规则语法规则：规定了如何从单词符号形成语法单位。语法规则是语法单位的形成规则。例子：floatr，h，s；s=2*3.1416*r*(h＋r)；20“s”是<变量>；“2*3.1416*r*(h＋r)”组合成<表达式>；<变量>=<表达式>组合成<赋值语句>。213）语义分析和中间代码生成语义分析：首先对每种语法单位进行静态的语义审查，然后分析其含义，并用另一种语言形式来描述这种语义。比源语言更接近于目标语言

（中间代码或直接用目标语言）223）语义分析和中间代码生成例子：将s=2*3.1416*r*(h＋r)翻译成如下形式的四元式中间代码：(1)(*,2,3.1416,T1)(2)(*,T1, r,T2)(3)(+,h, r,T3)(4)(*,T2,T3,T4)(5)(=,T4,__,s)例子：将s=2*3.1416*r*(h＋r)翻译成如下形式的四元式中间代码：233）语义分析和中间代码生成T1=2*3.1416T2=T1*id1T3=id2+id3T4=T2*T3Id1=T4问题作用域：{intJack=3;{intJack=4;cout<<Jack;}}二义性：JacksaidJerrylefthishomeworkathome244）代码优化

代码优化：对前阶段产生的中间代码进行等价变换或改造，以期获得更为高效即省时间和空间的目标代码。主要包括：局部优化和循环优化等，例子：四元式经局部优化后得：25(1)(*,6.28,

id2,T2)(2)(+,id3,id2,T3)(3)(*,T2,T3,T4)(4)(=,T4,__,id1)5）目标代码生成目标代码生成：将中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。26表格管理和错误处理在编译程序的各个阶段中，都涉及表格管理和错误处理。

表格：记录源程序中所提供的、在编译过程中产生的信息；表格管理：构造、查找、修改或存取表格中的信息；错误处理：编译程序在编译过程中，应具有广泛的程序查错能力，并能准确地报告错误的种类及出错位置，以便用户查找和纠正。27编译程序的结构28

源程序语义分析和中间代码生成程序语法分析程序词法分析程序代码优化程序目标代码生成程序

目标程序表格管理程序出错处理程序(字符串)1.3编译程序的生成方法编译程序是一个复杂的系统程序，需要考虑以下几方面：29

对源语言和目标语言认真分析

设计编译算法

选择语言编制程序

调试编译程序

提交相关文档资料编译程序的自动生成随着编译技术和自动机理论的发展,近年来已研制出了一些编译程序的自动生成系统：词法分析程序的自动生成系统：Flex/Lex;语法分析程序自动生成系统：Bison/YACC等30编译程序的自动生成生成编译程序的方法还常采用自编译方式和移植方式。随着并行技术和并行语言的发展，处理并行语言的并行编译技术和将串行程序转换成并行程序的自动并行编译技术正在深入研究之中。311.4编译技术在软件开发中的应用大部分系统软件和应用软件的开发，通常要用到编译的原理和技术。例子：词法分析器的串匹配技术用于正文编辑器、信息检索系统和模式识别程序；上下文无关文法和语法制导定义用于排版、绘图系统和语言结构化编辑器中；代码优化技术用于程序验证器和从非结构化的程序产生结构化程序中。32本章小结什么是编译程序编译过程的五个阶段编译程序的结构框图33编译程序是一种翻译程序，它将高级语言所写的源程序翻译成等价的机器语言或汇编语言的目标程序。词法分析、语法分析、语义分析和中间代码生成、代码优化、目标代码生成本章小结34

源程序语义分析和中间代码生成程序语法分析程序词法分析程序代码优化程序目标代码生成程序

目标程序表格管理程序出错处理程序(字符串)讨论

351为什么有这么多编程语言？（科学计算浮点数组FORTRAN，商业应用报表信息提取SQL，系统控制操纵资源C/C++)2为什么还有新语言？程序员培训成本广泛使用的语言适应新变化缓慢开始新语言容易新应用范围新语言长得像旧的（javavsC++）3什么是好编程语言？没有统一的语言设计标准用户越多就越好？第2章文法和语言的基本知识36研究语言的翻译，首先要解决的问题语言自身如何描述？第2章文法和语言的基本知识37形式语言理论是编译的重要理论基础。本章主要介绍编译理论中用到的有关形式语言理论的最基本概念，重点介绍如何采用形式化的方法描述程序设计语言。第2章文法和语言的基本知识乔姆斯基（NoamChomsky,1928--）美国语言学家，转换-生成语法的创始人。1955年完成博士论文《转换分析》，获得博士学位。曾任该校语言学与哲学系主任，并任该校认知科学研究中心主任，为语言学界培养了一批有素养的学者。38第2章文法和语言的基本知识39字母表和符号串文法和语言的形式定义短语、直接短语和句柄语法树和文法的二义性文法和语言的分类2.1概述例如语句s＝2*3.1416*r*(r+h)40语法：赋值语句由一个变量，后随一个赋值号“＝”，其后面再跟一个表达式构成。语义：首先计算语句右部表达式的值，然后把所得结果送给左部变量中。语用：赋值语句可用来计算和保存表达式的值。形式化的方法,是用一整套带有严格规定的符号体系来描述问题的方法形式语言(FormalLanguage)理论是编译的重要理论基础如何采用形式化的方法描述程序设计语言2.1概述412.2字母表和符号串1.字母表(Alphabet)元素的非空有穷集合。例如，∑={a,b,c}根据字母表的定义，Σ是字母表，它有a、b、c三个元素例如，∑'={0,1}组成。∑‘是字母表，它有0、1两个元素422.2字母表和符号串2.符号（字符）Symbol字母表中的元素称为符号或称为字符。43

2.2字母表和符号串3.符号串(Stringorword)（字）符号的有穷序列称为符号串。设有字母表∑={a,b,c}符号串a，b，ab，ba，cba，

abc…

442.2字母表和符号串不包含任何符号的符号串,称为空符号串，用ε表示。45空符号串由0个符号组成，其长度|ε|=02.2字母表和符号串1.符号串的连结设x和y是符号串，则串xy称为它们的连结。例如，设X＝ABC，Y＝10A则XY＝ABC10AYX＝

10AABC462.2字母表和符号串2.集合的乘积设A和B是符号串的集合,则A和B的乘积定义为：47AB={xy|x∈A,y∈B}2.2字母表和符号串例如：设A={a,b},B={c,d}48{

}A＝A{

}＝

A则AB={ac,ad,bc,bd}由于对任意的符号串x，总有

x=x

=x所以,对任意集合A,我们有:

是符号串{

}表示由空符号串

所组成的集合Φ表示空集合{}2.2字母表和符号串492.2字母表和符号串3.符号串的幂运算50设x是符号串,x的幂运算定义为：x0=

x1=xx2=xxx3=xxx

…xn=xx…x=xxn-1(n>0)n注意：x0≠12.2字母表和符号串例如,设x＝abc则51x0=__x1=__x2=xx=__

…2.2字母表和符号串4.集合的幂运算设A是符号串的集合，则集合A的幂运算定义为A0={}A1=AA2=AA…An=AA…A(n个)=AAn-1(n>0)52例如，设A={a,b}，则A0=__A1=A={a,b}A2=AA=_______

…A3=AAA=A2A={aaa,aab,aba,abb,baa,bab,bba,bbb}2.2字母表和符号串532.2字母表和符号串5.集合A的正闭包A＋与闭包A*54设A是符号串的集合，则A的正闭包A＋和A的闭包A*的定义为:A+=A1∪A2∪…∪An…A*=A0∪A1∪A2∪…∪An…A*={ε}∪A+2.2字母表和符号串例如，设A={a,b},则：55A+={a,b,aa,ab,ba,bb,aaa,aab,…}A*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}2.3.1形式语言(FormalLanguage)56每个形式语言都是某个字母表上按某种规则构成的所有符号串的集合。序列的集合称为形式语言。• NoteverystringofEnglishcharactersisanEnglishsentence• Note:ASCIIcharactersetisdifferentfromEnglishcharacterset57Alphabet=EnglishcharactersLanguage=EnglishsentencesAlphabet=ASCIILanguage=Cprograms2.3.1形式语言例如，设有字母表A={a,b,c}，则58

均表示字母表A上的一个形式语言。L1={a,b,c}L2={a,aa,ab,ac}L3={c,cc}2.3.1形式语言例如，设字母表∑={0,1},则59∑+=∑1∪∑2∪∑3∪…={0,1,00,10,11,01,000,100,…}当语言为无穷集合时，如何能描述这个集合呢？A→0A→1A→A0A→A1∑+=∑1∪∑2∪∑3∪…∑+={0,1,00,10,11,01,000,100,…}A01001001112.3.1形式语言60从无穷到有穷2.3.1形式语言运用类似于递归、数学归纳法的方法，解决无穷语言的问题。61有穷规则无穷集合2.3.1形式语言Lindenmayer系统（L

System)是1968年由匈牙利生物学家林登麦伊尔提出的有关生长发展中的细胞交互作用的数学模型，尤其被广泛应用于植物生长过程的研究。622.3.1形式语言自动机理论:形式语言和形式文法乔姆斯基层级文法语言极小自动机类型0无限制递归可枚举图灵机n/a(无公用名)递归判定器类型1上下文有关上下文有关线性有界n/a附标附标嵌套堆栈n/a树-邻接适度上下文有关嵌入下推类型2上下文无关上下文无关非确定下推n/a确定上下文无关确定上下文无关确定下推类型3正则正则有限每个语言或文法范畴都是其直接上面的范畴的真子集。632.3.2文法的形式定义1.

规则

也称产生式规则是一个符号与一个符号串的有序对（A,β），写作：64A→β（或A∷＝β)2.3.2文法的形式定义65例如，前述例中一组规则

A→0A→1A→A0A→A1∑+={0,1,00,10,11,01,000,100,…}2.3.2文法的形式定义2.文法规则的非空有穷集合，通常表示成四元组66

VN是规则中非终结符号的集合。VT是规则中终结符号的集合。P

是文法规则的集合。

G=(VN,VT,P,S)开始符合关键缩写为：A→

1|

2|…

|

nA→

1A→

2A→

n

…

对左部相同的规则候选式2.3.2文法的形式定义672.3.2文法的形式定义前例中描述∑+的文法是:68G=(VN，VT，P，S)VN={A}VT={0，1}P={A→0|1|A0|A1}S=A∑+={0,1,00,10,11,01,000,100,…}2.3.2文法的形式定义例1

设字母表∑={a,b}，

设计一个文法描述语言L={a2n,b2n|n≥1}69当n＝1L={____}……L={aa,bb,aaaa,bbbb,aaaaaa,bbbbbb,…}L={a2n,b2n|n≥1}当n＝2L={_______}当n＝3L={aaaaaa,bbbbbb}L是由偶数个a，偶数个b这样的符号串组成的集合2.3.2文法的形式定义702.3.2文法的形式定义71因此，定义语言L的文法

G=(VN，VT，P，S)其中：

VN={A,B,D}VT={a,b}P={A→aaS=AB→aaD→bb|bbD}|bb|bbD注意:VT≠{aa,bb}|aaB|aaB2.3.2文法的形式定义72问题:描述该语言的文法是否唯一？P':A→B|DB→aa|aBaD→bb|bDbG"是否是描述该语言的文法？2.3.2文法的形式定义73G"=({A},{a,b},P",A)其中P"={A→aa|bb|Aaa|Abb}2.3.2文法的形式定义例2试设计一个表示所有标识符的文法74

2.3.2文法的形式定义75G=(VN，VT，P，S)其中：

VN={I,L,D}VT={a,b,c,…

x,y,z,0,1,2,…,9}P={I→LS=IL→a|b|c|…|x|y|zD→0|1|2|3|…|9}|IL|ID2.3.2文法的形式定义76将定义标识符的文法设计成：

G=(VN，VT，P，S)P={I→L|IDL→a|b|c|…|x|y|zD→0|1|2|3|…|9}2.3.2文法的形式定义77字母字母或数字串2.3.2文法的形式定义P:I→L|LTT→L|D|LT|DTL→a|b|c|…|x|y|zD→0|1|2|3|…|978字母字母或数字串2.3.2文法的形式定义例3已知自然语言描述的算数表达式如下，请用文法定义之。算术表达式定义用自然语言描述如下：变量i是一个表达式；若

E1和E2是算术表达式,则E1＋E2、E1*E2、(E1)也是算术表达式。79

G=({E},{i,+,*,(,)},P,E)其中P={E→i|E+E|E*E|(E)}{i,i+i,i*i,i+i*i,(i+i),…}2.3.2文法的形式定义802.3.2文法的形式定义例4设字母表Σ={a,b},

试设计一个文法，描述语言L={abna|n≥0}81请同学分析,该语言中串的结构特征是?

2.3.2文法的形式定义例5设字母表∑={(,)},

试设计一个文法描述语言L={(n)n|n≥0}82请同学分析,该语言中串的结构特征是?2.3.3语言的形式定义1.直接推导83令G是一文法，称xAy直接推导出xαy，即xAy

xαy仅A→α是G的一条规则,且x,y

(VN∪VT)*。从符号串xAy直接推导出xαy仅使用一次规则2.3.3语言的形式定义例如，设有文法G[S]:84S

01使用规则S

01此时x＝

，y＝

P为：S→01|0S1

有如下直接推导：S

0S1使用规则S

0S1此时x＝

，y＝

0S1

0011使用规则S

01此时x＝0，y＝100S11

000S111使用规则S

0S1此时x＝00,y＝11000S111

00001111使用规则S

01此时x＝000y＝111S→01|0S12.3.3语言的形式定义852.3.3语言的形式定义2.推导86

如果存在一个直接推导序列：α0

α1

α2

…

αn从0出发，经一步或若干步（使用若干次规则）可推导出n对i+i*i有如下直接推导序列:我们可记为

其中P为：E→E+T|TT→T*F|FF→(E)|iE

E+T

T+T

F+T

i+T

i+T*F

i+F*F

i+i*F

i+i*iEi+i*i+2.3.3语言的形式定义例设有文法G[E]=({E,T,F},{i,+,*,(,)},P,E)872.3.3语言的形式定义3．广义推导88我们有：

0

n表示从

0出发，经0步或若干步，可推导出n。*

0

n意味着0

n或者0=

n。*+EE*Ei+i*i*E→E+T|TT→T*F|FF→(E)|i2.3.3语言的形式定义4.句型和句子89设有文法G[S]（S是文法G的开始符号）

如果S

x,x

∈(VN∪VT)*

则称符号串x

为文法G[S]的句型。*

如果S

x,x

∈VT*

则称符号串x为文法G[S]的句子。*我们有:

符号串01、0S1、00S11和000111都是文法G[S]的句型；01和000111又是文法G[S]的句子。S

01*S

0S1*S

00S11*S

000111*2.3.3语言的形式定义例1设有文法G[S]：S→01|0S190试证明符号串(i*i+i)是文法G[E]的一个句子。E→E+E|E*E|(E)|i2.3.3语言的形式定义例2设有文法G[E]：91E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)即有E(i*i+i),所以符号串(i+i*i)是文法G[E]的一个句子。*2.3.3语言的形式定义E→E+E|E*E|(E)|i922.3.3语言的形式定义5．语言

文法G[S]产生的所有句子的集合称为文法G所定义的语言,记为L(G[S])：

L(G[S])={x|Sx且x∈VT*}93*2.3.3语言的形式定义94例3设有文法G[S]：S→01|0S1求该文法所描述的语言是什么？2.3.3语言的形式定义95我们应用第二个规则n－1次，然后再应用第一个规则1次，有：S0S100S11…0n-1S1n-10n1n即S0n1n*可见，此文法定义的语言为L(G[S])={0n1n|n≥1}S→01|0S12.3.3语言的形式定义96例4设有文法G[S]：S→0S|1S|ε该文法所定义的语言是什么？由该文法所确定的语言为L(G[S])={ε,0,1,00,01,10,11,…}={x|x∈{0,1}*}例5设有文法G[A]：该文法所定义的语言是什么？

A→yBB→xB|x2.3.3语言的形式定义972.3.3语言的形式定义98形式语言理论可以证明如下两点：(1)给定一种语言，能确定其文法，但这种文法不是唯一的，即：L→G1或G2或…(2)给定一个文法，就能从结构上唯一确定其语言，即：G→L(G)；2.3.4规范推导和规范归约99例如，设有文法G[N1]N1→NN→ND|DD→0|1|2①N1NNDN2D212②N1NNDDD1D12③N1NNDDDD212句子12有下列三种不同的推导序列:2.3.4规范推导和规范归约100例设有文法G[S]:请给出句子101001的最右、最左推导。

S→ABA→A0|1BB→0|S12.3.4规范推导和规范归约101S

AB

AS1

AAB1

AA01

A1B01

A1001

1B1001

101001句子101001的最右推导为:S→ABA→A0|1BB→0|S12.3.4规范推导和规范归约最左推导：是指在推导过程中任何一步α

β(α和β是句型),都是对α的最左非终结符进行替换。102句子101001的最左推导为：S→ABA→A0|1BB→0|S1S

AB

1BB

10B

10S1

10AB1

101BB1

1010B1

101001若用

表示归约，设A→α是文法G中的一个规则，则我们有：.xAyxαyxαyxAy.2.3.4规范推导和规范归约归约是与推导相对的概念103则有规范归约：规范推导的逆过程，称为最左归约，也称为规范归约。N1NNDN2D21212D2.N2.ND.N.N1.2.3.4规范推导和规范归约例如，例文法G[N1]中有规范推导：1042.3.5递归规则与文法的递归性递归规则105如果文法中有规则A→A…称为规则左递归。如果文法中有规则A→…A称为规则右递归。如果文法中有规则A→…A…称为规则递归。2.3.5递归规则与文法的递归性文法的递归性106若文法中有推导AA…称文法左递归。+若文法中有推导A

…

A称文法右递归。+若文法中有推导A

…A…称文法递归。+这三条规则都不是递归规则，但有

U→VxV→Uy|zU

VxUyx则该文法是左递归的。2.3.5递归规则与文法的递归性例如文法中有如下规则：107由于该文法无递归性，由它所描述的语言是有穷的。该文法描述的语言为:A→aB|bBB→a|bL(G[A])={}2.3.5递归规则与文法的递归性例2考虑文法G[A]：108aa,ab,ba,bb定义的语言为N1→NN→ND|DD→0|1|22.3.5递归规则与文法的递归性例3考虑文法G[N1]109{0,1,2}+课堂练习1设文法的规则如下：A→A1|A0|Aa|Ac|a|b|c，

该文法的句子是。A.bc10B.bbbbC.bcbcD.10012若一个不含多余规则的文法是递归的，则该文法生成语言的句子个数______。A.是有穷的B.是无穷的

C.对具体文法才可以确定D.无法确定1102.4短语、直接短语和句柄短语G[s]是一个文法,假定αβδ是文法G的一个句型，如果有则称β是相对于非终结符A的,句型αβδ的短语。S

αAδ*+且A

β

2.4短语、直接短语和句柄直接短语则称β是直接短语。S

αAδ*且A

β

令G是一个文法，S是文法的开始符号，假定αβδ是文法G的一个句型，如果有2.4短语、直接短语和句柄句柄

一个句型的最左直接短语称为该句型的句柄。句柄特征：(1)它是直接短语，即某规则右部。(2)它具有最左性。2.4短语、直接短语和句柄例如设有文法G[S]=({S,A,B},{a,b},P,S)

其中P为：求句型baSb的全部短语、直接短语和句柄。S

ABA

Aa|bBB

a|Sb2.5语法树与文法的二义性推导和语法树1.语法树对句型的推导过程给出一种图形表示,这种表示称为语法树，也称推导树。2.5.1推导和语法树例如设有文法G[E]:构造句型i*i+i的语法树。E

E+T|E–T|TT

T*F|T/F|FF

(E)|i2.5.1推导和语法树根据推导过程构造句型i*i+i的语法树如下：EE+TEE+TT+TTT*F+TT*FF*F+TFi*F+Tii*i+Tii*i+FFi*i+ii2.5.1推导和语法树2.子树语法树的子树是由某一结点连同所有分枝组成的部分。EE+TTT*FFiiFi2.5.1推导和语法树句型的短语、直接短语和句柄的直观解释：短语：子树的末端结点形成的符号串是相对于子树根的短语。直接短语：简单子树的末端结点形成的符号串是相对于简单子树根的直接短语。句柄：最左简单子树的末端结点形成的符号串是句柄。2.5.1推导和语法树短语:EE+TTT*FFiiFii*i+ii*i第一个i第二个i第三个i三个i都是直接短语第一个i是句柄句子i*i+i2.5.1推导和语法树前例对文法G[S]=({S,A,B},{a,b},P,S)其中P为：S

ABA

Aa|bBB

a|Sb2.5.1推导和语法树分析

首先根据句型baSb的推导过程画出对应的语法树如下：

Sb

为句型的相对于B的短语、直接短语baSb

为句型的相对于S的短语ba

为句型的相对于A的短语a

句型的相对于B的短语、直接短语和句柄SABbBBbaBbaSbSABASbbBSbbaSbSABbBSba由语法树可知文法的某个句型是否只对应唯一的一棵语法树呢？或者，它是否只有唯一的一个最左推导呢？它是否只有唯一的一个最右推导呢？2.5.2文法的二义性对于文法G中任一句型的推导序列,我们总能为它构造一棵语法树。问题：2.5.2文法的二义性文法G[E]：

E

E+E|E*E|(E)|i2.5.2文法的二义性最左推导1EE+EE*E+Ei*E+Ei*i+Ei*i+i

EE*Ei*Ei*E+Ei*i+Ei*i+i

EE*EE+EiiiEE+EE*Eiii最左推导22.5.2文法的二义性如果一个文法存在某个句子，对应两棵不同的语法树，则这个文法是二义性的。如果一个文法存在某个句子，有两个不同的最左(最右)推导，则这个文法是二义性的。E

E+E|E*E|(E)|i2.5.3文法二义性的消除1.不改变文法中原有的语法规则,仅加进一些非形式的语法规定。EE+EE*Eiii2.5.3文法二义性的消除2.构造一个等价的无二义性文法。即将排除二义性的规则合并到原有文法中,改写原有的文法。 例如，对于上例文法G[E]，将运算符的优先顺序和结合规则：*优先于＋;＋、*

左结合加到原有文法中,可构造出无二义性文法如下：2.5.3文法二义性的消除则句子i*i+i只有唯一一棵语法树：E

E+T|TT

T*F|FF(E)|iEE+TTT*FFiiFi2.5.3文法二义性的消除例2定义某程序语言条件语句的文法G为:试证明该文法是二义性的S

ifbS|ifbSelseS|A2.5.3文法二义性的消除S

ifbS|ifbSelseS|A所以该文法是二义的。SifbSbSSifAelseASbSSifAelseAifbS句子ifbifbAelseA2.5.3文法二义性的消除消除文法的二义性可采用下面两种方法：不改变已有规则，仅加进一非形式的语法规定：else与前面最接近的不带else的if相对应。SifbSbSSifAelseA2.5.3文法二义性的消除2.改写文法G为G'S

S1|S2

S1

ifbS1elseS1|AS2

ifbS

|

ifbS1elseS2

G':S

ifbS|ifbSelseS|A(其它语句）G:2.5.3文法二义性的消除S

S1|S2

S1

ifbS1elseS1|AS2

ifbS

|

ifbS1elseS2

ifbSbifAelseASS2S1S1S1对改写后的文法，句子ifbifbAelseA只对应唯一的一棵语法树。2.5.3文法二义性的消除可能有两个不同的文法G和G’，而且其中一个是二义性的，另一个是无二义性的,但却有L(G)=L(G’),即这两个文法所产生的语言是相同的。2.5.3文法二义性的消除一个语言是二义性的，是指对它不存在无二义性的文法，这样的语言称为先天二义性的语言。L={aibjck|i=j或j=k且i,j,k≥1}2.6文法和语言的分类乔姆斯基将文法和语言分为四大类，即0型、1型、2型、3型。2.6文法和语言的分类3型文法（正规文法）右线性文法和左线性文法都称为3型文法。

若文法G=(VN,VT,P,S)中的每一条规则的形式为A

aB或Aa,其中：A,BVN,a

VT*,则称G是右线性文法。

若文法G=(VN,VT,P,S)中的每一条规则的形式为A

Ba或Aa,其中：A,BVN,a

VT*,则称G是左线性文法。3型语言由

有穷自动机识别。

3型文法也称正规文法。正规文法产生的语言称为正规语言。3型文法描述的语言是3型语言。2.6文法和语言的分类例如，用左线性正规文法和右线性正规文法定义标识符 用I代表标识符;l代表任意一个字母;d代表任意一个数字;则定义标识符的文法为：左线性文法:P:I→l|Il|Id右线性文法:P:I→l|lT

T→l|d|lT|dT2.6文法和语言的分类例如，用左线性正规文法和右线性正规文法定义无符号整数用N代表无符号整数;d代表任意一个数字；则定义的无符号整数文法为：左线性文法:P:N→Nd|d右线性文法:P:N→dN|d2.6文法和语言的分类2型文法（上下文无关文法）2型文法又称上下文无关文法，其产生的语言又称为上下文无关的语言。若文法G=(VN,VT,P,S)中的每一条规则的形式为A

β,其中：A

VN,β(VN∪VT)*则称G是2型文法。其描述的语言为？L2(G[S])={}其中：VN={S,A,B},VT={a,b}P={S

aB|bAA

a|aS|bAAB

b|bS|aBB}2.6文法和语言的分类例如，有2型文法G=(VN,VT,P,S)

x|x{a,b}+且x中a和b的个数相同2.6文法和语言的分类1型文法（上下文有关文法）1型文法也称为上下文有关文法，相应的语言又称为上下文有关语言。若文法G=(VN,VT,P,S)中的每一条规则的形式为αAβ

αμβ,其中：α,β(VN∪VT)*,A

VN,则称G是1型文法。

μ(VN∪VT)+2.6文法和语言的分类例如，有1型文法G=(VN,VT,P,S)

其中：VN={S,A,B},VT={a,b,c}P:S

aSAB|abBBA

BA'BA'

AA'

AA'

ABbA

bbbB

bccB

cc其描述的1型语言为L1(G[S])={

}anbncn|n≥12.6文法和语言的分类0型文法（无限制文法）若文法G=(VN,VT,P,S)中的每条规则αβ

是这样一种结构：而且α中至少含一个非终结符,则称G是0型文法。α(VN∪VT)+,β

(VN∪VT)*0型文法没有加任何限制条件，又称为无限制性文法，相应的语言称为无限制性语言。2.6文法和语言的分类例如，有0型文法G=(VN,VT,P,S)

其中：VN={A,B,S},VT={0,1}其描述的0型语言为L0(G[S])={

}P:S

0AB1B

0B

SA|01A1

SB1A0

S0B2.6文法和语言的分类L0

L1

L2

L32.7有关文法的实用限制和变换对文法的实用限制有以下两点：1.文法中不能含有形如A→A的规则。这种规则我们称之为有害规则。2.文法中不能有多余规则。所谓多余规则是指文法中出现以下两种规则：2.7有关文法的实用限制和变换例如设有文法G[S]:P:S

BdA

Ad|dB

Cd|AeC

CeD

e删除多余规则后的文法变换为:S->BdB-AeA->Ad|d本章小结本章重点介绍了语言的语法结构的形式描述、语法树以及文法的二义性,主要内容有：1.设计一个文法定义一个已知的语言(1)文法是一个四元组G=(VN,VT,P,S)，文法四大要素中，关键是一组规则,它定义（或描述）了一个语言的结构。从文法定义可知,文法对于程序设计者来说，文法给出了语言的精确定义和描述。本章小结(2)分析已知语言句子的结构特征,设计出相应的一组规则，但不唯一。(3)设计的文法必须能定义已知的语言,不能超出或缩小所定义语言的范围。(4)若语言是无穷集合,设计该语言的文法一定是递归的。分析根据语言句子的结构特征，设计出相应规则P2:S→ABL2={ab,abb,abbb,…aabb,aabbb,aabbbb,… aaabbb,aabbbb，…}A→aAb|abB→bB|ε本章小结例1.给出语言L2={anbm|m≥n≥1}的文法分析根据语言句子的结构特征，设计出相应规则P1':A→aB|aP1：A→aAa|a

或L1={a,aaa,aaaaa,aaaaaaa,aaaaaaaaa，…}B→aa|aBa本章小结例2.给出语言L1={a2n+1|n≥0}的文法本章小结例3.给出语言L3={anbmck|n,m,k≥0}的文法分析根据语言句子的结构特征，设计出相应规则P3:A→aA|bB|cC|εP3':A→aA|B或L3={ε,a,aa,aaa…,b,bb,bbb…,c,cc,ccc,…,ab,abb,…,bc,bcc，…}C→cC|εB→bB|cC|εC→cC|εB→bB|C本章小结例4.写一个文法,使其语言是正偶数的集合,每个偶数不以0开头。L4={2,4,6,8,10,12,14,16,18,20,22,24,26,…}P4:N→E′|AEN→2|4|6|8|BN'

或分析不以0开头的偶数集合中串的结构特征:A→D|AD′E→0|2|4|6|8D→1|2|3|…|9D'→0|1|2|3|…|9B→1|2|3|…|9|B0P4':E'→2|4|6|8N'→BN'|0|2|4|6|8A→0A1|εP

:S→1S0|0A1|ε 分析根据语言句子的结构特征,设计出相应规则L={ε,01,0011,…,10,1100,…,1010,100110,110100,11001100…}本章小结例5.给出语言L={1n0m1m0n|n,m≥0}的文法。P

:S→a|0S0|1S1 分析根据语言句子的结构特征，设计出相应规则L={a,0a0,1a1,01a10,10a01,00a00,11a11,101a101,110a011,100a001,…}W={ε,0,1,01,10,00,11,101,110,100,111,…}本章小结例6.给出语言L={WaWt

|W∈{0|1}*}，其中Wt表示W的逆的文法。本章小结2.已知一个文法，确定该文法所定义的语言。(2)给定一个文法，可根据语言和推导定义推导出文法的句子，从而确定出该文法所定义的语言。(1)文法所定义的语言

L(G[S])={x|S

x且x∈VT*}*本章小结(3)语言可用①自然语言描述。例如,L={x|x∈{a,b}+且x中a,b个数相同}②式子描述。例如L={a2nbb|n≥0}。③正规式描述。本章小结例1文法G[A]=({A},{a,b},{A→bA|a},A)所生成的语言是什么？分析∵A

bA

bbA

bbbA

…

bnA

bna∴L(G[A])={bna|n≥0}N→ND|DD→0|1|2|3|4|5|6|7|8|9(1)G[N]所生成的语言是什么？(2)给出句子0127的最左、最右推导。本章小结例2文法G[N]为:本章小结N→ND|DD→0|1|2|3|4|5|6|7|8|9L(G[N])={α|α∈{0,1,2,…9}+}={α|α为可带前导0的正整数}={α|α为数字串}最左推导:N

ND

N7

ND7

N27

ND27

N127

D127

0127最右推导:N

ND

NDD

NDDD

DDDD

0DDD

01DD

012D

0127本章小结例3.已知文法G[S]=({A,B},{a,b,c,d},P,S),其中P为:分析∵S

AB

aAbB

a2Ab2B

…

an-1Abn-1B

anbnB

anbncBd

anbnc2Bd2

…

anbncm-1Bdn-1

anbncmdm

∴L(G[S])={anbncmdm|n,m≥1}该文法所生成的语言是什么？A→aAb|abB→cBd|cdS→AB本章小结3.求句型的短语、直接短语和句柄(1)短语、直接短语和句柄是对某句型而言的。(2)短语总是句型的某个子串，它对应子树未端结点形成的符号串。(3)直接短语是某条规则右部，它对应简单子树未端结点形成的符号串。(4)最左边的直接短语是句柄。证明E+T*F是它的一个句型,指出这个句型的短语﹑直接短语和句柄。∵E

E+T

E+T*F短语:E+T*F、T*F∴E+T*F是它的一个句型。画出该句型的语法树:句柄:T*F直接短语:T*FETFT+E*E→E+T|E-T|TT→T*F|T/F|FF→(E)|i本章小结例1

已知文法G[E]：本章小结例2

已知文法G[S]：试找出符号串(a)和(A((SaA)(b)))的短语﹑直接短语和句柄(如果有的话)。S→(AS)|(b)A→(SaA)|(a)∴符号串(a))不是文法的句型，因此它没有短语﹑直接短语和句柄。分析∵S

(AS)

((a)S)

(a)/本章小结S→(AS)|(b)A→(SaA)|(a)∵S

(AS)

(A(AS))

(A(A(b)))

(A((SaA)(b)))∴符号串(A((SaA)(b)))是文法的句型，画出该句型的语法树如下图：本章小结从句型的语法树求短语:

(A((SaA)(b)))((SaA)(b))(SaA)(b)直接短语：(SaA)、(b)句柄：(SaA)SA(S)A(S)(SaA))b(S→(AS)|(b)A→(SaA)|(a)对于句型(A((SaA)(b)))本章小结4．文法二义性的判断一个文法存在某个句子对应两棵不同的语法树或对应两个不同的最左（最右）推导，则该文法是二义性的。

试证明文法G[S]有二义性。分析因为对文法的句子iiiei有如下两棵不同的语法树与之对应，所以该文法是二义的本章小结例1设有文法G[S]:S→iSeS|iS|i本章小结S→iSeS|iS|i句子iiiei对应下面两颗语法树：SSieSiSiiSiSiSieSi本章小结例2设有文法G[N]:N→SE|ES→SD|DE→0|2|4|6|8|10D→0|1|2|3|4|5|6|7|8|91.

试证明文法G[N]有二义性。2.

此文法所描述的语言是什么？

3.试写出另一文法G'使L(G')=L(G)且G'是无二义性的。本章小结分析因为对文法的句子10有两棵不同的语法树与之对应，所以该文法是二义的NES0D1NE01N→SE|ES→SD|DE→0|2|4|6|8|10D→0|1|2|3|4|5|6|7|8|9本章小结N→SE|ES→SD|DE→0|2|4|6|8|10D→0|1|2|3|4|5|6|7|8|9该文法所描述的语言是所有无符号偶数的集合(可以0开头)。改写后的文法G‘[S]为:

N→SE|ES→SD|DE→0|2|4|6|8D→0|1|2|3|4|5|6|7|8|9第3章词法分析与有穷自动机

词法分析程序功能

单词符号及输出单词的形式

语言单词符号的两种定义方式

正规式与有穷自动机

正规文法与有穷自动机

词法分析程序的编写方法175intfib(intn){if(n<=1)returnn;returnfib(n-1)+fib(n-2);}chara[100]="Enteraninteger:";intmain(){print_string(a);intmax=read_int();intn=1;do{print_int(fib(n++));print_string("\n");}while(n<=max);return0;}关键字

if，while,do标识符

各种名字，如变量名、常量名、数组名、函数名等。常数整型常数125、实型常数0.718、布尔型常数TRUE等。运算符＋、－、*、/、＜等。分界符，、；、（、）、：等。1763.1词法分析程序的功能语言的单词符号是指语言中具有独立意义的最小语法单位。1773.1词法分析程序的功能3.1词法分析程序的功能1783.1词法分析程序的功能179

字符串表示的源程序词法分析器字符单词符号取下一个单词符号语法分析器输入:if(a＞1)b=100；3.2单词符号及输出单词的形式词法分析程序输出单词的形式词法分析程序所输出的单词符号通常表示成如下的二元式：180

（单词种别，单词自身的值）3.2单词符号及输出单词的形式例子:if(a＞1)b=100；181标识符的种别编码整数10；常数的种别编码整数11；基本字if种别编码2；赋值号的种别编码17；大于号的种别编码23；分号的种别编码26；左括号的种别编码29；右括号的种别编码30；3.2单词符号及输出单词的形式if(a＞1)b=100；182（2,）基本字if（29,）左括号(（10,‘a’）标识符a（23,）大于号＞（11,1）常数1（30，）右括号)（10，‘b’）标识符b（17，）赋值号=（11，100）常数100（26,）分号；问题：下面的内容表达什么？\A(?:[a-z0-9!#$%&'*+/=?^_‘{|}~-]+(?:\.[a-z0-9!#$%&'*+/=?^_‘{|}~-]+)*|"(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21\x23-\x5b\x5d-\x7f]|\\[\x01-\x09\x0b\x0c\x0e-\x7f])*")@(?:(?:[a-z0-9](?:[a-z0-9-]*[a-z0-9])?\.)+[a-z0-9](?:[a-z0-9-]*[a-z0-9])?|\[(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?|[a-z0-9-]*[a-z0-9]:(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21-\x5a\x53-\x7f]|\\[\x01-\x09\x0b\x0c\x0e-\x7f])+)\])\z1833.3单词符号的两种定义方式正规式例子：l(l|d)*对应的正规文法：I→l|Il|Id或：I→l|lTT→l|d|lT|dT/quickstart.html184

3.3.1正规式和正规集设有字母表Σ={a1,a2,…,an}，在字母表Σ上的正规式和它所表示的正规集可用如下规则来定义：1.Φ是Σ上的正规式，它所表示的正规集是Φ，即空集{}。2.ε是Σ上的正规式，它所表示的正规集仅含一空符号串，即{ε}。3.ai是∑上的一个正规式，它所表示的正规集是由单个符号ai所组成，即{ai}。1853.3.1正规式和正规集4.如果e1和e2

是∑上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，则：(1)e1|e2是∑上的一个正规式，它所表示的正规集为L(e1|e2)=L(e1)∪L(e2)(2)e1e2也是∑上的一个正规式，它所表示的正规集为L(e1e2)=L(e1)L(e2)(3)(e1)*也是∑上的一个正规式，它所表示的正规集为L((e1)*)=(L(e1))*1863.3.1正规式和正规集例1设有字母表Σ={a,b}，根据正规式与正规集的定义有：1.a和b是正规式，正规集为L(a)={a},L(b)={b}2.a|b是正规式，正规集为L(a|b)=L(a)∪L(b)={a,b}3.ab是正规式，正规集为L(ab)=L(a)L(b)={a}{b}={ab}1873.3.1正规式和正规集4.(a|b)*是正规式，相应正规集为L((a|b)*)=(L(a|b))*

={a,b}*={ε,a,b,aa,ab,ba,bb,…}问题：{a,b}*的子集{anbn|n≥1}是正规集吗？1883.3.1正规式和正规集5.ba*是正规式，正规集为L(ba*)=L(b)L(a*)={b,ba,baa,baaa,…}6.(a|b)*(aa|bb)(a|b)*是正规式，正规集为L((a|b)*(aa|bb)(a|b)*)=L((a|b)*)L(aa|bb)L((a|b)*)＝{a,b}*{aa,bb}{a,b}*1893.3.1正规式和正规集例2设Σ={a,b,c},则aa*bb*cc*是∑上的一个正规式,它所表示的正规集：L={abc,aabc,abbc,abcc,aaabc,