还剩63页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
教材资料授课顺序1教学目的正确理解什么是编译程序;了解编译程序工作的基本过程及其各阶段的基本任务;熟悉编译程序总框;了解编译程序的生成过程和构造工具教学重点与难点编译程序工作的基本过程及其各阶段的基本任务,编译程序总框授课学时2学时教学方式多媒体讲授教学内容第一章引论
1.1什么是编译程序
一、基本概念
1、翻译程序是指这样的一种程序,它能够把一种语言程序源语言程序转换成另一种功能等价的语言程序目标语言程序
2、编译程序是一种翻译程序,其源程序是高级语言,目标语言程序是低级语言通常是一次性翻译方式如TC等高级语言编译程序
3、解释程序也是一种翻译程序,它与编译程序的区别立即执行源程序,通常是逐句翻译执行如BASIC、SQL、J__A的BYTECODE解释程序等
二、高级语言程序的处理过程高级程序设计语言程序的典型处理过程如下图所示
1.2编译过程和编译程序结构
一、编译过程的阶段划分一般编译程序的工作过程按阶段进行,每个阶段将源程序从一种表示形式转换成另一种表示形式典型的阶段划分方法是将整个编译过程分为如下六个阶段
1、词法分析任务对构成源程序的字符串进行扫描和分解,识别出单词如标识符等符号输入源程序输出单词符号序列例子有待分析源程序__in{intx=10y;}词法分析后的输出1)保留字__in2)界符左圆括号3)界符右圆括号4)界符左大括号{5保留字int6标识符x7运算符=8常数10,界符,9标识符y10界符;11)界符右大括号}
2、语法分析任务根据语言的语法规则对单词符号串符号序列进行语法分析,识别出各类语法短语可表示成语法树的语法单位,判断输入串在语法上是否正确输入单词序列输出语法分析后的单词序列
3、语义分析任务按语义规则对语法分析器归约出的语法单位进行语义分析,审查有无语义错误,为代码生成阶段收集类型信息,并进行类型审查和违背语言规范的报错处理输入语法分析后的单词序列输出语义分析后带语义信息的单词序列
4、中间代码生成(并非所有的编译程序都包含此阶段)任务将语义分析得到的源程序变成一种结构简单、含义明确、易生成、易翻译成目标代码的内在代码形式常用的中间代码形式是四元式(算符,运算对象1,运算对象2,结果)输入语义分析后的单词序列输出中间代码
5、代码优化(可放到目标代码生成阶段后)任务对中间代码或目标代码进行变换改造等优化处理,使生成的代码更高效输入中间代码或目标代码输出优化后的中间代码或目标代码
6、目标代码生成任务将中间代码生成特定机器上的绝对或可重定位的指令代码或汇编指令代码输入语义分析后的单词序列或优化后的中间代码输出目标代码
二、编译程序结构上述六个阶段的任务分别由六个模块来完成一个完整的编译程序还应包括表格管理和出错处理程序典型编译程序结构框图如下
三、编译阶段的组合
1、前后端组合法编译前端与源语言有关与目标机无关的部分第1-4阶段编译后端与目标机有关的部分第6阶段注第5阶段置前或后端都可以组合方式1)同一源语言的编译前端+不同后端=不同机器上同一源语言的编译程序;2)不同源语言的编译前端生成同一种中间语言+使用共同后端=同一机器上不同语言的编译程序
2、遍组合法遍/趟对源程序或源程序的中间结果从头到尾扫描一次称为一遍每一遍扫视完成一个或几个阶段的工作一个编译程序可由一遍或多遍完成.实际编译程序分遍的主要参考因素是源语言与目标机器的特征
1.3编译技术和软件工具
一、编译技术的发展1950S早期算术工式译成机器代码1950S中期FORTRAN编译系统1950S末期自动生成工具出现,如LEX、YACC1960S自展技术1971年用自展技术生成PASCAL编译程序现代并行编译技术
二、编译技术与软件工具
1、先进的软件__技术和软件工具能提高编程效率、缩短调试时间
2、编译程序本身是一种软件工具
3、大部分软件工具的__常用到编译技术和方法
4、进行源程序处理的软件工具实质上都在不同程度上用到了编译程序各个部分的技术和方法如
(1)语言结构化编辑器(语法);
(2)语言程序调试工具(语法、语义);
(3)语言程序测试工具(静、动态测试,发现错误);
(4)高级语言之间的转换工具;
(5)程序格式化工具、程序理解工具等
1.4程序设计语言规范从支持的计算模式来看,程序设计语言(是指书写计算机程序的高级语言)规范有如下几种
1、强制命令式语言,即过程式语言该型语言中,一个过程可看作是一系列动作,其动作由命令驱动,以语句形式表示,一个语句接一个语句的执行属于这种规范的语言如PASCAL、C、FORTRAN等,C++、Ada、COBOL等也支持这种模式本课程介绍的编译技术针对这型语句
2、函数式语言,即应用式语言该型语言注重程序所表示的功能,程序的__过程是从前面已有函数出发构造出更加复杂的函数,对初始数据集进行操作,直到最后形成的函数可以得到最终结果属于这种规范的语言如ML、LISP等
3、基于规则(逻辑)的语言该型语言程序的执行过程是检查一定的使能条件,满足时,则执行适当的动作如逻辑程序设计语言PROLOG,其基本的使能条件是某种谓词逻辑表达式;再如YACC,其使能条件是程序的形式语法(BNF)
4、面向对象语言该型语言的主要特点是提供抽象数据类型,支持封装性、继承性和多态性C++、Ada、J__a等也支持这种模式
1.5编译程序的构造
一、编译程序的构造途径
1、用某种程序语言编写;
2、用编译程序自动构造工具构造
3、通过现有的编译基础设施进行改造和组装
二、T型图T型图是用来表示一个编译程序所涉及到的三个方面的语言的一种工具,将源语言S通过用语言H书写的编译器翻译成目标语言T的编译程序可用如下T型图THST表示T型图的两种组合方式
三、编译程序的自展
1、方法用“滚雪球”的方式生成编译程序
2、思想先用目标机的汇编语言或机器语言书写源语言的一个子集的编译程序,再用这个子集作为书写语言(属于高级语言),实现源语言的编译程序例设,目标机A的语言为A,则两层自展构造实现语言C对应A机器的编译程序过程可描述为如下其自展过程用语言A编写语言C1的编译程序TAC1A;再用C1书写语言C的编译程序TC1CA;最后再将TC1CA经过TAC1A编译得到TACA
四、编译程序的移植、自编译、交叉编译
1、移植将某一机器宿主机上已有的软件移植到另一机器目标机上的过程
2、自编译用某种语言本身书写自己的编译程序的过程例如在机器A上已有语言C的编译程序(将语言C翻译成A的机器码A),现希望利用此编译程序生成机器B上的语言C的编译程序(将语言C翻译成B的机器码B)
3、交叉编译把某源语言在宿主机上经过编译而产生目标机的汇编语言或机器语言的过程
五、可重定向编译程序
1、由于交叉编译是在一个平台上生成另一个平台上的可执行代码的过程交叉编译受限较多
2、编译基础设施为__各种编译程序成分提供相应生成工具
3、可重定向编译程序能够根据不同的目标机生成相应目标代码的编译程序它将与目标机相关的部分单独编写成不同模块,根据不同的目标机调用不同的模块自由软件__CGNU工程的编译程序__是目前使用广泛的可重定向编译程序4、支持可重定向编译的关键技术 1)中间表示技术区别于四元式等传统的中间表示,支持可重定向编译的中间表示应在适当的抽象层次上,向上能够支持多语言映射、向下能够适应多平台转换后宜于进行各种优化2机器描述技术区别于传统的假定式体系结构抽象模型的描述技术,支持可重定向编译的机器描述机制应能描述系统和硬件的共性,又能描述它们各自的特性,且能适应于不同编译程序的处理研究表明,基于体系结构描述语言详细地指定了体系结构是产生高质量机器级工具的关键技术3)代码生成程序的构造技术为简化开始过程、提高代码可靠性,支持代码生成程序的自动构造工具是关键技术和主要难点4)目标机描述与目标代码生成的接口技术在重定向编译程序的开始过程中,抽取一系列函数和数据结构作为目标机描述与目标代码生成的接口可以简化编译程序的__,提高编译程序的效率授课顺序2教学目的使学生了解文法的直观描述、符号和符号串,掌握文法和语言的形式定义、文法的分类教学重点文法和语言的形式定义、文法的分类教学难点文法和语言的形式定义授课学时2学时教学方式多媒体讲授教学内容第三章文法和语言
3.1语言概述和文法的直观概念
一、基本概念
1、语言是由句子组成的__,是由一组符号所构成的__
2、汉语所有符合汉语语法的句子的全体
3、英语所有符合英语语法的句子的全体
4、程序设计语言所有该语言的程序的全体
二、语言研究的内容
1、语法(Syntax)每个句子构成的规律/每个程序构成的规律表示构成语言句子的各个记号之间的组合规律在形式语言理论中,阐明语法的工具是文法
2、语义(Se__ntics)每个句子的含义/每个程序的含义表示各个记号的特定含义(各个记号和记号所表示的对象之间的关系)
3、语用(Prag__tics)每个句子和使用者的关系/每个程序和使用者的关系表示在各个记号所出现的行为中,它们的来源、使用和影响
三、文法的直观描述通常,用句子表述一种语言,但是句子是无穷的
1、例子以自然语言为例,人们无法列出全部句子,但是人们可以给出一些规则,用这些规则来说明或者定义句子的组成结构,比如汉语句子可以是由主语后随谓语而成,构成谓语的是动词和直接宾语下面采用EBNF来表示句子的构成规则先给定如下一组规则〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉|〈名词〉〈代词〉∷=我|你|他〈名词〉∷=王明|学生|工人|英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是|学习〈直接宾语〉∷=〈代词〉|〈名词〉有了这一组规则后,用它们导出句子的方式如下1)找∷=左端的带有〈句子〉的规则并把它由∷=右端的符号串代替,这个动作表示成〈句子〉〈主语〉〈谓语〉2)在得到的串〈主语〉〈谓语〉中,选取〈主语〉或〈谓语〉,再用相应规则的∷=右端代替之比如选取了〈主语〉,并采用规则〈主语〉∷=〈代词〉,那么得到〈主语〉〈谓语〉〈代词〉〈谓语〉,3)重复上述步骤导出句子“你是学生”的全部动作过程是〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉你〈谓语〉你〈动词〉〈直接宾语〉你是〈直接宾语〉你是〈名词〉你是学生因此,“你是学生”的构成符合上述规则,而“你学生是”不符合上述规则,因此,它不是句子
2、文法的直观定义上例中的规则就是我们判别句子结构合法与否的依据,可以将这些规则看成是一种元语言,用它描述汉语由此可得文法的直观定义如下文法____一些规则的有穷__,它是以有穷规则集来刻划无穷句子__的工具
3.2符号和符号串
一、基本概念
1、字母表元素的非空有穷集,记为Σ
2、符号字母表中的元素
3、符号串符号的有穷序列
4、空符号串什么符号也不含的符号串,记为ε例Σ={a,b,c,d,……z}a、b、c……都称为符号hello、stri、ae__g、__in、fjfka都是Σ上的符号串
二、符号串的基本操作
1、符号串的长度符号所包含符号的个数,设x是一符号串,其长度记为|x|例|hello|=5,|__in|=4,|ε|=
02、符号串的连接设x、y是两个符号串,则xy被称为x与y的连接特别有x=xε=εx=εxε例x=my,y=clas__ate,则xy=myclas__ate
3、符号串的方幂设x是符号串,x自身的连接称为符号串的方幂,有例x=ba,x0=ε,x1=ba,x2=bababa
4、符号串的__若__A中元素都是某字母表Σ上的符号串,则A是Σ上的符号串__
5、符号串__的乘积若A、B均为Σ上的符号串__,则AB={xy|x∈A,y∈B}例设A={ab,cd},B={ef,jh},则AB={abef,a__h,cdef,cdjh}A{ε}=A,φA=Aφ=φ
6、符号串__的正闭包设符号串__A,A的正闭包记为A+,A的闭包记为A*例设Σ={0,1},则Σ+={0,1,00,01,10,11,000,001……}Σ*={ε,0,1,00,01,10……}
3.3文法和语言的形式定义
一、基本概念
1、产生式设VN,VT分别是非空有限的非终结符号集和终结符集V=VN∪VT,VN∩VT=φ所谓产生式是一个序偶对α,β,其中α∈V+,β∈V*,通常表示为α→β或α∷=β,产生式也叫规则、重写规则、生成式例___数字→0|1|2|3…|
92、文法文法G是一个四元组,G=VN,VT,P,S其中VN,VT分别是非空有限的非终结符集和终结符集,且二者交集为φ;P为产生式集;S∈VN,是文法的开始符号或识别符,它是一个非终结符,至少要在一条规则中作为左部出现例文法G=VN,VT,P,S,其中VN={S,B},VT={0,1},P={S→0B,B→1,B→1B}开始符为S可用文法的通俗表示法表示如下G[S]S→0B,B→1,B→1B这个文法表示所有形如01,011,0111,01111的串
3、直接推导设α→β是文法G=VN,VT,P,S的产生式,γ,δ∈VN∪VT*,若有符号串v,w满足v=γαδ,w=γβδ,则称w是v的直接推导,或称v是w的直接归约记作v=w例现有文法G[E]E→E+T|TT→T*F|FF→E|i设v=E+F*i,w=E+i*i,则有v=w或E+F*i=E+i*i
4、推导如存在一直接推导序列v=α0=α1=α
2....=αn=un0,则称符号串u为符号串v的一个推导或者说v是u的一个归约,记为v=+u;若有v=+u,且有v=u,则记作v=*u例对于上例中文法G[E]E→E+T|TT→T*F|FF→E|i设v=E,u=i+i*i,则有v=+u相应的直接推导序列为E=E+T=E+T*F=E+F*F=T+F*F=F+F*F=F+F*i=F+i*i=i+i*i
5、句型和句子设G[S]是一文法,如有S=*x,则称x是文法G[S]的句型若x是G[S]的句型,且x∈VT*,则称x是G[S]的句子
6、语言文法G[S]的语言是G[S]的所有句子构成的__即LG={x|S=*x,且x∈VT*}例文法G[S]S→MVDM→小王|小张V→是|不是D→大学生则文法G[S]表示的语言可定义为LG={小王是大学生,小王不是大学生,小张是大学生,小张不是大学生}MVDM是DM是大学生等均是G[S]的句型
7、文法的等价若LG1=LG2则称G1和G2是等价的
3.4文法的类型Chomsky将文法按其所表示的语言的表达能力,由高往低分为四类0型,1型,2型,3型文法
一、定义
(1)0型文法如果文法G的产生式α→β,其中α∈VN∪VT*,且至少含有一个非终结符号,β∈VN∪VT*则称G为0型文法0型文法又称短语结构文法
(2)1型文法如果0型文法G的产生式α→β满足|β|=|α|,仅当β=ε时例外则称此文法G是1型文法1型文法也称上下文有关文法
(3)2型文法一个1型文法G,如果满足α∈VN,则称为2型文法或者说2型文法的产生式都形如A→β2型文法也称上下文无关文法
(4)3型文法一个2型文法G,如果产生式全都是形如A→a或A→aB,其中A、B∈VN,a∈∪VT*,则G为3型文法3型文法也称正则文法或正规文法或右线性文法它对应有穷自动机
(5)四类文法产生对应的四类语言
二、文法之间的关系四类文法的定义是通过逐步增加限制条件进行的即有3型文法2型文法1型文法0型文法
三、例题判断下列文法类型例1文法G[S]S→aSYZS→aYZaY→ayyY→yyyZ→yzZY→YZzZ→zz0,1例2文法G[S]S→xSYZS→xYZxY→xyY→yyyZ→yzZY→YZzZ→zz0,1例3文法G[S]S→aTT→bT|cT|b|c0,1,2,3例4文法G[S]S→xB|cB→AzA→cS0,1,2,3授课顺序3教学目的使学生掌握语法树的构造、句型分析的方法,了解二义性文法的改造和有关文法实用性的一些说明教学重点句型分析教学难点二义性文法的改造、句型分析授课学时2学时教学方式多媒体讲授教学内容
3.4上下文无关文法及语法树上下文无关文法有足够的能力来描述现今程序设计语言的语法结构今后如无特别说明,“文法”一词均指上下文无关文法
一、语法树语法树也称推导树,给定文法G=VN,VT,P,S,对于文法G的任意一个句型都存在一个相应的语法树,它满足1树中每一个结点都有一个标记,此标记是V=VN∪VT中的一个符号2根的标记是S3苦树的一结点A至少有一个子女,则A∈VN4如结点A的子女结点从左到右次序为B1,B
2...Bn,则必有产生式A→B1B
2...Bn例G[S]S→aAS|aA→__A|SS|ba对句型aabbaa的推导过程可表示为下图所示语法树下面两个推导过程均可由上图表示1SaASa__ASaabASaabbaSaabbaa2SaASaAaa__Aaa__baaaabbaa这说明同一语法树可以表示对同一句型不同的推导过程
二、最左右推导
1、如果每一步αβ中,都是对α中最左右非终结符进行替换,则称之为最左右推导
2、最右推导称为规范推导,由规范推导所得的句型称为规范句型
3、同一语法树最多对应唯一的最左右推导
4、一个句型有可能对应着不同的语法树例文法G[E]E→i|E+E|E*E|E,则句型i*i+i可能对应着下面两个最右推导1EE+EE+iE*E+iE*i+ii*i+i2EE*EE*E+EE*E+iE*i+ii*i+i
三、二义性语法树
1、如果一个文法存在某个句子对应着两棵不同的语法树,则称此文法是二义的不存在一种算法能在有限步骤内判断一个2型文法是否是二义的
2、实际应用中,常找出一组无二义性的充分条件来构造无二义性文法
3、例子例1下列简单算术表达式的文法是二义性文法E→E+E|E-E|E*E|E/E|E|id引入新的非终结符后可变换为非二义性文法E→E+T|E-T|TT→T*F|T/F|FF→E|id例2If语句的文法G[S]S→ifEthenSS→ifEthenSelseSS→EE→a≠0|a0|b=1|b=-1|b=0假设执行下列语句前b=0,有If句子ifa≠0thenifa0thenb=1elseb=-1则当a=1时,b=1;当a=-1时,b=-1;当a=0时,b=0通过引入新非终结符、加ε规则进行改造后得文法1S→U|M|E2U→ifEthenS3U→ifEthenMelseU4M→ifEthenMelseM5M→S6M→ε7E→a≠0|a0|b=1|b=-1|b=0课堂作业为上述改造前和和改造后的文法构造唯一的语法树
3.6句型的分析句型的分析就是识别一个符号串是否为某文法的一个句型本课程介绍的分析算法都是从左到右的分析算法它们分为两大类自顶向下分析、自底向上分析
一、自顶向下分析自顶向下分析由根向下逐步建立语法树,是一个逐步推导的过程例文法G[S]S→cAdA→ab|a对输入串cabd进行识别过程为ScAdcabd,构造语法树步骤如图所示识别过程也有可能是ScAdcad,此时无法识别出串cabd,需要回溯
二、自底向上分析自底向上分析自叶向上构造语法树,是一个逐步约的过程自底向上分析法的核心在于寻找“可归约串”例对串cabd归约过程为cabdcAdS,构造语法树步骤如图所示归约过程也有可能是cabdcAbd,此时无法识别出串cabd,也需要回溯
三、句型分析的有关问题
1、基本概念
(1)令G[S]是一文法,αβδ是文法G的一个句型,如果有S=*αAδ,且A=+β,则称β是句型αβδ相对于非终结符A的短语,如有Aβ,则称β是αβδ相对于非终结符A或相对于规则A→β的直接短语也叫简单短语
(2)一个句型的最左直接短语称为该句型的句柄注意作为短语的β必须是需要分析的句型αβδ的一部分
2、例子例1已知文法G[E]E→E+T|TT→T*F|FF→E|i对于给定的句型i*i+i,指出该句型的所有短语、直接短语和句柄解将句型改写为i1*i2+i3,则1)因E=+i1*i2+i3,E=+i1*i2,故句型相对于E的短语有i1*i2+i3,i1*i22)因T=+i1*i2,T=+i1,T=+i3,故句型相对于T的短语有i1*i2,i1,i33)因F=+i1,F=+i2,F=+i3,故句型相对于F的短语为i1,i2,i3;且i1,i2,i3均为句型相对于规则F→i的直接短语,其中i1为句柄下面根据语法树进行分析例2G[S]S→aASS→aA→__AA→SSA→ba要求对句型aabbaa的进行分析解将句型改写为a1a2b1b2a3a4,则1)该句型相对于S的短语a1a2b1b2a3a4和a4;2)该句型相对于A的短语a2b1b2a3和b2a3;3)该句型相对于Sàa的直接短语a2,a4;4)该句型相对于Aàba的直接短语b2a3;5)句柄a2问题a
1、b
1、b
2、a3___不是短语?
3.7文法实用性的一些说明
一、有关文法的实用限制
1、在实用中,文法中不得含有害规则或多余规则
2、形如U→U的规则为有害规则
3、不可达规则或不可终止规则为多余规则例G[S]S→Ab|CdA→bD→eC→Ca
二、限制使用ε规则即形如A→ε的规则,它会使有关文法的证明和讨论变得复杂习题讲解P48第11题扩展令文法G[E]为E→T|E+T|E-TT→F|T*F|T/FF→E|i要求证明F+T*F是它的一个句型,构造其语法树,并指出这个句型的所有短语、直接短语和句柄解1)证明因为EE+TT+TF+TF+T*F,即有E=*F+T*F,故F+T*F是G[E]的一个句型语法树如下图所示2)句型分析该句型相对于E的短语F+T*F、F;该句型相对于T的短语T*F、F;该句型相对于T→F的直接短语F,相对于T→T*F的直接短语T*F;该句型的句柄F作业P47练习
2、
5、
9、
11、16授课顺序4教学目的让学生了解词法分析程序的概念及设计原则、单词的分类,掌握正规文法、正规式的相关概念及等价转换方法教学重点正规文法和正规式的相关概念及等价转换教学难点正规文法和正规式的等价转换授课学时2学时教学方式多媒体讲授教学内容第四章词法分析
4.1词法分析程序的设计
一、词法分析程序的设计思想通常将词法分析程序(扫描器)设计为子程序形式,当语法分析程序需要单词时,则调用该子程序
二、单词分类通常分为5类1基本字关键字、保留字具有特殊含义的标识符,不作他用,有分隔语法的作用;2标识符表示各种名字;3常量整型、实型、布尔型、字符型;4运算符算术、逻辑、关系运算符;5界符包括.,;,,,:,,等,有时也把运算符称作界符
三、词法分析程序的设计原则1)把扫描器当作语法分析的一个过程,当语法分析需要一个单词时,便调用扫描器2扫描器从初态出发,当识别一个单词后便进入终态,同时输出二元组
四、词法分析程序的输出词法分析程序扫描后输出单词序列表示为如下二元组形式二元组(单词种别,单词自身值或指针)例若规定标识符、常数、基本字、运算符、界符的种别用整数编码分别为
1、
2、
3、
4、5,则对程序段“ifk=7thena:=b;”,则其经扫描器扫描后输出的单词符号及其二元组为基本字if3,’if’标识符k1,指向k的符号表入口的指针等号=4,‘=’常数7(2,‘7’)基本字then3,’then’标识符a1,指向a的符号表入口的指针赋值号:=4,’:=’标识符b1,指向b的符号表入口的指针分号;5,’;’
五、词法分析程序__设计的优点1使整个编译程序的结构更加简洁、清晰、条理化;2改进了编译程序的效率;3)增加了编译程序的可移植性
4.2单词的描述工具
一、正规文法3型文法,又称右线性文法或正规文法RegularGram__rs,其表达式形如A→aB或A→a正规文法描述的语言是VT*上的正规集绝大部分程序设计语言的单词都能用正规文法来描述
二、正规式和正规集
1、定义正规式也称正规表达式,是表示正规集的工具,递归定义如下1ε和φ都是字母表上的正规式,表示正规集为{ε}和φ;2a∈,a是上的正规式,表示正规集{a};3假定e
1、e2都是上的正规式,对应正规集为Le
1、Le2,则e
1、e1|e
2、e
1.e
2、e1*也是正规式,分别表示的正规集为Le1,Le1∪Le2,Le
1.Le2,和Le1*;4仅由有限次运用上述步骤产生的表达式才是上的正规式,仅由这些正规式产生的字集才是上的正规集例:设={0,1},则有正规式正规集0{0}0|1{0,1}01{01}1*{ε,1,11,
111...}0|1*{ε,0,1,01,
10......}
3、正规式服从的代数规则设r,s,t为正规式,则正规式服从如下的代数规则r|s=s|r或满足交换律r|s|t=r|s|t或满足结合律rst=rst连接满足结合律rs|t=rs|rt分配律rε=εr=rε是连接的恒等元素注意rssrr|strs|rt
三、正规式和正规文法的等价性任意一个正规语言既可以由正规式定义,也可由正规文法来定义正规式和正规文法之间可进行等价转换
1、正规式转换成正规文法将=VT上的正规式r换成正规文法G=VN,VT,P,S方法如下1令S→r2对形如A→xy的产生式,可分解成A→xB,B→y3对形如A→x*y的产生式,可分解成为A→xA,A→y4对形如A→x|y的产生式,可分解为A→x,A→y反复利用上述规则,直至所有产生式中最多只含一个终结符例将R=aa|d*转换成相应的正规文法解步骤如下1S→aa|d*2S→aB,B→a|dB,B→ε3S→aB,B→aB,B→dB,B→ε相应的正规文法如3式所示,即G[S]:S→aBB→aB|dB|ε
2、正规文法转换成正规式将正规文法G=VN,VT,P,S换成=VT上的正规式r的转换规则1)将产生式A→xBB→y合写为A=xy;2)将产生式A→xAA→y合写为A=x*y;3)将产生式A→xA→y合写为A=x|y反复利用上述规则,直至只剩下一个由开始符定义的产生式,且该产生式右部不含一个非终结符例将正规文法G[S]:S→dA|eBA→aA|bB→bB|c换成正规式解步骤如下1由A→aA|b,将A转换成a*b;由B→bB|c,将B转换成b*c;2由S→dA|eB,将S可转换成da*b|eb*c故所求正规式为R=da*b|eb*c授课顺序5教学目的让学生掌握DFA和NFA的定义,了解DFA和NFA的表示方法,掌握NFA与DFA的等价转换方法及DFA的化简方法教学重点DFA和NFA的定义、等价转换及DFA的化简教学难点DFA和NFA的等价转换、DFA的化简授课学时2学时教学方式多媒体讲授教学内容
4.3有穷自动机
一、概述有穷自动机FiniteAuto__ta:可准确识别正规集(即识别正规文法所定义的语言和正规式所表示的__)的一种装置它分为两类:1确定的有穷自动机DeterministicFiniteAuto__ta,简称DFA2不确定的有穷自动机NondeterministicFiniteAuto__ta,简称NFA
二、确定的有穷自动机DFA
1、定义确定的有穷自动机表示为一个五元组M=K,,f,S,Z,其中1K是一有穷状态集;2是一有穷字母表,称输入符号字母表;3f是转换函数,是在K→K上的映射如fki,a=kj;4S是唯一的一个初态;5ZK,是一终态集,终态也称结束态或可接受态
2、DFA的状态图表示假设DFAM有m个状态,n个输入字符,则1状态图有m个结点,每个结点最多有n条弧射出;2有唯一的一个初态结点,前面冠以“=”或“-”标记;3有若干终态结点,用双圆圈或“+”标记;例下图所示DFA可识别正则集Lab*c,如串abbc可被认别
3、DFA的矩阵表示1行表示状态;2列表示输入字符则;3矩阵元素表示相应状态行和输入字符列下新状态(即k行a列为fk,a的值);4用“=”标记行或第一行表示初态;5终态行右端标以1,非终态行右端标以0例上图也可表示为矩阵形式abcSA0AAB0B
14、转换函数定义扩充方便起见,对DFA中转换函数定义进行扩充f是转换函数,是在K*→K上的映射,有1fk1,ε=k12fk1,aα=ffk1,a,α其中,k1∈K,a∈,α∈*
5、接受识别设DFA=K,,f,S,Z,若fS,α=P∈Z,则称符号串α∈*可被该DFA接受识别例:试证串abbc可被图示DFA识别证fS,abbc=ffS,a,bbc=ffA,b,bc=ffA,b,c=fA,c=B由于B为终态,得证
6、语言确定有穷自动机M所接受的所有符号串集称为此自动机可接受的语言LM
7、重要结论1上的一个字符串集V*是正规集,当且仅当存在着一个上的确定有穷自动机M,使得V=LM2DFA的确定性表现在状态转换函数是单值函数,即fk,a唯一确定一个后继状态
二、不确定的有穷自动机NFA
1、定义不确定的有穷自动机表示为一个五元组NFAM=K,,f,S,Z,其中1K是一有穷状态集1是一有穷字母表,称输入符号字母表3f是转换函数,是在K*→K的子集上的映射4S是初态集5ZK,是一终态集,终态也称结束态或可接受态例状态图表示的NFA如下状态图表示的DFA如下
4、转换函数定义扩充因为f是转换函数,是在K*→K的子集上的映射,有1fk,aα=fk1,α∪fk2,α...∪fkn,α其中,ki∈K,a∈,α∈*,且fk,a={k1,k2,....kn}
5、接受识别设NFA=K,,f,S,Z,如果z0∈fS,α且z0∈Z,则称符号串α∈*可被该NFA接受识别例:试证串abc可被图示NFA识别证fS,abc=fA,bc=fA,c∪fC,c=B,又因为B∈终态集{B},得证
6、语言不确定有穷自动机M所接受的所有符号串集称为此自动机可接受的语言LM
7、重要结论1)对于每个NFAM,必存在一个DFAM1,使得LM=LM1;2对于任何两个有穷自动机M1和M2,若LM1=LM2,则称有穷自动机M1和M2等价
三、NFA到DFA的转换
1、相关概念ε闭包ε-closureI表示状态集I中任何状态A经任意条ε弧而能到达的状态集状态集I的a弧转换表示为J=moveI,a,J是所有那些从I中任一状态经一条a弧而到达的后继状态全体令:Ia=ε-closureJ=ε-closuremoveI,a例对下图NFA,取I={S,1},则ε-closureI={S,1,2},J=moveI,0={1},I0=ε-closureJ={1,2}
2、NFA的确定化用造表法将NFA确定化过程如下0表的第0行和第0列作标识行列的值1将ε-closureI作为表中第1行第1列1假定={a1,a2,...an},设第i行第一列已确定状态集为I,则置该行第i列为Iai,如Iai未曾在任何行第一列出现过,则将Iai加入下一空行i+1的第一列,并在第0列标记为Ti+13反复重复第1步,直至无新状态出现为止4重新命名新状态例将上图所示NFA确定化0-3步造表整理后得重新命名新状态得DFA如下图所示
四、DFA的化简
1、相关概念1一个DFA是化简最小化了的,即它没有多余状态且其状态中没有相互等价的2多余状态是指从自动机的开始状态出发,任何输入串也不可达的状态
2、状态等价在DFA中,两个状态s和t等价的条件是1一致性条件状态s和t必须同时为可接受态和不可接受态2蔓延性条件对于所有输入符号,状态s和t必须转换到等价的状态里
3、DFA最小化处理对DFA最小化的本质消除多余状态、合并等价状态DFA最小化具体过程用分割法将不含多余状态的DFA分成一些不相交的子集,使得任何两个不同的子集中的状态都是可区别的,而相同子集中状态是等价的分割时,首先将DFA状态分成终态子集和非终态子集,再根据输出弧所达到状态的性质逐步细分例对左图所示DFA最小化解P0={{1,2,3},{4,5,6,7}}根据各子集输出弧0和1所达到状态是否为终态,划分为P1={{1},{2},{3},{4,5,6,7}},最小化后DFA如上右图所示授课顺序6教学目的让学生掌握正规文法、正规式和有穷自动机的等价转换方法,了解词法分析程序自动构造工具LEX的工作原理及基本使用方法教学重点正规文法、正规式和有穷自动机的等价转换教学难点正规文法、正规式和有穷自动机的等价转换授课学时2学时教学方式多媒体讲授教学内容
4.4正规式和NFA的等价性
一、概述对于上的每个NFAM,可以构造一个相应的上的正规式R,使得LR=LM对于上的每个正规式R,可以构造一个相应的上的NFAM,使得LR=LM
二、为NFAM构造相应的正规式R首先,引入两个新结点x,y;x经ε弧到所有初态,所有终态经ε弧到y;然后,再用如下消解规则消去除x,y外的所有结点,最后x,y间弧上的标记串就是所求正规式例给出与图示NFAM等价的正规式R解R=0|1*00|110|1*
三、由正规式R构造相应的NFAN其过程与上述过程相反用如下规则构造NFA对R=ε、R=a和R=st(其中,s、t分别为正规式)分别构造:对R=s|t和R=s*分别构造例为R=a|b*abb构造NFAN,使LR=LN解与R=a|b*abb等价的NFAN如下
4.5NFA和正规文法的转换
一、概述对于上的每个NFAM,可以构造一个相应的上的正规文法G,使得LG=LM对于上的每个正规文法G,可以构造一个相应的上的NFAM,使得LM=LG
二、构造正规文法G等价的NFAM1为G中每个非终结符生成M一个状态,开始符为初态2增加一新状态Z,做为NFAM的终态3对形如A→aB或A→B的产生式,构造M的转换函数fA,a=B或fA,ε=B4对形如A→a的产生式,构造M的转换函数fA,a=授课顺序7教学目的让学生了解自顶向下语法分析思想,掌握LL1文法的概念及判别方法教学重点FIRSTα集和FOLLWA集的计算、LL1文法的判别教学难点FIRSTα集和FOLLWA集的计算、LL1文法的判别授课学时2学时教学方式多媒体讲授教学内容第五章自顶向下语法分析方法语法分析是编译程序的核心部分,其作用是检查由扫描器输出的单词符号序列是否是符合该语言文法的句子语法分析器的输入是单词符号序列,输出是分析树语法分析方法(当今编译程序构造的实用方法)
1、自顶向下分析确定的自顶向下分析(递归下降法、预测分析法)、不确定带回溯的自顶向下分析
2、自底向上分析算符优先分析、LR分析(LR0分析、SLR1分析、LR1分析、LALR0分析)
5.1自顶向下分析思想
一、自顶向下的分析方法的基本思想面向目标寻找输入符号串最左推导,试图根据当前输入单词判断使用哪个产生式基本过程是从根开始,按与最左推导相对应的顺序,构造输入符号串的分析树例根据下面文法G[E],对符号串i+i*i进行分析,并按照最左推导构造分析树E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→E|i解与最左推导对应的语法树
二、候选式的确定与回溯给定文法S→cAdA→ab|a,判断句子cad是否该文法定义语言的句子产生式候选式的选择与回溯Backtracking当要进行关于某个语法变量的推导时,希望能够根据当前符号确定候选式
三、FIRSTα集
1、定义对于α、β∈VT∪VN*,定义α的首符号集为FIRSTα={a|α=*aβ,a∈VT}
2、各文法符号的FIRST集各文法符号的FIRST集计算方法如下1对X∈VT,FIRSTX={X};2对X∈VN,且X→a…,a∈VT,则a∈FIRSTX;3对X∈VN,且X→ε,则ε∈FIRSTX;4对X∈VN,Y1,Y2,…都∈VN,且X→Y1Y2…Yn,则
①当Y1不能=*ε时,FIRSTX=FIRSTY1;
②当Yi都能=*εi∈[1,n-1]时,FIRSTX={FIRSTYi的并集-{ε}}∪FIRSTYj,其中i∈[1,n-1],j∈[1,n]即当规则右部Y1Y2…Yn只有前面部分能推导出ε时,FIRSTX中不含ε
③当Yi都能=*εi∈[1,n]时,FIRSTX=FIRSTYi的并集,其中i∈[1,n]即当规则右部Y1Y2…Yn都能推导出ε时,FIRSTX中才会含ε因为FIRSTYi中都含ε
④对X∈VN,重复如上述过程,直到所有FIRST集不变为止
3、符号串的FIRST集计算符号串(设串α=X1X2…Xn)的FIRST集方法如下1当X1不能=*ε时,则FIRSTα=FIRSTX1即当串α的第一个符号X1不能推导出ε时,只考虑FIRSTX12当X1能=*ε,但存在Xi不能=*εi∈[2,n]时,则FIRSTα=FIRSTXi的并集-{ε}即当串α的第一个符号能推导出ε,但串中存在某个符号不能推导出ε时,FIRSTα不含ε3当X1能=*ε,其余所有Xi也都能=*εi∈[2,n]时,则FIRSTα=FIRSTXi的并集即当串α的所有符号都能推导出ε时,FIRSTα才含ε例计算表达式文法的语法符号的FIRST集G[E]E→TEE→+TE’E→εT→FTT→*FT’T→εF→EF→i解FIRSTE={+,ε}FIRST+={+}FIRSTT={*,ε}FIRST*={*}FIRST={}FIRST={}FIRSTi={i}FIRSTF={,i}FIRSTT=FIRSTF={,i}FIRSTE=FIRSTT={,i}若换成T→T’FE→E’T则FIRSTT={FIRSTT’-{ε}}∪FIRSTF={,i,*}FIRSTE={FIRSTE’-{ε}}∪FIRSTT={,i,+,*}
四、FOLLOWA集
1、定义对于A∈VN定义A的后续符号集FOLLOWA={a|SuAβ,a∈VT,且a∈FIRSTβ,u∈VT,*,β∈V+};若β=*ε,则#∈FOLLOWA也可以定义为FOLLOWA={a|S…Aa…,a∈VT}若有S=*…A,则规定#∈FOLLOWA
2、计算FOLLOW集对于所有出现在规则右部的非终结符,重复进行以下计算1将#加入到FOLLOWS,其中#为句子的结束符2若A→αBβ,且β不能=*ε,则FOLLOWB=FIRSTβ3如果A→αB,则FOLLOWB=FOLLOWA4如果A→αBβ,且β=*ε,则FOLLOWB={FIRSTβ-{ε}}∪FOLLOWA注意只考虑FIRSTβ中非空元素例求下列表达式文法G[E]的语法变量(即非终结符)的FOLLOW集G[E]E→TEE→+TE’|εT→FTT→*FT’|εF→E|i解FOLLOWE=FIRST∪{#}={,#}联FOLLOWE=FOLLOWE={,#}FOLLOWT={FIRSTE-{ε}}∪FOLLOWE∪FOLLOWE={+,,#}FOLLOWT=FOLLOWT={+,,#}FOLLOWF={FIRSTT-{ε}}∪FOLLOWT∪FOLLOWT={*,+,,#}
五、SELECT集对于G的每个非终结符A的候选式A→α,1若α不能=*ε,则SELECTA→α=FIRSTα2若α=*ε,则SELECTA→α={FIRSTα-{ε}}∪FOLLOWA
5.2LL1文法的判别
一、LL1文法的定义LL1文法表示了自顶向__法能够处理的一类文法第一个L表示从左向右扫描输入符号串,第二个L表示生成最左推导,1表示读入一个符号可确定下一步推导G是LL1文法的充要条件对于G的每个非终结符A的任何两个不同的候选式A→α|β,满足SELECTA→α∩SELECTA→β=φ其中,α、β不能同时=*ε
二、LL1文法的判别
1、判别原则文法G是LL1文法的充要条件
2、判别步骤1)画出各非终结符能否推导出ε的情况表;2)用定义法或关系图法计算FIRST、FOLLOW集;3)计算各规则的SELECT集;4)根据同一个左部的规则其SELECT集是否相交来判断给定文法是否为LL1文法
三、用关系图计算FIRST集
1、终结符a结点用符号本身标记,非终结符A结点用FIRSTA标记;
2、对A→αXβ且α=*ε,则从A到X连一条箭弧注意A→aB或A→a已包含在其中;
3、凡从FIRSTA结点出发有路径可达到的所有终结符都为FIRSTA的成员;
4、再根据A能否推导出ε的情况,若能推导出ε,则将ε加入FIRSTA
四、用关系图计算FOLLOW集
1、终结符a和#结点用符号本身标记,非终结符A结点用FIRSTA或FOLLOWA标记;
2、从开始符S的FOLLOWS到#号连一条箭弧;
3、对规则A→αBβX且β=*ε,则从FOLLOWB到FIRSTX连一条箭弧,当X∈VT时,则与X相连;
4、对A→αBβ且β=*ε,则从FOLLOWB到FOLLOWA连一条箭弧;
5、对每一个FIRSTA结点,若有规则A→αXβ,且α=*ε,则从FIRSTA到FIRSTX连一条箭弧;
6、凡从FOLLOWA结点出发有路径可到达的所有终结符或#,都为FOLLOWA的成员;
五、例题例1判别下列G[S]是否为LL1文法,要求用关系图求FIRST集和FOLLOW集G[S]S→AB|bCA→ε|bB→ε|aDC→b|ADD→aS|c解1画出非终结符推导ε的情况表,如下图1所示2用关系图计算各非终结符的FIRST集,如下图
2、图3所示图1图2图33用关系图求出FOLLOW集,如下图
4、图5所示图4图54根据前述三张表计算SELECTT集如下5判别是否为LL1文法由于SELECTS→AB∩SELECTS→bC={b}≠φ,SELECTC→b∩SELECTC→AD={b}≠φ故G[S]不是LL1文法例2LL1文法例子G[E]E→TEE→+TE|εT→FTT→*FT|εF→E|i解由于SELECTE→+TE={+}SELECTE→ε={#,}SELECTT→*FT={*}SELECTT→ε={+,#,}SELECTF→E={}SELECTF→i={i}SELECTE→+TE∩SELECTE→ε={+}∩{#,}=φSELECTT→*FT∩SELECTT→ε={*}∩{+,#,}=φSELECTF→E∩SELECTF→i={}∩{i}=φ故G[E]是LL1文法例3非LL1文法例子对下列文法G[S]作输入串cad的分析G[S]S→cAdA→ab|a结论非LL1文法具有不确定性不确定性的解决方法
(1)采用带回朔的(即确定的)自顶向下分析法过于复杂,代价很高,实用编译程序几乎不用
(2)改写文法将非LL1文法改写为等价的LL1文法授课顺序8教学目的让学生掌握非LL1文法到LL1文法的转换方法、了解递归子程序分析法的基本原理,掌握预测分析方法及应用教学重点非LL1文法到LL1文法的转换、预测分析表的构造、预测分析方法的应用教学难点非LL1文法到LL1文法的转换、预测分析方法的应用授课学时2学时教学方式多媒体讲授教学内容
5.3某些非LL1向LL1文法的等价转换非LL1的文法不能用确定的自顶向下分析法可通过消除左递归、提取左公共因子的方法将非LL1文法转换成LL1文法
一、提取左公共因子
1、左公共因子引发的问题文法G中有形如A→αβ|αγ的规则时,会导致FIRSTαβ与FIRSTαγ相交,使得SELECTA→αβ∩SELECTA→αγ≠φ,则G必为非LL1文法
2、提取左公共因子的方法
(1)特殊形式将形如A→αβ|αγ的规则先提取左公共因子A→αβ|γ,再引进新非终结符A’,改为A→αA’和A’→β|γ
(2)一般形式将形如A→αβ1|αβ2|…|αβn的规则改写为A→αA’和A→β1|β2|…|βn
(3)__将形如A→αβ1|αβ2|…|αβn|γ1|γ2|…|γm的规则改写为A→αA’|γ1|γ2|…|γm和A→β1|β2|…|βn例1(显式)G[S]S→a__|aS|ε解提取左公共因子S→aSb|ε|ε,引进新非终结符A得S→aSA|ε和A→b|ε例2(隐式)G[A]A→ad|BcB→aA|bB解作变换A→ad|aA|bBc即A→ad|aAc|bBc,提取左公共因子得A→ad|Ac|bBc引进新非终结符A’得G’[A]A→aA’|bBcA’→d|AcB→aA|bB显然,改造后的G’[A]为LL1文法因为SELECTA→aA’∩SELECTA→bBc=φ,SELECTA’→d∩SELECTA’→Ac=φ,SELECTB→aA∩SELECTB→bB=φ
3、变换后的压缩通过提取左公共因子和引进新非终结符,作变换后,可能使原来某些规则无用,必须消除掉例3对G[S]S→aSd|AcA→aS|b解通过提取左公共因子和引进新非终结符作等价变换后得S→a__|bcB→d|cA→aS|b此时,A不可达,则以A为左部的规则必须消去
二、消除左递归
1、左递归引发的问题
(1)无法根据左递归文法进行自顶向下的分析;
(2)产生回溯现象例如文法G[S]S→Sa|b对baa进行识别出现的问题;
(3)递归分析时死循环,无法编递归子程序
2、左递归的类型
(1)直接左递归A→Aβ
(2)间接左递归A→Bβ且B→Aα其中A、B∈VN,α、β∈V*
三、左递归的消除
1、直接左递归的消除方法将A→Aα|β替换为A→βA’和A’→αA’|ε例表达式文法E→E+T|TT→T*F|FF→E|i消除直接左递归后为E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→E|i
2、间接左递归的消除先将间接左递归化为直接左递归,再消除例G[S]S→Ac|cA→Bb|bB→Sa|a1将B的定义代入A产生式得A→Sab|ab|b2将A的定义代入S产生式得S→Sabc|abc|bc|c3消除直接左递归S→abcS’|bcS’|cS’ S’→abcS’|ε4删除“多余的”产生式A→Sab|ab|b和B→Sa|a5结果G[S]S→abcS’|bcS’|cS’ S’→abcS’|ε
3、消除左递归的一般方法将产生式组A→Aα1|Aα2|…|Aαn|β1|β2|…|βn用产生式组A→β1B|β2B|…|βnB,B→α1B|α2B|…|αnB|ε代换其中B为新变量,相当于A’
4、消除左递归算法描述若非终结符排序为A1,A
2....An,则fori=1;i=n;i++{forj=1;j=i-1;j++{若Aj所有产生式为Aj→α1|α
2...|αk,则替换形如Ai→Ajβ的产生式中Aj,变为形如Ai→α1β|α2β...|αkβ的产生式即化间接左递归为直接左递归}消除Ai中一切直接左递归}删除无用规则例G[S]S→Qc|cQ→Rb|bR→Sa|a解不妨设非终结符排序为S、Q、R非终结符排序交换时,得不同文法,但各文法相互等价1将S产生式代入R产生式中R→Qca|ca|a2将Q产生式代入R产生式中得R→Rbca|bca|ca|a3消除左递归得R→bca|ca|aM和M→bcaM|ε4删除多余的产生式,结果为G[S]R→bca|ca|aMM→bcaM|ε同样,按R、Q、S排列可有S→abc|bc|cMM→abcM|ε和按R、S、Q排列有Q→cab|ab|bMM→cabM|ε
5.4确定的自顶向下分析法常用的确定的自顶向下分析法有递归下降分析法(递归子程序法)和预测分析方法递归子程序法
一、基本实现思想对应文法中的第一个非终结符编写一个递归下过程,每个过程的功能是识别由该非终结符推出的串,当某个非终结符的规则有多条时能够按LL1形式唯一确定候选规则进行推导
二、采用数据结构递归子程序法对每个过程可能存在直接或间接调用,通常需要在入口时需要保留某些信息,出口时恢复常用先进后出栈来处理
三、用递归子程序法构造语法分析程序过程1改造文法消除二义性、消除左递归、提取左因子;2求每个候选式的FIRST集和变量的FOLLOW集;3检查是不是LL1文法若不是LL1,说明文法的复杂性超过自顶向__法的分析能力,需要附加新的“信息”4按照LL1文法画语法图;5化简语法图;6按照语法图,为每个非终结符设置一个子程序事实上,如果有一个恰当的文法,可以直接根据每个语法变量的产生式设计相应的程序
四、优缺点分析
1、优点1直观、简单、可读性好;(2便于扩充
2、缺点1递归算法速度慢、占用空间多,其实现效率低;2处理能力相对有限,要求文法必须为LL1文法,所以通用性差;3难以自动生成预测分析法对于LL1型文法,可用预测分析法在使用预测分析法时,必须先将文法化为LL1型文法
一、预测分析器的构造预测分析器由三部份组成1预测分析表矩阵;2先进后出栈用来存放分析过程的语法符号;3预测分析程序
二、预测分析表
1、预测分析表为一个二维矩阵,其形式为M[A,a],其中A∈VN,a∈VT或#
2、若有产生式A→α,使得a∈SELECTA→α,则将A→α填入M[A,a]中书写时,通常省略规则左部,只填→α
3、对所有没有值的M[A,a]标记为出错例文法G[E]E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→E|i解计算G[E]的SELECT集SELECTE→TE’={,i}SELECTE’→+TE’={+}SELECTE’→ε={#,}SELECTT→FT’={,i}SELECTT’→*FT’={*}SELECTT’→ε={+,#,}SELECTF→E={}SELECTF→i={i}根据SELECT集构造G[E]的预测分析矩阵M[X,a]如下
四、预测分析程序
1、一些符号的约定#句子结束符;S文法开始符;a当前输入符号a,输入指针指向的符号;X工作栈栈顶符号
2、算法描述#,S进栈;//初始化工作do{X=当前栈顶符号;a=当前输入符号;ifX∈VT∪{#}{ifX==a{ifX!=#{将X弹出,且前移输入指针}}elseerror}else{ifM[X,a]==Y1Y2…Yk{将X弹出;依次Yk…Y2Y1将压入栈;}elseerror};}whileX!=#;
3、例根据上例中G[E]的预测分析矩阵M[X,a],对串w=i+i*i进行分析解对输入串w=i+i*i#的分析过程如下表所示(注意规则右部以逆序入栈)课堂作业对输入串w=i*i+i*i#作分析作业教材P99-101的
1、
2、4题,6题的
(1)
(2)
(3)小题授课顺序9教学目的让学生了解自底向上优先分析的基本思想,掌握优先关系、简单优先文法的定义、简单优先分析法、直观算符优先分析法、算符优先文法的定义教学重点优先关系表的构造、直观算符优先分析法的应用、算符优先文法的定义教学难点优先关系表的构造、直观算符优先分析法的应用授课学时2学时教学方式多媒体讲授教学内容第六章自底向上优先分析法
6.1概述
一、知识回顾
1、最左推导Left-mostDerive每次推导都施加在句型的最左边的语法变量上与最右归约对应
2、最右推导Right-mostDerive每次推导都施加在句型的最右边的语法变量上与最左归约(规范归约)对应,得规范句型
3、令G[S]是一文法,αβδ是文法G的一个句型,如果有S=*αAδ,且A=+β,则称β是句型αβδ相对于非终结符A的短语,如有Aβ,则称β是αβδ相对于非终结符A或相对于规则A→β的直接短语也叫简单短语
4、一个句型的最左直接短语称为该句型的句柄注意作为短语的β必须是需要分析的句型αβδ的一部分
5、规范归约设α为文法G的句子,如果1α=αn=αn-1=…=α2=α1=S;2对每个i1≤i≤n,αi-1是将句型αi中的句柄归约后得到的句型;则称由规范归约组成的序列αn,…,α1为α的规范归约序列例子一个简单的归约过程示例设文法为G[S]S→aAcBeA→Ab|bB→d解对句子abbcde的分析
二、自底向上分析
1、思想从输入串出发,反复利用产生式进行归约,如果最后能得到文法的开始符号,则输入串是句子,否则输入串有语法错误
2、核心寻找句型中的“句柄”进行归约用不同的方法寻找句柄,就可获得不同的分析方法
6.2简单优先分析法简单优先分析法的实现思想按所有文法符号包括非终结符和终结符之间的优先关系来确定句柄
一、优先关系X≡Y表示X和Y的优先关系相等;X≮Y表示X比Y的优先性小;X≯Y表示X比Y的优先性大
1、优先关系的定义X≡Y当且仅当G中存在规则A→XY…即XY并列出现X≮Y当且仅当G中存在规则A→…XB…且B=+Y…即X与非终结符B并列(位于最前的Y经过至少一步归约后得到的B)X≯Y当且仅当G中存在规则A→…BD…且B=+…X和D=*Y…即非终结符B与D并列(位于最后的X经过至少一步归约后得到B,位于最前的Y经过0步或多步归约后得到D)
2、例G[S]S→bAbA→B|aB→Aa文法符号间优先关系如下≡由bA有b≡A,由Ab有A≡b,由B有≡B,由Aa有A≡a,由a有a≡;≮因为ABAaBa…,ABAaaa…,Aa,故由bA有b≮,b≮a;因为BAaBaAaa…,BAaaa,故由B有≮A,≮,≮a;≯因为ABAaBa…,ABAaaa…,Aa,故由Ab有B≯b,≯ba≯b;故由Aa有B≯a,a≯a,≯a注意对于符号S和#作特殊处理,定义#优先级≮所有与之相邻符号所有与之相邻符号优先级≯#引入产生式S‘→#S#来判断与#相邻符号与#的优先关系,且约定#≡#对前例由#S有#≮S;由SbAb和#S有#≮b;由S#有S≯#;由SbAb和S#有b≯#综上所述得如下优先关系矩阵
二、简单优先文法的定义1任意两符号间最多只有一种优先关系成立;2在文法中任意两产生式没有相同的右部
三、简单优先分析法步骤1将输入符号串a1a2a3…an#依次入栈,直到栈顶符号优先级高于下一个待输入符2以栈顶符号ai为句柄尾,往下找句柄头ak(当ak-1≮ak时,终止查找),并将句柄归约为一个非终结符,将句柄出栈,非终结符入栈;若无句柄可归约则报错3重复
(1)和
(2)4当栈中只剩S时,分析成功,否则报错课堂练习根据前例对输入串b(aa)b#和b(aa)#用简单优先分析法进行分析
四、简单优先分析法优缺点准确、规范,分析效率低,实用价值不大
6.3算符优先分析法直观算符优先分析法
一、直观算符优先分析法中优先级和结合性的确定
1、算符优先文法只考虑算符广义为终结符之间的优先关系
2、例G[E]E→E+E|E*E|i,对3+4*5#分析的过程如下3+4*5E+4*5E+E*5E+E*EE+EE思考为何不将E+E归约成E关键在于如何确定算符间的优先级和结合性
3、直观算符优先分析法中优先级和结合性的确定方法人为指定例对文法E→E+E|E-E|E*E|E/E|E^E|E|i,我们可指定优先级和结合性如下1作运算对象的终结符i优先性最高;2^右结合,且高于其它运算符2^3^2,有^≮^^≯其它运算符,其它运算符≮^;3*,/高于+-且左结合有*≯**≯/*≯+*≯-/≯*/≯//≯+/≯-,+≯-+≯+-≯+-≯-…4括号的优先性大于括号外运算符,小于括号内运算符,内括号优先性大于外括号;5对于#可#≮所有与之相邻符号;所有与之相邻符号优先级≯#引入产生式E‘→#E#来判断与之相邻符号对G[E‘]E’→#E#E→E+E|E-E|E*E|E/E|E^E|E|i有
二、算符优先算法设置两个工作栈一个是用来寄存运算符的OPTR,另一个为用来寄存操作数或结果的OPND算法描述如下1首先置操作数栈OPND为空,将#入OPTR栈2依次读入表达式中每个单词,若是操作数则进OPND栈,若是运算符则转
[3]3查算符优先关系表,将当前读入的运算符θ2与OPTR栈顶元素θ1进行比较,若θ1θ2,则θ2进栈,转2;若θ1=θ2如θ2为#,则分析成功;否则,OPTR栈顶元素θ1出栈,并转(
(3);若θ1>θ2则出栈OPND栈顶元素至b,又出栈其栈顶元素至a,出栈OPTR栈顶元素至t,进行运算r=atbt为运算符,并将结果r存入栈OPND后转(
(2)若θ1和θ2之间无优先关系,则报错例根据前例文法,对5*1+4作直观算符优先分析,其过程如下算符优先文法如果文法G=(VN,VT,P,S)中不存在形如A→…BC…的产生式,其中B、C为非终结符,则称之为算符文法OG—operatorGram__r即如果文法G中不存在具有相邻非终结符的产生式,则称为算符文法
一、算符间的优先关系设G=(VN,VT,P,S)为OG,则定义:a≡bA→…ab…∈P或者A→…aBb…∈Pa≮A→…aB…b∈P且B=+b…或者B=+Cb…a≯A→…Bb…b∈P且B=+…a或者B=+…aC
二、算符优先文法设G=(V,T,P,S)为OG,如果ab∈VTa≡ba≮ba≯b至多有一个成立,则称之为算符优先文法OPG—OperatorPre__den__Gram__r在无ε产生式的算符文法G中,如果任意两个终结符之间至多有一种优先关系,则称为算符优先文法授课顺序10教学目的让学生掌握算符优先关系表的构造、算符优先分析算法、优先函数的计算,了解算符优先分析法的局限性教学重点算符优先关系表的构造、算符优先分析法的应用、优先函数的计算教学难点算符优先关系表的构造、算符优先分析法的应用、优先函数的计算授课学时2学时教学方式多媒体讲授教学内容算符优先关系表的构造
一、由定义直接构造优先矩阵对语法变量A定义
1、FIRSTVTA={b|A+b…或者A+Cb…}
2、LASTVTA={b|A+…b或者A+…bC}则对产生式A→X1X2…Xn按如__法构造各文法符号对之间的优先关系后填入算符优先关系表1如果XiXi+1∈VTVT则Xi≡Xi+12如果XiXi+1Xi+2∈VTVNVT则Xi≡Xi+23如果XiXi+1∈VTVN则a∈FIRSTVTXi+1,Xi≮a4如果XiXi+1∈VNVT则a∈LASTVTXi,a≯Xi+1例文法G[E‘]E’→#E#E→E+T|TT→T*F|FF→P^F|PP→E|i则求出非终结符的FIRSTVT、LASTVT集现对形如A→…aB…的规则根据FIRSTVT集求≮关系,对形如A→…Bb…的规则根据LASTVT集求≯关系,如下表由定义直接求出前例的优先矩阵为
二、用算法构造优先矩阵
1、优先矩阵的构造算法基于两条原则1若有规则A→a…或A→Ba…则a∈FIRSTVTA;2若a∈FIRSTVTB且有规则A→B…则a∈FIRSTVTA;
2、求FIRSTVT集的算法步骤先设立一个布尔数组F[Aa],其值为真时,当且仅当a∈FIRSTVTA,则第1步按原则1对每个数组元素F[Aa]置初值,并对F[Aa]初值为真的符号对Aa入栈;第2步处理栈当栈不空时,弹出栈项元素Ba,再按原则2,对形如A→B…的规则若有F[Aa]为假,则使其变为真,再让Aa入栈;第3步重复至栈空为止
3、求FIRSTVT集的算法描述voidinsertAa{if!F[Aa]then{F[Aa]=1;pushAatostack;}}void__in{for每一个非终结符A和终结符aF[Aa]=0;for每一个形如A→a…或A→Ba…的规则insertAa;whilestack不空{opBa;for每一个形如A→B…的规则insertAa;}}对前例G[E’]E’→#E#E→E+T|TT→T*F|FF→P^F|PP→E|i对各非终结符第一次扫描规则后,栈初值如下6pi5p4F^3T*2E+1E’#对栈项6pi,由规则F→PT→FE→T,使6依次变为FiTiEi当Ei出栈后,无入栈项,此时栈顶为5p同理,可得下述栈项4F^、3T*、2E+、1E’#最后,当E’#出栈后,无入栈项,栈为空
4、根据算法求FIRSTVT集凡在栈中出现过的Aa,其F[Aa]值必为1根据各个A的F[Aa]值,即可求出FIRSTVTA对前例,有
5、由关系图求FIRSTVT集
(1)图中结点为FIRSTVTA和a;
(2)对形如A→a…或A→Ba…的规则从FIRSTVTA连弧到a;
(3)对形如A→B…的规则从FIRSTVTA连弧到FIRSTVTB;
(4)凡是从FIRSTVTA经所有路径可达到a,都有a∈FIRSTVTA对前例按关系图求出各非终结符的FIRSTVT如下用类似方法求出各非终结符的LASTVT集
6、构造优先矩阵的算法voidtable{for每个规则X1X2…XnAfork=1;kSPAN{ifXkXk+1∈VTVTXi≡Xi+1;ifkXkXk+1Xk+2∈VTVNVTXk≡Xk+2;ifXkXk+1∈VTVNforFIRSTVTXk+1中每个bXk≮b;ifXkXk+1∈VNVTforLASTVTXk+1中每个aa≯Xk+1;}}用算法求出优先矩阵为算符优先分析算符优先分析和规范归约的核心均为寻找句柄规范归约的句柄是“最左直接短语”算符优先分析的句柄是“最左素短语”
一、素短语与最左素短语
1、什么是素短语?S=*αAβandA=+γ,γ至少含一个终结符,且不含更小的含终结符的短语,则称γ是句型αγβ的相对于变量A的素短语句型的至少含一个终结符且不含其它素短语的短语最左边的素短语称为最左素短语
2、例E→T+E|TT→T*F|FF→E|id解句型T+T*F+i的短语有T*F,i,T*F+iT+T*F+i;其中的素短语为T*F和i;
3、T*F为最左素短语,是被归约的对象课堂作业按照文法E→E+E|E*E|E|id,求i+E*i+i的短语和素短语解句型i+E*i+i的短语i,E*iiii+E*i和i+E*i+i;其中的素短语为iii
3、最左素短语总结设句型的一般形式为#N1a1N2a2…Nnan#其中Ni∈VN∪{ε}ai∈VT,则它的最左素短语是满足下列条件的最左子串NiaiNi+1ai+1…NjajNj+1,其中ai-1≮aiai≡ai+1≡…≡aj-1≡aj,aj≯aj+1
二、算符优先分析法的实现
1、分析算法描述设单元a中存放当前输入符,S为一个符号栈,则1将当前输入符存放到a中,将#入符号栈2将栈顶第一个终结符b与a比较如果b≡a,而b==#且栈中只剩一个非终结符时,则成功;否则a入栈;如果b≮a则a入栈;如果b≯a在栈顶寻找最左素短语,并将最左素短语归约为一个非终结符;如果文法中找不到相应规则,则出错;3重复2至成功或失败
2、例文法G[E]E→#E#E→E+T|TT→T*F|FF→P^F|PP→E|i,其优先矩阵为对句子i+i作规范归约和算符优先分析的语法树比较对串i+i#规范归约的过程如下对串i+i#算符优先分析的过程如下现取i分别为
3、
2、4,则有串3+2*4#,对该串进行算符优先分析过程如下优先函数用优先函数代替优先矩阵可节约存储空间(由n+1n+1减少到2n+1
二、优先函数的定义优先函数用值为整数的两个函数f和g来表示,其中f和g满足如下条件若a≡b则令fa=gb;若a≮b则令faSPAN;若a≯b则令fagb
三、优先函数的构造
1、由定义直接构造Floyed算法根据各终结符对的优先关系,构造f和g步骤如下第1步对终结符a含#,令fa=ga=1或其它常整数再对优先关系矩阵逐行扫描重复2-4步第2步若a≯b而fa=gb,则令fa=gb+1;第3步若a≮b而fa=gb,则令gb=fa+1;第4步若a≡b而fa≠gb,则令min{gbfa}=__x{gbfa};第5步重复2-4步,直到过程收敛若对优先关系矩阵逐行扫描,扫描矩阵一遍相当于进行一次迭代重复2-4步过程中出现了大于2n的值,表明该优先文法不存大算符优先函数
2、例子对前例的表达式文法,根据优先矩阵,其优先函数的计算过程如下
(1)扫描第一行+≯+f+=g++1=2;+≮*g*=f++1=3;+≮^g^=f++1=3;+≮igi=f++1=3;+≮g=f++1=3;+≯满足f+g;+≯#满足f+g#;
(2)扫描第二行*≯+f*=g++1=2;*≯*f*=g*+1=4;*≮^g^=f*+1=5;*≮igi=f*+1=5;*≮g=f*+1=5;*≯满足f*g;*≯#满足f*g#;
(3)扫描第三行^≯*f^=g*+1=4;
(4)扫描第四行i≯^fi=g^+1=6;
(5)扫描第五行≮+g+=f+1=2;
(6)扫描第六行≯^f=g^+1=6;第一遍扫描完关系矩阵后,将各f、g函数的最大值填入下表再用相同方法处理第二遍、第三遍…扫描,直到各f、g函数的最大值不再变化(即为所求)才终止扫描注意实际迭代过程中,每次只需考虑最新变化了的函数
3、由关系图构造优先函数根据优先矩阵按如下步骤构造关系图第1步对所有终结符a含#,用带和下标的fa和ga作结点,构造2n个结点;第2步若a≯b或a≡b则从fa连弧到gb;若a≮b或a≡b则从gb连弧到fa;第3步从每一个结点出发所能到达的结点个数(含本身),即为该结点对应的优先函数值第4步对优先函数按优先矩阵检查一遍,若不满足优先矩阵中优先关系,则关系图中存在回路,说明不存在优先函数例1对下面优先矩阵利用关系图求优先函数优先矩阵优先函数优先关系图例2对下面优先矩阵利用关系图求优先函数优先矩阵优先函数优先关系图该例中由于优先函数值都相等,对应优先关系为a≡a、a≡b、b≡a、b≡b显然不满足优先矩阵中优先关系,即关系图中存在回路,所以优先矩阵不存在优先函数
四、优先函数和优先矩阵的关系
1、一个优先关系矩阵对应的优先函数不唯一(各函数值加上同一常数后,优先关系不变);
2、所表示的优先关系唯一的矩阵不一定存在优先函数
五、优先函数的缺点当两个终结符对之间无优先关系时,优先矩阵可以将相应元素置出错信息,而使用优先函数却无法识别这种情况,不能准确指出出错位置算符优先分析法的局限性
一、优点效率高,原因,只考虑终结符之间的优先关系确定句柄,而与非终结符无关
二、缺点由于去掉了单非终结符之间的归约如T→F,有可能将错误的句子识别为正确的例文法G[S]S→S;D|DD→DT|HH→a|ST→T+S|S要求现对给定串a+a#进行算符优先分析解其优先矩阵和对给定串a+a#的分析过程如下所示优先矩阵对给定串a+a#的分析过程可见用算符优先分析法对串a+a#能分析成功,但a+a#不是文法G[S]的句子这就是由于去掉了单非终结符之间的归约所造成的
三、适用范围表达式的语法分析作业教材P122的
1、
2、
3、4题授课顺序11教学目的让学生了解LR分析基本思想,掌握可归前缀和子前缀的计算方法及LR0分析方法教学重点可归前缀和子前缀的计算方法、LR0项目集规范族和分析表的构造、LR0分析方法的应用教学难点可归前缀和子前缀的计算方法、LR0项目集规范族和分析表的构造、LR0分析方法的应用授课学时2学时教学方式多媒体讲授教学内容第七章LR分析法
7.1LRLeft-Right分析概述
一、算符优先分析法存在的问题强调算符之间的优先关系的唯一性,这使得它的适应面比较窄;算法在发现最左素短语的尾时,需要返回来寻找对应的最左素短语头
二、LRk分析法L从左到右扫描输入符号,R最右推导对应的最左归约k超前读入k个符号,用以确定归约所用的规则
三、LR分析器工作示意图
四、LR分析表LR分析表包括action[sa]、goto[sX]表两部分,LR
0、SLR
1、LR
1、LALR1将以不同的原则构造这张分析表构造表时约定用sn表示将符号a、状态n压入栈;用rn表示用第n个产生式进行归约
7.2LR0分析法
一、引言LR0分析表构造的思想和方法是构造其他LR分析表的基础例:G[S]:S→aAcBe
[1]A→Ab
[2]A→b
[3]B→d
[4]S→S
[0]对句子abbcde分析过程如下:ab
[3]b
[2]cd
[4]e
[1]aAb
[2]cd
[4]e
[1]aAcd
[4]e
[1]aAcBe
[1]S
[0]S其中ab
[3]aAb
[2]aAcd
[4]aAcBe
[1]和S
[0]称为可归前缀(即规范句型中每步归约前句型的前部分串)可归前缀的前缀称活前缀如ab的活前缀有ε、a、ab
二、规范句型活前缀
1、活前缀和可归前缀的形式定义若S’=*αAγ=αβγ是G的拓广文法G’的一个规范推导则称αβ为可归前缀;若有串W是αβ的前缀,则称W是G的一个活前缀(S‘为文法拓广后的开始符,它只出现在规则左部)可归前缀是包含句柄的活前缀
2、说明
(1)LR分析时,把αβ的前缀W列出在符号栈中,一旦出现αβ即说明句柄形成,则用A→β归约
(2)规范规约所得到的规范句型的活前缀是出现在分析栈中的符号串,所以,活前缀中不会出现句柄之后的任何字符
三、识别活前缀的有穷自动机例:G[S]:S→aAcBe
[1]A→Ab
[2]A→b
[3]B→d
[4]S→S
[0]对句子abbcde其可归前缀为ab
[3]aAb
[2]aAcd
[4]aAcBe
[1]S
[0]对它们分别构造有穷自动机,然后,通过加入一开始状态X和一些ε弧,将各可归前缀的有穷自动机合并成一个有穷自动机NFA其中由S
[0]得到的终态称为句子识别状态,用*标记上图是通过一个句子abbcde的归约过程直观的看出其活前缀和可归前缀,然后构造其NFA进一步将其确定化为DFA如下思考如何求一个文法的所有可归前缀?
四、求可归前缀的一般算法
1、定义设文法G是一个2型文法,对于非终结符A,定义__LCA={α|S‘=*αAβα∈V*β∈VT*}LCA即A左边所出现的符号串集显然,LCA为所有不包括句柄的活前缀若有产生式A→γ即LCA.γ为一可归前缀习惯上将LCA写成[A]
2、推论若文法G中有产生式B→αAβ则有LCB.αLCA证S’=*δBγ=δαAβγ,显然有上推论成立
3、求可归前缀的一般方法利用此推论即可列出正规式方程组,求得所有的活前缀;再利用文法规则和所求得的活前缀,即可求得可归前缀例1对文法G[S]:S→SS→aAcBeA→AbA→bB→d求所有可归前缀.解列方程组如右[S]=ε[S]=[S]ε[A]=[S]a|[A]ε[B]=[S]aAc可解得[S]=ε[S]=ε[A]=a[B]=aAc
4、在LR0方法中,含句柄在内的活前缀计算方法LR
(0)CA→β=LCA.{β}对前例LR
(0)CS’→S=SLR
(0)CS→aAcBe=aAcBeLR
(0)CA→b=abLR
(0)CA→Ab=aAbLR
(0)CB→d=aAcd即所求可归前缀为SaAcBeaAbabaAcd例2对文法G[S‘]:S’→EE→aAE→bBA→cAA→dB→cBB→d求所有可归前缀和活前缀解列方程组如右[S]=ε[E]=[S]ε[A]=[E]a|[A]c[B]=[E]b|[B]c可解得[S]=ε[E]=ε[A]=a|[A]c=a|a|[A]cc=…=aε|c|cc|…=ac*[B]=b|[B]c=b|b|[B]cc=…=bε|c|cc|…=bc*则所求可归前缀有LR
(0)CS’→E=ELR
(0)CE→aA=aALR
(0)CE→bB=bBLR
(0)CA→cA=ac*cALR
(0)CA→d=ac*dLR
(0)CB→cB=bc*cBLR
(0)CB→d=bc*d即SaAcBeaAbabaAcd根据可归前缀构造文法对应NFA,再确定化为DFA
五、LR0分析表的构造以上方法从理论角度讲很严格,但实现复杂实际中常用构造项目集规范族的方法
1、LR0项目在文法G中每个产生式的右部适当位置添加一个圆点构成项目圆点左边代表该用产生式归约时句柄中已识别过的部份,右边为未识别过的部份例产生式S→aAcBe对应的6个项目是
[0]S→.aAcBe
[1]S→a.AcBe
[2]S→aA.cBe
[3]S→aAc.Be
[4]S→aAcB.e
[5]S→aAcBe.特别的,对A→ε有项目为A→.
2、项目的分类移进项目形如A→α.aβ;待约项目形如A→α.Bβ;归约项目形如A→αBβ.;接受项目形如S→α.
3、项目集规范族项目的__称项目集识别活前缀的DFA项目集状态的全体称项目集规范族
4、项目集的闭包(Closure)求法
(1)I的项目均在CLOSUREI中;
(2)若A→α.Bβ∈CLOSUREI,则每条形如B→.γ的项目也∈CLOSUREI;
(3)重复
(2)直到CLOSUREI中不出现新项目为止
5、后继项目和核A→α.Xβ的后继项目是A→αX.β新状态的初始项目称为核所有圆点不在规则右部最左位置S’→.S除外的项目都为核
6、闭包之间的转移goIX=CLOSUREJ={A→αX.β|A→α.Xβ∈I},其中J为I状态中圆点从X前移到X后形成的项目集状态状态转移的计算确定在某状态遇到一个文法符号后的状态转移目标,如图所示
7、计算LR0项目集规范族C(即分析器状态__)的算法LR0FUNC{C={closure{S→.S}};WhileC中有新项目出现{forI∈C,X∈VN∪VTif(goIX≠Φ且CgoIX)C=C∪goIX}例文法G[S]:S→E
[0]E→aA
[1]E→bB
[2]A→cA
[3]A→d
[4]B→cB
[5]B→d
[6]其规范项目集族构造如下
8、LR0分析表的构造算法设G’的LR0项目集规范族{I0I1…In}用i表示闭包Ii对应的分析器状态即相应的DFA状态则
(1)置0为开始状态;
(2)对Ii∈C ifA→α.aβ∈Ii且goIia=Ijaction[ia]=sj;ifA→α.Bβ∈Ii且goIiB=Ijgoto[iB]=j;ifA→α.∈Iifora∈VT∪{#}doaction[ia]=rj;ifS→S.∈Iiaction[i#]=acc;
(3)所有空格置error前例的LR
(0)分析表如下
六、LR0分析算法
1、算法描述
(1)置输入指针ip指向输入串的第一个符号;令s是栈顶状态,a是ip所指向的符号;将#压入符号栈,将开始状态0压入状态栈;
(2)重复执行如下过程if(action[sa]=sj){把符号a入符号栈,把状态j入状态栈;使ip指向下一个输入符号}elseif(action[sa]=rj){从栈顶弹出第j条规则右部串长|β|个符号;把归约得到的非终结符A压入符号栈;将goto[sA]的值j压入状态栈;并输出规则A→β}elseif(action[sa]=acc)return;elseerror;}
2、例子对文法G[S]:S→E
[0]E→aA
[1]E→bB
[2]A→cA
[3]A→d
[4]B→cB
[5]B→d
[6]对输入串bccd#分析如下
七、LR
(0)文法
1、冲突定义如果I中至少含两个归约项目,则称I有归约—归约冲突(Redu__/Redu__Conflict)如果I中既含归约项目,又含移进项目,则称I有移进—归约冲突(Shift/Redu__Conflict)如果I既没有归约—归约冲突,又没有移进—归约冲突,则称I是相容的Consistent,否则称I是不相容的
2、LR
(0)文法定义对文法G,如果I∈C都是相容的,则称G为LR0文法授课顺序12教学目的让学生掌握SLR1分析法和LR1分析法教学重点SLR1分析表的构造、LR1项目集规范族和分析表的构造、SLR1和LR1分析方法的应用教学难点LR1分析表的构造、LR1项目集规范族和分析表的构造、SLR1和LR1分析方法的应用授课学时2学时教学方式多媒体讲授教学内容
7.3SLR1分析法
一、LR0分析存在的问题例如教材P137的实型变量说明文法有移进归约冲突,不能用LR0分析再如下例也不能用LR
(0)分析G[S’]0S’→S1S→A2S→B3A→aAc4A→a5B→bBd6B→b
二、解决方法对含有移进—归约和归约—归约冲突的项目集I={X→α.bβ,A→γ.,B→δ.},若所有含有A和B的句型中,满足FOLLOWA∩FOLLOWB=Φ且FOLLOWA∩{b}=FOLLOWB∩{b}=Φ,则在状态I中面临输入符a的动作可由下面规定决策
1、若a=b,则移进;
2、若a∈FOLLOWA,则用A→γ.归约,若a∈FOLLOWB,则用B→δ.归约;
3、此外报错类似,可推出含多个移进项目和归约项目的一般情况能用上述方法解决冲突的文法称为SLR
(1)文法
三、SLR1分析表的构造算法
1、算法描述设G’的LR0项目集规范族{I0I1…In}用i表示闭包Ii对应的分析器状态即相应的DFA状态
(1)0为开始状态
(2)对Ii∈C if(A→α.aβ∈Ii且goIia=Ij)action[ia]=sj;if(A→α.Bβ∈Ii且goIiB=Ij)goto[iB]=j;if授课顺序15教学目的让学生了解符号表的作用和地位、符号的主要属性及作用、符号表的组织和管理,掌握目标程序运行时数据空间的使用和管理方法和常见的参数传递方法教学重点目标程序运行时数据空间的使用和管理、参数传递方法教学难点目标程序运行时数据空间的使用和管理、参数传递方法授课学时2学时教学方式多媒体讲授教学内容第九章符号表
9.1符号的一般结构和功能
一、概述
1、符号表在编译程序中用符号表来存放语言中出现的有关标识符的语义特征属___
2、在编译的每个阶段都要从符号表中存取不同的属___
3、记录源程序中出现的各种符号的相关属性,为编译提供相应的信息地址、类型……
二、符号表的功能
1、收集符号属性任何一个符号都可能有多种属性如种类(Kind)、类型(Type)、长度、作用域、标志(引用/定义)、地址等例intA;符号A可能有类型整型、值两个属性例floatB
[5];符号B可能有类型数组、存储地址、长度等属性
2、作为上下文语义合法性检查的依据同一个标识符可能在程序的不同地方出现,需要通过符号表将其属性记录下来,以作语义检查例inta;float*a;
3、作为目标代码生成阶段地址分配的依据
(1)对于语言中的变量,在目码代码生成时要确定其相对位置
(2)位置由两部份组成存储所在区和在区中的相对位置例staticinti;/*分配在静态区域*/
9.2符号表的主要属性及作用语言符号可分为保留字符号、操作符符号、标识符符号程序设计语言中通用的标识符属性主要有如下几种
1、符号名语言中的标识符可能是变量名、函数名、过程名等,常用特定的字符串来表示如ac_dfhello等为将不同符号名区分开来,常在符号表中给一个唯一的ID一般就是符号表的入口地址
2、符号的类型符号的数据类型,如整型、实型、字符型、布尔型、数组型等不同的类型的符号,其存储格式、在其上可实施的操作运算都可能不同
3、符号的存储类别如公共变量、静态变量、寄存器变量、局部变量等一般用关键字指明,或根据变量出现在程序中的位置来决定存储类别是过程语义检查、处理、存储分配的重要依据还决定了作用域、可视性、生命周期等问题
4、符号的作用域和可视性
(1)作用域即该变量在程序中起作用的范围,一般由该定义该符号的位置及存储类别决定
5、符号变量的存储分配信息
(1)静态存储区a)该存储区单元经定义分配后成为静态单元,在整个语言程序运行过程中是不可变的b)生命周期为整个程序运行期c)在编译系统中一般设置一个固定空间作静态存储区d)该存储区又分为公共和局部静态区域
(2)动态存储区a)设置该区是为了适应局部变量的生成和消亡b)在需要的时候给局部变量分配空间,用完后回收空间各符号变量应分配的存储区及在该区中所处具__置由其存储类别和它本身出现的位置和次序来确定例:inta;/*放公共静态区*/......floatb;/*放公共静态区*/......struct|unionA{intd;/*放局部静态区*/floate;/*放局部静态区*/......}c;/*放公共静态区*/......相对于C语言上例中变量a、b、c、d、e在符号表中的位置属性如下思考___当A定义为结构体时a、b、c、d、e在符号表中的位置属性不是
0、
2、
0、
2、6?注意存放任何类型变量的地址都必须是其所需字节数的整数倍处地址,如int型变量首址须为2的整数倍处
0、
2、
4、…
6、其它属性
(1)数组的内情向量(首地址、维数、每维的长度)用于确定数组分配时所占空间及具__置
(2)记录结构的成员信息(C中用struct,PAS中用record定义)用于确定结构型变量存储分配时所占空间及具__置
(3)函数或过程的形参用于作进程调用时的匹配处理和语义检查
9.3符号表的组织
一、符号表的总体组织符号表的总体组织方式分为三种
1、按属性完全相同的符号组织在一起,构造出多张表其特点有多个符号表,每个符号表内部符号的属性个数和结构完全相同对于单个符号管理方便,空间效率高,但从宏观上看,管理复杂例:设文法中有三类符号及其所需属性,按这类方法来组织如下
2、把所有语言中出现的符号都组织在一张表中其特点把所有符号的所有可能属性作为符号表的表项属性,便于集中一致管理,但导致了无用属性空间过多,管理繁杂例对上例中按这类方法来组织如下:
3、上两种方案的折衷根据符号的相似程度,由设计者自己根据需要设计成多张表,各表都为定长,且可看成一个多元组,各元组又由若干属性组成,元组间有相同的成员个数和一致的排列,元组间的区分由唯一的一个“关键字栏”决定例上例中表按这类方法可组织为
二、符号表项信息的排列方式符号表中每一项对应着一个多元组符号表总体上看就是一个多元组集符号表项的组织可分为线性组织、排序组织、散列组织等
1、线性组织
(1)规定符号表中表项按它的符号被扫描到的先后次序建立
(2)适于事先确定符号个数且个数不大时例...a...b...d...a...c..可组织为
2、排序组织
(1)符号表的表项中按符号的字符代码串的值的升/降序排列
(2)通常在建立和查找符号项时用二分查找法
(3)排序表的空间组织和存储开销同于线性表,但运行效率高,算法也复杂
3、散列组织
(1)符号表按散列表hash的形式进行组织,运行效率高
(2)关键问题是解决冲突的方法和hash函数的选取
(3)现代编译系统多采用它,其hash函数一般使用对符号代码的位操作(如字段迭加、符号代码对折/多折)函数
三、关键字域的组织
1、关键字域就是符号本身
2、采用关键字池的索引结构,既能保证关键字段的等长,又能减少甚至消除冗余
3、索引结构可用字符数组或字符串实现,前者用整数值表示关键字在字池中的位置下标,后者通过指针指向其在字池中的位置
四、其它域的组织
1、同类型且等长属性域的组织表中各符号的该属性值具有相同的类型且等长,则用该长度和类型来定义该域的类型结构1可给数据类型编码码长固定2表示关系符号之间关系的属性例:structc{intafloatb}stv;可表示为
2、同类型但不等长属性域的组织表中各符号的该属性值可能具有相同类型但长度不同,则另外设置相关空间来存放该属性值,而在表项的某个域内设置一个指针指向相关另设空间(结构体/联合体变量、多态域)例:数组的组织inta
[1]
[2]b
[2]
[9]
[1];
五、下推链域的组织
1、分层结构中,同名标识符在程序的某一处只能看到一个,但其它标识符仍然存在,为实现这种语义功能,符号表中设置了下推链域组织
2、下推链域组织要求进入一个内层结构并发生重名标识符定义时,把当前符号表中外层的该符号下推到链中,而在下推表项处建立内层同名标识符的表项
9.4符号表的管理
一、符号表的初始化---静态管理即在开始编译时刻,定义建立符号表的初始状态当表长渐增可变时,可以令表尾指针为表头指针;当表长固定时,对其清空
二、动态管理
1、符号表的登录—动态管理一1定义当从程序中获得一个符号并确定它在符号表中尚不存在,则将它填入符号表2方法对二分法排序表,创建新表项后,按符号词典顺序插入到表中确定位置;对散列表,由hash算法决定登录表项位置3内容含名字登录和属性登录,后者中部分是在扫描符号时进行,另一部分则是在语法分析过程中逐步进行的
2、符号的查找—动态管理二目的为了建立或确认某个符号的语义属性,找到则根据该属性进行语义检查并登录新属性,否则,登录符号常用二分查找
3、分程序结构层次的管理—动态管理三1)分表结构对各分程序建立一张__的符号表,扫描时建立,扫描结束时释放;2)单表结构
①对各分程序中定义的标识符集中到一张统一的符号表中
②为实现作用域、可视性规则要求,在表中设置一个符号所在的层次属性域,编译程序进入下一层分程序时,表示层次的状态量加一层
③用下推链域组织实现重名标识符第十章目标程序运行时的存储组织在程序语言中程序中使用的存储单元都由标识符来表示它们对应的内存地址都是由编译程序在编译时或目标代码运行时来进行分配
10.1数据空间的使用和管理
一、运行目标程序时所需空间的分类
1、容纳目标代码的空间
2、目标代码运行时的数据空间(这类空间中某些部分无法在编译时确定存储位置)1)变量和常量所需空间2)中间结果及参数传递所需的临时单元3)调用过程时的连接单元4)I/O操作所需缓冲区
二、运行时刻的内存划分以上为分配时的一个活动记录局部数据区中的一个栈单元)
三、静态存储分配
1、特点编译时刻确定存储位置;访问效率高
2、主要用途子程序的目标代码段;全局数据目标(全局变量)
3、静态存储分配无法解决的问题
(1)动态可变数组问题—层次单元法
(2)递归调用问题—栈式存储分配
(3)允许用户自由申请和释放空间的问题—堆式存储分配
四、栈(Stack)式存储分配
1、用途过程的局部环境、活动记录;
2、特点嵌套调用次序、先进后出、生存期限于本次调用、自动释放
五、堆(Heap)式存储分配
1、用于动态数据结构存储空间的动态分配和释放
2、实现方法
(1)将内存空间分为若干块,根据用户要求分配;
(2)无法满足时,调用无用单元收集程序将被释放的块收集起来重新分配
10.2参数传递过程函数是结构化程序设计的主要手段可以在别的程序、过程或函数中调用已有定义的过程调用与被调用过程两者之间的信息主要通过全局变量或参数来传递参数分为形参和实参参数传递方式传地址、传值、传名、宏扩展(即传结果,或__传递
一、传值调用(call-by-value)
1、过程调用时计算实参Actuals,将值存到活动记录;
2、形参For__ls绑定于活动记录的实参域,作为局部变量处理,在被调用过程中为形参开辟空间单元;
3、实参值放在形参单元中,对形参的运算不影响实参
二、引用调用Call-by-Referen__/Address
1、如果实参具有左值(实际为地址),则存放其左值到活动记录中;
2、如果实参无左值,则先计算出表达式的值,将此值存入一个单元,并将该单元的地址传给被调用者;
3、被调过程中对形参的任何引用和赋值都有通过指针传递到调用过程中相应地址,变成间接访问例voidswap1intaintb{inttemp;temp=a;a=b;b=temp;}voidswap2intaintb{inttemp;temp=a;a=b;b=temp;}void__in{intcd;c=2;d=4;swap1cd;swap2dc;}
三、过程参数和数组参数
1、对于数组,数组名可做参数传递;
2、对于嵌套过程或函数,可将过程或函数名做参数传递授课顺序16教学目的让学生了解常用优化技术,掌握基本块的变换方法、基本块的DAG表示及应用教学重点基本块的变换方法、基本块的DAG表示及应用教学难点常用优化技术、基本块的DAG表示及应用授课学时2学时教学方式多媒体讲授教学内容第十一章代码优化
11.1优化技术简介
一、代码优化分类
1、按阶段分类中间代码优化、目标代码优化
2、按程序范围分类局部(基本块)优化、循环优化、全局优化
二、代码优化原则等价原则、高效原则
三、代码优化技术例有如下源程序段,求其四元式形式的中间代码,并优化之设A为实型数组,每个元素占四个字节P=0;fori:=1to20doP:=P+A[i]*B[i];
1、数组的存储空间设数组中每个元素占t个存储空间,则
2、程序段对应的中间代码为如下四元式序列1)删除公共子表达式4*i和代码外提472)强度削弱T1的乘法变为加法3)变换循环控制条件T1=
80、合并已知量T1:=4和复写传播T6:=T5[T1]4)删除无用赋值
2、
6、
1111.2局部优化
一、局部优化的概念
1、基本块的定义一个基本块是指程序中一顺序执行的语句序列,其中只有一个入口和一个出口入口是程序第一个语句或转移语句的目标语句,或转移语句的后继第一个语句出口是程序最后一个语句或转移语句
2、对中间代码求基本块后,凡是没被纳入某个基本块的语句,则是控制流程无法到达的、也不会被执行的语句,可删去
3、在基本块范围内的优化称为局部优化
二、基本块的变换
1、提高运算效率的代数变换;
2、四种保结构变换1)删除公共子表达式;2)删除无用代码;3)重新命名临时变量引入新的临时变量不影响基本块的运算结果;4)变换语句次序当两个语句相互没有引用关系时,变换语句次序也不影响基本块的运算结果例如1t1:=a+b;2t2:=c+d;3t1:=t2+b其中,1和2可交换次序
三、基本块的DAG表示
1、DAG图即有向无环图例
2、附加信息的DAG图缺省方向由上向下1)以四元式为结点构造中间代码的DAG,其中,ni表示结点编号,结点下符号为结点标记(一般只有叶结点带),结点右边符号为附加标识符2)基本块中各种四元式及对应DAG图的结点形式3)按基本块后继结点数,可将四元式分为四类0型,1型,2型,3型4)对由
0、
1、2型四元式构成的基本块,其DAG构造算法描述参见教材
3、DAG的应用例子构造右边所示基本块B1的的DAG解根据DAG结点原来的构造顺序重写四元式如下B11T0:=
3.142T1:=
6.283T3:=
6.284T2:=R+r5T4:=T26A:=
6.28*T27T5:=A8T6:=R-r6A:=
6.28*T29B:=A*T6可见根据DAG结点重写的四元式已是进行了合并已知量、删除多余运算和无用赋值等优化后的结果
4、结论利用DAG可进行代码优化这种优化提供了1)基本块的保结构变换代数和语序变换;2)其他优化信息,如在基本块外被定值而在块内被引用的所有标识符,就是叶结点上的标识符;在基本块内被定值而在块后被引用的所有标识符,就是各结点上的那些附加标识符上例中若假设T0T1…T6在基本块B1后不会再被引用,则通过重新命名临时变量的基本块保结构变换,可将B1的四元式代码进一步优化为:B11S1:=R+r2A:=
6.28*S13S2:=R-r4B:=A*S2
四、DAG构造算法的讨论1、对于数组元素赋值、间接赋值、多变量共享一单元的情况,应修改DAG构造算法,否则会引起DAG与代码不等价的问题; 例X:=A[I]; A[J]=Y; Z:=A[I] 是否可变换为X:=A[I]; Z:=A[I]; A[J]=Z 问题当I=J时,对A[J]的赋值即对A[I]的赋值2、解决方法在适当的时候“注销”引发问题的标识符,其所代表的变量不再取该点的值若在此后该变量的值还要引用,则需要重新构造一个以它为标记的叶结点3、根据作过注销处理的DAG重写四元式时,DAG结点应遵循如下顺序1)对数组A任何元素赋值和引用都有必须跟在原来位于其前面的对A的任何元素赋值和引用之后2)对间接赋值、多变量共享一单元、过程调用的情况,也用类似数组赋值处理授课顺序17教学目的让学生掌握控制流分析与循环优化的基本方法,了解数据流的分析与全局优化方法、简单的代码生成器的构造、代码生成技术研究现状教学重点控制流分析与循环优化教学难点控制流分析与循环优化、数据流的分析与全局优化授课学时2学时教学方式多媒体讲授教学内容
11.3控制流分析与循环优化
一、基本问题1、循环的概念即程序中可能反复执行的代码2、如何找出程序的循环?利用控制流(程)图来查找循环3、找出循环后如何优化?代码外提、删除归纳变量、强度削弱
二、控制流图1、控制流图即具有只唯一首结点的有向图2、控制流图可表示为三元式NEn03、以N表示程序的基本块,E表示基本块间的流程关系这样的图称为程序流图
三、循环的定义和查找
1、循环的定义在程序流中,一个循环必须具有以下性质
(1)强连通序列中任意两点都可达,若只有一个结点,则有一条返回本身的回边;
(2)有且只有一个入口结点从序列外某结点,有一条有向边指向它,或它为图中首结点例下图中的循环有{6}、{4567}、{234567},强连通但不是循环的有{24}、{234}、{467}、{457}
2、必经点集的计算
(1)为找出循环,需要分析流图中的控制关系;
(2)从流图的首结点入口开始,到n如果必须经m,则称m是n的必经结点记作mDOMn;
(3)n的所有必经点的__,称必经结点集,记作Dn;
(4)由于DOM具有自反性、传递性和__称性,所以它是一个偏序关系任何结点n的必经结点集是一个有序集
(5)求必经点集的算法{Dn0={n0};forn∈N-{n0}{Dn=N;Flag=1;}whileFlag{Flag=0;forn∈N-{n0}{NEWD:={n}∪Dp的交集;p∈Pn;ifDn!=NEWD{Flag=1;Dn=NEWD;}}}}其中,Pn为n的前驱结点集例利用算法求下图所有结点的Dn解
3、循环的查找1)通过必经点集求回边,利用回边即可求出循环;2)回边设a-b是一条有向边,如bDOMa,则称a-b是流图中的一条回边例前例图中回边有6-67-44-2;3)对于回边n-d,由它可以求得一个循环,它以d为入口点,以{dn}∪{存在可达n但不经过d的所有结点}为结点集例前例图中循环有{6},{4,5,6,7},{2,3,4,5,6,7}
4、求循环的算法1)基本思想求回边dn组成的循环,有d为循环入口点,n是它的一个出口.将n的前驱结点以及前驱的前驱...加入循环,直至所求出的前驱是d2)算法描述insertm{if(m不属于loop){m加入循环;m下推进栈stack;}}__in{stack:=空;loop={d};insertn;whilestack不空{栈顶元素m出栈;对m的所有前驱p属于Pm做insertp;}}
5、流图的深度为主查找及扩展树DFST1)采用深度为主次序查找在每次迭代中前一步计算的结果立即用于下一步计算,可减少迭代次数,加快计算速度2)对有向边m-n,在深度为主扩展树中,若m是祖先,则称m-n为流图的前向边;若n=m或n是祖先,则称m-n为流图的后向边;若无祖先后代关系,则称m-n为流图的横向边3)对于一个流图和它的一棵扩展树,流图中任何无环通路含有的后向边数的最大值勤称为该流图的深度
四、可归约流图
1、一个流图被称为可归约的,当且仅当流图中除去回边后,其余的边构成一个无环路流图
2、如果程序流图是可归约的,则程序中任何能反复执行的代码都会被纳入一个循环中
3、对可归约流图进行优化比较容易
五、循环优化
1、代码外提的问题对于不变运算,是否都能外提?1)定值点变量被赋值或被输入值的地点2)引用点变量被引用的地点例下例中将B3的i:=2外提会改变原来程序的运行结果外提后j值总为2,实际上当xy(如取x=20y=15)时,j值应为
12、代码外提规则将循环不变运算s:A:=BopC外提时,必须满足下列两组条件之一条件一1S所在的结点是L的所有出口点的必经点;2A在L中其它地方未定值;3L中所有A的引用点,只有s中A的定值才能到达条件二A在离开L之后不再是活跃即不再被引用的
3、强度削弱和删除归纳变量1)强度削弱指将程序中执行时间较长的运算替换为执行时间较短的运算如将乘方换乘法,乘法换加法等;2)删除归纳变量如果循环中有I:=I+C;J=C1*I+C2,则对于基本归纳变量I的线性增长关系(C为循环不变量)可转换成为与I同族的归纳变量J的线性增长关系,从而可删除I的递归定值四元式3)删除归纳变量在强度削弱之后进行
11.4数据流的分析与全局优化
一、基本概念
1、到达---定值定值点d到达p是指流图中从d有一条路径到达p且该通路上没有A的其它定值
2、引用---定值链u-d链到达u的所有A的定值点的全体
3、定值---引用链d-u链d能到达的所有引用点的全体
二、到达-----定值方程
1、方程out[s]=in[s]-kill[s]∪gen[s]in[B]:到达基本块入口前的变量定值点;kill[B]在基本块中被“注销”的定值点;gen[B]在B中定值并到达B出口之后的所有定值点集
2、例子求ud链的迭代过程in初值为φout初值为gen作业教材P271-P273的
3、
4、
6、7题第十二章代码生成
12.1代码生成概述
一、代码生成要考虑的主要问题
1、充分利用寄存器的问题1)基本块中全局寄存器分配不把寄存器平均分配给各个变量使用,而是从可用的寄存器中分出几个,固定分配给几个变量单独使用2)标准以各变量在循环内需要访问主存单元的次数为标准具体细节依赖于目标机器和操作系统
2、选择计算机指令系统的问题
3、选择计算次序的问题
二、目标代码的分类
1、分类已定位的机器语言代码;可重定位的机器语言代码;汇编语言(宏汇编)
2、目标代码指令形式opsour__destinationADDsd//d+sSUBsd//d-sMOVsd//sd
三、目标代码质量指标
1、占用空间;
2、执行效率(主要依赖于寄存器的使用)
四、目标代码的构造
1、输入语法分析或进行优化后生成的中间代码;
2、输出特定机器的机器语言或汇编语言
3、目标代码的构造与输出的目标机器紧密相关
12.2简单的代码生成器
一、寄存器分配
1、寄存器分配在一个基本块范围内考虑
2、寄存器分配原则1)尽可能地让变量值或计算结果保留在寄存器中,直到寄存器用完为止,这样可减少访问内存次数,提高运行速度;2)到基本块出口时,将变量值存放到内存,保证块外变量值都在内存中;3)对在块内赋值或引用过,但在后继块中不再被引用的变量应尽早释放,以提高寄存器利用
二、待用信息链
1、待用信息若在一个基本块中,变量A在四元式i中被定值,在i后面的四元式j中要引用A值,且从I到j之间没有其它对A的定值点,这时我们称j是四元式i中对变量A的待用信息或称下次引用信息,同时也称A是活跃的
2、待用信息链若A被多次引用则可构成待用信息链与活跃信息链通过从基本块的出口由后向前扫描,可对每个变量建立相应的待用信息链和活跃变量信息链
3、计算待用信息的算法1)在符号表中,增加“待用信息”栏和“活跃信息”栏;2)对各基本块的符号表中的“待用信息”栏和“活跃信息”栏置初值,即把“待用信息”栏置“非待用”,对“活跃信息”栏按在基本块出口处是否为活跃而置成“活跃”或“非活跃”假定变量都是活跃的,临时变量都是非活跃的3)从基本块出口到基本块入口由后向前依次处理每个四元式对每个四元式i:A:=BopC,依次执行下述步骤a)把符号表中变量A的待用信息和活跃信息附加到四元式i上;b)把符号表中变量A的待用信息栏和活跃信息栏分别置为“非待用”和“非活跃”(由于在i中对A的定值只能在i以后的四元式中才能引用,因而对i以前的四元式来说是不活跃也不可能是待用的);C)把符号表中变量B和C的待用信息和活跃信息附加到四元式i上;d)把符号表中变量B和C的待用信息栏置为“i”活跃信息栏置为“活跃”注意以上a)和b),c)和d0的次序不能颠倒例若用A,B,C,D表示变量,用T,U,V表示中间变量,有四元式如下
(1)T:=A-B
(2)U:=A-C
(3)V:=T+U
(4)D:=V+U其名字表中的待用信息和活跃信息如下表所示,表中用“F”表示“非待用”“非活跃”,用“L”表示活跃1234表示四元式序号表内容说明表中“待用信息链”与“活跃信息链”的每列从左至右为每从后向前扫描一个四元式时相应变量的信息变化情况,空白处为没变化待用信息和活跃信息在四元式上的标记如下所示1T3L:=A2L-BFL2U3L:=AFL-CFL3V4L:=TFF+U4L4DFL:=VFF+UFF
3、寄存器描述和地址描述为随时掌握各寄存器的情况,用寄存器描述数组RVALUE来描述每个寄存器当前的状况;用变量地址描述数组__ALUE来表示变量的存放情况
4、基本块的代码生成算法假设只有A:=BopC的四元式序列,则首先,对每个四元式i:A:=BopC,依次执行下述步骤1)以四元式i:A:=BopC为参数,调用过程getregi:A:=BopC从getreg返回时,得到一寄存器R,用它作存放A现行值的寄存器;2)利用__ALUE[B]和__ALUE[C],确定出B和C现行值存放位置B’和C’,如果其现行值在寄存器中,则把寄存器取作B’和C’;3)如果B’≠R,则生成目标代码LDR,B’opR,C’否则,生成目标代码opR,C’如果B’或C’为R,则删除__ALUE[B]或ALUE[C]中的R;4)令__ALUE[B]={R},并令RVALUE[R]={A},以表示变量A的现行值只在R中并且R中的值只代表A的现行值;5)如果B或C的现行值在基本块中不会再被引用,它们也不是基本块出口之后的活跃变量(由四元式I上的附加信息知道),并且其现行值在某个寄存器Rk中,则删除RVALUE[Rk]中的B或C以及__ALUE[B]或__ALUE[C]中的Rk,使该寄存器不再为B或C所占用其次,处理完基本块中所有的四元式之后,检查现行值在某寄存器R中的每个变量M,若它在出口之后是活跃的,则生成STR,M,放到主存中例有如下左边四元式,现假定d在基本块的出口是活跃的,则得下列右边代码序列
三、从dag图生成目标代码
1、例求赋值语句T4:=A+B-E-C+D的目标代码解先构造其DAG如下然后,根据dag图生成目标代码如下方案2的效率高于方案1,因为T4的计算紧跟在T1之后
2、结论尽可能使一个结点的求值紧接着它的最左变量的求值之后,以提高效率
12.3代码生成研究现状
一、中间语言的选取
1、中间语言的选取原则要兼顾考虑高级语言的实现模型、可移植性,还要能体现目标机特点,并保证移植后效率不下降
2、常用中间代码形式前缀式、后缀式、三元组、四元组、树表示形式
二、代码生成自动化研究
1、解释性代码生成法常用宏定义、子程序实现,质量容易保证
2、样板匹配代码生成法用机器描述语言形式地描述目标机的资源指令及语义有关信息
3、表驱动代码生成法是样板匹配代码生成法的改进,自动化构成,是代码生成自动化研究所追求的目标。