编译原理汇总

编译原理汇总第1页/共431页写在课程之前木桶原理：一个木桶由许多块木板组成，如果组成木桶的这些木板长短不一，那么这个木桶的最大容量不取决于长的木板，而取决于最短的那块木板。蝴蝶效应：1963年12月，洛伦兹（Lorenz）在华盛顿的美国科学促进会的一次讲演中提出：一只蝴蝶在巴西扇动翅膀，有可能会在美国的德克萨斯引起一场龙卷风。他的演讲和结论给人们留下了极其深刻的印象。马太效应：“马太福音”第二十五章由这么几句话：“凡有的，还要加给他叫他多余；没有的，连他所有的也要夺过来。”。1968年，美国科学史研究者罗伯特·莫顿（RobertK.Merton）提出这个术语用以概括一种社会心理现象：“相对于那些不知名的研究者，声名显赫的科学家通常得到更多的声望即使他们的成就是相似的，同样地，在同一个项目上，声誉通常给予那些已经出名的研究者，例如，一个奖项几乎总是授予最资深的研究者，即使所有工作都是一个研究生完成的。”

第2页/共431页学时与参考教材学时：44+16学时参考教材：1、AlfredAhoect.《编译原理》，赵建华等译，机械工业出版社，2009.10.2、KennethC.Louden，《编译原理及实践》，冯博琴等译，机械工业出版社，2001.2.3、金成植，《编译程序构造原理和实现技术》，高等教育出版社，2000.7.4、陈火旺等，《程序设计语言编译原理》，国防工业出版社，2003.8.印刷第3页/共431页学时与参考教材5、何炎祥等，《编译原理》，华中理工大学出版社，2000.10.6、蒋立源，《编译原理》，西北工业大学出版社，2000.7.7、肖军模，《程序设计语言编译方法》，大连理工大学出版社，2000.88、蒋宗礼等，《形式语言与自动机理论》，清华大学出版社，2003.1.第4页/共431页主要内容编译系统及其设计概述（总体结构、设计方法）语言与文法（文法、推导、归约、分类、分析树）词法分析（词法分析、正规式与正规文法、DFA的状态转移图）语法分析（自顶向下：LL(1)、递归子程序；自底向上：LR）语义分析（属性文法、各种语句的语法制导翻译）运行环境（存储分配、过程调用、符号表管理）代码优化（基本块的优化、循环优化等）代码生成（目标机器模型、基本块和流图、寄存器分配、基本块的DAG表示、从 DAG生成目标代码）第5页/共431页教学目的——《编译原理》是一门非常好的课程AlfredV.Aho：编写编译器的原理和技术具有十分普遍的意义，以至于在每个计算机科学家的研究生涯中，本书中的原理和技术都会反复用到涉及的是一个比较适当的抽象层面上的数据变换（既抽象，又实际）一些具体的表示和变换算法“自顶向下的方法”和“自底向上的方法”系统设计方法（思想、方法、实现全方位讨论）一个相当规模的系统的设计（含总体结构）计算机专业最为恰当、有效的知识载体之一第6页/共431页教学要求掌握编译程序总体结构在系统级上认识算法、系统的设计具有把握系统的能力学习有关的原理、实现方法和技术，了解计算学科的基本方法、思想掌握典型方法。“在每一个计算机科技工作者的职业生涯中，这些原理和技术都被反复用到。”兼顾语言的描述方法、设计、应用——形式化能形式化就能自动化进一步培养“计算机思维能力”软件系统的非物理性质第7页/共431页学习成果__以学生为中心理解和掌握编译过程各个阶段的工作原理理解标准编译器各个组成部分的任务熟悉编译过程各阶段所要解决的问题及其采用的方法和技术应用一些标准的技术解决编译器构造过程中所产生的相关问题理解编译器在生成代码时如何充分利用特定处理器的特征第8页/共431页第1章引论1.1计算机语言的发展1.2翻译系统1.3编译系统的功能分析1.4编译程序总体结构1.5

