整套课件：编译原理(北京工业大学)

《编译原理》

(PrinciplesofCompiling)主要内容编译系统及其设计概述(总体结构、设计方法——2)语言与文法(文法、推导、归约、分类、分析树——6)词法分析(词法分析、正规式与正规文法、DFA状态转移图——6)语法分析(自顶向下：LL(1)、递归子程序；自底向上：算符优先、LR——14)语义分析(属性文法、各种语句的语法制导翻译——10)运行环境(存储分配、过程调用、符号表管理——4)总结——2教学目的计算学科的定义对信息描述和变换算法的系统研究，主要包括它们的理论、分析、效率、实现和应用。计算学科的根本问题是什么能被（有效地）且如何自动化。它讨论问题求解的“能行性”。学科特征：理工兼有思维特征：抽象思维与逻辑思维教学目的计算学科本科生专业能力构成“计算思维能力”——模型化、抽象思维能力、逻辑思维能力算法设计与分析能力程序设计与实现能力计算机系统的认知、分析、设计和应用能力教学目的——《编译原理》是一门非常好的课程涉及的是一个比较适当的抽象层面上的数据变换（既抽象，又实际）一些具体的表示和变换算法“自顶向下”和“自底向上”的系统设计方法（思想、方法、实现全方位讨论）一个相当规模的系统的设计（含总体结构）AlfredV.Aho：编写编译器的原理和技术具有十分普遍的意义，以至于在每个计算机科学家的研究生涯中，本书中的原理和技术都会反复用到结论：计算机专业最恰当、有效的知识载体之一教学要求掌握编译程序总体结构在系统级上认识算法、系统的设计具有把握系统的能力学习有关的原理、实现方法和技术，了解计算学科的基本方法、思想掌握典型方法。“在每一个计算机科技工作者的职业生涯中，这些原理和技术都被反复用到。”兼顾语言的描述方法、设计、应用——形式化进一步培养“计算机思维能力”程序的非物理性质学习方法勤于思考博览、多思（学而不思则罔、思而不学则怠；书由厚到薄、由薄到厚）、常实践思考由怀疑和答案组成。怀疑是智慧的大门，知道得越多，就越会发问，而问题就越多。发问使人进步。强化基础在独立思考之前，必须先有基础知识。所谓“获得基础知识”并不是形式上读过某门课程，而是将学过的东西完全弄懂。理论与实践的结合能力学习方法应对困难不畏惧困难从教训到经验——亲身体验要实践（作业、实验），加深理解学习是一个过程上课、读书、复习、做作业、讨论、做实验、自己编程序、上机调试排错………是绝对必要的辅导答疑教师是最宝贵的资源…自己要思考，以获得最大收获：习题、问题第1章引论1.1计算机语言的发展1.2翻译系统1.3编译系统的功能分析1.4编译程序总体结构1.5编译程序的生成1.6编译技术的应用1.1计算机语言的发展机器语言(MachineLanguage)汇编语言(AssembleLanguage)0、1代码与助记符：更接近于计算机硬件指令系统的工作高级语言(HighLevelLanguage)定义数据、描述算法（程序）如：C、FORTRAN、PASCAL、C++、JAVA、SQL(数据定义、数据操作)命令语言(Command)以功能封装为特征高级语言的分类强制式语言(ImperativeLanguage)FORTRAN(段结构)、BASIC、Pascal(嵌套结构)、C……函数(应用)式语言(FunctionalLanguage)LISP、ML……逻辑式(基于规则)语言(LogicalLanguage)Prolog……面向对象语言(Object-OrientedLanguage)Smalltalk、C++、Java、Ada(程序包)……1.2翻译系统翻译程序(Translator)将某一种语言描述的程序(源程序——SourceProgram)翻译成等价的另一种语言描述的程序(目标程序——ObjectProgram)的程序。翻译程序源程序目标程序(*.C/*.PAS/*.AS)(*.OBJ/*.EXE/*.*)1.2翻译系统解释程序(Interpreter)口译与笔译（单句提交与整篇提交）源程序输入数据计算结果解释程序1.2翻译系统编译程序(Compiler)高级语言程序→汇编/机器语言程序源程序目标程序编译程序1.2编译系统SP Compiler

S-Source O-Object OP P-ProgramInput RS RS-RunSys. Output 编译系统(CompilingSystem)编译系统=编译程序+运行系统支撑环境、运行库等1.2翻译系统其它：诊断编译程序（DiagnosticCompiler)优化编译程序（OptimizingCompiler)交叉编译程序（CrossCompiler)可变目标编译程序（RetargetableCompiler)并行编译程序（ParallelizingCompiler）汇编程序(Assembler)、交叉汇编程序(CrossAssembler)、反汇编程序（Disassembler)1.2翻译系统—汇总ML MLP Assembler DisassemblerAL ALP Compiler DataHL HLP Interpreter ResultM-MachineL-LangugeP-ProgramA-AssembleH-HighLevelTranslator1.3编译系统的功能分析程序分析词法、语法、语义分析综合语句的翻译、代码生成例如：标识符左值与右值的绑定(binding)变量：存储单元函数：目标代码序列1.4编译程序总体结构请参阅P5图1.1

目标代码生成器代码优化器语义分析与中间代码生成器语法分析器表格管理出错处理中间代码中间代码目标代码语法单位单词符号词法分析器源程序1.词法分析例：res=fact*(term1+term2);结果IDN res‘=’IDNfact‘*’‘(’IDN term1‘+’IDNterm2‘)’‘;’1、词法分析词法分析器(LexicalAnalyzer)又叫做扫描器(Scanner)，完成词法分析功能：词法分析器从左到右扫描源程序（字符串），并将其转换成单词(记号—Token)串；同时查词法错误，进行标识符登记——符号表管理。输入：字符串 输出：(种别码，属性值)——序对属性值——token的机内表示2、语法分析语法分析器(SyntaxAnalyzer，又叫Parser)完成语法分析功能：Parser实现“组词成句”，构造分析树，指出语法错误，指导翻译输入：Token序列输出：语法成分2.语法分析res=fact*(term1+term2); 字符串*；赋值语句表达式=）（fact表达式res表达式表达式表达式表达式+term1term23.语义分析功能：分析由语法分析器给出的语法单位的语义获取标识符的属性：类型、作用域等语义检查：运算的合法性、取值范围等子程序的静态绑定：代码的相对地址变量的静态绑定：数据的相对地址4.中间代码生成中间代码(intermediateCode)例:id1+id2*id3后缀表示(逆波兰ReversePolishNotation)id1id2id3*

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

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

EE+Eid1E*Eid2id3语法树波兰表示问题——Lukasiewicz1929/1951年发明

中缀表示(Infixnotation):(a+①b)*(-c+②d)+③e/f波兰表示（Polish/Prefix/Parenthesis-free/Lukasiewicznotation）——也就是前缀表示+③*+①ab+②@cd/ef运算顺序从右向左逆波兰表示(ReversePolish/Suffix/Postfixnotation)——也就是后缀表示

ab+①c@d+②*ef/+③运算顺序从左向右4.中间代码生成中间代码的特点简单规范机器无关易于优化与转换三地址码的另一种表示形式T1=id2*id3T2=id1*T1其它类型的语句举例

printf(“hello”)x:=s （赋值）paramx （参数）callf （函数调用）s是hello的地址f是函数printf的地址对中间代码的优化处理:对代码进行等价变换以求提高执行效率——提高运行速度和节省存储空间与机器无关的优化与机器有关的优化5.代码优化与机器无关的优化局部优化常量合并：常数运算在编译期间完成，如8+9*4公共子表达式的提取:基本块内循环优化强度削减代码外提与机器有关的优化寄存器的利用将常用量放入寄存器，以减少访问内存的次数体系结构MIMD、SIMD、SPMD、向量机、流水机存储策略根据算法访存的要求安排：Cache、并行存储体系——减少访问冲突任务划分按运行的算法即体系结构，划分子任务(MPMD)6.目标代码生成将中间代码转换成目标机上的机器指令代码或汇编代码7、表格管理管理各种符号表（常数、标号、变量、过程、结构……），查、填（登记、查找）源程序中出现的符号和编译程序生成的符号，为编译的各个阶段提供信息。辅助语法检查、语义检查完成静态绑定、管理编译过程Hash表、链表等各种查、填表技术8、错误处理进行各种错误的检查、报告、纠正，以及相应的续编译处理（如：错误的定位与局部化）词法：拼写……语法：语句结构、表达式结构……语义：类型不匹配……模块分类分析：词法分析、语法分析、语义分析综合：中间代码生成、代码优化、目标代码生成辅助：符号表管理、出错处理8项功能对应8个模块编译程序总体结构中间代码目标代码生成器代码优化器语义分析与中间代码生成器语法分析器表格管理出错处理中间代码目标代码语法单位单词符号词法分析器源程序例一个语句的翻译9编译的遍（Pass）根据系统资源的状况、运行目标的要求……等，可以将一个编译程序设计成多遍扫描的形式，在每一遍扫描中，完成不同的任务。遍可以和阶段相对应，也可无关单遍代码不太有效10、编译的前端与后端前端与源语言有关、与目标机无关的部分词法分析、语法分析、语义分析与中间代码生成、与机器无关的代码优化后端与目标机有关的部分与机器有关的代码优化、目标代码生成1.5编译程序的生成设计目标目标程序小，执行速度快。编译程序小，执行速度快。诊断能力强，可靠性高。可移植性，可扩充性。如何实现编译器？直接用可运行的代码编制——太费力！Ｔ形图表示语言翻译的Ｔ形图源语言表示语言目标语言功能1）交叉编译(CrossCompiling)/移植问题一：A机上有一个C语言编译器，是否可利用此编译器实现B机上的C语言编译器？条件：Ａ机有Ｃ语言的编译程序目的：实现Ｂ机的Ｃ语言的编译1.

(人)用Ｃ语言编制B机的Ｃ编译程序P0(C→B)(Ａ机的C编译P1)编译P0，得到在A机上可运行的P2(C→B)Ｃ语言Ｃ语言Ｂ机器Ｃ语言Ａ机器A机器Ｃ语言A机器Ｂ机器P0P1P2上次课主要内容基本概念翻译程序、编译程序、解释程序、编译系统汇编程序、其他编译的扫描遍数、前端、后端编译程序总体结构中间代码目标代码生成器代码优化器语义分析与中间代码生成器语法分析器表格管理出错处理中间代码目标代码语法单位单词符号词法分析器源程序上次课主要内容T形图移植源语言表示语言目标语言3.(Ａ机的P2)编译P0，得到在B机上可运行的P3(C→B)Ｃ语言Ｂ机器Ｂ机器P3Ｃ语言Ｃ语言Ｂ机器Ｃ语言Ａ机器A机器Ｃ语言A机器Ｂ机器P0P1P2P2Ｃ语言Ａ机器Ｂ机器Ｃ语言Ｃ语言Ｂ机器P0获得一个工具2)本机编译器利用问题二：A机上有一个C语言编译器，现要实现一个新语言NEW的编译器？能利用交叉编译技术么？用C编写NEW的编译，并用C编译器编译它NEW语言Ｃ语言A机器Ｃ语言Ａ机器A机器NEW语言A机器A机器P0(编写)P1(原有)P2(生成)问题三：直接在一个机上实现C语言编译器，还有别的技术么？解决：用汇编语言实现一个Ｃ子集的编译程序(P0—人)用汇编程序处理该程序,得到P2(P2:可直接运行)用Ｃ子集编制Ｃ语言的编译程序(P3—人)用P2编译P3，得到P43)编译程序的自展技术4.用P2编译P3，得到P4Ｃ语言机器语言机器语言P4Ｃ子集汇编语言机器语言P01.

用汇编语言实现一个Ｃ子集的编译程序(P0—人)汇编语言机器语言机器语言Ｃ子集机器语言机器语言P1P22.用汇编程序(P1)处理该程序,得到P2(P2:可直接运行)P2Ｃ子集机器语言机器语言获得一个工具Ｃ语言Ｃ子集机器语言P33.用Ｃ子集编制Ｃ语言的编译程序(P3—人)4)利用编译程序自动生成器词法分析器的自动生成程序词法规则说明词法分析程序(C程序)输入： 词法（正规表达式） 识别动作（Ｃ程序段）输出：

yylex()函数LEX语法分析器的自动生成程序语法规则说明语法分析程序(C程序)输入： 语法规则（产生式） 语义动作（Ｃ程序段）输出：

yyparse()函数ＹＡＣＣ1.6编译技术的应用把复杂数据看作一条语句数据格式的分析利用词法分析、语法分析方法数据处理的框架基于语法制导的语义处理框架编译技术可以用于各种复杂数据的分析处理例1-1DOS命令date的输出格式例：9-2-1993、09-03-1993、9-03-93语法date→month-day-year词法month→DIGITDIGIT|DIGITday→DIGITDIGIT|DIGITyear→DIGITDIGIT|DIGIIDIGITDIGITDIGIT例1-1（续）语义year(年)、month(月)、day(日)语义约束条件0<month.value<130<day.value<32，31，300<year.value<10000习题1.试分析一个简短的C程序，找出几个属于语法、词法、语义的语言现象。2.试分析例1-1的date输出数据的处理中，应该做哪些词法分析、语法分析、语义处理。3.理解交叉编译/移植和自展技术第2章高级语言

及其文法2.1语言概述2.2基本定义2.3文法(Grammar)的定义2.4CFG的语法(分析)树(ParseTree)2.5文法的分类2.6文法的构造本章主要内容2.1语言概述什么是语言自然语言(NaturalLanguage)是人与人的通讯工具语义(Semantics):环境、背景知识、语气、二义性——难以形式化计算机语言(ComputerLanguage)计算机系统间、人机间通讯工具严格的语法(Grammar)、语义(Semantics)——易于形式化：严格语言是用来交换信息的工具——功能性描述2.1语言概述语言的描述方法——现状自然语言：自然、方便-非形式化数学语言（符号）：严格、准确-形式化形式化描述高度的抽象，严格的理论基础和方便的计算机表示。2.1语言概述语言——形式化的内容提取单词(Token)：满足一定规则字符(Character)串句子(Sentence)：满足一定规则单词序列语言(Language)：满足一定条件的句子集合语言是字和组合字的规则——结构性描述例：一译开天第课今始编节上今天开始上第一节编译课2.1语言概述程序设计语言——形式化的内容提取程序设计语言(ProgrammingLanguage)：组成程序的所有语句的集合程序(Program)：满足语法规则的语句序列语句(Sentence)：满足语法规则的单词序列单词(Token)：满足词法规则的字符串例变量=表达式if条件then语句while条件do语句call过程名(参数表)2.1语言概述描述形式——文法语法——语句语句的组成规则描述方法：BNF范式、语法(描述)图词法——单词单词的组成规则描述方法：BNF范式、正规式2.2基本定义字母表（Alphabet）是一个非空有穷集合，字母表中的元素称为该字母表的一个字母（Letter），也叫字符（Character）。例以下是不同的字母表： ⑴{a，b，c，d} ⑵{a，b，c，……，z} ⑶{0，1}2.2基本定义字母表上符号串(String)的定义

(1)ε是∑上的一个符号串，叫做空串。(2)若x是∑上的符号串，而a是∑的元素,

则xa是∑上的符号串。(3)y是∑上的符号串,当且仅当它由(1)和(2)导出。由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串,也称作“字”(Word)。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}2.2基本定义定义3设∑是一个字母表，∑的正闭包(PositiveClosure)：∑+=∑∪∑2∪∑3∪∑4∪……∑的克林闭包(KleeneClosure)：∑*=∑0∪∑+=∑0∪∑∪∑2∪∑3∪……2.2基本定义例{0,1}+={0，1，00，01，11，000，001，010，011，100，……}{a，b，c，d}+={a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，……，aaa，aab，aac，aad，aba，abb，abc……}2.2基本定义例{0,1}*={ε，0，1，00，01，11，000，001，010，011，100，…}{a，b，c，d}*={ε，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，…，aaa，aab，aac，aad，aba，abb，abc，…}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}*2.2基本定义设s是符号串：01290273前缀：移走s的尾部的零个或多于零个符号后缀：删去s的头部的零个或多于零个符号子串:从s中删去一个前缀和一个后缀子序列:从s中删去零个或多于零个符号(这些符号不要求是连续的）长度：是该符号串中的符号的数目。例如|aab|=3,|ε|=0。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,…...2.3文法的定义如何实现语言结构的形式化描述？考虑一个句子——文法要素的提取分析：Thegraywolfwilleatthegoat〈谓语〉〈主语〉〈形容词〉〈名词〉〈动词〉〈直接宾语〉助动词〈句子〉动原冠词名词Thegraywolfwilleatthegoat〈冠词〉

句子

→

主语

谓语

主语

→

冠词

形容词

名词

谓语

→

动词

直接宾语

动词

→

助动词

动词原形

直接宾语

→

冠词

名词

产生句子的规则——从产生语言的角度

冠词

→

the

形容词

→

gray

助动词

→

will

动词原形

→

eat

名词

→

wolf

名词

→

goat终结符号集VT={the，gray,wolf,will,eat,goat}非终结符号集VN={

句子

，

主语

，

谓语

，

冠词

，

形容词

，

名词

，

动词

，

直接宾语

，

助动词

，

动词原形

}语法规则集P={

句子

→

主语

谓语

，……}开始符号S=

句子

句子的语法组成

——终结符号集，非终结符号集，语法规则，开始符号文法G的形式定义文法G为一个四元组:

Ｇ=(ＶT，ＶN，Ｐ，Ｓ)ＶT：终结符(Terminal)集ＶN：非终结符(Variable)集，ＶT∩ＶN=Φ语法范畴——某个语言结构Ｓ：开始符号(StartSymbol)，S∈ＶN至少在产生式左侧出现一次文法G的形式定义Ｐ：产生式(Product)集合α→β，被称为产生式（定义式），读作：α定义为β。其中α∈(ＶT∪ＶN)+，且α中至少有ＶN中元素的一个出现。β∈(ＶT∪ＶN)*。α称为产生式α→β的左部(LeftPart)，β称为产生式α→β的右部(RightPart)。

句子

主语

谓语

冠词

形容词

名词

谓语

the

形容词

名词

谓语

thegray

名词

谓语

thegraywolf

谓语

thegraywolf

动词

直接宾语

thegraywolf

助动词

动词原形

直接宾语

thegraywolfwill

动词原形

直接宾语

thegraywolfwilleat

直接宾语

thegraywolfwilleat

冠词

名词

thegraywolfwilleatthe

名词

thegraywolfwilleatthegoat句子的派生（推导）___根据规则

句子

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

thegraywolfwilleatthegoat还可以“得出”其他的句子例2-1算术表达式的文法考虑简单算术表达式组成的语言递归定义——中缀表示标识符(id)（常数、变量）是表达式；表达式加一个表达式是表达式；表达式减一个表达式是表达式；表达式乘一个表达式是表达式；表达式除一个表达式是表达式；表达式加上括号后是表达式。上次课主要内容编译程序实现技术自展自动生成：lex、Yacc语言信息交流的工具字和组合字的规则的统一体字母表上的语言字母表∑+

、∑*、a∈∑，x∈∑*、L

∑*、x∈L前缀、后缀、子串、串长、串的连接、串的幂上次课主要内容文法通过刻画语言的结构描述语言用有穷描述无穷Ｇ=(ＶT，ＶN，Ｐ，Ｓ)表达式的递归定义例2-1算术表达式的文法考虑用式子表示这个定义标识符(id)是表达式表达式加一个表达式是表达式E→idE→E+E表达式减一个表达式是表达式E→E-E表达式乘一个表达式是表达式E→E*E表达式除一个表达式是表达式E→E/E表达式加上括号后是表达式E→(E)例2-1算术表达式的文法P:E→E+EE→E-EE→E*EE→E/EE→(E)E→idG=（{id，+，-，*，/，(，)}，{E}，P，E）约定：只写产生式简写E→E+E|E*E|(E)|id产生式的简写对一组有相同左部的产生式α→β1，α→β2…，α→βn可以简单地记为：α→β1|β2|…|βn读作：α定义为或者β1，或者β2，…，或者βn。并且称它们为α产生式。β1，β2，…，βn称为候选式(Candidate)。产生式规定的一些变换E由第一个候选式可以变成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+id1E→E+E2E→E*E3E→(E)4E→id5E→E-E6E→E/E文法使用举例E

E+E （1）

id+E （4）

id+E*E （2）

id+id*E （4）

id+id*id （4）E

5id+id*id1E→E+E2E→E*E3E→(E)4E→id5E→E-E6E→E/E直接推导与归约根据产生式对符号串进行变换的过程Ａ→γ是文法Ｇ的一个产生式，且α、β∈（ＶT∪ＶN）*，称αＡβ的直接推导/派生(Derive)出αγβ，也称αγβ直接归约(Reduce)为αＡβ。记为αＡβ

αγβ例：id+E

id+E*E（多步）推导α0

α1

α2

…

αn记为α0

nαn

(恰用n步)α0

+αn

（至少一步）

α0

*αn

（若干步:零步或多步）推导/归约举例E

E+E （1）串中含有变量

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

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

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

id+id*id （4）串中没有变量到此串中已经没有（语法）变量了，不能再推了——得到句子1E→E+E2E→E*E3E→(E)4E→id句型与句子E

5id+id*id定义:如果S

*x，且x∈ＶT*，则称x是G产生的一个句子(Sentence)E

E+E

E+E*EE

4id+id*E定义:如果S

*α，α∈(ＶT∪ＶN)*则称α是G产生的一个句型(SententialForm)文法G产生的语言定义： L(G)={x|S

*xandx∈VT*}文法E→E+E|E*E|(E)|id可以派生出多少个句子？文法G的作用——语言的有穷描述以有限的规则描述无限的语言现象有限:产生式集合、终结符集合、非终结符集合无限：可以导出无穷多个句子（注：L也可是有穷）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*id

E+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-~)（最右归约）

E

5

id+id*id最左推导与最右推导最左推导(Left-mostDerivation)每次推导都施加在句型的最左边的语法变量上。——与最右归约对应最右推导(Right-mostDerivation)每次推导都施加在句型的最右边的语法变量上。——与最左归约（规范规约）对应的规范(Canonical)句型短语(Phrase)自然语言中什么叫短语？如果Ｓ

*

αＡβ&A

+γ，则称γ是句型αγβ的相对于变量A的短语如果Ｓ

*

αＡβ&A

γ，则称γ是句型αγβ的相对于变量A的直接短语最左直接短语叫做句柄(Handle)例：(直接)短语E

E+T

T+T

F+T

(E)+T

(E+T)+T

(E+T)+T

(T+T)+T

(F+T)+T

(a+T)+T

(a+T*F)+T

(a+F*F)+T

(a+b*F)+T

(a+b*c)+T

(a+b*c)+F

(a+b*c)+dE→E+T|TT→T*F|FF→(E)|id句柄(Handle)：最左直接短语E→E+T|TT→T*F|FF→(E)|idE

E+T

T+T

F+T

(E)+T

(E+T)+T

(E+T)+T

(T+T)+T

(F+T)+T

(a+T)+T

(a+T*F)+T

(a+F*F)+T

(a+b*F)+T

(a+b*c)+T

(a+b*c)+F

(a+b*c)+d例2-2标识符的文法1S→L|LT T→L|N|TL|TN L→a|b|c|d letter N→0|1|2|3|4|5 digit?正整数的文法；正实数的文法2.４文法的分类(Chomsky体系)语言结构的复杂程度（形式语言）涉及文法的复杂程度、分析方法的选择如果G满足文法定义的要求，则Ｇ是０型文法（短语结构文法PSG:PhraseStructureGrammar）。L(G)为PSL。上下文有关文法(CSG)若产生式集合中所有｜α｜≤｜β｜，除Ｓ→ε外，则Ｇ是１型文法即：上下文有关文法（CSG——ContextSensitiveGrammar）L(G)为1型/上下文有关/敏感语言(CSL)上下文无关文法(CFG)若α∈ＶN，β∈(ＶN∪ＶT)*，则Ｇ是２型文法即：上下文无关文法(CFG:ContextFreeGrammar)L(G)为2型/上下文无关语言（CFL）例：程序设计语言的多数语法特征例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 T→1T|2T|3T|4T|5T正规文法(RG)设Ａ、Ｂ∈ＶN，ａ∈ＶT或为

右线性(RightLinear)文法：Ａ→ａＢ或Ａ→ａ左线性(LeftLinear)文法：Ａ→Ｂａ或Ａ→ａ都是３型文法(正规文法RegularGrammar-RG)L(G)为3型/正规集/正则集/正则语言（RL）例：程序设计语言的多数词法特性左、右线性文法不可混用例非CFL的文法L={anbncn|n>0}的文法S

aBC|aSBCCB

BCaB

abbB

bbbC

bc“可以证明”不存在CFGG,使L(G)=L

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

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

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

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

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

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

---其识别系统是有穷自动机(FA)四种文法之间的关系是将产生式作进一步限制而定义的。四种文法之间的逐级“包含”关系如下：2型文法1型文法0型文法3型文法Chomsky体系——总结ＢＮＦ范式——Backus-NaurForm

Backus-NormalFormα→β表示为α∷＝β非终结符用“<”和“>”括起来终结符：基本符号集其他β(α1|α2…|αn)≡βα1|βα2…|βαn{α1|α2…|αn}nm

[α]≡α|ε……ＢＮＦ范式——BackusNormalForm例简单算术表达式(只写产生式)<简单表达式>∷＝<简单表达式>+<简单表达式><简单表达式>∷＝<简单表达式>*<简单表达式><简单表达式>∷＝(<简单表达式>)<简单表达式>∷＝id即：<简单表达式>∷＝<简单表达式>+<简单表达式>| <简单表达式>*<简单表达式>|(<简单表达式>)|id哪些是终结符？哪些是变量？例2-5句子结构的表示

(文法E→E+E|E*E|(E)|id

）EE+EE→E+EidE→idEE*E→E*EidE→ididE→idE

E+E

id+E

id+E*E

id+id*E

id+id*id一棵树！上次课主要内容产生式的简写：

α→β1|β2|…|βn（候选式）文法的简写：只写产生式集、开始符约定直接派生/归约：αＡβ

αγβＡ→γN步派生/归约：αＡβ

NαγβＡ

Nγ句子与句型：S

*x S

*α语言：L(G)={x|S

*xandx∈VT*}上次课主要内容短语：短语、直接短语、句柄Chomsky体系BNF范式最左推导（最右归约）最右推导（最左归约）规范推导/归约，规范句型例:(a1+a2)*a3E→E+T|E-T|TT→T*F|T/F|FF→(E)|id2.5CFG的语法树ParseTree用树的形式表示句型的结构树根：开始符号中间结点：非终结符叶结点：终结符或者非终结符每个推导对应一个中间结点及其儿子——一个二级子树-直接短语又称为语法分析树例短语与语法(分析)树

(文法E→E+E|E*E|(E)|id

）EE+Eid(a1)EE*id(a2)id(a3)短语——一棵子树的叶子！短语：一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。直接短语：仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串。句柄：一个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。例如，对表达式文法G[E]和句子a1+a2*a3，挑选出推导过程中产生的句型中的短语，直接短语，句柄。用子树解释短语，直接短语，句柄E

E+T

T+T

F+T

a1+T

a1+T*F

a1+F*F

a1+a2*FE+T

T,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*FFa2a3

a1+a2*a3短语二义性文法与先天二义性语言对同一句子存在两棵语法分析树在理论上不可判定EE*EidEE+ididEE+EEEid*idid

1.描述一个句子的文法不是唯一的；

2.对于一个句子的分析应是唯一的。考虑表达式下面的文法G[E],其产生式如下：

E

E+E

E*E

(E)

id

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

E

E+E

a1+E

a1+E*E

a1+a2*E

a1+a2*a3E

E*E

E+E*E

a1+E*E

a1+a2*E

a1+a2*a3文法的二义性

E

E+E

a1+E

a1+E*E

a1+a2*E

a1+a2*a3

E

E*E

E+E*E

a1+E*E

a1+a2*E

a1+a2*a3EE+Ea1E*Ea2a3EE*E+EEa1a2a3最左推导

E

E*E

E*a3

E+E*a3

E+a2*a3

a1+a2*a3EE+Ea1E*Ea2a3EE*E+EEa1a2a3最右推导

E

E+E

a1+E

a1+E*E

a1+a2*E

a1+a2*a3如果一个文法的句子存在两棵分析树,那么,该句子是二义性的。如果一个文法包含二义性的句子,则称这个文法是二义性的;否则，该文法是无二义性的。几点说明：1.一般来说，程序语言存在无二义性文法，对于表达式来说，文法（2.1）是无二义性的。对于条件语句，经常使用二义性文法描述它：S

ifexprthenS

ifexprthenSelseS

other二义性的句子:ife1thenife2thens1elses2

二义性（歧义性,ambiquity)2.对于任意一个上下文无关文法，不存在一个算法，判定它是无二义性的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的。3.存在先天二义性语言。例如，

aibicj

i,j

1

aibjcj

i,j

1

存在一个二义性的句子akbkck4.在能驾驭的情况下，使用二义性文法——简单二义性（歧义性，ambiquity)E→E+T|E-T|TT→T*F|T/F|FF→(E)|id参考书：(抽象)语法树不同(语法)分析树EE+idE+EEidid(抽象)语法树+id+idid2.6文法的构造——为了更好地理解文法目的：给出语言的有穷描述途径：刻画语言的结构做法：给出定义的形式化描述根据经验给出描述文法举例{x|x是长度为偶数的0、1串}S→00S|01S|10S|11S|ε{0m1n|m,n≥1} ——RLS→0S|0A A→1A|1{0n1n|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→ε例2-7：{w|w为十进制数}R→N|N.DN→1|2|3|4|5|6|7|8|9N→N0|N1|N2|N3|N4|N5|N6|N7|N8|N9D→1|2|3|4|5|6|7|8|9D→0D|1D|2D|3D|4D|5D|6D|7D|8D|9DD→0|0.D|N.0|0.0无用产生式与无用符号E→T|E+T|E-TT→F|T*F|T/FF→(E)|idE→E|H+TT→FH|TQ+PF|EQFM

→(E)|id单一产生式、派生不出终极符号行(H、Q、P)、从开始符号无法派生出来(M)文法构造小结明确描述对象──语言合法的语言结构确定基本符号集VT引入非终结符各种句子结构定义句子的组成规则BNF范式或产生式值得注意的问题文法描述描述句子的组成规则，不涉及语义文法正确不能保证语义正确（例）明确目标要描述语言的结构确认基本符号集合理引入非终结符（语义明确）本章小结：几个基本概念文法是语言的一种有穷描述，它严格、准确、简洁。文法的形式定义句型、句子、语言文法的分类ＣＦＧ的语法树习题1)给定文法如下：E→T|E+T|E-TT→F|T*F|T/FF→(E)|id画出表达式id*(id+id)+id的分析树2)判断上题的文法属于哪个类型的文法？为什么？上次课主要内容正规式转换成正规文法对“|”、“*”、“+”、连接的替换正规文法到正规定义式的转换代入（减少语法变量）、递归状态转换图——FAA→aBA→aA→rB,B→

sBABaAaAsrB上次课主要内容整数识别的状态转移图据状态转移图设计与实现词法分析程序词法分析器的自动生成器简介第4章

自顶向下的语法分析语法分析文法的改造问题自顶向下(TopDown)的分析推导(Derivation)语法分析方法语法分析方法 递归子程序法自顶向下 预测分析法(LL(1))

算符优先分析法自底向上

LR(0)、SLR(1)[LR(1)、LALR]

TopDownBottomUp文法产生语言自动机识别语言4.1语法分析的功能检查由扫描器输出的单词符号序列是否符合该语言的文法——句子，并分析出组成此句子的语法成分扫描器分析器语义处理单词符号语法树源程序分析器的输入：Token序列分析器的输出语法树出错处理:定位、续编译4.2自顶向下分析面临的问题与CFG的改造一、自顶向下的分析从文法的开始符号出发，寻求所给的输入符号串的最左推导从树根S开始，构造所给输入符号串的语法树例：G为：S→xAyA→**|*，输入串：x**yS

xAy

x**ySxAy**二、重要概念回顾推导:αＡβ

αγβ(依据：Ａ→γ)最左(Left-most)推导——最左分析左句型最左推导对应最右归约最右(Right-most)推导——最右分析规范推导、规范句型（右句型）最右推导对应最左归约（规范归约）二义性(先天二义性语言、二义性文法)三、重要问题——虚假匹配

x*y发现不匹配,需要回退SxAy*SxAy**S输入串x**yS→xAyA→**|*S

xAy

x**y匹配成功

xAy三、重要问题——回溯SSxAy*SxAy**x**yS

xAy

x**y匹配成功x**y发现不匹配,需要回退

xAy

x*y三、重要问题——二义性对同一句子存在两棵语法分析树，哪个是对的？影响句子分析！EE*EidEE+ididEE+EEEid*idid三、重要问题——左递归问题例：文法S→Say|*与它的句子*ayay*ayayS

*不对！S

Say

Sayay

Sayayay……

Sayay……ayay一个无限循环！三、重要问题——左递归问题例简单算术表达式的文法——左递归E→E+T|E-T|T|-ET→T*F|T/F|FF→E↑P|PP→(E)|id|const|FUN(L)FUN→abs|sin|cos|ln|log|exp|sqrtL→E|E,LVN＝{E,T,F,P,FUN,L｝VT＝{id,const,+,-,*,/,(,),\,,abs,sin,cos,log,ln,exp,sqrt}S＝E四、消除二义性例：简单算术表达式的文法二义性文法E→E+E|E-E|E*E|E/E|(E)|id非二义性文法E→E+T|E-T|TT→T*F|T/F|FF→(E)|id改造方法：使文法含有更多的信息，引入语法变量四、消除二义性再例：If语句S→ifEthenSS→ifEthenSelseSS→other设执行下列语句前b=0,Ifa≠0thenifa>0thenb=1elseb=-1当a=1时,b=1;当a=-1时，b=-1Ifa≠0thenifa>0thenb=1elseb=-1当a=1时,b=1;当a=-1时，b=0一个句子有两棵不同的语法树

S S E E S S Ifa≠0thenifa>0thenb=1elseb=-1 S S E E S S Ifa≠0thenifa>0thenb=1elseb=-1四、消除二义性1.重写文法S→U|MU→ifEthenSU→ifEthenMelseUM→ifEthenMelseM|other2.设置一个规则——实现“就近”、“最长”匹配原则改造1改造2S→TS|CSC→ifEthenT→CSelseC—ConditionT—Else每个else与前面最近的没有配对的then配对，即出现在then和else之间的语句必须是配对的按照“改造1”构造的语法树

S U S M E E M MIfa≠0thenifa>0thenb=1elseb=-1M→ifEthenMelseM|other按照“改造2”构造的语法树

S S

T(最长) C C E E S SIfa≠0thenifa>0thenb=1elseb=-1S→TS|CSC→ifEthenT→CSelse按照“改造2”构造的语法树

S T

S(非最长) C C E E S SIfa≠0thenifa>0thenb=1elseb=-1S→TS|CSC→ifEthenT→CSelse四、消除二义性

S S S

T(最长) T(最长) S C C C CifEthenifEthenSelseifEthenSelseifEthenSS→TS|CSC→ifEthenT→CSelse五、消除左递归无法根据左递归文法进行自顶向下的分析

Aa1a2……ai……an直接左递归A

Aα 当前变量 输入指针

(栈顶、最左变量)间接左递归 A

+Aα左递归的消除方法将A→Aα|β替换为A→βA′和A′→αA′｜ε例：表达式文法直接左递归的消除E→E+T｜TT→T*F｜FF→(E)｜idE→TE’E’→+TE’|εT→FT’T’→*FT’｜εF→(E)｜id例：间接左递归的消除S→Ac|c A→Bb|b B→Sa|a将B的定义代入A产生式得：A→Sab|ab|b将A的定义代入S产生式得:S→Sabc|abc|bc|c消除直接左递归： S→abcS’|bcS’|cS’

S’→abcS’|ε删除“多余的”产生式：A→Sab|ab|b和B→Sa|a结果： S→abcS’|bcS’|cS’

S’→abcS’|ε 消除左递归的一般方法用产生式组A

β1B|β2B

|…|βnBB

α1B|α2B

|…|αnB|ε替换产生式组A→Aα1|Aα2|…|Aαn|β1|β2|…|βm

其中：B为新变量，相当于A’消除左递归的算法见P70的算法为非终结符编号，再采用代入法将间接左递归变为直接左递归，消除直接左递归上次课主要内容自顶向下的分析推导（派生）：自顶向下构造语法分析树待处理的问题虚假匹配——回溯二义性文法S→TS|CSC→ifEthenT→CSelseS→U|MU→ifEthenSU→ifEthenMelseUM→ifEthenMelseM|other上次课主要内容消除左递归A→Aα1|Aα2|…|Aαn|β1|β2|…|βm

的等价产生式组A

β1B|β2B

|…|βnBB

α1B|α2B

|…|αnB|ε其中：B为新变量，相当于A’提取左因子六、提取左因子例：if语句的原始文法S→ifEthenS

|ifEthenSelseS|other遇到if时难以判断用哪一个产生式进行匹配（推导）存在左因子ifEthenS提取作因子：S→ifEthenSS’|otherS'→ε|elseS左因子提取方法将形如A→αβ1|αβ2|…|αβn|γ1|γ2|…|γm的规则改写为A→αA'|γ1|γ2|…|γm和A'→β1|β2|…|βn结果：S→ifEthenSS’|otherS'→ε|elseSS→TS|CS|otherC→ifEthenT→CSelse七、CFG的使用限制没有一种方法能够有效地分析所有上下文无关文法存在无法处理的２型文法(CFG)每种方法能够处理一部分上下文无关文法每种方法都有适用范围八、常用文法与分析方法LL文法和LR文法都是CFG的子集(无二义性)可用不同的文法来描述同一语言对于不同的文法，可用不同的分析方法LL文法──递归下降分析法、预测分析法多用于编译的手工实现LR文法──LR分析法多用于编译的自动生成4.3自顶向下的分析方法基本思想寻找输入符号串的最左推导试图根据当前输入单词确定使用哪个产生式基本过程从根开始，按与最左推导相对应的顺序，构造输入符号串(Token)的语法分析树例符号串id+id*id的分析E→TE’E’→+TE’｜εT→FT’T’→*FT’｜εF→(E)｜idE→E+T｜TT→T*F｜FF→(E)｜id按照最左推导过程，构造语法树id+id*id

的最左推导与语法树的生成对应ＥＴＥ’ＦＴ’Ｔ＋Ｅ’idεＦＴ’idεＦ＊Ｔ’idε1、E→TE’2、T→FT'3、F→id4、T'→ε5、E'→+TE’6、T→FT’7、F→id8、T'→*FT’9、F→id10、T'→ε11、E'→εid+id*id的最左推导再现E

TE’ E→TE’

FT’E’ T→FT’

idT’E’ F→id

idE’ T’→ε

id+TE’ E’→+TE’

id+FT’E’ T→FT’

id+idT’E’ F→id

id+id*FT’E’ T’→*FT’

id+id*idT’E’ F→id

id+id*idE’ T’→ε

id+id*id E’→ε候选式的确定与回溯(Backtracking)给定文法S→cAd A→ab|e?句子ced是该文法定义语言的句子ec A dS候选式的确定与回溯(Backtracking)给定文法S→cAd A→ab|e?句子cad是该文法定义语言的句子

c A dSba候选式的确定与回溯(Backtracking)给定文法S→cAd A→ab|a?句子cad是该文法定义语言的句子c A dSbaac A dS候选式的确定与回溯(Backtracking)当要进行某个语法变量的推导时，希望能够根据当前符号确定候选式。如果有几个候选式（右部）左端第一个符号相同，则分析程序无法根据当前输入符号选择产生式，只能试探希望：寻找一类文法，我们可以方便地根据当前输入符合确定正确的候选式4.3.1FIRST和FOLLOW集对于

α∈(VT∪VN)*定义:α的首符号集FIRST(α)={a|α

*a…，a∈VT*}对于

A∈VN定义A的后续符号集：

FOLLOW(A)={a|S

*…Aa…，a∈VT}求FIRST(X)的算法1)对

x∈VT，FIRST(x)={x}；2)对

X∈VN，取FIRST(X)的初值：

{a|X→a…∈P}； X→ε

PFIRST(X)= {a|X→a…∈P}∪{ε}； X→ε∈P3)对

X∈VN，重复如下过程，直到所有FIRST集不变若X→Y…∈P

，且Y∈VN，则FIRST(X)=FIRST(X)∪(FIRST(Y)-{ε})；若X→Y1…Yn∈P，且Y1...Yi-1

*ε，则对k=1到i-1:FIRST(X)=FIRST(X)∪(FIRST(Yk)-{ε})；若Y1...Yn

*ε，则FIRST(X)=FIRST(X)∪{ε}