编译原理课件(龙书为教材)

编译原理12/17/20241自我介绍姓名：辛明影电话： 86413213

教研室：计算机软件基础办公室：综合楼513

xmy63@xmy63@126.com助课教师：洪晓鹏，综合楼614

单丽丽，新技术楼60812/17/2024计算机学院

2辛明影开课目的及应用前景：

介绍设计与构造程序设计语言编译程序的原理与方法源程序编译程序目标程序连接可执行程序预备知识：形式语言与自动机、两门以上的高级程序设计语言汇编语言数据结构等How?12/17/2024计算机学院

3辛明影内容简介：第一章：编译器的基本结构第二章：高级语言及其语法描述第三章：词法分析器第四章：语法分析技术第五章：语法制导翻译的主要概念及中间代码第六章：程序运行时的存贮分配问题第七章：代码优化第八章：目标代码生成12/17/2024计算机学院

4辛明影教学设计：(1)自顶向下，逐步求精的方法(2)问题驱动(3)将课程设计成一个应用平台(4)用实验拓广课堂教学(5)精讲多练(6)承前启后教学目标：12/17/2024计算机学院

5辛明影第一章绪论编译器就是一个程序，它读入用某种语言编写的源程序，并翻译成一个与之等价的另一种语言编写的源程序。编译器源程序目标程序错误信息Fortran、Pascal、Java、C…..另一种程序设计语言、汇编语言、机器语言1.1什么叫编译程序12/17/2024计算机学院

6辛明影1.2编译过程概述编译程序的工作，从输入源程序开始，到输出目标程序结束，与自然语言之间的翻译有很多相似之处。一段英文翻译成中文，需经下列步骤：识别出句子中的单词分析句子的语法结构根据句子的含义进行初步分析对译文进行修饰写出最后的译文编译程序词法分析代码优化语法分析语义分析及中间代码生成目标代码生成构成编译程序各个阶段Iamaexperiencedteacher.12/17/2024计算机学院

7辛明影编译器的各个阶段：编译器是分阶段执行的。每个阶段将源程序从一种表示转换成另一种表示源程序词法分析器错误处理器符号管理表语法分析器语义分析器中间代码生成器代码优化器代码生成器编译的各个阶段12/17/2024计算机学院

8辛明影各分析阶段随着编译器各个阶段的进展，源程序的内部表示不断地发生变化。以a=b+c*d

为例1。词法分析读入源程序完成的任务：识别出单词：a、=、b、+、c、*、d并用记号方式表示识别出的单词关键字、标识符、常数、算符和界符例：25表示a、b、c、d；36：＝；３2：＋；31：*记号表示逻辑上相关的字符序列，常用整数来表示上述单词表示为：(25,a),(36,_),(25,b),(32,_),(25,c),(31,_),(25,d)12/17/2024计算机学院

9辛明影语法分析在词法分析的基础上，根据语言的语法规则，把单词符号串组成各类语法单位.具体的说，语法分析是在单词流的基础上建立一个层次结构-----建立语法树赋值语句标识符=表达式a表达式标识符b+表达式表达式*标识符c表达式标识符d12/17/2024计算机学院

10辛明影语义分析阶段语义分析利用语法分析阶段确定的层次结构来识别表达式和语句中的操作信息及类型信息=+ab*c

dtemp1=c*dtemp2=b+temp1temp1temp2a=temp212/17/2024计算机学院

11辛明影中间代码生成阶段本阶段将产生源程序的一个显式中间表示这种中间表示可以看成是某种抽象的程序，通常是与平台无关的其重要性质：1.易于产生

2.易于翻译成目标程序下面是用三地址码和四元式表示的例子：temp1=c*dtemp2=b+temp1a=temp2（*,c,d,tempt1)(+,b,tempt1,tempt2)(=,tempt2,,a)12/17/2024计算机学院

12辛明影代码优化阶段试图改进中间代码，以产生执行速度较快的机器代码对上面中间代码进行优化处理后，产生如下的代码：temp1=c*da=b+temp1temp1=c*dtemp2=b+temp1a=temp212/17/2024计算机学院

13辛明影代码生成阶段生成可重定位的机器代码或汇编代码MovfR2，cMultR2,dMovfR1,bAddfR2,R1Movfa,R212/17/2024计算机学院

14辛明影1.3符号表管理int

a,b;floate,fcharch1,ch2;为什么要先说明?

定义了变量的类型，也就规定了变量在内存中的存放形式，在其上所能进行的运算解决符号地址到存贮地址上的映射12/17/2024计算机学院

15辛明影

编译器的一个基本功能是记录源程序中使用的标识符并将它们记载到符号表中。符号表是一个数据结构。每个标识符在符号表中都有一条记录名字记号类型种属……addrid1(25)id2(25)ba例：inta,b;int简变

0

4

并收集与每个标识符相关的各种属性信息，int简变12/17/2024计算机学院

