1、编译原理全册配套课件编译原理全册配套课件编译原理3自我介绍自我介绍n姓名：刘善梅姓名：刘善梅nQQQQ ： 3068353030683530n办公室：逸夫楼办公室：逸夫楼C427C427n 邮箱：邮箱： 4课程介绍课程介绍n两门独立的课程：理论（两门独立的课程：理论（4848学时）学时） 实验（实验（1616学时）学时）n考试成绩组成考试成绩组成 理论：理论：平时作业和考勤占平时作业和考勤占20%20%，期末结业，期末结业考试占考试占80%80%； 实验：实验：根据实验报告和程序源代码评分，根据实验报告和程序源代码评分，实验报告占实验报告占40%, 40%, 程序源代码占程序源代码占60%60
2、%。n课程特点：课程特点：难！难！5开课目的：开课目的：介绍设计与构造程序设计语言介绍设计与构造程序设计语言编译程序编译程序的的原理与方法原理与方法源程序源程序编译编译程序程序目标程序目标程序连接连接可执行程序可执行程序预备知识：预备知识：形式语言与自动机、形式语言与自动机、两门以上的高两门以上的高级程序设计语级程序设计语言言汇编语言汇编语言数据结构等数据结构等How?6教学要求教学要求 通过课程的学习和实验的完成，通过课程的学习和实验的完成， 应该应该清楚的理解一个编译程序是如何工作的；清楚的理解一个编译程序是如何工作的； 如果在以后遇到了任何一个程序设计语言，如果在以后遇到了任何一个程序设
3、计语言，应该应该知道如何实现这个语言的多数机制；知道如何实现这个语言的多数机制； 应应具有一定的使用编译构造工具开发编译程序的具有一定的使用编译构造工具开发编译程序的经验；经验； 会会将所学的常用技术和算法应用于类似的软件的将所学的常用技术和算法应用于类似的软件的设计和实现中。设计和实现中。理论课内容简介：理论课内容简介：第一章：绪论 第二章：编译基础(形式语言 、有穷自动机等）第三章：词法分析 第四章：语法分析第五章：语法制导翻译和中间代码生成第七章：程序运行时的存贮分配问题第八章：代码优化第九章：目标代码生成 第六章：符号表实验课内容简介：实验课内容简介：第一次课：词法分析 （4学时）第二
4、次课：语法分析 （4学时）第三次课：词义分析、代码生成 （4学时）第四次课：小型C语言编译器设计（4学时）详细实验内容请见实验要求和实验指导书9教材：教材：编译原理编译原理（第（第2版），张素琴、吕映芝、蒋维杜、戴桂版），张素琴、吕映芝、蒋维杜、戴桂 兰，清华大学出版社兰，清华大学出版社 2004参考书：参考书：教材及主要参考书教材及主要参考书 Compilers: Principles, Technigues, and Tools Alfred V.Aho, Ravi Sethi, Jeffrey D.Ullman, Addison-Wesley,1986. 译著版：机械工业出版社，译著版：
5、机械工业出版社，2003，李建中，姜守旭译。，李建中，姜守旭译。(龙书）龙书） 中文名：编译原理技术和工具中文名：编译原理技术和工具 Modern Compiler Implementation in Java Modern Compiler Implementation in C Andrew W.Appel，人民邮电出版社影印，人民邮电出版社影印，2005 （虎书）（虎书） 中文名：现代编译原理中文名：现代编译原理 Advanced Compiler Design and Implementation Steven S. Muchnick, 1997. 机械工业出版社影印机械工业出版社影印
6、，2003 （鲸书）（鲸书） 中文名：高级编译器设计与实现中文名：高级编译器设计与实现内地内地 陈火旺（国防科大版）陈火旺（国防科大版） 陈意云（中国科技大学版）陈意云（中国科技大学版） 王生原等（人民邮电版）王生原等（人民邮电版） 王生原等（清华大学第三版）王生原等（清华大学第三版） 主要参考书主要参考书11第一章绪论第一章绪论n编译器就是一个编译器就是一个程序程序，它，它读入读入用某种语言用某种语言编写的源程序，并编写的源程序，并翻译翻译成一个成一个与之等价与之等价的的另一种语言编写的源程序。另一种语言编写的源程序。编译器编译器源程序源程序目标程序目标程序错误信息错误信息Fortran、P
7、ascal、Java、 C .另一种程序另一种程序设计语言、设计语言、汇编语汇编语言、机言、机器语言器语言1.1什么是编译程序什么是编译程序什么是编译程序什么是编译程序 编译程序编译程序通常通常是是从较高级语言的程序翻译从较高级语言的程序翻译 至较低级语言的程序至较低级语言的程序，如，如C 代码汇编代码a C compilerC+ 代码汇编代码a C+ compilerC+ 代码C代码another C+ compilerJava 代码Bytecode代码a Java compiler131.2编译过程概述编译过程概述编译程序的工作，从输入源程序开始，到输出目编译程序的工作，从输入源程序开始，
8、到输出目标程序结束，与自然语言之间的翻译有很多相似之处。标程序结束，与自然语言之间的翻译有很多相似之处。 一段英文翻译成中文，一段英文翻译成中文，需经下列步骤：需经下列步骤：识别出句子中的单词识别出句子中的单词分析句子的语法结构分析句子的语法结构根据句子的含义进行初步分析根据句子的含义进行初步分析对译文进行修饰对译文进行修饰写出最后的译文写出最后的译文编译程序编译程序词法分析词法分析代码优化代码优化语法分析语法分析语义分析及中语义分析及中间代码生成间代码生成目标代码生成目标代码生成构成编译程构成编译程序各个阶段序各个阶段I am a teacher.14编译器的各个阶段：编译器的各个阶段：编译
9、器是分编译器是分阶段执行的。阶段执行的。每个阶段将源程每个阶段将源程序从一种表示转序从一种表示转换成另一种表示换成另一种表示源程序源程序词法分析器词法分析器错错误误处处理理器器符符号号管管理理表表语法分析器语法分析器语义分析器语义分析器中间代码生成器中间代码生成器代码优化器代码优化器代码生成器代码生成器编译的各编译的各个阶段个阶段15各分析阶段各分析阶段随着编译器各个阶段的进展，源程序的内部表示不随着编译器各个阶段的进展，源程序的内部表示不断地发生变化。断地发生变化。以以a=b+c *d为例为例1。词法分析。词法分析读入源程序读入源程序完成的任务：完成的任务：识别出单词：识别出单词： a、=、
10、b、+、c 、 *、 d并用记号方式表示识别出的单词并用记号方式表示识别出的单词关键字、标识关键字、标识符、常数、算符、常数、算符和界符符和界符例：例：25表示表示a、b、c、d；36：；：；2：；：；31：*记号表示逻辑记号表示逻辑上相关的字符上相关的字符序列，常用整序列，常用整数来表示数来表示上述单词表示为：上述单词表示为：(25,a),(36,=),(25,b),(32,+),(25,c),(31,*),(25,d)n程序文本程序文本If x = y then z := 1 else z := 2; 经经词法分析，变成一个个单词词法分析，变成一个个单词nif, x, =, y, then
11、, z, :=, 1, else, z, :=, 2, ;n语言的单词符号是由语言的单词符号是由词法规则词法规则所确定的。所确定的。词法词法规则规则规定了字母表中哪样的字符串是一个单词规定了字母表中哪样的字符串是一个单词符号。符号。又又例例， 从左至右扫描字符流的源程序从左至右扫描字符流的源程序、分解构成源、分解构成源程序的字符串，程序的字符串，识别出识别出(拼拼)一个个的一个个的单词单词（符号）（符号） 单词符号是语言中具有独立意义的最基本单词符号是语言中具有独立意义的最基本结构。多数程序语言中，结构。多数程序语言中，单词单词符号一般符号一般包括包括 各类型的各类型的常数、保留字、标识符常数
12、、保留字、标识符、运算符、界符、运算符、界符等等。等等。 词法分析词法分析第一步识别单词第一步识别单词position := initial + rate * 60;单词类型单词类型单词值单词值 标识符标识符1(id1) position 算符算符(赋值赋值) := 标识符标识符2(id2) initial 算符算符(加加) + 标识符标识符3(id3) rate 算符算符(乘乘) * 整数整数 60 分号分号 ；词法分析词法分析19语法分析语法分析在词法分析的基础上，根据语言的语法规则，在词法分析的基础上，根据语言的语法规则，把单词符号串组成各类语法单位把单词符号串组成各类语法单位.具体的说
13、，语法分析是在单词流的基础上建立具体的说，语法分析是在单词流的基础上建立一个层次结构一个层次结构-建立语法树建立语法树赋值语句赋值语句标识符标识符=表达式表达式 id1表达式表达式标识符标识符 id2 +表达式表达式表达式表达式*标识符标识符 id3表达式表达式 整数整数 60语法分析语法分析 举例举例id1 := id2 + id3 * 60 ;（Pascal）语法规则）语法规则 :=“:=” :=“+” :=“*” :=“(”“)” := := := 赋值语句赋值语句标识符标识符表达式表达式表达式表达式+表达式表达式表达式表达式标识符标识符整数整数标识符标识符:=表达式表达式*id1:=i
14、d2+id3*60:=+60*id1id2id323语义分析阶段语义分析阶段语义分析利用语法分析阶段确定的层次结构来识别语义分析利用语法分析阶段确定的层次结构来识别表达式和语句中的操作信息及类型信息表达式和语句中的操作信息及类型信息= + a b*c dtemp1=c*dtemp2=b+temp1 temp1 temp2a=temp2语义分析语义分析n 句子的结构理解了，句子的结构理解了，扑捉它的扑捉它的“含义含义” 如：杰克说杰瑞把他的作业落在了家里。如：杰克说杰瑞把他的作业落在了家里。 “他的他的”是谁的？是谁的？ 又：杰克说杰克把他的作业落在了家里。又：杰克说杰克把他的作业落在了家里。
15、几个杰克？几个杰克？n杰克把她的作业落在了家里。杰克把她的作业落在了家里。（杰克是男生）（杰克是男生）“杰克杰克”和和“她的她的”不一致。不一致。 “杰克杰克”和和“他的他的”才匹配才匹配语义分析语义分析26中间代码生成阶段中间代码生成阶段本阶段将产生源程序的一个显式中间表示本阶段将产生源程序的一个显式中间表示这种中间表示可以看成是某种抽象的程这种中间表示可以看成是某种抽象的程序，通常是与平台无关的序，通常是与平台无关的其重要性质：其重要性质：1.易于产生易于产生2.易于翻译成目标程序易于翻译成目标程序下面是用下面是用三地址码三地址码（四元式）（四元式）表示的例子：表示的例子：temp1=c*
16、dtemp2=b+temp1a=temp2（* , c , d , tempt1) (+ , b, tempt1 , tempt2) (= , tempt2 , , a)id1:= id2 + id3 * 60(1)(inttoreal, 60, ,t1)(2)(*,id3,t1,t2)(3)(+,id2,t2,t3)(4)(:=,t3,id1)28代码优化阶段代码优化阶段对代码进行变换对代码进行变换以使得编译产生的目标代码更高效以使得编译产生的目标代码更高效（执行速度更快）（执行速度更快）。对上面中间代码进行优化处理后，产生如对上面中间代码进行优化处理后，产生如下的代码：下的代码：temp1
17、=c*da=b+temp1temp1=c*dtemp2=b+temp1a=temp2如下程序 语法分析结果j = 2 * i + 1;if (j = n) j = 2 * i + 3;return aj;t1 = 2 * it2 = t1 + 1j = t2t3 = j nif t3 goto L0t4 = 2 * it5 = t4 + 3j = t5L0: t6 = ajreturn t6t1 = 2 * it2 = t1 + 1j = t2t3 = j nif t3 goto L0t4 = 2 * it5 = t4 + 3j = t5L0: t6 = ajreturn t6t1 = 2 *
18、 ij = t1 + 1t3 = j nif t3 goto L0 j = t1 + 3L0: t6 = ajreturn t6代码优化代码优化代码优化代码优化id1:= id2 + id3 * 60(1)(inttoreal60-t1)(2)( * id3 t1t2)(3)( +id2t2t3)(4)( :=t3-id1) 变换变换 （1） ( *id360.0 t1) ( 2）（）（ + id2 t1id1)32代码生成阶段代码生成阶段生成目标机机器代码或汇编代码生成目标机机器代码或汇编代码(*,id360.0 t1)(+,id2t1id1)movf id3,R2mulf #60.0,R2
19、movf id2,R1addf R2,R1movf R1,id1nExample: a in R0, i in R1, n in R2t1 = 2 * ij = t1 + 1t3 = j nif t3 goto L0 j = t1 + 3L0: t6 = ajreturn t6sll R1, 1, R1add R1, 1, Jcmp J,R2blt .LL3add R1, 3, J.LL3: ld R0+J, Rt retr代码生成代码生成n记录记录源程序中使用的源程序中使用的标识符标识符n收集收集每个标识符的各种每个标识符的各种属性信息属性信息n普通变量：普通变量：类型、作用域、分配存储信息
20、类型、作用域、分配存储信息n函数或过程：函数或过程：参数个数、类型、传递方法参数个数、类型、传递方法 返回值类型返回值类型符号表管理符号表管理(登录，查找）登录，查找）1.3 符号表符号表35符号表管理符号表管理int a,b;float e,fchar ch1,ch2;为什么要先说明为什么要先说明? 定义了变量的类型，也就规定了变量定义了变量的类型，也就规定了变量在内存中的存放形式，在其上所能进行的在内存中的存放形式，在其上所能进行的运算运算解决符号地址到存贮地址上的映射解决符号地址到存贮地址上的映射36编译器的一个基本功能是编译器的一个基本功能是记录源程序中使用记录源程序中使用的标识符的标
21、识符并将它们并将它们记载到符号表中记载到符号表中。符号表是一个数据结构。符号表是一个数据结构。 每个标识符在符号表中都有每个标识符在符号表中都有一条记录一条记录名字名字记号记号类型类型种属种属 addrid1(25)id2(25) b a例：例：int a,b;int简变简变 0 4 并并收集与每个标识符相关的各种属收集与每个标识符相关的各种属性信息，性信息，int简变简变37在编译的各个阶段都会发现源程序中的错误，在编译的各个阶段都会发现源程序中的错误，1.4错误检测与报告错误检测与报告为了使编译器能继续运行，以检测出源程序中为了使编译器能继续运行，以检测出源程序中更多的错误，在检测到错误后
22、，必须以合适的方式更多的错误，在检测到错误后，必须以合适的方式进行错误处理。进行错误处理。error38小结：小结：编译器编译器的各个的各个阶段阶段源程序源程序词法分析器词法分析器错错误误处处理理器器符符号号管管理理表表语法分析器语法分析器语义分析器语义分析器中间代码生成器中间代码生成器代码优化器代码优化器代码生成器代码生成器39编译的前端和后端编译的前端和后端 前端包括词法分析、语法分析、语前端包括词法分析、语法分析、语义分析，以及相关的错误处理和符号表义分析，以及相关的错误处理和符号表的建立的建立 前端依赖于源程序并在很大程度上前端依赖于源程序并在很大程度上独立于目标机器。独立于目标机器。
23、40 后端主要包括代码优化、代码生成和相后端主要包括代码优化、代码生成和相关错误处理。关错误处理。 后端依赖于目标机器。后端依赖于目标机器。 后端处理对象是由前端产生的结果，即中后端处理对象是由前端产生的结果，即中间代码间代码 前端生成与平台无关的字节码前端生成与平台无关的字节码 后端是由与平台有关的解释器对所生成后端是由与平台有关的解释器对所生成的字节码文件进行解释执行的字节码文件进行解释执行Java语言的编译采用的是前端后端方式。语言的编译采用的是前端后端方式。编译程序的组织编译程序的组织 编译程序的遍编译程序的遍（Passes / Phases）- 对一种代码形式从头到尾扫描一遍对一种代
24、码形式从头到尾扫描一遍- 将一个代码空间变换到另一个代码空间将一个代码空间变换到另一个代码空间- 代码空间代码空间 = 代码代码 + 符号表符号表 + 其他有用信息其他有用信息 编译程序的组织取决于各遍的组织编译程序的组织取决于各遍的组织- 单遍单遍编译程序，编译程序，多遍多遍编译程序编译程序- 多个遍之间有逻辑上的先后关系多个遍之间有逻辑上的先后关系- 多个遍的实现可采用顺序结构或并发结构多个遍的实现可采用顺序结构或并发结构 （后者不常用）（后者不常用）编译程序的组织编译程序的组织 例：一个以语法、语义分析程序为中心的例：一个以语法、语义分析程序为中心的 单遍编译程序单遍编译程序组织组织so
25、urce programtarget program语法、语义语法、语义分析程序分析程序词法分词法分析程序析程序代码生代码生成程序成程序编译程序的伙伴程序编译程序的伙伴程序 解释程序解释程序（Interpreter）- 不产生目标程序文件不产生目标程序文件- 不区别翻译阶段和执行阶段不区别翻译阶段和执行阶段- 翻译源程序的每条语句后直接执行翻译源程序的每条语句后直接执行- 程序执行期间一直有解释程序守候程序执行期间一直有解释程序守候- 常用于实现虚拟机常用于实现虚拟机 比较比较编译程序和解释程序编译程序和解释程序源程序源程序编译程序编译程序目标程序目标程序输入输入目标程序目标程序输出输出解释程
26、序解释程序输出输出输入输入源程序源程序 预处理程序预处理程序（Preprocessor）- 支持宏定义支持宏定义（Macro definition） 如C源程序中 #define 行的处理- 支持文件包含支持文件包含（File inclusion） 如C源程序中 #include 行的处理- 支持其他更复杂的源程序扩展信息支持其他更复杂的源程序扩展信息 预处理程序和编译程序的关系预处理程序和编译程序的关系预处理程序预处理程序不含扩展信不含扩展信息的源语言息的源语言程序程序编译程序编译程序目标程序目标程序含扩展信息含扩展信息的源语言程的源语言程序序编译程序的伙伴程序编译程序的伙伴程序 汇编程序汇
27、编程序（Assembler）- 翻译翻译汇编语言程序至可重定位的汇编语言程序至可重定位的（Relocatable） 机器语言程序机器语言程序 装入和连接程序装入和连接程序（Loader and Link-editor）- 装入程序对可重定位机器语言程序进行修改装入程序对可重定位机器语言程序进行修改 将相对地址变换为机器绝对地址- 连接程序合并多个可重定位机器语言程序文件连接程序合并多个可重定位机器语言程序文件 到同一个程序到同一个程序- 装入和连接程序产生最终可执行的机器语言程序装入和连接程序产生最终可执行的机器语言程序编译程序的伙伴程序编译程序的伙伴程序 编译程序、汇编程序及装入和连接程序编
28、译程序、汇编程序及装入和连接程序 之间的典型关系之间的典型关系编译程序编译程序可重定位可重定位的机器语的机器语言程序言程序装入和连接程序装入和连接程序源程序源程序汇编程序汇编程序汇编语言程序汇编语言程序可执行的可执行的机器语言机器语言程序程序编译程序的伙伴程序编译程序的伙伴程序运行时库运行时库和分开编和分开编译的例程译的例程 调试程序调试程序（Debugger）- 反馈目标程序运行时信息反馈目标程序运行时信息- 将目标程序运行时信息与源程序关联将目标程序运行时信息与源程序关联- 断点管理、单步跟踪、读断点管理、单步跟踪、读/写目标机状态等功能写目标机状态等功能 调试程序和编译程序的关系调试程序
29、和编译程序的关系编译程序编译程序调试信息调试信息调试程序调试程序运行时信息运行时信息源程序源程序装入和连接程序装入和连接程序可执行程序可执行程序编译程序的伙伴程序编译程序的伙伴程序Thank YouThats all for today. 第二章 编译基础-形式语言本讲内容本讲内容n字母表、串、语言字母表、串、语言n文法的引例文法的引例n文法的形式定义（定义、分类）文法的形式定义（定义、分类）n正规文法与有穷自动机正规文法与有穷自动机n上下文无关文法上下文无关文法第一节第一节 字母表、串、语言字母表、串、语言1 字母表字母表：有穷非空字符集：有穷非空字符集 语言允许使用的语言允许使用的字符集字
30、符集可识别符号可识别符号例：例： =a-z,A-Z,0-9,+,_,*,/,/(,),=.2 字符串：字符串：字母表中符号组成的任何有穷字母表中符号组成的任何有穷序列序列单词单词例：例：scanf,int,3.1415,x1,100,ascanf,int,3.1415,x1,100,a3 字符串运算：字符串运算： A、B为字符串集合为字符串集合 x，y为字符串为字符串连接：连接： xy 称为称为x和和y的连接的连接 例：例：int x x=100积：积：AB=xy/x A,而而y B 闭包：闭包：A*=A0 A1 A2. . An 其中：其中： A0= = ， Ai= = Ai-1 A A+=
31、 = A*- - A+中的每一个元素即为一个中的每一个元素即为一个语句语句例：例： x=3.14159x=3.14159* *r r* *r r形式语言形式语言是一个字母表上按某种规则构成的是一个字母表上按某种规则构成的所有串的所有串的集合集合。在语言中这些串称为。在语言中这些串称为句子句子。对于一个句子，存在两个过程：对于一个句子，存在两个过程：读读-识别过程识别过程-编译的过程编译的过程写写-推导过程推导过程-书写源程序书写源程序第二节第二节 文法的引例文法的引例 句子：句子：I am a teach.Iamateacher amateacher i第三节第三节 文法的形式定义文法的形式定
32、义一、几个概念一、几个概念1、非终结符、非终结符语法变量语法变量2、终结符、终结符单词单词3、产生式、产生式规则规则二、文法的定义二、文法的定义文法是一个四元组，表示为：文法是一个四元组，表示为： G=（VN，VT，P，S）其中：其中： VN -非终结符集合非终结符集合 VT -终结符集合终结符集合 P-产生式集合产生式集合 S-开始符号开始符号P： VV+ + ， V V* * V=VN VT例：描述系表结构的文法，其形式描述为例：描述系表结构的文法，其形式描述为G=（VN，VT，P，S）VN = VT =I，am ,a ,teacherS= amateacher P=i再给出一个描述算术表
33、达式的文法例子再给出一个描述算术表达式的文法例子 p=EE+T|T p=EE+T|T TT TT* *F|FF|F F(E)|a F(E)|a 文法文法G G（E E）：）：G=（VN，VT，P，S）VN =E，T，FVT =+，*，（，），（，），aS= E *句型：句型：S= , , V V* * 为句型为句型例：例： I am I am *句子句子：S= w, ww, w V VT T* * w w为句子为句子例：例：Iam a teacherIam a teacher *语言语言：L=w/w w w V VT T* * , , 且且S=w例：例：I am a teacher推导的定义推
34、导的定义若存在若存在v v ww0 0 ww1 1 . . wwn n=w(n0)=w(n0) 则记为则记为v v =+ w w，v v推导出推导出ww，或，或ww归归约到约到v v若有若有v =+ wv =+ w，或，或v=wv=w， 则记为则记为v =v =* * w w例：例：GEGE： EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|aE EE+T E+T T+T T+T F+T F+T a+T a+T a+Ta+T* *F F a+Fa+F* *F F a+aa+a* *F F a+aa+a* *a a句子：用符号句子：用符号a a，+ +，* *，(
35、 (和和) )构成的算术构成的算术表达式表达式EE+TTFaT*FFaaE EE+T E+T T+T T+T F+T F+T a+T a+T a+Ta+T* *F F a+Fa+F* *F F a+aa+a* *F F a+aa+a* *a a 通过对产生式施加不同的限制，通过对产生式施加不同的限制，ChomskyChomsky将文法分为将文法分为四种类型：四种类型：0 0型文法：对任一产生式型文法：对任一产生式，都有，都有 (V(VNNVVT T) )+ +， (V(VNNVVT T) )* *1 1型文法：对任一产生式型文法：对任一产生式，都有，都有|， 仅仅仅仅 SS除外除外2 2型文法
36、：对任一产生式型文法：对任一产生式AA，都有，都有AVAVNN ， (V(VNNVVT T) )* *3 3型文法：任一产生式型文法：任一产生式AA的形式都为的形式都为AaBAaB或或 AaAa，其中，其中AVAVNN ，BVBVNN ，aVaVT T文法分类：文法分类：文法的类型文法的类型自然语言属于上下文有关文法自然语言属于上下文有关文法例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法GSGS：SCDSCDAbbAAbbACaCACaCABaaBBaaBCbCBCbCBBbbBBbbBADaDADaD C CBDbDBDbD D DAabDAabD文法的类型文法的类型是语法
37、分析的基础是语法分析的基础例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GSGS：SABABABS|0BS|0BSA|1SA|13 3型文法型文法GS： S0A|1B|00A|1B|0A0A|1B|0S0A|1B|0SB1B|1|01B|1|0GI：I lT lTI l lT lT lTT dT dTT l lT d d是词法分析的基础是词法分析的基础文法的类型文法的类型四种四种文法文法之间之间的的逐级逐级“包含包含”关系关系0 0型文法型文法1 1型文法型文法2 2型文法型文法3 3型文法型文法文法和语言文法和语言n0 0型文法产生的语言称为型文法产生的语言称为0 0型语言
38、型语言1 1型文法或上下文有关文法（型文法或上下文有关文法（ CSG CSG ）产生的语言）产生的语言称为称为1 1型语言或上下文有关语言（型语言或上下文有关语言（CSLCSL）2 2型文法或上下文无关文法（型文法或上下文无关文法（ CFG CFG ）产生的语言）产生的语言称为称为2 2型语言或上下文无关语言（型语言或上下文无关语言（ CF L CF L ） 3 3型文法或正则（正规）文法（型文法或正则（正规）文法（ RG RG ）产生的语言）产生的语言称为称为3 3型语言正则（正规）语言（型语言正则（正规）语言（ RL RL ） 根据形式语言理论根据形式语言理论, ,文法和识别系统文法和识别
39、系统间有这样的关系间有这样的关系 0 0型文法（短语结构文法）的型文法（短语结构文法）的能力相当于图能力相当于图灵机，灵机，可以表征任何递归可枚举集，而且可以表征任何递归可枚举集，而且任何任何0 0型语言都是递归可枚举的型语言都是递归可枚举的 1 1型文法（上下文有关文法）：产生式的形型文法（上下文有关文法）：产生式的形式为式为1 1AA2 21 12 2，即只有，即只有A A出现在出现在1 1和和2 2的上下文中时，才允许的上下文中时，才允许取代取代A A。其其识别系统是线性界限自动机。识别系统是线性界限自动机。 2 2型文法（上下文无关文法型文法（上下文无关文法CFGCFG）：产生）：产生
40、式的形式为式的形式为AA，取代取代A A时与时与A A的的上下文无关。上下文无关。其识别系统是不确定的其识别系统是不确定的下推自动机。下推自动机。 3 3型文法（正规文法型文法（正规文法RGRG）：产生的语言）：产生的语言是是有穷自动机有穷自动机（FAFA）所接受的集合）所接受的集合第四节第四节 正规文法与有穷自动机正规文法与有穷自动机一、正规文法一、正规文法1. 正规文法正规文法 能能 产生语言产生语言L(G)2. 写出产生语言写出产生语言L(G)的正规文法的正规文法第四节第四节 正规文法与有穷自动机正规文法与有穷自动机1、正规文法、正规文法 产生的语言的推导产生的语言的推导例：文法例：文法
41、 G=（VN，VT，P，S）其中：其中： VN=A，B，C VT=a,b,c S=AP:A aB A aA aB A aA B bB B bC B bB B bC C cC C c C cC C cL(G)=aL(G)=ammb bn nc cp p/m,n,p/m,n,p1 1A=aA=aaA=A=aA=aaA=.=aa.=aaaBaB =aa =aaabB=aaabB=aaabbabbbCbC =aa =aaabbabbbcC= aabcC= aaabbabbbccCbccC = aa = aaabbabbbccbccc c最小句子：最小句子：abcabcP:A aB A aA aB A
42、aA B bB B bC B bB B bC C cC C c C cC C c例例1 1：写出产生语言：写出产生语言L(G)=aL(G)=ammbcbcn n/m,n/m,n00的的正规文法正规文法解：文法解：文法 G=（VN，VT，P，S）其中：其中： VN=A，C VT=a,b S=AP:最小语言：最小语言：b bA aAaAA bA bA bCA bCC cCC cCCcCc2. 写出产生语言写出产生语言L(G)的正规文法的正规文法例例2 2：C C语言标识符的文法描述语言标识符的文法描述L L（G G）=w/w=w/w为字母或为字母或- -打头的字母数字串打头的字母数字串 解：解：P
43、:IaB I -BaB I -B B aB B dB Ba B d B aB B dB Ba B dI aI aIBT Ta-a,d 其其它它2. 写出产生语言写出产生语言L(G)的正规文法的正规文法二、有穷自动机二、有穷自动机正规文法产生的正规语言用有穷自动机来识正规文法产生的正规语言用有穷自动机来识别别根据文法根据文法-写程序写程序 -编译时用有穷自动机识别编译时用有穷自动机识别二、有穷自动机二、有穷自动机1 1、特点：接收离散输入，状态有穷，只需考、特点：接收离散输入，状态有穷，只需考虑当前输入和当前内部状态虑当前输入和当前内部状态2 2、原理：、原理：有穷自动机控制器有穷自动机控制器读
44、头自左向右读头自左向右逐个扫描并读入逐个扫描并读入输入符号输入符号，并且根据控制器，并且根据控制器的的当前状态当前状态和和当前输入符号当前输入符号控制转入控制转入下一个下一个状态状态、模型、模型Main ( ) int I , j , k ;有穷控制器有穷控制器、表示、表示状态图状态图IBT Ta-a,d 其其它它例：例：C C语言的标识符语言的标识符、形式定义、形式定义确定的有穷自动机是一个五元组确定的有穷自动机是一个五元组 M=M=（QQ， ， ，q q0 0，Z Z）其中：其中：QQ是一有穷状态集是一有穷状态集是有穷输入字母表是有穷输入字母表是是Qx QQx Q的映射函数的映射函数 其含
45、义：其含义： （ q q1 1,a)= q,a)= q2 2q q0 0 Q,Q,唯一的初态唯一的初态Z Z是的子集，是终态集是的子集，是终态集 例：奇偶测试器例：奇偶测试器q00q11q101自动机：（自动机：（QQ， ， ，q q0 0，Z Z）QQ q q0 0, q, q1 1 =0,1 =0,1 q q0 0=q=q0 0 Z=q Z=q1 1 映射函数：映射函数：（ q q, ,)= q)= q（ q q, ,)= q)= q（ q q1 1, ,)= q)= q（ q q1 1, ,)= q)= q例：例：q00q11q101三、正规表达式与有穷自动机三、正规表达式与有穷自动机关
46、系：等价、交换关系：等价、交换文法文法 G=（VN，VT，P，S）和）和自动机自动机 M=M=（QQ， ， ，q q0 0，Z Z）可转换为：可转换为： VN为终态为终态q q0 0 VT，S若若 映射函数：映射函数：、：、： a a2 2 , , 则则（ ,a)= A,a)= A2 22 2、：、： a, a, 则则（ ,a)= T,a)= T3 3、（ ,a)= ,a)= 空动作空动作例：已知正规文法例：已知正规文法（A,B,C,A,B,C,a,b,c,P,S a,b,c,P,S 其中：其中：P:A aA A aB B bB aA A aB B bB B bC C cC Cc B bC C
47、 cC Cc试写出与其等价的试写出与其等价的解：解：(A,B,C,a,b,c, ,S,T)(A,B,C,a,b,c, ,S,T)ABCTaabbcc映射函数：映射函数：（ A,a)= AA,a)= A （ A,a)= BA,a)= B（B,b)= BB,b)= B （B,b)= CB,b)= C（C,c)= CC,c)= C （C,c)= TC,c)= T练习：练习：w/ww/w是和的个数都为偶是和的个数都为偶数的、串数的、串试写出能识别该语言的自动机和描述该语试写出能识别该语言的自动机和描述该语言的文法言的文法第五节上下文无关文法语法基础第五节上下文无关文法语法基础一、上下文无关文法一、上下
48、文无关文法文法文法 G=（VN，VT，P，S） ： A （ VN VT)例：例：anbn/n 1P: S aSbaSb S abab 二、自嵌套性二、自嵌套性如果上下文无关文法中存在一个终如果上下文无关文法中存在一个终结符，且结符，且 ( ( , 不空），不空），称该上下文无关文法具有可嵌套性称该上下文无关文法具有可嵌套性例：例：wcwr/w （a | |b), wr是是w的的反置反置P: S aSaaSa S bSbbSb ， S c c句子句子abbacabbaabbacabba三、下推自动机三、下推自动机、模型、模型输入带输入带有穷有穷控制器控制器下下推推栈栈、操作、操作、接收、接收b.
49、b.空动作空动作（ q, q, ,Z)= (q1, ),Z)= (q1, )A A、读入输入符号，替换栈顶，改变状、读入输入符号，替换栈顶，改变状 态，读头右移态，读头右移（ q,a,Z)= (q1, )q,a,Z)= (q1, )空栈：输入串空，栈内也空空栈：输入串空，栈内也空终态：规定终态，导致进入终态的串被终态：规定终态，导致进入终态的串被 认为接收。此时，栈内可能不为认为接收。此时，栈内可能不为 空空、定义、定义是一个七元组，是一个七元组， M=M=（Q, ,Q, , ,q, ,q0 0, , 0 0 , , ）是有穷输入字母表；是有穷输入字母表；其中：其中：QQ是一有穷状态集是一有穷
50、状态集是下推字母表是下推字母表是是Qx(Qx( )x)x Q Q xx* *的映射函的映射函 数数, , 其含义：其含义： ( q( q1 1,a,Z)= (q,a,Z)= (q2, 2, )q q0 0 Q,Q,唯一的初态唯一的初态; ;F F是的子集，是终态集是的子集，是终态集0 0 是栈底符号是栈底符号例：例：wcwr/w （a | |b), wr是是w的的反置反置,写出识别该语言的写出识别该语言的解：解：M=M=（Q, ,Q, , ,q, ,q0 0, , 0 0 , , ）QQ q q0 0， q q， q qa,ba,b；=Z Z0 0，q q0 0 q q0 00 0 = =0