编译程序的生成1.6编译技术的应用第9页/共431页1.1计算机语言的发展机器语言(MachineLanguage)与汇编语言(AssembleLanguage)0、1代码与助记符：更接近于计算机硬件指令系统的工作高级语言(HighLevelLanguage)其表示方法更接近于待解问题的表示方法定义数据、描述运算、控制流程、传输数据如：C、FORTRAN、PASCAL、C++、JAVA、SQL(数据定义、数据操作)命令语言(CommandLanguage)控制系统的工作——以功能封装为特征如UNIX上的shell第10页/共431页1.2翻译系统翻译程序(Translator)将某一种语言描述的程序(源程序——SourceProgram)翻译成等价的另一种语言描述的程序(目标程序——ObjectProgram)的程序。翻译程序源程序目标程序(*.C/*.PAS)(*.OBJ/*.EXE)第11页/共431页1.2翻译系统解释程序(Interpreter)口译与笔译（单句提交与整篇提交）源程序输入数据计算结果解释程序第12页/共431页1.2翻译系统编译程序(Compiler)高级语言程序→汇编/机器语言程序源程序目标程序编译程序第13页/共431页1.2编译系统SP Compiler

S-Source O-Object OP P-ProgramInput RS

RS-RunSys. Output 编译系统(CompilingSystem)编译系统=编译程序+运行系统支撑环境、运行库等第14页/共431页1.2翻译系统其它：诊断编译程序（DiagnosticCompiler)优化编译程序（OptimizingCompiler)交叉编译程序（CrossCompiler)可变目标编译程序（RetargetableCompiler)并行编译程序（ParallelizingCompiler）汇编程序(Assembler)、交叉汇编程序(CrossAssembler)、反汇编程序（Disassembler)第15页/共431页1.2翻译系统—汇总ML MLP Assembler DisassemblerAL ALP Translator Compiler DataHL HLP Interpreter ResultM-MachineL-LangugeP-ProgramA-AssembleH-HighLevel第16页/共431页1.3编译系统的功能分析程序分析词法、语法、语义分析综合语句的翻译、代码生成标识符处理：左值与右值的绑定(binding)变量：存储单元函数：目标代码序列第17页/共431页1.4编译程序总体结构目标代码生成器代码优化器语义分析与中间代码生成器语法分析器表格管理出错处理中间代码中间代码目标代码语法单位单词符号词法分析器源程序第18页/共431页1.词法分析例：main(){printf(“hello”);}结果IDN main‘(’‘)’‘{’IDN printf‘(’STR hello‘)’‘;’‘}’第19页/共431页1、词法分析词法分析由词法分析器完成(LexicalAnalyzer)，词法分析器又叫做扫描器(Scanner)词法分析器从左到右扫描源程序——发现一个字符串，则将该字符串转换成单词(记号—Token)串；同时要：查词法错误，进行标识符登记——符号表管理。输入：字符串 输出：(种别码，属性值)——序对属性值——token的机内表示第20页/共431页2、语法分析语法分析由语法分析器(SyntaxAnalyzer)完成，语法分析器又叫Parser。功能：Parser实现“组词成句”

将词组成各类语法成分：表达式、因子、项，语句，子程序…构造分析树指出语法错误指导翻译输入：Token序列输出：语法成分第21页/共431页2.语法分析res=fact*(term1+term2);*；赋值语句表达式=）（fact表达式res表达式表达式表达式表达式+term1term2第22页/共431页3.语义分析功能：分析由语法分析器识别出的语法单位的语义获取标识符的属性：类型、作用域等语义检查：运算的合法性、取值范围等子程序的静态绑定：代码的相对地址变量的静态绑定：数据的相对地址第23页/共431页4.中间代码生成中间代码(intermediateCode)例:id1+id2*id3后缀表示(逆波兰Anti-PolishNotation)id1id2id3*

+前缀表示(波兰PolishNotation)+id1*id2id3四元式表示(三地址码)1(*,id1,id2,T1)2(+,id3,T1,T2)

三元式表示1(*,id2,id3)2(+,id1,(1))

EE+EidE*Eidid语法树第24页/共431页4.中间代码生成中间代码的特点简单规范与机器无关易于优化与转换三地址码的另一种表示形式T1=id2*id3T2=id1*T1其它类型的语句例：printf(“hello”)x:=s （赋值）paramx （参数）callf （函数调用）注释s是hello的地址f是函数

printf的地址第25页/共431页对中间代码的优化处理:对代码进行等价变换以求提高执行效率——提高运行速度和节省存储空间与机器无关的优化与机器有关的优化5.代码优化第26页/共431页与机器无关的优化局部优化常量合并：常数运算在编译期间完成，如8+9*4公共子表达式的提取:基本块内循环优化强度削减用较快的操作代替较慢的操作代码外提将循环不变计算移出循环第27页/共431页与机器有关的优化寄存器的利用将常用量放入寄存器，以减少访问内存的次数体系结构MIMD、SIMD、SPMD、向量机、流水机存储策略根据算法访存的要求安排：Cache、并行存储体系——减少访问冲突任务划分按运行的算法及体系结构，划分子任务(MPMD)第28页/共431页6.目标代码生成（CodeGenerator）将中间代码转换成目标机上的机器指令代码或汇编代码确定源语言的各种语法成分的目标代码结构（机器指令组/汇编语句组）制定从中间代码到目标代码的翻译策略或算法目标代码的形式具有绝对地址的机器指令汇编语言形式的目标程序模块结构的机器指令（需要链接程序）第29页/共431页7、表格管理管理各种符号表（常数、标号、变量、过程、结构……），查、填（登记、查找）源程序中出现的符号和编译程序生成的符号，为编译的各个阶段提供信息。辅助语法检查、语义检查完成静态绑定、管理编译过程Hash表、链表等各种查、填表技术第30页/共431页8、错误处理进行各种错误的检查、报告、纠正，以及相应的续编译处理（如：错误的定位与局部化）词法：拼写……语法：语句结构、表达式结构……语义：类型不匹配……第31页/共431页编译系统词法分析语法分析语义分析中间代码代码优化目标代码错误处理符号表源程序目标程序分析综合第32页/共431页模块分类分析：词法分析、语法分析、语义分析、中间代码生成综合：代码优化、目标代码生成辅助：符号表管理、出错处理8项功能对应8个模块第33页/共431页例一个语句的翻译第34页/共431页9编译的遍（Pass）根据系统资源的状况、运行目标的要求……等，可以将一个编译程序设计成多遍扫描的形式，在每一遍扫描中，完成不同的任务。如：首遍构造语法树，二遍处理中间表示，增加信息等。遍可以和阶段相对应，也可无关单遍代码不太有效第35页/共431页10、编译的前端与后端前端与源语言有关、与目标机无关的部分词法分析、语法分析、语义分析与中间代码生成、与机器无关的代码优化后端与目标机有关的部分与机器有关的代码优化、目标代码生成第36页/共431页1.5编译程序的生成设计目标目标程序小，执行速度快。编译程序小，执行速度快。诊断能力强，可靠性强。可移植性，可扩充性。如何实现编译器？直接用可运行的代码编制——太费力！自举-使用语言提供的功能来编译该语言自身。“第一个编译器是怎样被编译的？”第37页/共431页问题：直接在一个机上实现C语言编译器，还有别的技术么？解决：用汇编语言实现一个Ｃ子集的编译程序(P0—人)用汇编程序处理该程序,得到(P2:可直接运行)用Ｃ子集编制Ｃ语言的编译程序(P3—人)用P2编译P3，得到P41)编译程序的自展技术第38页/共431页2)利用编译程序自动生成器词法分析器的自动生成程序ＬＥＸ词法规则说明词法分析程序(C程序)输入： 词法（正规表达式） 识别动作（Ｃ程序段）输出：

yylex()函数第39页/共431页语法分析器的自动生成程序ＹＡＣＣ语法规则说明语法分析程序(C程序)输入： 语法规则（产生式） 语义动作（Ｃ程序段）输出：

yyparse()函数第40页/共431页1.6编译技术的应用把复杂数据看作一条语句数据格式的分析利用词法分析、语法分析方法数据处理的框架基于语法制导的语义处理框架编译技术可以用于各种复杂数据的分析处理第41页/共431页1.6编译技术的应用

语法制导的结构化编辑器程序格式化工具软件测试工具程序理解工具高级语言的翻译工具

……第42页/共431页例1-1DOS命令date的输出格式例：9-2-1993、09-03-1993、9-03-93语法date→month-day-year词法month→DIGITDIGIT|DIGITday→DIGITDIGIT|DIGITyear→DIGITDIGIT|DIGIIDIGITDIGITDIGIT第43页/共431页例1-1（续）语义year(年)、month(月)、day(日)语义约束条件0<month.value<130<day.value<32，31，300<year.value<10000第44页/共431页小结计算机语言的发展翻译系统及其功能编译的总体结构编译的各个阶段编译的生成及应用相关概念第45页/共431页习题1.试分析一个简短的C程序，找出几个属于语法、词法、语义的语言现象。2.试分析例1-1的date输出数据的处理中，应该做哪些词法分析、语法分析、语义处理。第46页/共431页高级语言及其文法第47页/共431页2.1语言概述2.2基本定义2.3文法(Grammar)的定义2.4CFG的分析树（ParseTree）2.5文法的分类2.6文法的构造本章主要内容第48页/共431页2.1语言概述什么是语言？第49页/共431页2.1语言概述语言特征自然语言(NaturalLanguage)是人与人的通讯工具语义(semantics):环境、背景知识、语气、二义性——难以形式化计算机语言(ComputerLanguage)计算机系统间、人机间通讯工具严格的语法(Grammar)、语义(semantics)——易于形式化：严格第50页/共431页2.1语言概述语言的描述方法——现状自然语言：自然、方便-非形式化数学语言（符号）：严格、准确-形式化形式化描述高度的抽象，严格的理论基础和方便的计算机表示。第51页/共431页2.1语言概述语言——形式化的内容提取语言(Language)：满足一定条件的句子集合句子(Sentence)：满足一定规则的单词序列单词(Token)：满足一定规则的字符(Character)串语言是字和组合字的规则例（自然语言：第译始一天课今开编上节）今天开始上第一节编译课第52页/共431页2.1语言概述程序设计语言——形式化的内容提取程序设计语言(ProgrammingLanguage)：组成程序的所有语句的集合。程序(Program)：满足语法规则的语句序列。语句(Sentence)：满足语法规则的单词序列。单词(Token)：满足词法规则的字符串。例：变量:=表达式if条件then语句while条件do语句call过程名(参数表)第53页/共431页2.1语言概述描述形式——文法语法——语句语句的组成规则描述方法：BNF范式、语法(描述)图词法——单词单词的组成规则描述方法：BNF范式、正规式第54页/共431页形式语言于自动机理论的产生与作用语言学家Chomsky最初从产生语言的角度研究语言。1956年，通过抽象，他将语言形式地定义为是由一个字母表中的字母组成的一些串的集合。可以在字母表上按照一定的规则定义一个文法（Grammar），该文法所能产生的所有句子组成的集合就是该文法产生的语言。克林（Kleene）在1951年到1956年间，从识别语言的角度研究语言，给出了语言的另一种描述。克林是在研究神经细胞中，建立了自动机，他用这种自动机来识别语言：对于按照一定的规则构造的任一个自动机，该自动机就定义了一个语言，这个语言由该自动机所能识别的所有句子组成。第55页/共431页形式语言于自动机理论的产生与作用1959年，Chomsky通过深入研究，将他本人的研究成果与克林的研究成果结合了起来，不仅确定了文法和自动机分别从生成和识别的角度去表达语言，而且证明了文法与自动机的等价性。20世纪50年代，人们用巴科斯范式（BackusNourForm或BackusNormalForm，简记为BNF）成功地对高级语言ALGOL-60进行了描述。实际上，巴科斯范式就是上下文无关文法（ContextFreeGrammar）的一种表示形式。这一成功，使得形式语言在20世纪60年代得到了大力的发展。第56页/共431页形式语言于自动机理论的产生与作用形式语言与自动机理论除了在计算机科学领域中的直接应用外，更在计算学科人才的计算思维的培养中占有极其重要的地位计算思维能力的培养，主要是由基础理论系列课程实现的，该系列主要由从数学分析开始到形式语言结束的一些数学和抽象程度比较高的内容的课程组成。它们构成的是一个梯级训练系统。在此系统中，连续数学、离散数学、计算模型等三部分内容要按阶段分开，三个阶段对应与本学科的学生在大学学习期间的思维方式和能力的变化与提高过程的三个步骤。第57页/共431页计算思维能力的培养过程中学数学 数学分析离散数学

具体.静止 变量.运动 离散.抽象 形式.模型

(基本运算系统)

(计算系统)

实数 抽象集合

单一、具体的计算

一般、形式化的计算 （实例计算）

（模型化计算）

形式语言与自动机理论运算范围特征高水平计算专业人才的计算思维能力的渐进培养第58页/共431页2.2基本定义字母表（Alphabet）∑是一个非空有穷集合，字母表中的元素称为该字母表的一个字母（Letter），也叫字符（Character）。例以下是不同的字母表： ⑴{a，b，c，d} ⑵{a，b，c，……，z} ⑶{0，1}

(4)ASCII字母表第59页/共431页2.2基本定义符号串的定义由字母表中的符号所组成的任何有穷序列被称之为该字母表上的符号串,也称作"字"。(1)ε是∑上的一个符号串。(2)若x是∑上的符号串，而a是∑的元素,则xa是∑上的符号串。(3)y是∑上的符号串,当且仅当它由(1)和(2)导出。第60页/共431页2.2基本定义设s是符号串，则s的前缀：移走s的尾部的零个或多于零个符号后缀：删去s的头部的零个或多于零个符号子串:从s中删去一个前缀和一个后缀子序列:从s中删去零或多于零个符号(这些符号不要求连续）逆转：将S中的符号按相反次序写出而得到的符号串长度：是该符号串中的符号的数目。例如|aab|=3,|ε|=0。第61页/共431页2.2基本定义符号串的连接和方幂1.连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串。例如，x=ba,y=nana,xy=banana.2.方幂：x0=;x1=x;x2=xx;……；xn=xn-1x;例如,设x=ba,则x1=ba,x2=baba,x3=bababa,……第62页/共431页2.2基本定义定义1设∑1、∑2是两个字母表，∑1与∑2的乘积(Product)定义为∑1∑2={ab|a∈∑1，b∈∑2}例:∑1={0,1},∑2={a,b},∑1∑2={0a,0b,1a,1b}定义2设∑是一个字母表，∑的n次幂(Power)递归地定义为：⑴∑0={ε}⑵∑n=∑n-1∑n≥1例：∑13={000,001,010,011,100,101,110,111}第63页/共431页2.2基本定义定义3设∑是一个字母表，∑的正闭包(PositiveClosure)定义为：∑+=∑∪∑2∪∑3∪∑4∪……∑的克林闭包(KleeneClosure)为：∑*=∑0∪∑+=∑0∪∑∪∑2∪∑3∪……

第64页/共431页2.2基本定义例{0,1}+={0，1，00，01，11，000，001，010，011，100，……}{0,1}*={ε，0，1，00，01，11，000，001，010，011，100，…}

第65页/共431页2.2基本定义定义5设∑是一个字母表，L∑*，L称为字母表∑上的一个语言（Language），x∈L，x叫做L的一个句子。例：字母表{0，1}上的语言{0，1}{00，11}{0，1，00，11}{0，1，00，11，01，10}{00，11}*{01，10}*第66页/共431页2.3文法的定义如何实现语言结构的形式化描述？第67页/共431页考虑一个句子——文法要素的提取分析：Thegreywolfwilleatthegoat〈谓语〉〈主语〉〈形容词〉〈名词〉〈动词〉〈直接宾语〉助动词〈句子〉动原冠词名词Thegreywolfwilleatthegoat〈冠词〉第68页/共431页句子主语

谓语（1）主语冠词形容词名词（2）冠词the

（3）形容词grey

（4）谓语

动词直接宾语（5）动词助动词动词原形（6）助动词will

（7）动词原形eat

（8）直接宾语

冠词名词（9）名词wolf

（10）

名词goat

（11）句子的组成规则问题：如何用符号来描述？即如何形式化？〈谓语〉〈主语〉〈形容词〉〈名词〉〈动词〉〈直接宾语〉助动词〈句子〉动原冠词名词The

grey

wolf

will

eat

the

goat〈冠词〉第69页/共431页终结符号集VT= {the，grey,wolf,will,eat,goat}非终结符号集VN= {句子，主语，谓语，冠词，形容词，名词，

动词，直接宾语，助动词，动词原形}语法规则集P={句子

主语谓语，……}开始符号S=句子定义句子的规则的语法组成

__终结符号集，非终结符号集，语法规则，开始符号问题：有了定义句子的规则，如何判定某一句子是否属于某语言？第70页/共431页句子主语谓语冠词形容词名词谓语the

形容词名词谓语thegrey名词谓语thegreywolf

谓语thegreywolf

动词直接宾语

…...thegreywolfwilleatthegoat句子的派生（推导）-从产生语言的角度

句子的归约-从识别语言的角度-均根据规则第71页/共431页句子thegreywolfwilleatthegoat

thegreywolfwilleatthewolf

thegreygoat

willeatthewolfthegreygoat

willeatthegrey符合语法且符合语义的句子仅是：

thegreywolfwilleatthegoat句子的语义要求第72页/共431页文法G的形式定义文法G为一个四元组: Ｇ=(ＶT，ＶN，Ｐ，Ｓ)ＶT：终结符(Terminal)集ＶN：非终结符(Variable)集，ＶT∩ＶN=Φ语法成分——代表某个语言的各种子结构Ｓ：开始符号(StartSymbol)，S∈ＶN代表文法所定义的语言，至少在产生式左侧出现一次第73页/共431页文法G的形式定义Ｐ：产生式(Product)集合α→β，被称为产生式（定义式），读作：α定义为β。其中α∈(ＶT∪ＶN)+，且α中至少有ＶN中元素的一个出现。β∈(ＶT∪ＶN)*。α称为产生式α→β的左部(LeftPart)，β称为产生式α→β的右部(RightPart)。产生式定义各个语法成分的结构（组成规则）

第74页/共431页例2-1算术表达式的文法递归定义——中缀表示标识符(id)（常数、变量）是表达式(E)；表达式加一个表达式是表达式；表达式减一个表达式是表达式；表达式乘一个表达式是表达式；表达式除一个表达式是表达式；表达式加上括号后是表达式；第75页/共431页例2-1算术表达式的文法考虑简单算术表达式组成的语言G=({id，+，*，(，)}，{E}，P，E)P:E→E+EE→E*EE→(E)E→id约定：只写产生式简写E→E+E|E*E|(E)|id（2.1）第76页/共431页产生式的简写对一组有相同左部的产生式α→β1，α→β2…，α→βn可以简单地记为：α→β1|β2|…|βn读作：α定义为或者β1，或者β2，…，或者βn。并且称它们为α产生式。β1，β2，…，βn称为候选式(Candidate)。第77页/共431页基于产生式的变换--推导或归约E→E+E|E*E|(E)|idE由第一个候选式可以变成E+EE+E中的第一个E由第二个候选式可以变成E*E，从而E+E变成E*E+E根据第4个候选式，E*E+E中的E都可以变成id:E*E+E变成id*E+Eid*E+E变成id*E+idid*E+id变成id*id+id也就是说，根据第4个候选式，E*E+E经3步变换变成id*id+id第78页/共431页直接推导与归约根据产生式对符号串进行变换的过程Ａ→γ是文法Ｇ的一个产生式，且α、β∈（ＶT∪ＶN）*，称αＡβ直接推导/派生(Derive)出αγβ，也称αγβ直接归约(Reduce)为αＡβ。记为αＡβαγβ例：id+Eid+E*E第79页/共431页（多步）推导α0α1α2…αn记为α0n

αn

(恰用n步)

α0+

αn

（至少一步）

α0*

αn

（若干步:零步或多步）第80页/共431页推导/归约举例EE+E （1）串中含有变量

id+E （4）串中含有变量

id+E*E （2）串中含有变量

id+id*E （4）串中含有变量

id+id*id （4）串中没有变量到此串中已经没有（语法）变量了，不能再推导了1、E→E+E2、E→E*E3、E→(E)4、E→id第81页/共431页句型与句子E5id+id*id句子:如果S*x，且x∈ＶT*，则称x是G产生的一个句子(Sentence)EE+EE+E*EE4id+id*E句型:如果S*α，α∈(ＶT∪ＶN)*则称α是G产生的一个句型(SententialForm)第82页/共431页文法G产生的语言 Ｌ(Ｇ)＝{x｜Ｓ*

xandx∈ＶT*}文法E→E+E|E*E|(E)|id可以派生出多少个句子？文法G的作用——语言的有穷描述以有限的规则描述无限的语言现象有限：产生式集合、终结符集合、非终结符集合无限：可以导出无穷多个句子（L也可是有穷）第83页/共431页id+id*id的不同推导E→E+E|E*E|(E)|idE

E+E

id+E

id+E*E

id+id*E

id+id*idE

E+E

E+E*E

E+E*idE+id*id

id+id*idE

E*E

E+E*E

E+id*E

id+id*E

id+id*id不做限制句型(sententialForm)（归约）E*

id+id*id施于最右变量右句型/规范句型 (canonical~)(最左/规范归约)E+

id+id*id施于最左变量左句型(left-~)（最右归约）

E5

id+id*id第84页/共431页最左推导与最右推导最左推导(Left-mostDerivation)每次推导都施加在句型的最左边的语法变量上。——与最右归约对应最右推导(Right-mostDerivation)每次推导都施加在句型的最右边的语法变量上。——与最左归约（规范规约）对应的规范(Canonical)句型第85页/共431页例2-2标识符的文法1S→L|LT T→L|N|TL|TN L→a|b|c|d letter N→0|1|2|3|4|5 digit问题：正整数的文法?正实数的文法？第86页/共431页2.４文法的分类(Chomsky体系)根据语言结构的复杂程度（形式语言）涉及文法的复杂程度、分析方法的选择反映文法描述语言的能力如果G满足文法定义的要求，则Ｇ是０型文法（短语结构文法PSG:PhraseStructureGrammar）。L(G)为PSL。第87页/共431页上下文有关文法(CSG)若产生式集合中所有｜α｜≤｜β｜，除Ｓ→ε外，则Ｇ是１型文法即：上下文有关文法（CSG——ContextSensitiveGrammar）L(G)为1型/上下文有关/敏感语言(CSL)第88页/共431页上下文无关文法(CFG)若α∈ＶN，β∈(ＶN∪ＶT)*，则Ｇ是２型文法即：上下文无关文法(CFG:ContextFreeGrammar)L(G)为2型/上下文无关语言（CFL）CFG能描述程序设计语言的多数语法成分第89页/共431页例2-3标识符的文法2S→L|LT T→L|N|TL|TN L→a|b|c|d N→0|1|2|3|4|5S→a|b|c|d S→aT|bT|cT|dT T→a|b|c|d|0|1|2|3|4|5 T→aT|bT|cT|dT|0T |1T|2T|3T|4T|5T第90页/共431页正规文法(RG)设Ａ、Ｂ∈ＶN，ａ∈ＶT或为右线性(RightLinear)文法：Ａ→ａＢ或Ａ→ａ左线性(LeftLinear)文法：Ａ→Ｂａ或Ａ→ａ都是３型文法(正规文法RegularGrammar-RG)L(G)为3型/正规集/正则集/正则语言（RL）能描述程序设计语言的多数单词左、右线性文法不可混用第91页/共431页例非CFL的文法L={anbncn|n>0}的文法SaBC|aSBCCBBCaBabbBbbbCbc“可以证明”不存在CFGG,使L(G)=L第92页/共431页

在我们使用的程序设计语言中,有些语言结构不能用上下文无关文法来描述。例2.4L1={wcw|w∈{a,b}+}。例,aabcaab就是L1的一个句子。这个语言是检查程序中标识符的声明应先于引用的抽象。

例2.5L2={anbmcndm|n,m≥0}，它是检查过程声明的形参个数和过程引用的参数个数是否一致问题的抽象。非上下文无关的语言结构第93页/共431页Chomsky体系——总结Ｇ=(ＶT，ＶN，Ｐ，Ｓ)是一个文法,α→β∈P* G是0型文法，L(G)是0型语言；

---其能力相当于图灵机* |α|≤|β|:G是1型文法，L(G)是1型语言(除Ｓ→ε);

---其识别系统是线性界限自动机* α∈ＶN:G是2型文法，L(G)是2型语言;

---其识别系统是不确定的下推自动机* A→aB或A→a:G是右线性文法，L(G)是3型语言

A→Ba或A→ａ:G是左线性文法，L(G)是3型语言

---其识别系统是有穷自动机第94页/共431页文法的类型四种文法之间的关系是将产生式作进一步限制而定义的。四种文法之间的逐级“包含”关系如下：2型文法1型文法0型文法3型文法第95页/共431页ＢＮＦ范式——Backus-NaurForm

Backus-NormalFormα→β表示为α∷＝β非终结符用“<”和“>”括起来终结符：基本符号集其他β(α1|α2…|αn)≡βα1|βα2…|βαn[α]≡α|ε……第96页/共431页ＢＮＦ范式——BackusNormalForm例简单算术表达式(只写产生式)<算术表达式>∷＝<简单表达式>+<简单表达式><简单表达式>∷＝<简单表达式>*<简单表达式><简单表达式>∷＝(<简单表达式>)<简单表达式>∷＝id即：<算术表达式>∷＝<简单表达式>+<简单表达式>|<简单表达式>*<简单表达式>|(<简单表达式>)|id哪些是终结符？哪些是变量？第97页/共431页例2-6句子结构的表示

(文法E→E+E|E*E|(E)|id）EE+EE→E+EidE→idEE*E→E*EidE→ididE→idEE+Eid+Eid+E*Eid+id*Eid+id*id一棵树！第98页/共431页2.5CFG的分析树ParseTree用树的形式表示句型的生成树根：开始符号中间结点：非终结符叶结点：终结符或者非终结符每个推导对应一个中间结点及其儿子——一个二级子树-直接短语又称为语法分析树第99页/共431页EE+TT+TF+T

a1+T

a1+T*F

a1+F*F

a1+a2*FE+TT,T+TF,F+Ta1,a1+Ta1,T*F,a1+T*Fa1,F,F*F,a1+F*F

a1,a2,a1+a2*F,a2*F

a1,a2,a3,a2*

a3

a1+a2*a3EE+TTFa1T*FFa2a3a1+a2*a3短语第100页/共431页二义性文法与先天二义性语言对同一句子存在两棵语法分析树在理论上不可判定EE*EidEE+ididEE+EEEid*idid第101页/共431页1.描述一个句子的文法不是唯一的；2.对于一个句子的分析应是唯一的。考虑表达式下面的文法G[E],其产生式如下：

EE+EE*E(E)a

对于句子a+a*a,有如下两个最左推导：

EE+Ea+Ea+E*Ea+a*Ea+a*a

EE*EE+E*Ea+E*Ea+a*Ea+a*a文法的二义性第102页/共431页

EE+Ea+Ea+E*Ea+a*Ea+a*a

EE*EE+E*Ea+E*Ea+a*Ea+a*aEE+EE*EaaaEE*E+EEaaa最左推导第103页/共431页

EE+EE+E*EE+E*aE+a*aa+a*a

EE*EE*aE+E*aE+a*aa+a*aEE+EE*EaaaEE*E+EEaaa最右推导第104页/共431页如果一个文法的句子存在两棵分析树,那么,该句子是二义性的。如果一个文法包含二义性的句子,则称这个文法是二义性的;否则，该文法是无二义性的。几点说明：1.一般来说，程序语言存在无二义性文法，对于表达式来说，文法（2.1）是二义性的。对于条件语句，经常使用二义性文法描述它：SifexprthenSifexprthenSelseSother二义性的句子:ife1thenife2thens1elses2

二义性（歧义性，ambiquity)的定义第105页/共431页

下面是

Smatched_sunmatched_smatched_sifexprthenmatched_selsematched_sotherunmatched_sifexprthenSifexprthenmatched_selseunmatched_s它显然比较复杂，因此：2.在能驾驭的情况下，使用二义性文法。描述if语句的无二义性文法的产生式第106页/共431页3.对于任意一个上下文无关文法，不存在一个算法，判定它是无二义性的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的。4.存在先天二义性语言。例如，

aibicji,j1aibjcji,j1存在一个二义性的句子akbkck。第107页/共431页(抽象)语法树与分析树不同(语法)分析树EE+idE+EEidid(抽象)语法树+id+idid第108页/共431页2.6文法的构造明确描述对象──语言合法的语言结构确定基本符号集ＶT引入非终结符各种语法成分的结构定义句子的组成规则BNF范式或产生式第109页/共431页文法举例{x|x是长度为偶数的0、1串}S→00S|01S|10S|11S|ε{0m

1n

|m,n≥1} ——RLS→0S|0A A→1A|1{0n

1n

|n≥1} ——CFLS→0S1|01{ww

|w∈{a,b}+} ——PSLS→aCAE|bCBE Aa→aAAb→bAAE→aRE RE→DaR→RabR→RbCR→aCA|bCBBa→aBBb→bBBE→bREaR→RabR→RbCR→aCA|bCBaD→DabD→DbED→ε第110页/共431页值得注意的问题文法描述描述句子的组成规则，不涉及语义文法正确不能保证语义正确（例）明确目标要描述语言的结构确认基本符号集合理引入非终结符（语义明确）第111页/共431页本章小结：几个基本概念文法是语言的一种有穷描述，它严格、准确、简洁。文法的形式定义句型、句子、语言文法的分类ＣＦＧ的分析树第112页/共431页词法分析第113页/共431页第三章词法分析词法分析器(Scanner)的功能正则表达式状态转换图词法分析器的设计与实现有穷自动机FA第114页/共431页3.1词法分析（扫描）器的功能功能：输入源程序，输出单词符号(token)。即：把构成源程序的字符串转换成单词符号的序列单词符号的形式按照最小的语义单位设计通常表示为二元组： （单词种别，属性值）关键——找出符号的分割符第115页/共431页1)单词符号的表示常用单词种别—分类（肖军模P53，杜P46）各关键字（保留字、基本字），各种运算符，各种分界符——各用一个种别码标识标识符——用一个种别码标识整、实、字符常数——各用一个种别码标识属性（值）——单词的值常数的值，标识符的名字等保留字、运算符、分界符的属性值可以省略第116页/共431页例3-1:单词符号序列

while(*pointer!='\0'){pointer++;}

while (WHILE，_)( (SLP，_)* (FETCH，_)pointer (IDN，符号表入口指针)!= (RELOP，NE)'\0' (CONST，0)) (SRP，_){ (LP，_)pointer (IDN，符号表入口指针)++ (INC，_); (SEMI，_)} (RP，_)跟实现有关第117页/共431页2）相关问题超前扫描双字符运算符（**,/*,:=,…）DO90k=1,10DO90k=1.10预处理问题剔除源程序中的无用符号、空格、换行、注释等扫描器的运行方式作为独立的遍：简单，但需增加额外的开销作为独立的子程序：节省内存第118页/共431页扫描器作为独立的子程序第119页/共431页2）相关问题符号表的查填兼顾问题兼顾：token自身值作为符号表的入口Token串长度统一，可放宽对标识符的限制，但要增加额外负担不兼顾：token自身值就是标识符、常数本身的符号串速度快，但要限制标识符的长度第120页/共431页2）相关问题错误处理行、列计数发现并定位词法错误处理方法恐慌模式删除剩余输入中的一个字符向剩余输入插入一个字符字符替换等第121页/共431页3）符号表的作用 符号表是一张表格，由编译程序建立，存在于内存或磁盘中，用于存储程序编译或运行过程中所使用的变量（标识符）和常量（数字常数、字符常数）等信息。词法分析阶段：建立符号表，查填符号表，将不重复的标识符、数字常数和字符常数的性质填入符号表中，如：名字、类型、数值等，并且将变量（或常数）在符号表中的入口地址写到其自身的TOKEN字中。语法分析阶段：主要是使用符号表。在分析过程中，需要用到某个标识符（或常数）时，就从符号表的指定入口处查找出该符号。语义分析及中间代码生成阶段：主要是查填符号表。在生成四元式时，通常不使用变量的名字，而是使用它们在符号表中的入口位置。另外，在翻译说明语句时，要向符号表中填入变量的类型信息等。第122页/共431页符号表的作用（2）数据存储分配：将变量（或常数）所使用的数据区映像地址写入符号表中的地址（ADDR）栏。若数据区是动态数据，则在符号表中存储过程层号和位移量等信息，待运行时再计算具体地址。代码优化阶段：使用符号表。一方面，遇到变量时，要到符号表中查找它的具体信息，另一方面，在优化过程中，也有可能要使用符号表，例如在进行合并已知量的优化时，要检查变量是否有常数值，这时要使用符号表的数值（VAL）栏进行判断。目标代码生成阶段：在此过程中主要是查找符号表，为最终生成目标代码提供必要的信息，如建立DAG节点标记时使用符号表暂存变量的引用活跃信息。第123页/共431页4）符号表的内容符号表中包括名字（NAME）、类型（TYPE）、种属（KIND）、数值（VAL）和地址（ADDR）等栏，还带有一个字符串表。其中名字栏包括两个子栏，一个用于存放标识符在字符串表中的起始位置，另一个存放该标识符的长度；类型栏表示该标识符的类型（整、实、布尔和字符型四者之一）；种属栏表示该标识符属于哪一种类的名字（简单变量、常数名、数组名、过程名等）；数值栏存放常数标识符的值；地址栏存放分配给该符号的地址。第124页/共431页5）一种符号表的数据结构第125页/共431页6）输入缓冲工作区(token)单词开始指针扫描指针正拼单词第126页/共431页每次移动向前指针都需要做两次测试双缓冲区问题__超前扫描导致的效率问题？如何设计和实现扫描器大小问题128Byte*2|1024Byte*2|4096Byte*2if

forward在缓冲区第一部分末尾

thenbegin重装缓冲区第二部分;forward:=forward+1endelseifforward在缓冲区第二部分末尾

thenbegin

重装缓冲区第一部分;

将forward移到缓冲区第一部分开始endelseforward:=forward+1;

forward:=forward+1;ifforward↑=eofthenbeginif

forward在第一部分末尾

thenbegin

重装第二部分;

forward:=forward+1endelseifforward在第二部分末尾

thenbegin

重装第一部分;

将forward

移到第一部分开始endelse/*eof

在表示输入结束*/

终止词法分析end

6）输入缓冲（1）第127页/共431页3.2词法单元的识别词法分析器要求能够检查输入字符串，在前缀中找出和某个模式匹配的词素。通过正则定义来描述各种词法单元的模式。第128页/共431页1）正则表达式——RE设∑是一个字母表，⑴Φ是∑上的RE，L(Φ)=Φ；⑵ε是∑上的RE，L(ε)={ε}；⑶对于a∈∑，a是RE，L(a)={a}；⑷如果r和s是RE，L(r)=R,L(s)=S，则：

r与s的“和”(r|s)是RE，L(r|s)=R∪S； r与s的“乘积”(rs)是RE，L(rs)=RS； r的克林闭包(r*)是RE，L(r*)=R*。⑸只有满足⑴、⑵、⑶、⑷的才是RE。第129页/共431页2）正则定义的例子C语言标识符的正则定义letter_

A|B|…|Z|a|b|…|z|_digit0|1|…|9idletter_(letter_|digit)*id对应的正则表达式为(A|B|…|Z|a|b|…|z|_)((A|B|…|Z|a|b|…|z|_)|(0|1|…|9))*第130页/共431页3）正则表达式的扩展基本运算符：并、连接、Kleen闭包扩展的运算符：一个或多个实例：单目后缀+r+等价于rr*零个或一个实例：？r?等价于ε|r字符类[a1a2…an]等价于a1|a2|…|an[a-e]等价于a|b|c|d|e用来使得正则表达式更加简洁，但是不会使得正则表达式能够描述更多的语言。第131页/共431页4）运算的优先级运算优先级和结合性:*高于“连接”和|，“连接”高于||具有交换律、结合律“连接” 具有结合律、和对|的分配律()指定优先关系意义清楚时，括号可以省略例：L(a(a|b)*(ε|((.|_)(a|b)(a|b)*))){a}{a,b}*({ε}∪{.,_}{a,b}{a,b}*)第132页/共431页第133页/共431页5）状态转换图状态转换图是词法分析器的重要组件之一状态转换图(transitiondiagram)状态(state)：表示了可能在识别词素的过程中可能出现的情况状态看作是已处理部分的总结。某些状态为接受状态或最终状态，表明已经找到词素。加上*的接受状态表示最后读入的符号不在词素中。开始状态（初始状态）：用start边表示。边(edge)：从一个状态指向另一个状态；边的标号是一个或者多个符号。如果当前符号为s，下一个输入符号为a，就沿着从s离开，标号为a的边到达下一个状态。第134页/共431页状态转换图的例子第135页/共431页6）保留字和标识符的识别在很多程序设计语言中，保留字也符合标识符的模式，识别标识符的状态转换图也会识别保留字。解决方法在符号表中预先填写保留字，并指明它们不是普通标识符。为关键字/保留字建立单独的状态转换图。并设定保留字的优先级高于标识符。第136页/共431页3.3词法分析器的设计和实现从转换图构造词法分析器的方法变量state记录当前状态一个switch根据state的值转到相应的代码每个状态对应于一段代码。这段代码根据读入的符号，确定下一个状态如果找不到相应的边，则调用fail()进行错误恢复进入某个接受状态时，返回相应的词法单元。注意状态有*标记时，需要回退forward指针。第137页/共431页状态转换图的例子第138页/共431页Relop对应的代码概要第139页/共431页处理多个模式的方法词法分析器需要匹配多个模式解决方法顺序地尝试各个词法单元对应的状态转换图。如果引发fail()，回退并启动下一个状态图。可以根据优先级确定尝试顺序。“并行地”运行各个状态转换图。通过greedy策略，识别最长的和某个模式匹配的输入前缀预先把各个状态转换图合成一个状态转换图，然后运行这个状态转换图。第140页/共431页3.4有穷自动机FA本质上和状态转换图类似，分为两类：不确定的有穷自动机（NondeterministicFiniteAutomata,NFA）边上的标号没有限制，一个符号可出现在离开同一个状态的多条边上，ε可以做标号确定的有穷自动机（DeterministicFiniteAutomata,DFA）对于每个状态以及每个符号，有且只有一条边。两种自动机都识别正则语言第141页/共431页1）不确定的有穷自动机NFA由以下几部分组成一个有穷的状态集合S一个输入符号集合Σ（inputalphabet）转换函数（transitionfunction）对于每个状态和Σ

U{ε}中的符号，给出相应的后继状态集合一个状态s0被指定为开始状态/初始状态（有些定义中可以有多个开始状态）S的一个子集被指定为接受状态第142页/共431页2）NFA的例子状态集合S={0,1,2,3}开始状态0接受状态集合{3}转换函数：(0,a){0,1}(0,b){0}(1,b)2(2,b)3相应的图形表示第143页/共431页3）输入字符串的接受一个NFA接受输入字符串x，当且仅当对应的转换图中存在一条从开始状态到某个接受状态的路径，该路径中各条边上的标号组成x（ε标号不考虑）。前面的NFA接受aabb，因为：NFA接受的语言：从开始状态到达接受状态的所有路径上的标号串的集合。就是它接受的所有符号串的集合第144页/共431页4）确定有穷自动机一个NFA被称为DFA，如果没有ε之上的转换动作对于每个状态s和每个输入符号，有且仅有一条标号为a的离开s的边可以高效判断一个串能否被一个DFA接受。每个NFA都有一个等价的DFA。即它们接受同样的语言。第145页/共431页5）从正则表达式到自动机的转换正则表达式可以简洁、精确地描述词法单元的模式但是在进行模式匹配时需要模拟DFA的执行。因此，需要将正则表达式转换为DFA步骤：正则表达式到NFANFA到DFA第146页/共431页6）正则表达式到NFA基本思想根据正则表达式的递归定义，按照正则表达式的结构递归地构造出相应的NFA。算法分成两个部分：基本规则处理ε和单符号的情况对于每个正则表达式的运算，建立组合组合相应NFA的方法。第147页/共431页转换算法（1）基本规则部分表达式ε表达式a第148页/共431页归纳部分s|rsr转换算法（2）第149页/共431页归纳部分s*转换算法（3）第150页/共431页7）转换得到的NFA的特性状态数量最多为r中的运算符和运算符分量总数的两倍因为每个步骤只引入两个状态有且只有一个开始状态和有关接受状态除接受状态之外，每个状态要么由一条标号不等于ε的出边，要么有两条标号为ε的出边。第151页/共431页正则表达式到NFA的例子（1）正则表达式(a|b)*abb第一个a对应的NFA第一个b对应的NFA第152页/共431页(a|b)的NFA第二个a的NFA正则表达式到NFA的例子（2）第153页/共431页(a|b)*的NFA正则表达式到NFA的例子（3）第154页/共431页8）NFA合并的方法合并方法：引入新的开始状态，并引入从这个开始状态到各个原开始状态的ε转换。第155页/共431页词法分析程序的设计与实现状态转移图——教材P