16辛明影符号表的接口：符号表的作用就是存放字符串或词素当一个字符串或词素被保存时，与之相对应的记号也被保存符号表上的操作：Insert(s,t):将符号串s和记号t插入符号表，返回相应表项的指针Lookup(s):在符号表中查找字符串s，查找成功返回相应指针，否则返回012/17/2024计算机学院

17辛明影关键字的处理通常情况下，将关键字存在符号表中，作为符号表的初值。当词法分析程序识别出一个标识符s后，用lookup(s)查找符号表，如果是关键字，返回相应的记号；如果是变量名，返回记号id12/17/2024计算机学院

18辛明影符号表的实现固定长标识符：采用前面的结构不定长标识符：使用单独的数组lexemesifeosinteospositioneosinitialeosIf(12)Int(13)Id1(25)Id2(25)存放标识符的字符串,符号表中存放标识符在lexemes的起始位置和相应记号12/17/2024计算机学院

19辛明影1.4编译各阶段的分组一、前端和后端前端包括词法分析、词法分析、语义分析，以及相关的错误处理和符号表的建立前端依赖于源程序并在很大程度上独立于目标机器。12/17/2024计算机学院

20辛明影后端主要包括代码优化、代码生成和相关错误处理。后端依赖于目标机器。后端处理对象是由前端产生的结果，即中间代码前端生成与平台无关的字节码后端是由与平台有关的解释器对所生成的字节码文件进行解释执行Java语言的编译采用的是前端后端方式。12/17/2024计算机学院

21辛明影二、编译的遍编译的若干阶段通常是以一遍来实现的，每遍读一次输入文件、产生一个输出文件。12/17/2024计算机学院

22辛明影在编译的各个阶段都会发现源程序中的错误，1.5错误检测与报告为了使编译器能继续运行，以检测出源程序中更多的错误，在检测到错误后，必须以合适的方式进行错误处理。error12/17/2024计算机学院

23辛明影第二章高级语言

及其语法描述12/17/202424内容简介：本章概述程序设计语言的结构2.1程序语言的定义任何语言实现的基础是语言定义。语言的定义决定了该语言

具有什么样的语言功能、

什么样的数据结构、

什么样的程序结构、

以及具体的使用形式等细节问题。和主要的共同特征，并介绍程序设计语言主要语句的文法描述与形式定义。12/17/2024计算机学院

25辛明影

对于编译程序设计者来说：语言定义就是具体实现的理论依据。

对于语言用户来说：语言定义就是一本用户手册。2.1.1语法语言的语法是指这样一组规则，用它可产生一个程序。规则：词法规则语法规则12/17/2024计算机学院

26辛明影词法规则是指单词符号的形成规则字母表就是一个有穷字符集。C语言的字母表为：

∑={a---z、

A—Z、

0—9、(、)、

[、]、

、.、!、~、+、-、*、

/、&、%、<、>、=、^、

|、?、,、;}C语言的标识符的构成规则：

字母、下划线打头的字母、数字和下划线构成的符号串。如：a1、ave

、_day一.词法规则12/17/2024计算机学院

27辛明影上述的定义是用文字来描述的，当设计编译程序时，就要把它用形式的方式描述出来，就要用到形式语言。各类型的常数、标识符、基本字、算符和界符等正规式和有穷自动机是描述词法结构和进行词法分析的有效工具在现今多数程序设计语言中，单词符号一般包括：12/17/2024计算机学院

28辛明影C语言的标识符的文法和自动机描述：例：C语言标识符的文法描述L（G）={w/w为字母或‘-’打头的字母数字串}解：P:I→aBI→-BI→aB→aB

B→dBB→aB→d识别L（G）的自动机IBTa-a,d其它12/17/2024计算机学院

29辛明影SACDFEB7ddddddd

ee+–T*例：C语言实常数的文法描述文法：S→dAA→dAA→eDA→.BB→dCC→dCC→eDD→-ED→+ED→dFE→dFF→dFF→d其它其它其它10003.1410e+33.14e-512e50.1e2412/17/2024计算机学院

30辛明影二.语法规则语法规则规定了如何从单词符号形成更大的结构（即语法单位），换言之，语法规则是语法单位的形成规则一般的程序设计语言的语法单位有：表达式、语句、分程序、函数、过程和程序等

下推自动机理论和上下文无关文法是我们讨论语法分析的理论基础12/17/2024计算机学院

31辛明影表达式：

E→E+TE→E-TE→TT→T*FT→T/F

T→FF→(E)F→id主要语句的形式描述：12/17/2024计算机学院

32辛明影布尔表达式：

