编译原理教案_第1页
编译原理教案_第2页
编译原理教案_第3页
编译原理教案_第4页
编译原理教案_第5页
已阅读5页,还剩42页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、第1章 编译原理概述主要内容:1 编译程序概述 2 编译程序的工作过程与结构 3 编译程序的开发 4 构造编译程序所应掌握的内容 任何一门高级语言都需要有相应的翻译程序将其翻译为机器语言,才能真正在计算机上执行。编译程序是这样的一种翻译程序,它对一个计算机系统来说非常重要。编写编译程序所涉及到的一些原理、技术和方法在计算机相关的各个领域中都会反复用到,具有十分普遍的意义。本章首先介绍编译原理的基本概念及与编译程序相关的一些工具,然后介绍编译的过程以及编译程序的结构、组成以及实现方法,最后对编译的相关理论和方法的应用做了简单介绍。1程序设计语言与翻译程序在计算机系统中,语言分三个层次:机器语言、

2、汇编语言和高级语言。只有机器语言程序可直接在计算机上执行,高级语言和汇编语言编写的程序必须翻译为对应的机器语言程序才能执行。计算机刚出现时,人们用机器语言(Machine Language)编写程序,如”C7 06 0000 0002”,其含义是将2放到一个存储单元中。用机器语言编写程序费时、乏味,开发难度大,周期长,很快就被汇编语言(Assembly Language)代替了。汇编语言以助记符的形式表示指令和地址。如与上述指令等价的汇编代码为:MOV X,2,它不能直接执行,需要汇编程序(Assembler)将其翻译为机器语言程序才能执行。与汇编语言有关的程序有:反汇编程序(disassem

3、bler)是把机器语言程序逆向翻译为汇编语言程序的程序;交叉汇编程序(cross assembler)是把甲计算机上的汇编语言程序翻译为乙计算机上的机器语言程序的程序。汇编语言仍与人类的思维相差甚远,不易阅读和理解,它严格依赖于机器,为一种机器编写的代码在应用于另一种机器时必须完全重写。高级语言的出现缩短了人类思维和计算机语言间的差距,如上述指令用PASCAL语言写为x:=2。编写高级语言程序类似于定义数学公式或书写自然语言,与机器无关。起初人们担心这不可能,或者即使可能,目标代码也会因效率不高而没有多大用处。编译程序(Complier)的出现解除了人们的这种担忧,它能够直接将高级语言(如FO

4、RTRAN、Pascal、C或Java等)程序翻译为对应的低级语言(如汇编语言或机器语言)程序。实际上,除了上述程序之间的翻译之外,同一种机器上的不同语言和不同种机器上的相同或不同语言程序之间都可以进行翻译Error! Reference source not found.给出了常见语言程序之间的翻译模式。把一种语言(称为源语言)书写的程序翻译成另一种语言(称为目标语言)书写的程序统称为翻译程序(Translator),后者与前者在逻辑上等价。高级语言之间也可以相互转换,把用一种高级语言书写的程序转换为另一种高级语言的程序,统称为转换程序(converter)。尽管人类可以借助高级语言与计算机

5、进行交往,但是计算机硬件真正能够识别的只是0、1组成的机器指令序列。实际使用中,高级语言除了通过编译程序将其翻译为机器语言执行外,解释程序也可以把高级语言翻译为机器语言,二者的主要区别是:编译程序先把全部源程序翻译为目标程序,然后再执行;该目标程序可以反复执行;解释程序对源程序逐句地翻译执行,目标代码只能执行一次,若需重新执行,则必须重新解释源程序。编译过程类似笔译,笔译后的结果可以反复阅读,而解释过程则类似于同步翻译,别人说一句,就译一句,翻译的结果没有保存。图1是两个过程的比较。(a)编译过程(b)解释过程图1 编译与解释过程对比2编译程序的发展及分类用高级语言编写程序简单方便,多数程序都

6、可用高级语言编写。在一台计算机中对每一种高级语言,都至少配有一个编译程序。对有些高级语言甚至配置了几个不同性能的编译程序,以实现用户的不同需求。编译程序最早出现在50年代早期,IBM的John Backus带领一个小组开发了FORTRAN语言,编写FORTRAN语言的编译器共用了18人年。与此同时Noam Chomsky开始了自然语言的研究,Chomsky的研究导致了根据语言文法 (grammar) 的难易程度以及识别它们所需的算法来对语言分类。接着人们花费了很大的功夫来研究编译器的自动构造,出现了词法和语法分析的自动生成工具Lex与YACC。在70年代后期和80年代早期,大量的项目都关注于编

