《语法分析—自上而下分析课件.ppt》由会员分享,可在线阅读,更多相关《语法分析—自上而下分析课件.ppt(51页珍藏版)》请在三一办公上搜索。
1、第四章 语法分析自上而下分析,编译原理,本章主要内容,本章主要介绍语法分析的处理语法分析的任务自顶向下分析法,词法分析器,语法分析器,语义分析与中间代码生成器,优化段,表格管理,出错处理,目标代码生成器,语法分析的任务,语法分析程序以单词串形式的源程序作为输入或分析的对象。它的基本任务是:根据语言的语法规则,分析源程序的语法结构,即分析如何由这些单词组成各种语法范畴(如下标变量、各种表达式、各种语句、程序段或分程序,乃至整个源程序等等),并在分析过程中,对源程序进行语法检查。,作为语法分析程序的输出,可以有多种不同的形式。在下面的讨论中,为简便起见,我们假定语法分析程序的输出,是用某种方法表示
2、的语法树,语法分析,如何精确描述和刻画语言中的基本语法成分-如表达式、语句和函数?如何识别语法成分及语法错误并执行某些相关的处理动作?,什么是语言,自然语言(Natural Language)是人与人的通讯工具语义(Semantics):环境、背景知识、语气、二义性难以形式化计算机语言(Computer Language)计算机系统间、人机间通讯工具严格的语法(Grammar)、语义(Semantics)易于形式化:严格语言是用来交换信息的工具功能性描述,什么是语言,语言单词(Token):满足一定规则字符(Character)串句子(Sentence):满足一定规则单词序列语言(Langua
3、ge):满足一定条件的句子集合语言是字和组合字的规则结构性描述例:去吃我们中汉堡午 中午我们去吃汉堡,如何描述一种语言?,1.如果语言是有穷的(只含有有穷多个句子),可以通过枚举法将语言所有的句子列出表示。例如,只含两个句子的语言:“I am a teacher”,“You are students”;,如何描述一种语言?,2.如果语言是无穷的,描述语言有两种途径:制定有限条规则,用于产生所要描述的语言的全部句子(可无限多),这些规则构成了该语言的文法。设计一种装置(算法或过程),它以某字母表上的符号串为输入,判别该符号串是否为所描述语言的句子。此装置称为自动机。,语言概述,程序设计语言形式化
4、的内容提取程序设计语言(Programming Language):组成程序的所有语句的集合程序(Program):满足语法规则的语句序列语句(Sentence):满足语法规则的单词序列单词(Token):满足词法规则的字符串,文法和语法分析,正规式的局限性:不能用于描述配对或嵌套的结构例1:配对括号串的集合例2:wcw|w是a和b的串,仅能表示给定结构的固定次数的重复或者没有指定次数的重复 适合描述和识别语言的单词符号;,文法和语法分析,高级语言的语法结构适合使用上下文无关文法描述。,文法及语言的形式定义,文法是对语言结构的定义与描述(或称为“语法”),即用适当条数的规则把语言的全部句子描述
5、出来。文法是以有穷的集合刻划无穷的集合的工具。,文法,文法能清晰地描述程序设计语言的语法构成易于理解。文法能自动地构造有效的语法分析器,检查源程序是否符合语言规定的语法形式。文法定义可以了解程序设计语言的结构,有利于将源程序转化为目标代码,以及检查出语法错误。基于文法实现的语言易于扩展。,文法及语言的形式定义,例:有一句子:“He has a pen.”这是一个在语法、语义上都正确的句子,该句子的结构(称为语法结构)是由它的语法决定的。在本例中它为“主谓宾结构”。,文法的形式定义,语法规则:我们通过建立一组规则,来描述句子的语法结构。,文法的形式定义,:=:=:=he:=a:=pen:=:=h
6、as:=:=pen,括起来的部分是语言的一个语法实体(称为语法单位、语法范畴、语法变量等),规定用“:=”表示“由组成”,终结符号集VT=he,has,a,pen非终结符号集VN=句子,主语,谓语,冠词,形容词,名词,动词,宾语,名词产生式集合P=句子 主语谓语,开始符号S=句子,句子的语法组成,句子的推导_根据规则,由规则推导句子:有了一组规则之后,可以按照一定的方式用它们去推导或产生句子。推导方法:从一个要识别的符号开始推导,即用相应产生式的右部来替代产生式的左部,每次仅用一条规则去进行推导。,=he=he has=he has=he has a=he has a pen,:=:=:=he
7、:=a:=pen:=:=has:=:=pen,上下文无关文法的形式定义,一个上下文无关文法G是一个四元式 G=(VT,VN,S,P),其中VT:终结符集合(非空)VN:非终结符集合(非空),且VT VN=S:文法的开始符号,SVNP:产生式集合(有限),每个产生式形式为P,PVN,(VT VN)*开始符S至少必须在某个产生式的左部出现一次。,例,定义只含+,*的算术表达式的文法 G=,其中,P由下列产生式组成:E iE E+EE E*EE(E),4.1 语法分析器的功能,语法分析的任务是分析一个文法的句子结构。语法分析器的功能:按照文法的产生式(语言的语法规则),识别输入符号串是否为一个句子(
8、合式程序)。,.,语法分析的方法:自下而上分析法(Bottom-up)基本思想:从输入串开始,逐步进行“归约”,直到文法的开始符号。即从树末端开始,构造语法树。所谓归约,是指根据文法的产生式规则,把产生式的右部替换成左部符号。算符优先分析法:按照算符的优先关系和结合性质进行语法分析。适合分析表达式。LR分析法:规范归约,G(E):E i|E+E|E-E|E*E|E/E|(E)i*i+i E*i+i E*E+i E+i E+E E,i,+,*,i,i,语法分析的方法:自上而下分析法(Top-down)基本思想:它从文法的开始符号出发,反复使用各种产生式,寻找匹配的推导。递归下降分析法预测分析程序
9、优点:直观、简单和宜于手工实现。,4.2自顶向下分析法,4.2.1 自顶向下分析的一般过程,从S出发采用最左推导,试图逐步推出输入串,L(GS)?S作为语法树的根,试图自上而下地为构造一棵语法树若叶结点从左向右排列恰好,则表示是文法的句子,而这棵语法树就是句子的语法结构若构造不出语法树,则不是文法的句子,【例4.1】=acbGS:SaAbAcd|c,分析过程是设法建立一棵语法树,使语法树的末端结点与给定符号串相匹配.,2.用S的右部,符号串去匹配输入串,完成一步推导SaAb 检查 a-a匹配 A是非终结符,将匹配任务交给A,3.选用A的右部符号串匹配输入串 A有两个右部,选第一个,完成进一步推
10、导Acd 检查,c-c匹配,b-d不匹配(失败)但是还不能冒然宣布 L(GS),4.回溯 即砍掉A的子树 改选A的第二右部,Ac 检查 c-c匹配 b-b匹配,建立语法树,末端结点为acb与输入acb相匹配,建立了推导序列 SaAbacbacbL(GS),=acbGS:SaAbAcd|c,自顶向下分析方法分类,确定的,不确定的,回溯,1.回溯问题,什么是回溯(backtracking)?,分析工作要部分地或全部地退回去重做叫回溯,造成回溯的条件:,文法中,对于某个非终结符号的规则其右部有多个选择,并根据所面临的输入符号不能准确的确定所要选择时,就可能出现回溯。,回溯带来的问题:,严重的低效率,
11、只有在理论上的意义而无实际意义,自顶向下分析存在的主要问题,例如:假定有文法G(S):(1)SxAy(2)A*|*分析输入串x*y(记为)。,效率低的原因,1)语法分析要重做,2)语义处理工作要推倒重来,因此我们要想办法消除回溯!,2.左递归问题,【例】文法GE:EE+T|TTT*F|FF(E)|i给出i*i+i自顶向下的分析过程。,左递归文法会使自顶向下分析法陷入死循环,如果文法具有间接左递归,则也将发生上述问题,只不过循环的圈子兜的更大,要实行自顶向下分析,必须要消除文法的左递归,从左向右扫描源程序,同时实施最左推导,在上述自上而下分析过程中,当一个非终结符用某一候选式匹配成功时,这种成功
12、可能只是暂时的。由于这种虚假现象,我们需要采用更复杂的回溯。当最终报告分析不成功时,我们难于知道输入串中出错的确切位置。,4.3 LL(1)分析法,构造不带回溯的自上而下分析算法要消除文法的左递归性克服回溯,1.递归规则:产生式右部有与左部相同的符号 左递归规则:AA 右递归规则:AA 自嵌入递归规则:AA,递归文法,递归文法,2.递归文法:含有递归规则的文法,为直接递归文法,递归文法,ABaBAb,4.3.1 左递归的消除,直接消除见诸于产生式中的左递归:假定关于非终结符P的规则为PP|其中不以P开头。我们可以把P的规则等价地改写为如下的非直接左递归形式:PPPP|,左递归变右递归,一般而言
13、,假定P关于的全部产生式是PP1|P2|Pm|1|2|n其中,每个都不等于,每个都不以P开头 那么,消除P的直接左递归性就是把这些规则改写成:P1P|2P|nPP1P|2P|mP|,左递归变右递归,例 文法G(E):EET|TTT*F|FF(E)|i经消去直接左递归后变成:ETE E+TE|TFT T*FT|F(E)|i,(4.2),PP1|P2|Pm|1|2|nP1P|2P|nPP1P|2P|mP|,例如文法G(S):SQc|cQRb|bRSa|a(4.3)虽没有直接左递归,但S、Q、R都是左递归的SQcRbcSabc,一个文法消除左递归的条件:不含以为右部的产生式不含回路。,消除左递归的算
14、法:1.把文法G的所有非终结符按任一种顺序排列成P1,P2,Pn;按此顺序执行;2.FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如PiPj的规则改写成 Pi1|2|k;(其中Pj1|2|k是关于Pj的所有规则)消除关于Pi规则的直接左递归性 END3.化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。,例 考虑文法G(S)SQc|cQRb|bRSa|a令它的非终结符的排序为R、Q、S。对于R,不存在直接左递归。把R代入到Q的有关候选后,把Q的规则变为 QSab|ab|b,例 考虑文法G(S)SQc|cQRb|bRSa|a令它
15、的非终结符的排序为R、Q、S。Q的规则变为 QSab|ab|b现在的Q不含直接左递归,把它代入到S的有关候选后,S变成SSabc|abc|bc|c,例 考虑文法G(S)SQc|cQRb|bRSa|aS变成SSabc|abc|bc|c消除S的直接左递归后:SabcS|bcS|cSSabcS|QSab|ab|bRSa|a,例 考虑文法G(S)SQc|cQRb|bRSa|a消除S的直接左递归后:SabcS|bcS|cSSabcS|QSab|ab|bRSa|a关于Q和R的规则已是多余的,化简为:SabcS|bcS|cSSabcS|(4.4),注意,由于对非终结符排序的不同,最后所得的文法在形式上可能不一样。但不难证明,它们都是等价的。例如,若对文法(4.3)的非终结符排序选为S、Q、R,那么,最后所得的无左递归文法是:SQc|cQRb|bRbcaR|caR|a R(4.5)R bca R|文法(4.4)和(4.5)的等价性是显然的。,