B→BorBB→BandBB→notBB→(E）

B→idrelopidB→trueB→false12/17/2024计算机学院

33辛明影赋值、分支、循环语句：

S→id=ES

→ifBthenS

S→ifBthenSelseS

S→whileBdoSS→{L}

L→L;S

L→S12/17/2024计算机学院

34辛明影调用语句：

S→callid(Elist)

Elist→Elist,E

Elist→E|ε12/17/2024计算机学院

35辛明影类型说明和过程说明语句：

P→DD→D;DD→id:TD→id（Elist）D;S

T→intT→float12/17/2024计算机学院

36辛明影数组说明语句：

L→id[Elist]

Elist→Elist,E

Elist→E12/17/2024计算机学院

37辛明影2.1.2

语义例：a=b+c*d例do999I=1,10

对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义，这就是语义问题对于编译程序来说，只有了解程序的语义，才知道应把它翻译成什么样的目标指令代码12/17/2024计算机学院

38辛明影2.2构造基础2.2.1程序结构简介一个高级语言程序通常由若干子程序段（过程、函数等）组成，许多语言还引入了类、程序包等更高级的结构12/17/2024计算机学院

39辛明影FORTRAN一个FORTRAN程序由一个主程序和若干个辅助程序段组成PROGRAMMAIN.ENDSUBROUTINESUB1..ENDFUNCTIONFUN1.END它的定义是并列的12/17/2024计算机学院

40辛明影

FORTRAN

的构成特点：同一名字在不同的程序段中一般都代表不同的对象，也就是说代表不同的存贮单元PROGRAMMAIN.integerxENDSUBROUTINESUB1Integerx.ENDIntegerxXX=9999100Integerx9999X=100XPROGRAMMAIN.

ENDSUBROUTINESUB1

.END一个名字对应多个对象12/17/2024计算机学院

41辛明影但是不同程序段里的同名公用块却代表同一个存贮区域PROGRAMMAIN.

Commona,bENDSUBROUTINESUB1

commonx,y.ENDPROGRAMMAIN.

ENDSUBROUTINESUB1

.ENDCommona,babA=100B=50

10050Commonx,yxyY=x+100200共享存贮单元多个名字对应一个对象12/17/2024计算机学院

42辛明影二。PascalPascal允许子程序嵌套定义

Programmain

说明部分Begin

可执行部分endPascal的程序结构Programmain

BeginendProcedureP1BeginendProcedureP11BeginendProcedureP2Beginend也允许并列定义12/17/2024计算机学院

43辛明影关于名字的作用域的规定：标识符X的任意一次出现（除去说明语句中）都意味着对某个说明语句中说明的这个变量X的引用此时，说明语句同标识符X应共处一个最小程序中，即：P1中说明的X只在P1中有效

P11是P1的内层子程序，P11中没有再对X作新的说明，则在P11中对X的引用，实际上引用的就是P1中说明的X，

即内部过程可以引用外部过程中定义的量12/17/2024计算机学院

44辛明影三.javaJava语言是一种面向对象的高级语言，它很重要的方面是类和继承的概念，同时支持多态性和动态绑定等特性Classcar{Intcolor_num;Intdoor_num;Intspeed;.Voidpush_break(){}

Voidadd_oil(){}}Classbenzextendscar

Doubleprice;VoidABS(){}

}12/17/2024计算机学院

45辛明影

一个类把有关的数据及其操作封装在一起构成一个抽象数据类型一个子类继承其父类的所有数据和方法，并且可以加入自己新的定义

在java中，变量和方法的定义之前可以加上public、private、pretected等修饰词，以限制其它类的对象对于这些变量和方法的使用12/17/2024计算机学院

46辛明影2.2.2构造基础程序设计语言的数据对象：数据、函数、过程常用能反映其本质的、有助于记忆的名字来表示一.名字特性：一个名字对应一个对象，普通变量多个名字对应一个对象一个名字对应多个对象，common,数组、重载、局部变量、重写、12/17/2024计算机学院

47辛明影

每个对象可以看做是一个存贮单元，可能是一个字，也可能是多个字名字具有属性，通常由说明语句给出一个名字的属性，包括：类型和作用域类型决定了它有什么样的值，作用域规定了值的存在范围

值在计算机内的表示，

以及对它能施加什么样的运算12/17/2024计算机学院

48辛明影二.数据类型1.初等数据类型①数值数据：整形、实型、双精度等，可施行算术运算②逻辑数据：可施行逻辑运算③字符数据：④指针类型：12/17/2024计算机学院

49辛明影三。数据结构1。数组从逻辑上讲，一个数组是由同类型数据所组成的n维矩形结构一个数组所需的存贮空间大小在编译时就已知道的，则称此数组是一个确定的数组；否则称为可变数组设intA[l1‥u1,][l2‥u2]……[ln‥un]为n维数组各维的长度：di=ui-li+1(1≤i≤n)12/17/2024计算机学院

50辛明影任一数组元素A[i1,i2,……in]的地址为：D=a+(i1-l1)d2d3……

dn

+(i2-l2)d2d2……

dn……+(in-1-ln-1)dn+(in-ln)

整理后C=(……

(l1d2+l2)d3+l3)d4+……