7、译器其他部分的生成自动化,其中就包括了代码生成自动化。目前,编译器的发展与复杂的程序设计语言的发展结合在一起,如用于函数语言编译的Hindley-Milner类型检查的统一算法;编译器也已成为基于窗口的交互开发环境(IDE)的一部分;随着多处理机和并行技术、并行语言的发展,将串行程序转换成并行程序的自动并行编译技术正在深入研究之中;另外随着嵌入式应用的迅速增长,推动了交叉编译技术的发展;对系统芯片设计方法和关键EDA技术的研究,也带动了专用语言VHDL等及其编译技术的不断深化。根据不同的用途和侧重,编译程序可分为很多类。专门用于帮助程序开发和调试的编译程序称为诊断编译程序(Diagnostic

8、 Complier)。着重于提高目标代码效率的编译程序叫优化编译程序(Optimizing Complier)。运行编译程序的计算机称为宿主机,运行编译程序所产生的目标代码的计算机称目标机。如果一个编译程序产生不同于其宿主机的机器代码,称为交叉编译程序(Cross Complier)。如果不需重写编译程序中与机器无关的部分就能改变目标机,则称该编译程序为可变目标编译程序(Retargetable Complier)。编译程序的重要性在于它使得多数计算机用户不必考虑与机器有关的繁琐细节,使程序员独立于机器硬件。除编译程序外,还需要其他一些程序才能生成在计算机上执行的目标程序。预处理程序是指,当源

9、程序以几个模块的形式存放在不同的文件中,将这些源程序汇集在一起的程序。预处理程序也能够把源程序中称为宏的缩写语句展开为原始语句加入到源程序中。源程序由编译程序编译后生成目标程序,图中的目标代码是汇编代码,需要经过汇编程序汇编转换为可装配的机器代码。再经装配连接程序连接成真正能在机器上运行的代码。装配连接程序是指,将可再装配的机器代码进行装配连接形成绝对机器代码的程序。3 编译过程和编译程序的结构 编译过程概述编译程序完成从源程序到目标程序的翻译工作,这是一个复杂的过程。整个工作过程需要分阶段完成,每个阶段将源程序的一种表示形式转换成另一种表示形式,各个阶段进行的操作在逻辑上是紧密连接在一起的。

10、根据各个阶段的复杂程度、理论基础和实现方法的不同,一般将编译程序的工作过程划分为词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成五个阶段。词法分析每种高级语言都规定了允许使用的字符集,如字母AZ,az,数字09,、*、/等。高级语言的单词符号都由定义在各语言的字符集上的这些符号构成,有的单词由一个符号组成,如,*,/等,有的单词由两个或多个符号组成,如<=、>=、end等,它们都是语言的最基本的组成成分。在多数程序设计语言中,单词一般分为5类:保留字(begin、end、if、for、while等)、标识符、常数、运算符和分界符(标点符号、括号、注释符号等)。词法

11、分析是编译的第一个阶段,其任务是从左至右逐个字符的对源程序进行扫描,产生一个个单词符号,把字符串形式的源程序改造成单词符号串形式的中间程序。在词法分析过程中,还要对源程序做一些简单处理,如滤掉空格、去掉注释、报告错误等。有的扫描器要求将识别出来的名字填入符号表,以备后续阶段使用。词法分析的工作主要依据语言的构词规则,描述构词规则的有效工具是正规式和有限自动机。语法分析语法分析是编译过程的核心部分,其基本任务是根据语言的语法规则进行语法分析,若不存在语法错误则给出正确的语法结构并为语义分析和代码生成做准备。完成语法分析任务的程序称为语法分析程序(parser)。如上述输入串中的单词序列id1:=

12、int1 + id2 * id3 + id2 * id3经过语法分析后可以确定它是一个赋值语句,可以表示为图2所示的语法树。图2 语句id1:=int1 + id2 * id3 + id2 * id3的语法树语法分析所依据的是语言的语法规则,语言的语法规则通常是由递归规则来定义,如上述例子中表达式和赋值语句可由下述递归规则来定义:(1) 任何标识符是表达式;(2) 任何常数是表达式;(3) 若表达式1和表达式2都是表达式,则表达式1+表达式2,表达式1*表达式2都是表达式;(4) 赋值语句就可以用规则:标识符 := 表达式;来定义。图1-2的语法树就是根据赋值语句和表达式的递归定义规则生成的。

