《编译原理课件.pptx》由会员分享，可在线阅读，更多相关《编译原理课件.pptx（122页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 第一讲 引论u课程信息u编译程序概述u高级语言的语法描述第1页/共122页CompilerPrinciples21.1.课程信息一、课程名称：编译原理基本内容是介绍编译程序构造的基本原理、方法和技术，包括词法分析、语法分析、语义分析与中间代码产生、代码优化及目标代码产生等。简言之，就是介绍如何将源程序翻译成目标代码程序。第2页/共122页CompilerPrinciples3二、课程性质：专业基础课，必修编译程序（器）出现于上世纪50年代后期（第一个高级语言1958年）60年代70年代是研究高峰期60年代中期开始在高校中开设课程80年代开始作为计算机科学与技术专业的必修基础课程第3页/共12
2、2页CompilerPrinciples4第4页/共122页CompilerPrinciples5三、课程特点：充分体现了计算学科中抽象、理论和设计三个学科形态该课程涉及多门课程的内容综合运用，涉及面广，涉及面广，内容庞杂，学习艰难内容庞杂，学习艰难程序设计语言、计算机体系结构、语言理论及算法等数据结构、离散数学该课程涉及的原理、方法和技术具有十分普遍的意义每一个计算机科学与技术工作者的职业生涯中反复用到，“享用一辈子”这儿接受的训练很难在其他地方获得，如：抽象与形式化方法、局部与全局优化方法、构造技术、证明方法等第5页/共122页CompilerPrinciples6四、学习该课程的意义编译
3、程序是计算机系统不可缺少的重要组成部分对程序设计语言的设计与实现能有更深刻的理解对程序设计语言有关理论有所了解从宏观上把握程序设计语言掌握了编译原理后，就不能再说：“某语言未学过，所以不会”有助于快速理解、定位和解决程序调试与运行中出现的问题第6页/共122页CompilerPrinciples7编译方法与技术有着广泛应用安全技术、程序理解、软件逆向工程、应用软件与软件工具开发、软件测试与验证等编译课程蕴含着计算学科中解决问题的思路、抽象和方法，这些与高等数学一样，使你“享用一辈子”课程所涉及的内容至今非常活跃自然语言的翻译软件移植网络安全形式化方法形式语义学等第7页/共122页Compile
4、rPrinciples8 鉴于以上所述，作为计算机科学与技术专业的学生必须学习和掌握编译原理这门课程，当然由于其综合性、处理问题的复杂性等，学习起来有一定难度，这就需要艰苦奋斗的精神和良好的学习方法第8页/共122页CompilerPrinciples9五、学习方法编译程序的构造是一个庞大而复杂的系统工程，无论是概念还是理论、方法，对初学者来说许多都是新的，学习起来会感到困难大一些，这一点必须有充分认识，为此建议学习方法上注意以下几点：第9页/共122页CompilerPrinciples101.课前预习，课堂认真听讲，课后复习加深理解，特别要经常有意识地将前后内容联系起来融会贯通。因为编译程
5、序是一个庞大的程序系统，讲解过程必须“分而治之”（这也是人们处理复杂问题的基本方法），这就要求大家在学习过程中，始终以处理过程为主线，把前后联系起来考虑。第10页/共122页CompilerPrinciples112.理论联系实际亲自动手，构造一个演示性编译程序，至少要完成扫描器和语法分析器，以及语法制导翻译产生中间代码（课程设计）3.认真完成作业，进一步巩固并加深理解所学知识4.特别要下功夫认真学习如何从实际问题进行抽象并形式化，最终建立实际问题的模型（上升为理性认识），并借助模型进一步设计实现，这将对你能力的提高大有益处第11页/共122页CompilerPrinciples12六、教材程
6、序设计语言编译原理（第3版）国防工业出版社 陈火旺等1.内容详实丰富，理论与技术相结合2.较为全面介绍了编译程序构造的基本原理、方法与技术3.厚度适中4.大多数院校一直采用，硕士入学考试参考书5.所谓教材，实为第一参考书而已第12页/共122页CompilerPrinciples13 七、参考书目1.编译原理第2版 赵建华等译，Compilers:Principles,Techniques,&Ravi 2009；2.编译原理课程设计 王雷等著，机械工业出版社，2005；八、期末总评平时成绩：10%课程设计：20%期终考试：70%第13页/共122页CompilerPrinciples14第14
7、页/共122页CompilerPrinciples152.2.编译程序概述一、翻译程序（Translator）能够把一种语言程序（称为源语言程序）转换成逻辑上等价的逻辑上等价的另一种语言程序（称为目标语言程序）的程序第15页/共122页CompilerPrinciples16任何非机器语言程序都需要翻译程序翻译程序的工作就是进行等价变换（映射）两个程序逻辑上等价是指对相同输入得到相同的输出翻译程序解释程序汇编程序编译程序第16页/共122页CompilerPrinciples171.汇编程序(Assembler)把汇编语言程序转变为机器语言程序的翻译程序2.解释程序(Interpreter)把
8、源程序作为输入接收，边解释边执行的翻译程序源程序数据解释程序结果第17页/共122页CompilerPrinciples183.编译程序将高级语言程序转变为低级语言程序的翻译程序源 程 序编译程 序目 标程 序第18页/共122页CompilerPrinciples19第19页/共122页CompilerPrinciples20编译程序又可根据用途和侧重点的不同，进一步分类为：诊断编译程序(Diagnostic Compiler)专门用于帮助程序开发和调试的编译程序 优化编译程序(Optimizing Compiler)着重于提高目标代码效率的编译程序 交叉编译程序(Cross Compile
9、r)能够产生不同于其宿主机机器代码的编译程序 可变目标编译程序(Retargetable complier)无须重写与机器无关部分就能改变目标机的 编译程序第20页/共122页CompilerPrinciples21二、与编译程序相关的程序 本讲义只介绍编译程序（器）构造的基本原理、方法与技术，但在一个完整的语言开发（或称程序设计）环境中，除了编译器这一主要工具外，还需要其他一些工具，如编辑器、连接器、装入程序等。现代计算机系统常将这些相互独立的程序设计工具集成起来，构成一个集成化的程序开发环境，以提高程序设计效率和程序的质量。如Turbo C、Visual C+等语言环境都是集成化的程序设计
10、环境。而Ada语言的集成环境是这方面的典型代表。第21页/共122页CompilerPrinciples22如Ada语言的集成环境是一个分层的程序开发环境编译程序MAPSE编辑程序连接程序宿主机OSAPSE工具界面用户界面KAPSE调试程序配置管理程序命令解释程序其他工具第22页/共122页CompilerPrinciples23 这儿要强调的是：尽管本课程只介绍编译的基本理论、方法和技术，但这些基本理论、方法与技术对其他工具的构造同样起作用！第23页/共122页CompilerPrinciples241.编辑器(Editor)完成源程序输入、编辑并产生标准文件（如ASCII文件）的程序。近来
11、已与编译器和其他程序捆绑进一个交互开发环境IDE中尽管这样的编辑器仍生成标准文件，但会转向正被讨论的程序设计语言的格式或结构（称为基于结构的），且已包含了编译器的某些操作；因此在程序编写时而不是编译时就可得知错误，甚至也可调用编译器第24页/共122页CompilerPrinciples252.预处理程序(Preprocessor)在真正翻译开始之前产生编译程序的输入的程序处理宏及注释：宏是被经常使用的较长结构的缩写处理文件包含：把头文件包含到程序正文中（如C的文件包含include）“理解”预处理器：把现代控制流和数据结构机制添加到比较老式的语言中语言扩充：通过大量的内部宏定义来增强语言的能
12、力，如Equel语言是一种嵌套在C语言中的数据库查询语言第25页/共122页CompilerPrinciples263.连接程序(Linker)又称为连接编辑器。将分别在不同的目标文件中编译（或汇编）的代码、所用标准库函数的代码以及操作系统提供的资源（如存储分配程序及输入/输出设备）收集到一个可直接执行的文件中的程序4.装配程序(Loader)完成程序的装入和连接编辑两项功能。装入过程包括读入可重定位机器代码、修改可重定位地址、并将修改后的指令和数据放到内存的适当位置。装入程序使得可执行代码更加灵活第26页/共122页CompilerPrinciples275.调试程序(Debugger)可在
13、被编译了的程序中判定执行错误的程序它经常与编译程序一起放在IDE中运行一个带有调试程序的程序与直接执行不同，这是因为调试程序保存着所有的或大多数源代码信息，它可以在预先指定的位置（断点BreakPoint）暂停执行，并提供有关信息（已调用的函数、变量名的当前值等）第27页/共122页CompilerPrinciples286.其他有关的还有描述器(Profiler)执行中搜集目标程序行为统计的程序项目管理程序(Project Manager)如Unix系统中的SCCS（源代码控制系统）和RCS（修正控制系统）和汇编程序等综上所述可给出一个“语言处理系统”的图示：第28页/共122页Compil
14、erPrinciples29我们这个课只介绍编译程序这一部分第29页/共122页CompilerPrinciples30三、编译过程与编译程序结构 1.编译过程：输入 输出（高级语言源程序）（低级语言目标程序）编译程序工作过程如下：l识别出一个个的单词l分析句子的语法结构l分析句子的语义并进行初步翻译l对初步翻译进行优化l整理出目标程序对以上过程进一步整理可得如下编译程序结构总框：编译程序第30页/共122页CompilerPrinciples312.编译程序总框：词法分析器语法分析器语义分析与中间代码产生器优化器目标代码生成器单词符号语法单位中间代码中间代码出错处理表格管理源程序目标代码第3
15、1页/共122页CompilerPrinciples323.五个阶段简介l第一阶段：词法分析依据语言构词规则，识别出一个个单词（符号）单词种类l保留字：for if whilel算符：l界符：，；（）l标识符：a1 a2 pil常数：9 1024 4.8 6E6无穷性有穷性思考：识别有穷集合 VS 识别无穷集合 第32页/共122页CompilerPrinciples33 词法分析工作由词法分析器（或称扫描器）完成。扫描器输出为等长度的单词符号（二元式）流。例：Position=initial+rate*60词法分析（扫描器）保留字表(06,Position)(11,)(06,initial)
16、(12,)(06,rate)(13,)(07,60的二进制)第33页/共122页CompilerPrinciples34l第二阶段：语法分析依据语言的语法规则，把扫描器提供的单词符号串分解成各种语法单位（范畴），如“短语”、“子句”、“句子”乃至“程序”。同时进行语法检查，以确定输入串是否正确，该工作是由语法分析器完成的。如：Position=initial+rate*60 是一个“赋值表达式”（C语言中）Position =表达式表达式表达式+表达式标识符表达式*表达式initial标识符常数rate60标识符第34页/共122页CompilerPrinciples35l第三阶段：语义分析与
17、中间代码产生针对各类不同的语法范畴，按语言的语义规则进行语义分析和初步翻译工作，产生某种中间语言形式的中间代码（即一种结构简单，含义明确的记号系统）。该阶段工作通常包括两个方面的工作：对每种语法范畴进行静态语义检查，包括：l变量是否定义过l类型是否正确l是否用了0作除数 第35页/共122页CompilerPrinciples36l将语法范畴翻译成某种形式的中间代码，如四元式：OpARG1ARG2Resultrate60T1initialT1T2=T2Position第36页/共122页CompilerPrinciples37l第四阶段：优化对前阶段产生的中间代码进行加工变换，以期在最后阶段能
18、产生出高效（节省时、空）的目标代码，这一任务是由优化器来完成的l根 据 优 化 的 范 围 不 同，可 分 为：局部优化，循环优化和全局优化l一个循环优化的例子：第37页/共122页CompilerPrinciples38 1K IM J100K JN 10KT1 1K IT1M J100K 10KT2 M10M JT2N N10N K1K K1K 循环 For(k=1;k=100;k+)M=I+10*k;N=J+10*k;For(k=1;k=100;k+)M=I+10*k;N=J+10*k;优化前用了两个临时工作单元(T1,T2),优化后没有用临时单元优化前循环体中要做300次加、200次乘
19、，优化后循环体内只做300次加第38页/共122页CompilerPrinciples39l第五阶段：目标代码生成把中间代码翻译成目标代码l显然这阶段要依赖于硬体系统结构和指令系统l涉及存贮分配、寄存器调度这一阶段工作是由代码生成器完成的说明：以上各阶段（或称工序）并不是截然分开 的，尤其编译程序结构十分复杂、体积相当庞大，所以有时人们把几个阶段的工作有机地组合在一起、穿插进行，构成遍。第39页/共122页CompilerPrinciples40遍（Pass）：对源程序或源程序的中间代码从头到尾扫描一次并做相应处理加工分遍的好处是结构清晰、节省内存（每遍都从外存获取前一遍的结果作为开始，工作结
20、果仍记入外存，每遍几乎可使用全部内存）分不分遍、如何分遍要视具体情况计算机内存容量、源语言的繁简、从事编译程序设计人员的情况等第40页/共122页CompilerPrinciples41如某PL/0编译程序的结构词法分析程序语法语义分析程序代码生成程序PL/0PL/0源程序目标程序表格管理程序出错处理程序第41页/共122页CompilerPrinciples42 4.前端与后端：概念上讲，编译程序的五个阶段可进一步划分为前端和后端：前端：主要由与源语言有关而与目标机无关的部分组成，包括词法分析、语法分析、语义分析和中间代码产生。代码优化一般也包含在前端。后端：主要由与目标机有关的部分组成，包
21、括目标代码生成和与目标机有关的优化等。第42页/共122页CompilerPrinciples43源程序词法分析语法分析语义分析和中间代码产生中间语言中间代码优化目标代码生成目标代码优化目标语言前端后端第43页/共122页CompilerPrinciples44l 划分前端和后端，就可以仅改写后端而生成不同目标机上的目标程序，当然也可考虑对不同语言仅稍加改变前端而产生相同的中间代码，经同一后端生成相同目标机的目标代码。就目前来说，针对相同中间代码适应不同目标机的工作较多，如Ada语言的APSE(Ada程序设计环境)中使用的Diana中间代码，Java语言定义的虚拟机代码Bytecode中间语言
22、，都是定义良好的中间语言。第44页/共122页CompilerPrinciples45Java的传统环境Java源程序(.java)编译环境Java编译器Java字节码(.class)Java 字节码（本地或网络传输）运行环境类加载程序字节码验证Java类库Java解释器即时编译器Java虚拟机硬件第45页/共122页CompilerPrinciples465.表格与表格管理表格记录源程序中的各类有用信息名字、函数、标号、过程、数值等每个阶段的工作都要与表格打交道：查、填、改等表格的结构与处理方法：统一的大表与分类的小表统一大表名字栏为主栏（关键字栏），信息栏又分成若干子栏种属、类型等NAME
23、INFORMATION第46页/共122页CompilerPrinciples47分类小表：每类一张表，如：符号名表(SNT)常数表(CT)3.141592648X哑元 实型A数组 整型 第47页/共122页CompilerPrinciples48DO编号(03)L1入口地址Swap二目子程序 入口地址入口表(ENT)标号表(LBT)基本字表 (KWT)第48页/共122页CompilerPrinciples496.出错处理：这是编译程序的又一重要组成部分，因为编译的各个阶段都有可能发现源程序中的错误。一旦发现这样或那样的错误，就应把错误的性质及位置报告给用户，并且使编译能继续下去。思考：l如
24、何准确地报告错误l如何从错误中恢复过来第49页/共122页CompilerPrinciples50四、编译程序的构造过程1.需求分析，确定语言文本(1)确定语言的种类：按语言范型分类，当今大多数程序语言可分为四类：过 程 式(强 制 式 语 言)：命 令 驱 动，面 向 语 句，如 FORTRAN、PASCAL、Ada及C等函数式(应用式)语言：功能驱动，面向函数，如LISP、SNOBOL及ML等逻辑式(基于规则的)语言：依据条件进行逻辑推演，如Prolog等OO语言：支持封装性、继承性、多态性及动态聚束等，以对象为运行单位，如Smalltalk、Java、C+等第50页/共122页Compi
25、lerPrinciples51通过用户提供的应用范围，决定采用何种语言。例如：偏重于科学计算的则选用Fortran；偏重于符号处理的则选用Lisp或Snobol；偏重于事务处理的则选用Cobol或数据库管理语言；第51页/共122页CompilerPrinciples52(2)深刻理解语言的结构、语法及语义 这就是说不仅仅是用程序设计语言编几个程序的问题，而是要在语法和语义方面下一些功夫。具体说来有以下几个方面：程序语言的定义：任何程序语言都是某个确定的字符集上的符号按照一定规则组成的有穷序列。这里所谓的规则是从两个方面来谈的：语法规则：用于形成和产生一个正确的程序的 一组规则。语义规则：用于
26、定义程序意义的一组规则。第52页/共122页CompilerPrinciples53例如：从语法的角度看，标识符和名字是一个东西，都是以字母开头的字母数字串；但从语义的角度看，标识符是一个没有任何意义的字符序列，而名字却有确定的意义和属性，而且具有一定的作用域和定义域，即有局部和全部之分。又如：程序从语法角度看，是一些语法范畴构成的如下层次结构：第53页/共122页CompilerPrinciples54程序分程序或子程序（过程、函数等）语句表达式数据引用算符函数调用而从语义的角度来说，程序是描述一定的数据结构及其处理过程。第54页/共122页CompilerPrinciples55程序结构：
27、现代高级语言程序通常由若干子程序段（过程、函数等）构成，许多语言还引入了类、程序包等更高级的结构。例如，Fortran、C程序是块结构的；Pascal程序是过程嵌套的；Algol既有分程序嵌套，又有过程嵌套；Java与C+是面向对象的，它们很重要的方面是类和继承的概念，同时支持多态性和动态聚束等特性；而在Ada中引入了程序包，它可以把数据和操作代码封装在一起，支持数据抽象。（详见教材 P15-18）第55页/共122页CompilerPrinciples56语言的基本成分：包括数据类型、表达式、语句、过程或函数等，这些在学习语言课时都已经学过了，但从编译的角度出发，应如何了解这些基本成分呢？初
28、等数据类型：牵扯到存储空间的问题；结构数据类型：牵扯到下标、维数、存放方式、分配时间-动态与静态等；表达式：牵扯到运算分量、运算符、形成规则、运算顺序等；语句：顺序、控制、循环等；过程与参数传递：传地址、传值、传名、得结果 等；存储管理：静态存储分配、动态存储分配；第56页/共122页CompilerPrinciples572.由程序设计环境确定编译程序构造的方式和方法最早是直接使用机器语言或汇编语言现在一般使用高级语言Pascal或C语言好处：编译方式还是解释方式便于阅读、理解和移植提高程序设计效率易于查错和修改第57页/共122页CompilerPrinciples58 任何一个编译程序至
29、少要涉及三种语言：源语言（S）、目标语言（T）和编译程序实现语言（I），可用如下T型图来表示三者之间的关系：STI第58页/共122页CompilerPrinciples59Ada语言A代码Ada语言A代码CCA代码A代码A代码用C语言编写Ada编译程序 如若A机上已经有了一个用A机器语言（称A代码）实现的C语言编译程序，则可用C语言作为工具编写Ada语言的编译程序。这样Ada语言的编译程序经过C语言编译程序编译后就可得到A代码的Ada语言编译程序。可图示如下：第59页/共122页CompilerPrinciples60l现在常用构造编译程序的方式除高级语言实现外，经常还用：自展（自编译）：类
30、似于滚雪球。先确定一个非常简单的核心L0，用低级语言写 出 其 编 译 程 序 C0。再 把 L0扩 充 为 L1，并用L0来编写L1的编译程序。如此逐渐扩展下去，可得到一个系统编程语言族：而Lk便是我们要编译的语言，其编译程序Ck可用Lk-1编写。这种滚雪球式的自展方法可大大减少开发工作量。第60页/共122页CompilerPrinciples61交叉编译：在机器A上产生机器B的目标代码，这种编译程序称为交叉编译。这儿A称宿主机，B称为目标机。这种情况一般是宿主机上有丰富的工具软件，而B机上没有任何高级语言可用。图示为：CB代码CB代码CCB代码B代码A代码第61页/共122页Compil
31、erPrinciples62移植：如果一个程序能比较容易地从一台机器上搬到另一台机器上运行，则称其为可移植的，移植一个程序的工作量要远小于开发它的工作量才有意义。显然一个编译程序要可移植，则其前端与后端的界面要清晰、简单，这样仅需改写后端即可。改写后亦可通过交叉编译的方法得到。第62页/共122页CompilerPrinciples63编译程序生成器：根据语言要求、设计实现的算法，能自动产生编译程序的工具软件。可图示为：第63页/共122页CompilerPrinciples643.确定编译方法：本课程要介绍若干方法，但不可能全采用，只能根据语言特点采用其中一种或二种4.总体设计：分不分遍、分
32、几遍、前端与后端接口并画出总框5.详细设计：进一步细划总框6.实现及调试：采用何种方式实现、分调与连调等第64页/共122页CompilerPrinciples65本节目的：为语言的语法描述寻求形式化工具 工具就是对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）形式化工具就是将形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则是以什麽符号串能出现的方式来陈述。3.3.高级语言的语法描述第65页/共122页CompilerPrinciples66本节主要内容预备知识上下文无关文法及其语言的形式定义文法的等价性语法树及文法二义性文法的类型语法分析的一些思考第66页
33、/共122页CompilerPrinciples67一、预备知识1.文法的直观概念 当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷多个句子的语言来讲，存在着如何给出它有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语。例如：第67页/共122页CompilerPrinciples68 “我是大学生”是汉语的一个句子对该句子我们可以通过下列一组规则描述：句子=主语谓语 主语=代词名词 代
34、词=我你他 名词=王明大学生工人英语 谓语=动词直接宾语 动词=是学习 直接宾语=代词名词有了这组规则以后，可按如下方式导出句子：先找=左端的带有句子的规则，并将它用 =右端的符号串代替，于是表示成：第68页/共122页CompilerPrinciples69 句子 主语谓语 然后在得到的串主语谓语中，选取主语或谓语，再用相应规则的=右端代替之。比如，选取了主语，并采用规则主语=代词，那么得到：主语谓语 代词谓语 依此类推，句子“我是大学生”的全部导出过程是：句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生 第69页/共122页CompilerPrincip
35、les70 “我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据。换句话说，这些规则看成是一种元语言，用它描述汉语，仅仅涉及汉语句子的结构描述。这里“”读作“导出”或“派生出”。而“:=”（通常又简记为“”）读作“定义为”或“由组成”，而每一条规则又称作是产生式或重写式。这样的一种描述形式就称作是BNF（Backus-Naur Form）。第70页/共122页CompilerPrinciples71例：赋值表达式可描述为 =|a1|b123|salary|stu_age 18|123|4.5|+|-|*|/第71页/共1
36、22页CompilerPrinciples722.语言概述语言是由句子组成的集合。汉语-所有符合汉语语法的句子的全体。英语-所有符合英语语法的句子的全体。程序设计语言-所有符合该语言语法的程序的全体。每个句子构成的规则研究语言 每个句子的含义 每个句子和使用者的关系第72页/共122页CompilerPrinciples73研究程序设计语言 每个程序构成的规则 每个程序的含义 每个程序和使用者的关系语言研究的三个方面:语法(Syntax)-表示构成语言句子的各个记号之 间的组合规则 语义(Semantics)-表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用(Pragmat
37、ics)-表示在各个记号所出现的行 为中，它们的来源、使用和影响。第73页/共122页CompilerPrinciples74 每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。第74页/共122页CompilerPrinciples75 如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个
38、数学系统。该数学系统称为文法。“形式”是指这样的事实：语言的所有规则描述什麽符号串以什么方式出现。形式语言理论是对符号串集合的表示法、结构及其特性的研究，是程序设计语言语法分析研究的基础。第75页/共122页CompilerPrinciples763.有关定义和记号回顾符号：可以相互区别的记号（元素）。字母表：符号（元素）的非空有穷集合。符号串(字)：由字母表 中的符号组成的任何有穷序列称为该字母表上的符号串。空字(没有符号的符号串)是 上的符号串；若x是 上的符号串,a是 的元素,则xa是 上 的符号串；y是 上的符号串,当且仅当它可以由和 导出。例如：=a,b =a,b ,a,b,aa,a
39、b,aabba ,a,b,aa,ab,aabba都是 上的符号串第76页/共122页CompilerPrinciples77符号串s的前缀：符号串s的任何首部。如:、b、ba、都是符号串banana的前缀.符号串s的后缀：符号串s的任何尾部。如:、a、na、都是符号串banana的后缀.符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串.如:ana是符号串banana的一个子串.符号串s的真前缀：xs且x的任何前缀x。s的真后缀，真子串可以类似地定义。第77页/共122页CompilerPrinciples78符号串的运算：符号串的长度：符号串中符号的个数.符号串s 的长度 记为|s|。
40、的长度为0连接：符号串x x、y y的连接,是把y y的符号写在x x的符号 之后得到的符号串xy xy 如 x=ab,y=cd x=ab,y=cd 则 xy=abcd xy=abcd 又如a=a a=a 方幂：符号串自身连接n n次得到的符号串 a an n 定义为 aaaaaa aa n n个a a a a0 0=,a=,a1 1=a,a=a,a2 2=aa=aa 第78页/共122页CompilerPrinciples79符号串集合：若集合A中所有元素都是某字母表 上的符号串，则称A为字母表 上的符号串集合。符号串集合A和B的乘积：AB=xy|xxy|x A A且y y B B 若 集合
41、A=ab,cdeab,cde B=0,10,1 则 AB=ab1,ab0,cde0,cde1ab1,ab0,cde0,cde1 的闭包：上的一切符号串（包括）组成的集合，记为 *。的正闭包：上的除外的所有符号串组成的集合，记为+。第79页/共122页CompilerPrinciples80例：=a,b=a,b *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,=a,b,aa,ab,ba,bb,aaa,aab,第80页/共122页CompilerPrinciples81语言：由句子构成的集
42、合。换言之,字母表上的一个语言是上的一些符号串的集合 (字母表上的每个语言是*的一个子集)。例如：字母表=a,b,*=,a,b,aa,ab,ba,bb,aaa,aab,集合ab,aabb,aaabbb,anbn,或表示为w|w*且w=anbn,n1为字母表上的一个语言。集合a,aa,aaa,或表示为w|w*且w=an,n1 为字母表上的一个语言。是一个语言，即 也是一个语言。第81页/共122页CompilerPrinciples82二、上下文无关文法及其语言的形式定义1.如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示；如果语言是无穷的，找出语言的有穷表示
43、。语言的有穷表示有两个途径：生成方式生成方式：语言中的每个句子可以用严格定义的规则来构造。识别方式识别方式：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要麽能停止并回答“不是”，要麽永远继续下去。第82页/共122页CompilerPrinciples83 文法是从生成方式描述语言的，而自动机则是从识别的角度来描述语言的。本节仅介绍有关文法的概念。前面关于“我是大学生”及“赋值表达式”的例子中，涉及到如下的概念：l所表示的是一个类概念，通常称作语法范畴或语法变量，如果用一个符号来代替,也称为非终结符(nonterminal)。所有规则中的非终结符
44、构成了一个非空有穷集，记为V VN N。l上述两例中的“句子”及“赋值表达式”显然是最大的语法范畴，也是我们最感兴趣的非终结符，通常称作开始符号，记为S S。l“大学生”、“我”、“是”、“a”、“+”等表示的是一个具体概念，用一个符号来表示，则称为终结符(terminal)。所有这样的符号同样构成了一个非空有穷集，记为V VT T。l我、8等称作产生式(production)。所有产生式的集合显然是有穷的，记为P。这样我们可以将文法抽象为如下的一个数学系统：第83页/共122页CompilerPrinciples842.文法的形式定义一个文法G定义为一个四元式(VN,VT,S,P)其中：VN
45、为非终结符号的非空有穷集；VT为终结符号的非空有穷集，VN VT=；P为产生式的集合；产生式也称重写规则或生成式，形如A，其中：A VN,(VN VT)*。A称为产生式的左部，称作产生式的右部。S称作识别符号或开始符号，S VN 且至少要在一条产生式中作为左部出现。VN VT中的符号统称为文法符号。第84页/共122页CompilerPrinciples85例1 文法G=（VN，VT，S，P）VN=S,VT=0,1 P=S0S1,S01 S为开始符号例2 文法G=（VN，VT，S，P）VN=，VT=a,b,c,x,y,z,0,1,9 P=,a,z,0,9 S=第85页/共122页Compile
46、rPrinciples86文法的写法 .G.G：SaASaAb Aab Aab AaA AaAb A A .GS.GS：SaSSaSb Aab AaA Aab AaAb A A .GSGS：SaSSaSb Aab|aA Aab|aAb|元符号：=|=|习惯表示：大写英文字母：非终结符/集合 字母表中靠前的小写英文字母：终结符 字母表中靠后的小写英文字母：字符串第86页/共122页CompilerPrinciples87上下文无关文法：它所定义的语法范畴是完全独立于这种范畴所能出现的环境。程序设计语言的词：a+b/3 a10)，则记为 v+w，v推导出w，或w归约到v。若有v+w，或v=w，则记
47、为v*w。例：G G：S0S1，S01 S 0S1 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 00S11 000S111 00001111 S+00001111 S*S 00S11*00S11第89页/共122页CompilerPrinciples90(3)最左（最右）推导最左（最右）推导：在推导的任何一步，都是对中的最左（右）非终结符进行替换。最右推导被称为规范推导。也就是说，规范推导具有最右性。规范推导的逆过程称为规范规约。也就是说，规范规约具有最左性。由规范推导所得的句型称为规范句型。第90页/共122页CompilerPrincipl
48、es914.句型、句子句型：有文法G，若S *x，x(V(VN NVVT T)*,则称x是文法G的句型。句子：有文法G，若S *x，且xVVT T*，则称x是文法G的句子。例1 1：G G：S0S1，S01 S 0S1 00S11 000S111 00001111 G的句型:S,0S1,00S11,000S111,00001111 G的句子:00001111,01第91页/共122页CompilerPrinciples92例2：GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|a这个文法都能推导出什么句子？EE+T T+T F+T a+T a+T*F a+
49、F*F a+a*F a+a*a用符号用符号a a，+，*，(和和 )构成的算术表达式构成的算术表达式思考：写出一个不同的文法，同样能够产生这些句子思考：写出一个不同的文法，同样能够产生这些句子第92页/共122页CompilerPrinciples935.语言的定义 由文法G生成的语言记为L(G),它是文法G的所有句子的集合。L(G)=x|S+x,S为开始符号,且x VT*例1 G1 G：S0S1，S01 L(G)=0n1n|n1 例2 2 文法GSGS：（1 1）SaSBESaSBE（2 2）SaBESaBE（3 3）EBBEEBBE（4 4）aBabaBab（5 5）bBbbbBbb（6
50、6）bEbebEbe（7 7）eEeeeEee L（G）=anbnen|n1 这个文法生成什么语言？这个文法与前面见过的文法有什么不同？第93页/共122页CompilerPrinciples94S a S BE (SaSBE)a aBEBE (SaBE)aabEBE(aBab)aabBEE(EBBE)aabbEE（bBbb)aabbeE（bEbe)aabbee（eEee)类似推导可以看出a,b,e在句子中出现的顺序及个数满足L(G)当然要进一步说明：G G生成的每个句子都在L(G)L(G)中 L(G)L(G)中的每个句子确实能被G G生成第94页/共122页CompilerPrinciple