+ln-1)dn+ln

C是数组计算中不变的部分12/17/2024计算机学院

51辛明影变量部分：v=(……

(i1d2+i2)d3+i3)d4+……

+in-1)dn+in任一数组元素A[i1,i2,……in]的地址:

addr=a-c+v12/17/2024计算机学院

52辛明影在编译时，当遇到说明时，必须把数组的有关信息记录在一个“内情向量”之中，用于数组元素的地址计算。数组的内情向量包括：维数，各维的上、下限，首地址及数组的类型……lnundn…………l2l1unund1d2N维数C常数T类型A首地址12/17/2024计算机学院

53辛明影对于确定数组来说，内情向量可登记在符号表中；

对于可变数组，内情向量的信息在编译时无法全部知道，只有到运行阶段才能全部确定下来，存贮分配也要等到运行时方能进行12/17/2024计算机学院

54辛明影2.记录（结构）从逻辑上讲，记录是由已知的数据组合起来的一种结构

Structstudent{charname[20];

boolean

partmember;

intage;}stu;12/17/2024计算机学院

55辛明影记录结构最简单的存贮方式是连续存放上述的变量stu共占7个字，共28个字节

SStu.partmember

Stu.age3.字符串、表格和队列kK+1….K+20….K+24….….……….12/17/2024计算机学院

56辛明影四.抽象数据类型一个抽象数据类型包括：⑶这种类型对象的封装⑵作用于这些数据对象的抽象运算的集合⑴数据对象的一个集合C++、Java语言通过类对抽象类型提供支持12/17/2024计算机学院

57辛明影五.语句与控制结构1.表达式要解决的问题：①优先级②结合率2.语句语句可分为：①说明语句：②可执行语句：定义各种不同数据类型的变量和运算描述语句的动作执行语句分为：赋值、控制和I/O语句12/17/2024计算机学院

58辛明影⑴赋值句A=B左值右值名字的左值指它所代表的存贮单元地址名字的右值指该单元的内容12/17/2024计算机学院

59辛明影⑵控制语句无条件转移语句：Goto

lable条件语句：IfBthenSIfBthenSelseS循环语句：WhileBdoSRepeatSuntilBForI=e1toe2stepe3过程调用语句：CallP(x1,x2,….xn)返回语句：Return(E)12/17/2024计算机学院

60辛明影⑶说明语句说明语句用于定义名字的性质。编译程序把这些性质登记在符号表中，并检查程序中名字的引用和说明是否一致。许多说明语句不产生目标代码但有的说明语句，如过程说明和可变数组说明，则要产生相应的目标代码12/17/2024计算机学院

61辛明影⑷简单句和复合句简单句是指不包含其它语句成分的基本句。赋值、goto语句等复合句则指那些句中有句的语句If(x==0)thenx=1{x=1;y=2;gotol1;}12/17/2024计算机学院

62辛明影

programreference（input，output）；

vara，b：integer；

procedureswap（x，y：integer）；

vartemp：integer；

begintemp:＝x；

x：＝y；

y：＝temp

end;

begin

a：＝1;b：＝2;

swap(a，b);