13、这种用递归规则表示语法规则的工具称为上下文无关文法,用下推自动机实现。推倒(derive)和归约(reduce)。推倒又分为最左推倒和最右推倒。例如:x=a+b*50;对该赋值语句进行:最右推倒,最左归约(根据文法要求,由文法的初始符号最终能够推出我们要证明的语句,且在最右推倒过程中,每次替换掉的都是产生式最右边的非终结符(大写符号)。若能推倒,则是正确地语句。AVEVETVET×F VET×C VET×50 VEF×50 VEV×50 VEb×50 VTb×50 VFb×50 VVb×50 Vab

14、15;50(V为最终结符) xab×50若将上式从右向左证明是一个赋值语句,最右推倒的反相推倒,这种方法就是最左归约(归约也分为最右归约和最左归约)。推倒和归约的关系互为逆过程。例如:x=a+b*50;对该赋值语句进行:最左推倒,最右归约AVExExETxTTxFTxVTxaTxaT×FxaF×FxaV×Fxab×Fxab×Cxab×50(在最右推倒过程中,每次替换掉的都是产生式最右边的非终结符。这里只做了最右推倒。若将上面的式子,从右向左替换,即为最左归约)。在描述程序语言的语法结构时,需要借助于上下文无关文法,而文法是描

15、述程序语言的依据。语法分析的方法通常分为两类,即自上而下分析方法和自下而上分析方法。所谓的自上而下分析方法,就是从文法的开始符号出发,根据文法的规则进行推导,最终推导出给定的句子来。包括递归下降分析法和LL(1)分析法。递归下降分析法是一种自上而下的分析方法,文法的每个非终结符对应一个递归过程。分析过程就是从文法开始符出发执行一组递归过程,这样向下推导直到推出句子;或者说从根结点出发,自上而下为输入串寻找一个最左匹配序列,建立一棵语法树。LL(1)分析法又称预测分析法,是一种不带回溯的非递归自上而下分析法。LL(1)分析法基本思想:自左向右扫描分析输入符号串从识别符号开始生成句子的最左推导 L

16、L(1):向前看一个输入符号,便能唯一确定产生式 LL(k):向前看k个输入符号,才能唯一确定产生式自下而上分析法则是从给定的输入串开始,根据文法规则逐步进行归约,直至归约到文法的开始符号为止。自下而上分析原理是从输入符号串开始,通过重复查找当前句型的“可归约串”并利用有关规则进行规约若能规约为文法的识别符号,则表示分析成功,输入符号串是文法的合法句子,否则有语法错误.算符优先分析法是一种简单且直观的自上而下分析方法,它适合于程序语言中各类表达式的分析,并且宜于手工实现。所谓算符优先分析,就是依照算术表达式的四则运算过程来进行语法分析,即这种分析方法要预先规定运算符(确切地说是终结符)之间的优

17、先关系和结合性质,然后借助于这种关系来比较相邻运算符的优先级,以确定句型的“可归约串”来进行归约。因此,算符优先分析法不是一种规范归约,在整个归约过程中起决定性作用的是相继两个终结符的优先关系。LR分析法是一种自下而上进行规范归约的语法分析方法,LR指“自左向右扫描和自下而上进行归约”。LR分析法比递归下降分析法、LL(1)分析法和算符优先分析法对文法的限制要少得多,对大多数用无二义的上下文无关文法描述的语言都可以用LR分析器予以识别,而且速度快,并能准确、及时地指出输入串的任何语法错误及出错位置。LR分析法的一个主要缺点是,若用手工构造分析器则工作量相当大,因此必须求助于自动产生LR分析器的

18、产生器。 语义分析与中间代码产生这一阶段的主要工作有两项:首先对语法分析所识别出的各类语法单位进行静态语义审查(如标识符是否定义,类型是否匹配等);若无语义错误,再根据识别出的语法单位的类型进行处理,若是说明语句,则将变量的类型等属性填入符号表,若是可执行语句,则进行初步的翻译,将其翻译为中间代码。所谓中间代码,是一种含义明确,便于处理的记号系统,通常独立于具体硬件,与现有计算机的指令系统非常相似,比较容易转换成特定计算机的机器指令。常用的中间代码有:三元式、四元式、逆波兰式等。不管用哪种表示形式,其设计原则是容易生成,也容易转换成计算机的机器指令。很多编译程序采用四元式形式的中间代码,其形式

19、为:(运算符,运算对象1,运算对象2,结果)语义分析和中间代码生成阶段的工作通常穿插在语法分析过程中完成,因而语义翻译程序通常由一组语义子程序组成。每当分析出一个完整的语法单位,就调用相应的语义子程序执行相应的分析和翻译任务。如当语法分析器分析完var x,y: integer;后,应把x,y的类型integer填入符号表的类型栏中;当分析赋值语句id1:=int1 + id2 * id3 + id2 * id3时,其语义处理过程是:一边读取一边检查result,B ,C,5是否定义,类型是否正确,一边就生成四元式序列,如表1。表中的T1,T2,T3和T4是编译期间引进的临时工作变量。该语句翻

20、译的过程是:首先将表达式翻译为中间代码,再把表达式的值赋值给id1。表1: 赋值语句id1:=int1 + id2 * id3 + id2 * id3的四元式序号四元式1(*, id2, id3, T1)2(+, int1, T1, T2)3(*, id2, id3, T3)4(+, T2, T3, T4)5(:=, T4, _, id1)经过语义分析分析和中间代码生成阶段后,源程序被加工为整齐和标准形式的中间代码。语义分析依据的是语言的语义规则,表示工具是属性文法、P代码等。代码优化代码优化的任务是:产生的中间代码进行等价变换,使生成的目标代码更为高效(时间和空间)。优化的目的主要是提高运行

21、效率,节省存储空间。优化主要有两类,一是与机器有关的优化,主要设计如何分配寄存器,如何选择指令,这类优化是在生成目标代码时进行的;另一类优化与机器无关,主要是对中间代码的优化。根据优化所涉及的程序范围,优化又分为局部优化,循环优化,全局优化。一个程序从结构上看,作为终点的基本块是其基础。因为基本块的够最简单、因素最单纯,左翼它也是优化的基础,对基本块的优化就是局部优化。循环是程序中要反复执行的部分,优化的效益当然很大,所以循环优化是优化工作的重点。针对整个程序的优化即全局优化,它涉及到对策划能够许数据流分析的问题。例如,对表1-1的中间代码,在优化阶段,编译程序发现两次计算id2 * id3,

22、就可以省掉第2次的计算,而使用第一次计算的结果。同时因为第5个四元式仅仅把T4赋值给id1,也可以被简化掉。经优化后可变换为表2的四元式。仅剩下了3个四元式,完成了和表1-1同样的功能。表2 赋值语句id1:=int1 + id2 * id3 + id2 * id3的优化后的四元式序号 四元式1(*, id2, id3, T1)2 (+, int1, T1, T2)3(+, T2, T1, id1)代码优化的主要依据是程序的等价变换规则。优化方法包括:公共子表达式的提取、循环优化、删除无用代码等。目标代码生成目标代码生成的任务是:把中间代码(或经优化的中间代码)变换成特定机器上的低级语言代码(

23、绝对指令代码、可重定位的指令代码或汇编指令代码)。这一阶段的工作依赖于机器的硬件系统结构和机器指令的含义。工作较复杂,涉及到硬件系统功能部件的运用,机器指令的选择,各种数据类型变量的存储空间分配以及寄存器的分配和调度。代码生成是指把语法分析后或者优化后的中间代码变换成目标代码,所生成的目标代码一般有如下三种形式:(1) 能够立即执行的机器语言代码,它们通常放在固定的存储区中并可直接执行,如PC机中后缀为.COM或.EXE的文件。(2) 待装配的机器语言模块,其地址均为相对地址,所以不能直接执行。当需要执行时由连接装配程序把它们与其他运行程序和库函数连接起来,装配成可执行的机器语言代码,如PC机

24、中后缀为.OBJ的文件。(3) 汇编语言程序,必须通过汇编程序的汇编才可转换成可执行的机器语言代码如PC机中后缀为.ASM的文件前面提到的五个阶段的划分是一种典型的划分方式,事实上,并非所有的编译程序都分成这五个阶段,有些编译程序并不生成中间代码,而是直接生成目标代码,有些编译程序不进行代码优化。表格与表格管理表格的作用:用来记录源程序的各种信息,以及编译过程中的各种状况。与编译前三个阶段有关的表格有:符号表、常数表、标号表、分程序入口表、中间代码表等。表3 符号表(1)符号表:用来登记源程序中的常量名、变量名、数组名、过程名等,记录它们的性质、定义和引用情况。NameInformationm

25、整型、变量地址n整型、变量地址k整型、变量地址void main()int m,n,k;(2)常数表和标号表表4 常数表值14表5标号表NameInformation10四元式序号4常数:数值型(整型和实型)、字符型、逻辑型;所有同类型的常数占有一张表格,整型占一张、实型占一张。标号表:现在用的很少。一般在词法分析时,是不生成四元式的,只记录标号,到了生成目标代码时才在Information处填入内容。(3)入口名表作用:登记过程的层号,分程序符号表入口等。由于程序是由几个过程构成的,过程都是存入内存里,每个过程从哪里执行?必须知道过程在哪个内存单元中?因此需要登记过程的层号,分程序符号表入口

26、等。(4) 中间代码表表6 中间代码表 序号OPARG1ARG2RESULT(1)im(2)jn(3)1k(4)(Jump)<100k(9)(5)m10m(6)n10n(7)k1k(8)Jump(4)(9)return在生成中间代码时才生成该表。出错处理任务:如果源程序有错误,编译程序应设法发现错误,并报告给用户。此过程非常复杂,因为很难发现错误,需要编写出错的处理程序来完成。错误类型: 可检测的错误和不可检测的错误。语法错误:在词法分析和语法分析阶段检测出来;(单词出错、句子不规范)语义错误:又分为静态语义错误和动态语义错误。静态语义错误一般在语义分析阶段检测出来,而动态语义错误是在目

27、标程序运行的时候才能查出来;(出现语义上的不可答错误,功能无法实现。如除数为0的错误)逻辑错误:不可检测的错误。而且程序的出错可能出现在任何阶段上,每一步的错误都由“出错处理”来完成。逻辑错误无法用编译程序检测出来,也就不检测此类错误。例如:while(a|c) /而a|c在循环时判断永远为Ture, /出现死循环,即为逻辑错误。编译程序的结构编译程序的五个阶段的功能可分别用五个模块来完成,分别称为词法分析器、语法分析器、语义分析与中间代码生成器、优化器和目标代码生成器。此外,一个完整的编译程序还必须包括“表格管理”和“出错处理”两部分。一个编译程序在编译过程中应尽量找出源程序中的错误,向用户

28、提供更多更准确的与错误有关的信图3 编译程序结构框图息,以便用户查找和纠正。一个典型的编译程序结构框图如图1.3所示。词法分析是实现编译器的基础,语法分析是实现编译器的关键。本书将按照这个顺序来讲述编译程序各个阶段涉及到的基本理论、实现方法和技术。4 编译器的构造及编译技术的应用1 如何构造一个编译程序要在一台机器上为某种语言构造一个编译程序,必须从下述三方面入手:(1) 源语言:是编译程序处理的对象。对被编译的源语言要深刻理解其结构和含义,即该语言的词法、语法和语义规则,以及有关的约束和特点;(2) 目标语言与目标机:是编译程序处理的结果和运行环境。目标语言是汇编语言或机器语言,必须对硬件系

29、统结构,操作系统的功能,指令系统等很清楚;(3) 编译方法与工具:是生成编译程序的关键。必须准确掌握把一种语言的程序翻译为另一种语言的程序的方法之一。同时应考虑所使用的方法与既定的源语言、目标语言是否相符合、构造是否方便,从时间、空间上考虑是否高效、实现的可能性和代价等诸多因素,并尽可能考虑使用先进、方便的生成工具。2 编译程序的实现方式编译程序本身也是一个程序,那怎样实现它呢?从理论上讲,基本上可以用任意语言来实现。早期人们用机器语言或汇编语言手工编写;为了充分发挥硬件资源的效率,满足各种不同的要求,许多人目前仍然采用低级语言编写;但由于编译器本身是一个十分复杂的系统,用低级语言编写效率很低

30、,现在越来越多的人使用高级语言来编写,这样可以节省大量的程序设计时间,且程序易读、易修改和移植;为了进一步提高开发效率和质量,可以使用一些自动生成工具来支持编译器某些部分的自动生成,如词法分析生成器LEX和语法分析生成器YACC等。概括起来,生成编译程序的方法有:1直接用机器语言或汇编语言编写(编译程序核心部分常用汇编语言编写);2用高级语言编写编译程序(这是普遍采用的方法);3自编译;4用编译工具自动生成部分程序:LEX(词法分析)与YACC(用LALR分析方法自动生成语法分析器);5.移植(同种语言的编译程序在不同类型的机器之间移植)。用高级语言编写编译程序当然离不开高级语言的程序开发环境

31、。目前常用的高级语言集成开发环境环境有Basic开发环境VB、C和C+开发环境VC+、C#开发环境VC#等。3 编译技术的应用为了提高软件开发效率、保证质量,在软件工程中除了遵循软件开发过程的规范或标准外,还尽量使用先进的软件开发技术和相应的软件工具。而大部分软件工具的开发,常常要用到编译技术和方法,实际上编译程序本身也是一种软件开发工具。为了提高编程效率,缩短调试时间,软件工作人员研制了不少对源程序处理的工具,这些工具的开发不同程度地用到了编译程序各个部分的技术和方法。下面是常用的软件工具:语言的结构化编辑器 结构化编辑器不仅具有通常的正文编辑器的正文编辑和修改功能,而且还能像编译程序那样对

32、源程序正文进行分析。这类产品有Turbo-Edit、editplus和Ultraedit等。语言程序的调试工具 结构化编辑器只能解决语法错误的问题,而对一个已通过编译的程序来说,需进一步了解的是程序执行的结果与编程人员的意图是否一致、程序的执行是否实现了预期的算法和功能。对算法错误或程序不能反应算法的功能的检查就需要调试工具来完成。调试功能越强,实现就越复杂,它主要涉及源程序的语法分析和语义处理技术。语言程序的测试工具 语言程序的测试工具有两种:静态分析器和动态测试器。静态分析器是对源程序进行静态的分析,它对源程序进行语法分析并制定相应表格,检查变量定值与引用关系,如检查某变量未被赋值就引用,

33、或定值后未被引用,或多余的源代码等一些编译程序的语法分析发现不了的错误;动态测试工具是在源程序的适当位置插入某些信息,并用测试用例记录程序运行时的实际路径,将运行结果与期望的结果进行比较分析,帮助编程人员查找问题。这种测试工具在国内已有开发,如FORTRAN和C语言的测试工具。高级语言之间的转换工具 由于计算机硬件的不断更新换代,更新更好的程序设计语言的推出为提高计算机的使用效率提供了良好的条件。然而一些已有的非常成熟的软件如何在新机器新语言情况下使用呢?为了减少重新编制程序所耗费的人力和时间,就要解决如何把一种高级语言程序转换成另一种高级语言程序,乃至汇编语言程序如何转换成高级语言程序的问题

34、。这种转换工作要对被转换的语言进行词法和语法分析,只不过生成的目标语言是另一种高级语言而已。这比实现一个完整的高级语言编译程序相比工作量要少些。目前已有成熟的转换系统。交叉编译程序 随着嵌入式技术的发展和广泛应用,嵌入式软件开发环境所涉及的关键技术是多目标交叉编译和调试工具。这些工具希望在宿主机上为源语言交叉编译生成多个目标板上的目标程序,并能对目标机上运行的程序进行调试。第2章 词法分析主要内容:1 词法分析器设计方法 2 一个简单的词法分析器示例 3 正规表达式与有限自动机简介 4 正规表达式到有限自动机的构造 5 词法分析器的自动生成 词法分析是编译的第一个阶段,其任务是从左至右逐个字符

35、的对源程序进行扫描,产生一个个单词符号,把字符串形式的源程序改造成单词符号串形式的中间程序。词法分析的工作主要依据语言的构词规则,描述构词规则的有效工具是正规式和有限自动机。状态转换图状态转换图是有限的有向图,结点代表状态,用圆圈表示;结点之间可由有向边连接,有向边上可标记字符。正规表达式和有限自动机字母表å, 定义在å 上的正规式和正规集递归定义如下:1. e和f都是å 上的正规式, 它们所表示的正规集分别为:e和f;2. 任何aÎ å , a是å 上的正规式,它所表示的正规集为:a; 3. 假定U和V å 上的正规式,

36、它们所表示的正规集分别记为L(e1) 和L(e2), 那么e1|e2, e1e2和e1*也都是å 上的正规式, 它们所表示的 正规集分别为L(e1) ÈL(e2)、 L(e1) L(e2)和(L(e1)*4. 任何å 上的正规式和正规集均由1、2和3产生。1.确定的有限自动机(DFA)M=(, Q, f,S, Z) :有穷字母表,它的每个元素称为一个输入符号Q:有穷集,它的每个元素称为一个状态SK,是唯一的初态Z Ì K是一个终态集,终态也称可接受状态或结束状态f是转换函数,是Q×Q上的单值映射:f(q1,a)=q2 2.不确定的有限自动机(N

37、FA)M=(, Q, f,S, Z) f是一个多值函数,是从Q×*到Q的子集的映射:f:Q×2Q 其中2Q是Q的幂集,即Q中所有子集组成的集合。3.状态转换图与状态转换矩阵DFA和NFA都可以用状态转换图表示。假定DFA有m个状态n个输入字符,则这个状态转换图含有m个状态,每个状态最多有n条输出边与其他状态相连接。DFA和NFA可以用状态转换矩阵表示。正规表达式到有限自动机的构造(1)对于字母表上的NFA M,可以构造一个上的正规式R,使得L(R)=L(M);(2)对于字母表上的每个正规式R,可以构造一个上的NFA M,使得L(M)=L(R)。 正规式RÞNFA

38、M(1)对NFA M构造一个广义的状态图,其中只有一个初态S和终态Z,连接S和Z的有向弧标记为正规式。(2)对正规式依次进行分解,分解的过程是一个不断加入结点和弧的过程,直到转换图上的所有弧标记上都是字母表上的元素或e为止。 词法分析器的自动生成:LEX的源程序一个LEX源程序主要由三个部分组成 说明部分 可选% 必须有识别规则 必须有(LEX的核心)% 可选辅助过程 可选1、说明部分:变量、常量说明和正规式定义正规式定义格式如下:D1 R1 D2 R2 Dn Rn 2、识别规则:是一串如下形式的LEX语句: R1 A1 R2 A2 Rm AmRi :正规式Ai:Ai为语句序列,在识别出单词R

39、i以后,词法分析器所应作的动作。 其基本动作是返回单词的类别编码和单词值。3、辅助过程:用户定义的子程序下面是识别C语言部分单词符号的LEX源程序:/*说明部分*/ digit 0-9letter A-Za-z id (letter|_)(letter|digit|_)* %/*识别规则,每条规则中的动作都用大括号括起来*/ “main”|”int”|”if” Upper(yytext,yyleng); printf("%s,KEYn",yytext); id printf("%s,IDn",yytext); “+”|”-”|”*” printf(&qu

40、ot;%s,SYMBOLn",yytext);%/*辅助过程*/Upper(char *s,int l) int i; for(i=0;i< l;i+)si=toupper(si);return 1;void main(void) yylex();LEX的实现LEX的功能是根据LEX源程序构造一个词法分析程序,该词法分析器实质上是一个有穷自动机。LEX的工作原理是将LEX源程序中的正规式转换成DFA,进一步通过控制程序识别单词第3章 语法分析主要内容:1 文法和语言 2 推导与语法树 3 自上而下分析方法 4 自下而上分析方法 5 LR分析法 主要开发了推导与语法树以及几种语法

41、分析的方法。推导与语法树给定文法GS, ba为该文法的句型, 若 S=>aA,且A=>b, 则b是句型ba相对于A的短语; 若 S=> aA, 且A=> b, 则b是句型ba相对于A的简单短语直观理解:短语就是某句型中的子串,这个子串是由某个非终结符通过至少一步推导得到的子串,而简单短语就是由某个非终结符通过一步推导得到的子串。素短语是一个短语,它至少包含有一个终结符号,并且除它自身以外不再包含其他素短语.其中最左边的素短语称为最左素短语。 例2-1求句型T+T*F+i的短语、简单短语、句柄、素短语、最左素短语短语:T+T*F+i, T+T*F, T,T*F,i简单短语

42、:T,T*F,i句柄:T素短语:T*F和i(因为T不包含终结符, T+T*F+i和T+T*F包含其他素短语)图2-7 句型T+T*F+i的的语法树最左素短语:T*F自上而下分析法所谓的自上而下分析方法,就是从文法的开始符号出发,根据文法的规则进行推导,最终推导出给定的句子来。包括递归下降分析法和LL(1)分析法。递归下降分析法是一种自上而下的分析方法,文法的每个非终结符对应一个递归过程。分析过程就是从文法开始符出发执行一组递归过程,这样向下推导直到推出句子;或者说从根结点出发,自上而下为输入串寻找一个最左匹配序列,建立一棵语法树。LL(1)分析法又称预测分析法,是一种不带回溯的非递归自上而下分

43、析法。LL(1)分析法基本思想:自左向右扫描分析输入符号串从识别符号开始生成句子的最左推导 LL(1):向前看一个输入符号,便能唯一确定产生式 LL(k):向前看k个输入符号,才能唯一确定产生式 LL(1)分析法主要是构造FIRST集和FOLLOW集。例2-2 GE:ETE'E'+TE'|eTFT'T'*FT'|eF(E)|i 求FIRST集。解:FIRST(F)=(,iFIRST(T)=*,FIRST(T)=FIRST(F)-=(,iFIRST(E)=+,FIRST(E)= FIRST(T)-=(,iFIRST(TE)=FIRST(T)-=(,

44、iFIRST(+TE)=+ FIRST()=FIRST(FT)= FIRST(F)-=(,iFIRST(*FT) =*FIRST((E))=(FIRST(i)=iFIRST(F)=(,iFIRST(T)=*,FIRST(T) =(,iFIRST(E)=+,FIRST(E)=(,i例2-3 GE:ETE'E'+TE'|eTFT'T'*FT'|eF(E)|i 求FOLLOW集。解:FOLLOW(E)=#,) E是开始符号#FOLLOW(E) 又F (E) )FOLLOW(E)FOLLOW(E)=#,) E TE FOLLOW(E)加入 FOLLOW(

45、E)FOLLOW(T)=+,),# E +TE FIRST(E)-加入FOLLOW(T) 又EÞ, FOLLOW(E)加入FOLLOW(T)FOLLOW(T)= FOLLOW(T)= +,),# T FT FOLLOW(T)加入FOLLOW(T)FOLLOW(F)=*,+,),# T FT FOLLOW(F)=FIRST(T)- 又TÞ FOLLOW(T)加入FOLLOW(F)自底向上分析法自下而上分析法则是从给定的输入串开始,根据文法规则逐步进行归约,直至归约到文法的开始符号为止。自下而上分析原理是从输入符号串开始,通过重复查找当前句型的“可归约串”并利用有关规则进行规约

46、若能规约为文法的识别符号,则表示分析成功,输入符号串是文法的合法句子,否则有语法错误.算符优先分析法是一种简单且直观的自上而下分析方法,它适合于程序语言中各类表达式的分析,并且宜于手工实现。所谓算符优先分析,就是依照算术表达式的四则运算过程来进行语法分析,即这种分析方法要预先规定运算符(确切地说是终结符)之间的优先关系和结合性质,然后借助于这种关系来比较相邻运算符的优先级,以确定句型的“可归约串”来进行归约。因此,算符优先分析法不是一种规范归约,在整个归约过程中起决定性作用的是相继两个终结符的优先关系。LR分析法是一种自下而上进行规范归约的语法分析方法,LR指“自左向右扫描和自下而上进行归约”

47、。LR分析法比递归下降分析法、LL(1)分析法和算符优先分析法对文法的限制要少得多,对大多数用无二义的上下文无关文法描述的语言都可以用LR分析器予以识别,而且速度快,并能准确、及时地指出输入串的任何语法错误及出错位置。LR分析法的一个主要缺点是,若用手工构造分析器则工作量相当大,因此必须求助于自动产生LR分析器的产生器。 LR分析算法描述:将S0移进状态栈,# 移进符号栈,S为状态栈栈顶状态a=getsym( ) /读入第一个符号给awhile(ACTIONS,a!=acc ) if ACTIONS,a=Si PUSH i,a(分别进栈); a=getsym( ) ;/读入下一个符号给a el

48、se if ACTIONS,a=rj (第j条产生式为A) 将状态栈和符号栈分别弹出| 项;push(A); 将GOTOS,A 移进状态栈(S为当前栈顶状态);else error( );第4章 语义分析和中间代码生成分析主要内容:1 概述 2 属性文法 3 几种常见的中间语言 4 表达式及赋值语句的翻译 5 控制语句的翻译 6 数组元素的翻译 7 过程或函数调用语句的翻译 8 说明语句的翻译9 递归下降语法制导翻译方法简介 主要介绍了语法制导翻译方法、几种中间语言以及语句的翻译。语法制导翻译方法语法制导翻译的方法就是为每个产生式配上一个翻译子程序(称语义动作或语义子程序),并在语法分析的同时

49、执行这些子程序。语法制导翻译是将语义规则与语法规则相结合,在语法分析的过程中通过执行语义动作,计算语义属性值,从而完成预定的翻译工作。 语法制导翻译分为两种处理方法:(1)语法制导定义(自底向上):对每个产生式编制一个语义子程序,在进行语法分析的过程中,当一个产生式获得匹配时,就调用相应的语义子程序实现语义检查与翻译。这种实现方案隐藏了其中语义规则的计算次序等实现细节,不必规定翻译顺序。(2)翻译方案(自顶向下):在产生式右部的适当位置,插入相应的语义动作,按照分析的进程,执行遇到的语义动作。这是一种动作与分析交错的实现方案。几种常见的中间语言1抽象语法树 抽象语法树也称图表示,是一种较为流行

50、的中间语言表示形式。在抽象语法树表示中,每一个叶结点都表示诸如常量或变量这样的运算对象,而其它内部结点则表示运算符。与抽象语法相对应的语法树称为抽象语法树或抽象树 2逆波兰表示法 逆波兰表示法把运算量(操作数)写在前面,把运算符写在后面,因而又称后缀表示法。例如,把a+b写成ab+,把a*(b+c)写成abc+*。 表达式E的后缀表示的递归定义如下: (1) 如果E是变量或常数,则E的后缀表示即E自身。 (2) 如果E为E1 op E2形式,则它的后缀表示为E1'E2'op;其中op是二元运算符,而E1'、E2'分别又是E1和E2的后缀表示。若op为一元运算符,

51、则视E1和E1'为空。 (3) 如果E为(E1)形式,则E1的后缀表示即为E的后缀表示 为了用逆波兰式表示一些控制语句,我们定义转移操作如下: (1) BL:转向某标号; (2) BT:条件为真时转移; (3) BF:条件为假时转移; (4) BR:无条件转移。部分程序语句的逆波兰表示: (1) 赋值语句。赋值语句“<左部>=<表达式>”的逆波兰表示为 <左部><表达式>= (2) GOTO语句。转向语句“GOTO<语句标号>”的逆波兰表示为<语句标号>BL 其中,“BL”为单目后缀运算符,“<语句标号>”则为BL的一个运算分量。(3) 条件语句。BR表示无条件转移单目后缀运算符。例如,“<顺序号>BR”表示无条件转移到“<顺序号>”处,这里的顺序号是BR的一个特殊运算分量,用来表示逆波兰式中单词符号的顺序号(即第几个单词),它不同于GOTO语句

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论