编译原理课件-Cha.ppt

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