writeln('a='，a，

'b=',b）

end.2.2.3参数传递

结果是什么？12/17/2024计算机学院

63辛明影1传值调用

实在参数和形式参数结合的方法：传值调用（call-by-value）

引用调用（call-by-reference）

复制恢复（copy-restore）

传名调用（call-by-name）12/17/2024计算机学院

64辛明影

子程序为每一个形参开辟一个存贮单元，用于存放相应实参的值。子程序执行时，每当访问形参时，就直接访问形参单元。实参：形参：传值调用可以实现如下：主调过程计算实在参数，并把它们的右-值放入到形式参数的存储空间中。12/17/2024计算机学院

65辛明影使用传值的方法，调用swap（a,b）等价于下面几步：

x：=a

y：=b

temp：=x

x：=y

y：=temp12/17/2024计算机学院

66辛明影2引用调用（传地址）

把实在参数的地址传递给相应的形式参数,

在目标代码中，在被调用过程中对形式参数的一次引用就成为对传递给被调用过程的指针的一个间接引用。Referenceabxy12swapabtemp12/17/2024计算机学院

67辛明影子程序为每个形参开辟一个单元，用于存放相应实参的地址，执行时，子程序间址方式访问这些形参单元

当实参为表达式或常数时，则存放它们值的临时单元。实参：地址形参：@Temp:=x;

x:=y;y:=temp;temp:=a;a:=b;b:=temp;12/17/2024计算机学院

68辛明影3复制恢复（传值结果）实现：

1.当控制流入到被调用过程之前，把实在参数的右-值和左-值传递到被调用过程中；

2.当控制返回时，把形式参数的现行右-值复制回到相应的实在参数的左-值中。12/17/2024计算机学院

69辛明影

子程序为每个形参分配两个存贮单元B1和B2，B1用于存放实参地址，B2用于存放实参值。

执行时，对B2单元使用直接访问形式；返回前，按B1中的地址把B2中的内容存入主调程序的实参单元中。实参：地址形参：B1B2@B112/17/2024计算机学院

70辛明影

在主调程序中设置计算实参地址和右值的形实替换子程序THUNK

子程序中为相应实参开辟一个形式单元，用于存放该实参的THUNK子程序的入口地址。

执行时，每当要对形参进行访问时，就调用THUNK子程序，以获得相应实参地址或值4传名调用对形参的访问是发生在实参单元上的12/17/2024计算机学院

71辛明影例：有程序段：procedurep(x,y,z)beginy=y+1;z=z+x;end

Begina=2;b=3;c=4;P(a,b,c);printa,b,c;end12/17/2024计算机学院

72辛明影传值：abc实参形参xyz234P(a,b,c);234y=y+1;

输出：23446Z=z+x;A=2B=3C=412/17/2024计算机学院

73辛明影传地址：abc实参形参xyz234P(a,b,c);&a&b&cy=y+1;@y=@y+1输出：24646Z=z+x;@z=@z+@x12/17/2024计算机学院

74辛明影传值结果：abc实参形参X—B1B2Y—B1B2Z—B1B2234&a&b

y=y+1;

输出：246Z=z+x;&c

按@B1返回B2

的值4

6

2344

612/17/2024计算机学院

75辛明影传名：abc实参形参xyz234P(a,b,c);&thunk&thunk&thunky=y+1;JSRThunkY→b输出：24646Z=z+x;

jsr

ThunkZ→c,x→a12/17/2024计算机学院

76辛明影例：有程序段：procedurep(x,y,z)beginy=y+1;z=z+x;end

Begina=2;b=3;P(a+b,a,a);printaend12/17/2024计算机学院

77辛明影传值：aba+b实参形参xyz23P(a+b,a,a);522y=y+1;

输出：2

37Z=z+x;A=2B=3512/17/2024计算机学院

78辛明影传地址：aba+b实参形参xyz235P(a+b,a,a);&a+b&a&ay=y+1;@y=@y+1输出：83Z=z+x;@z=@z+@x812/17/2024计算机学院

79辛明影传名：ab实参形参xyz23P(a+b,a,a);&thunk&thunk&thunky=y+1;JSRThunkY→a输出：939Z=z+x;

jsr

ThunkZ→a,x→a+b12/17/2024计算机学院

80辛明影第三章词法分析12/17/202481编译器的各个阶段：编译器是分阶段执行的。每个阶段将源程序从一种表示转换成另一种表示源程序词法分析器错误处理器符号管理表语法分析器语义分析器中间代码生成器代码优化器代码生成器编译的各个阶段12/17/2024计算机学院

82辛明影3.2词法分析器的手工构造：用DFA能识别3.3词法分析程序自动构造工具LEX简介3.1词法分析程序的设计：

12/17/2024计算机学院

83辛明影=80;0134256eniL字母字母字母字母数字数字数字==；；0124563Line=80;

id(25),‘Line’

=(

36),

num(27),‘80’

;(45),数字字母字母11==0003;;1输入输出有穷控制器单词的词类和属性（词类符号，单词的属性）12/17/2024计算机学院

84辛明影

3.1词法分析程序的设计二、扫描器的任务

一、词法分析程序的功能

源程序

单词序列

词法分析器1、组织源程序的输入2、识别单词，转换成机内表示形式3、删除注释行、空格及无用符号4、查填符号表5、检查词法错误12/17/2024计算机学院

85辛明影<12,><25,符号表入口><39,><25,符号表入口><20,><25,符号表入口><36,><26,常数表入口><8,><25,符号表入口><36,><26,常数表入口>ifi＞jtheni:＝0

elsej:=1词法分析if

I＞JThenI＝0

elsej=112/17/2024计算机学院

86辛明影三、词类和属性2．标识符：用来表示各种名字3．字面常数：256，3.14，true,‘abc’4．运算符：如，＋、－、*、/等等5．分界符：如逗号，分号，冒号等程序语言单词的分类：

1．关键字(保留字或基本字)：while,if12/17/2024计算机学院

87辛明影界符和运算符:词法分析器的输出：（词类编码，单词自身的属性值）关键字可分成一类，也可以一个关键字分成一类。常数可统归一类，也可按类型（整型、实型、布尔型等），每个类型的常数划分成一类。所有的标识符分为一类。词类编码原则:一字一码。一类型一码。一类一码。一符一码。12/17/2024计算机学院

88辛明影

表3.1单词词类编码12/17/2024计算机学院

89辛明影对于关键字、界符、运算符来说，它们的词类编码就可以表示其完整的信息，而对于标识符，词类编码所反映的信息不够充分，标识符的具体特性还要通过单词自身的属性进行互相区分。标识符的单词自身的属性常用其在符号表中的入口指针来表示故对于这类单词，其单词自身的属性值通常为空12/17/2024计算机学院

90辛明影对于常数，其单词自身的属性常用其在常数表中的入口指针来表示12/17/2024计算机学院

91辛明影

以语句子a=b+c*d为例，假设按表3.1为单词编码，词法分析后的结果为：Token字符号表a=b+c*da25<25,><36,--------><25,><32,--------><25,>b25<25,>c25

d25<31,-------->

12/17/2024计算机学院

92辛明影

四、词法分析的设计形式（1）设计成一个独立程序，完成词法分析的任务，结果以文件的形式组织，做为语法分析的输入源程序词法分析符号表TOKEN字错误信息12/17/2024计算机学院

93辛明影词法分析语法分析语义分析和中间代码生成源程序中间代码

符号表管理

错误的诊查处理（2）作为语法分析和语义分析的子程序12/17/2024计算机学院

94辛明影

五、词法分析程序的设计框图SCANNEROUTPUTsort字母RECOGID数字RECOGDIG/HANDLCOMRECOGDEC界符’RECOGSTRLOOKUP12/17/2024计算机学院

95辛明影3

2词法分析器的手工构造为了构造词法分析器，要研究构词法，每种词类的结构模式以及识别它的数学模型——有穷自动机。3

21确定的有限自动机（DFA）3

22构造识别单词的DFA3

23编写词法分析程序12/17/2024计算机学院

96辛明影SCANNEROUTPUTsort字母RECOGID数字RECOGDIG/HANDLCOMRECOGDEC界符’RECOGSTRLOOKUP12/17/2024计算机学院

97辛明影一、手工构造识别单词的DFAm

根椐DFA识别单词的定义，在研究给定程序语言单词结构的基础上，能直接构造出识别它的DFAm。例如：对于C语言整数：非空数字串。无符号实数（用d表示数字）:(a)dd.ddE(+-)ddddE(+-)dd(c)dd.dd0.1e+1412e-43.141592(d)dd…dd100012/17/2024计算机学院

98辛明影IBTTa-a,d其它例：C语言的标识符标识符：字母开始的字母数字串。12/17/2024计算机学院

99辛明影例：C语言实常数的文法描述01234567dddEdEd-+dd10003.141512e-40.1e+14.12/17/2024计算机学院

100辛明影在识别标识符的过程中，首先要拼写出来，并和保留字区别开来；识别出的标识符要填入符号表中二、编写词法分析程序根据画出的状态转换图（识别单词的）构造词法分析程序，每个状态对应一段程序，完成到达此状态的工作；在识别常数的过程中，要把它转换成机器表示以作为属性值，记录到常数表中。

词法分析程序的控制程序模拟状态转换图的状态转换。12/17/2024计算机学院

101辛明影programSCANNER;Begininitiate符号表,字符串表,行,列计数器;Open源文件,TOKEN文件,打印机文件;RepeatFIRSTCH(CH);ifCH!=EOLthencallSORT(CH)elseRDLINE;untilCH=EOF;把符号表,字符串表做成文件;close源文件,TOKEN文件;callOUTPUTR;模块0：扫描器主控12/17/2024计算机学院

102辛明影单词分类模块(SORT)输入：CH内含单词首符；procedureSORT(CH);{caseCHof‘字母’:‘字母’:callRECOGID(CH,TOKEN);‘/’:callHANDLECOM(CH,TOKEN);‘数字’:callRECOGDIG(CH,TOKEN);‘’‘callRECOGSTR(CH,TOKEN);otherwisecallRECOGDEL(CH,TOKEN);endcase;writeTOKENintoTOKEN文件;Return}

12/17/2024计算机学院

103辛明影procedureRECOGID(CH,TOKEN);{WORD:=‘’;

WORD:=WORD||CH;Repeat{callGETCH(CH);ifCH是字母或数字thenWORD:=WORD||CH;}untilCH!=字母或数字;ifCH是非法字符thencallPRINTERR(‘非法字符’)else列计数-1;ifWORD是关键字thenTOKEN:=(关键字种别码,_)else{callLOOPUP(WORD,'标识符',ENTRY)TOKEN:=(标识符种别码,ENTRY)};Return};识别标识符；输入：CH中含标识符的首字母；输出：TOKEN(二元式形式);12/17/2024计算机学院

104辛明影procedureHANDLECOM(TOKEN);{callGETCH(CH);ifCH!='*'then{列计数-1;TOKEN=(‘/’的识别码,_);return};TOKEN='-1';GETCH(CH);while列计数<=行长-1do{CH1:=CH;callGETCH(CH);ifCH1='*'andCH='/'thenTOKEN:=‘';}ifTOKEN!=‘’thencallPRINTERR(‘注解未完’);TOKEN:=‘';return}处理注解(HANDLECOM);输入：‘/’;进入该模块之前已扫描了一个字符‘/’输出：‘/’的TOKEN字或空TOKEN字;

12/17/2024计算机学院

105辛明影识别界限符(RECOGDEL)输入：CH内含单界限符；输出：各种界符的TOKEN字;procedureRECOGDEL(CH,TOKEN);{caseCHof‘+’:TOKEN:=(‘+’的种别码,_);‘)’:TOKEN:=(‘)’的种别码,_);‘<’:{callGETCH(CH);ifCH=‘=’thenTOKEN:=(‘<=’的种别码,_)elseifCH=‘>’thenTOKEN:=(‘<>’的种别码,_)

else{列计数-1;TOKEN:=(‘<’的种别码,_)}}……..

endcase;return}12/17/2024计算机学院

106辛明影3.3词法分析程序的自动构造工具LEX简介一.原理单词的结构用正规式描述正规式

NFA

DFA

minDFALEX编译器LEX源程序lex.1Lex.yy.c二.用LEX建立词法分析程序的过程12/17/2024计算机学院

107辛明影C编译器Lex.yy.ca.outa.out输入流单词序列三.lex源程序

lex源程序由三部分组成12/17/2024计算机学院

108辛明影声明%%翻译规则%%辅助过程12/17/2024计算机学院

109辛明影

声明包括变量，符号常量和正规定义式。翻译规则的形式为：

p1{动作1}

p2{动作2}……

pn{动作n}12/17/2024计算机学院

110辛明影

每个pi是正规定义式的名子，每个{动作i}是正规定义式pi识别某类单词时，词法分析器应执行动作的程序段。用C书写。标识符{字母}({字母}|{数字})*%%标识符{入口地址=LOOKUP();}%%LOOKUP()12/17/2024计算机学院

111辛明影辅助过程是动作需要的，这些过程用C书写，可以分别编译.例：LOOKUP()12/17/2024计算机学院

112辛明影第四章语法分析该讲语法分析了！这可是很重要的章节12/17/2024113主要内容：本章将重点介绍典型的语法分析方法及相关的概念和实现技术语法分析分为：自上而下:自下而上：递归下降分析法

LL（1）预测分析法推导算符优先分析法LR分析法归约从根向叶的方向建立分析树从叶向根的方向建立分析树12/17/2024计算机学院

114辛明影4.1语法分析器的功能词法分析器语法分析器语义分析符号表源程序单词符号语法树中间表示完成的任务：

①对词法分析器产生的单词符号进行处理，输出分析树

②与单词相关的信息记录到符号表中③类型检查④错误处理4.1.1语法分析器任务12/17/2024计算机学院

115辛明影4.1.2相关约定一.符号的使用约定1.终结符①.字母表中比较靠前的小写字,如a,b,c②.操作符，如+、-等③.标点符号，如括号、逗号等④.数字0、1、。。。9⑤.黑体串，如if、id等12/17/2024计算机学院

116辛明影2.下列符号是非终结符①.字母表中比较靠前的大写字,如A、B、C②.字母S，常用来表示开始符号③.小写斜体名字，如expr、stmt12/17/2024计算机学院

117辛明影3.字母表中比较靠后的大写字母，如X、Y、Z等，用来表示文法符号，也就是说，可以是终结符，也可以是非终结符4.字母表中比较靠后的小写字母，如u、v…z等，表示终结符的串联5.小写希腊字母α、β、γ等表示文法符号的串，所以一个产生式可写作：

A→α12/17/2024计算机学院

118辛明影4.2自顶向下分析法4.2.1使用的技术、存在的问题及解决方法12/17/2024计算机学院

119辛明影一、推导推导：就是用产生式的右部的串来代替左部的非终结符事实上推导给出了自顶向下构成分析树过程的精确描述例：有描述算术表达式的文法G字符串id+id*id

是该文法的句子，其推导过程如下：E→E+E|E*E|（E）|-E|id12/17/2024计算机学院

120辛明影E几个约定：=〉E+T=>E+T*F=>E+T*id

=〉E+F*id=〉E+id*idE=〉-EE推导出-E=>一步或多步推导=>零步或多步推导*+=〉T+id*id=〉F+id*id=〉id+id*id12/17/2024计算机学院

121辛明影最左推导：每一步都坚持替换当前句型中

最左非终结符的推导最右推导：每一步都坚持替换当前句型中

最右非终结符的推导，也称为

规范推导

+句子：S=〉w称终结符串w是文法G句子

+句型：S=〉α

称α是文法G的句型

+语言：L（G）={w/S=〉w

}12/17/2024计算机学院

122辛明影二、语法树语法描绘了如何从文法的开始符号推导出一个句子的过程语法树可以看成是推导的图形表示，但它不能显示出替代的顺序前面句子id+id*id推导过程所对应的分析树如下：12/17/2024计算机学院

123辛明影

EE+TTT*FFFididid12/17/2024计算机学院

124辛明影4.如杲A是某个内结点的非终结符标记，A1，A2，……An是该结点从左到右排列的所有子结点的标记，则A→A1A2……An是一个产生式3.每个内结点由一个非终结符标记1.树根标记为开始符号2.每个叶结点由终结符或者ε标记语法具有如下特性的树：12/17/2024计算机学院

125辛明影语法树的叶结点从左到右的排列，刚好是这个文法所产生的语言的一个句子一个文法生成的语言就是它的某个分析树所生成的句子的集合为给定的终结符串（句子）构造一棵分析树的过程称为这个串（句子）的语法分析（parsing)12/17/2024计算机学院

126辛明影三、二义性句子id+id*id有两棵分析树与之对应EE+EidE*EididEE*EE+Eididid12/17/2024计算机学院

127辛明影给定一个文法G，如果L（G）中存在一个具有两棵或两棵以上分析树的句子，很显然，描述算术表达式的文法G

E→E+E|E*E|（E）|-E|id

是一个二义性文法造成二义性的原因是：文法中没有体现出结合率和优先级我们就称该文法为二义性的，G也叫二义性文法。12/17/2024计算机学院

128辛明影

大多数的语法分析器都要求文法是无二义性的消除二义性：可以通过改写文法来消除二义性例：stmt→ifexprthenstmt|ifexprthenstmtelsestmt|other12/17/2024计算机学院

129辛明影通过例子

ifE1thenifE2thenS2elseS3很容易证明这是一个二义性文法sifEthenSelseSifEthenS12/17/2024计算机学院

130辛明影SifEthenSifEthenSelseS12/17/2024计算机学院

131辛明影在程序设计语言中，我们常常采用“最近匹配”原则来解决这种二义性文法改写出为：

stmt→matched_stmt|unmatched_stmtmatched_stmt→

ifexprthenmatched_stmt

elsematched_stmt|otherunmatched_stmt→

ifexprthenmatched_stmt

elseunmatched_stmt

|ifexprthen_stmt12/17/2024计算机学院

132辛明影四、左递归如果文法G具有一个非终结符A使得对

某个字符串α存在推导A=>Aα,例：下面是描述算术表达式的算法

S→EE→E+T|TT→T*F|FF→(E)|id为句子id*id+id构造分析树

SE+TE+TE+T：则称文法G是左递归的；如果A→Aα，则称文法G是直接左递归的+12/17/2024计算机学院

133辛明影左递归会使分析进入到无限循环之中消除简单左递归的方法：

对于含有左递归的产生式A→Aα|β可用下面的非左递归的产生式代替：

A→βA’A’→αA’|ε12/17/2024计算机学院

134辛明影例：下面是描述算术表达式的算法

E→E+T|TT→T*F|FF→(E)|id消除E和T的直接左递归，得到：

E→TE’

E’→+TE’|εT→FT’F→(E)|idT’→*FT’|ε12/17/2024计算机学院

135辛明影对于一般情况而言，若某一文法G的产生式具有如下形式：

则可用如下方法消除左递归:A→Aα1|Aα2

|…|Aαm|

β1|β2|…|βn

A→β1A’|β2A’|…|βn

A’A’→α1A’|α2A’|…|αmA’|

ε很容易证明改造前后的文法是等价的12/17/2024计算机学院

136辛明影例：文法G（P）：

P→（Q）|aP|aQ→Q,P|P试消除左递归12/17/2024计算机学院

137辛明影消除左递归后，方法改为：

P→（Q）|aP｜aQ→PＱ’

Q→，ＰＱ’｜ε12/17/2024计算机学院

138辛明影

S→Qc|cQ→Rb|bR→Sa|aS这样的递归无法用前面的方法消除对于含有间接左递归的文法：=>Qc=>Rbc=>Sabc出现了左递归12/17/2024计算机学院

139辛明影消除左递归的一般算法：输入：无循环推导和ε产生式的方法G输出：与G等价的无左递归文法算法：12/17/2024计算机学院

140辛明影1.以某种顺序排列非终结符A1A2…An2.fori=1tondobeginforj=1toi-1dobegin

改写Ai→Aj

γ

规则，方法如下：如果Aj→δ1|δ2|…|δk

则Ai→δ1γ

|δ2γ

|…|δnγ；end

消除Ai中的所有直接左递归End3.化简由2所得文法12/17/2024计算机学院

141辛明影

S→Qc|cQ→Rb|bR→Sa|a对如下文法消除左递归：1.将非终结符排序为R、Q、S2.R不存在左递归，将R代入Q：

Q→Sab|ab|b3.Q不存在左递归，将Q代入S

S→Sabc|abc|bc|c4.消除直接左递归后，得文法：12/17/2024计算机学院

142辛明影

S→abcS’|bcS’|cS’

S’→abcS’|ε

Q→Rb|bR→Sa|a5.化简文法

S→abcS’|bcS’|cS’

S’→abcS’|ε

12/17/2024计算机学院

143辛明影

Z-