1、第四章 语法分析自上而下分析,编译原理,本章主要内容,本章主要介绍语法分析的处理语法分析的任务自顶向下分析法,词法分析器,语法分析器,语义分析与中间代码生成器,优化段,表格管理,出错处理,目标代码生成器,语法分析的任务,语法分析程序以单词串形式的源程序作为输入或分析的对象。它的基本任务是： 根据语言的语法规则 ，分析源程序的语法结构，即分析如何由这些单词组成各种语法范畴 (如下标变量、各种表达式、各种语句、程序段或分程序，乃至整个源程序等等)，并在分析过程中，对源程序进行语法检查。,作为语法分析程序的输出，可以有多种不同的形式。在下面的讨论中，为简便起见，我们假定语法分析程序的输出，是用某种方
2、法表示的语法树,语法分析,如何精确描述和刻画语言中的基本语法成分-如表达式、语句和函数？如何识别语法成分及语法错误并执行某些相关的处理动作？,什么是语言,自然语言(Natural Language)是人与人的通讯工具语义(Semantics):环境、背景知识、语气、二义性难以形式化计算机语言(Computer Language)计算机系统间、人机间通讯工具严格的语法(Grammar)、语义(Semantics) 易于形式化：严格语言是用来交换信息的工具功能性描述,什么是语言,语言单词(Token)：满足一定规则字符(Character)串句子(Sentence)：满足一定规则单词序列语言(La
3、nguage)：满足一定条件的句子集合语言是字和组合字的规则结构性描述例：去吃我们中汉堡午 中午我们去吃汉堡,如何描述一种语言？,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.”这是一个在语法、语义上都正确的句子，该句子的结构（称为语法结构）是由它的语法决定的 。在本例中它为“主谓宾结构”。,文法的形式定义,语法规则：我们通过建立一组规则，来描述句子的语法结构。,文法的形式定义, := :=
6、 := he := a := pen := := has := := pen,括起来的部分是语言的一个语法实体（称为语法单位、语法范畴、语法变量等）,规定用“:=”表示“由组成”,终结符号集VT = he, has, a, pen非终结符号集VN = 句子，主语，谓语，冠词，形容词，名词 ， 动词 ，宾语 ，名词产生式集合P = 句子 主语谓语 ， 开始符号S = 句子,句子的语法组成,句子的推导_根据规则,由规则推导句子：有了一组规则之后，可以按照一定的方式用它们去推导或产生句子。推导方法：从一个要识别的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条规则去进行推导。, =
7、 = = 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：文法的开始符号，SVNP：产生式集合(有限)，每个产生式形式为P， PVN， (VT VN)*开始符S至少必须在某个产生式的左部出现一次。,例，定义只含+，*的算术表达式的文法 G=， 其中，P由下列产生式组成：E iE E+EE E*EE (
8、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
9、E+E E,i,+,*,i,i,语法分析的方法：自上而下分析法(Top-down)基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找匹配的推导。递归下降分析法预测分析程序优点：直观、简单和宜于手工实现。,4.2自顶向下分析法,4.2.1 自顶向下分析的一般过程,从S出发采用最左推导，试图逐步推出输入串,L(GS)?S作为语法树的根，试图自上而下地为构造一棵语法树若叶结点从左向右排列恰好，则表示是文法的句子，而这棵语法树就是句子的语法结构若构造不出语法树，则不是文法的句子,【例4.1】 =acbGS:SaAbAcd|c,分析过程是设法建立一棵语法树,使语法树的末端结点与给定符号串相匹配.
10、,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相匹配,建立了推导序列 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
13、.3.1 左递归的消除,直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为PP | 其中不以P开头。 我们可以把P的规则等价地改写为如下的非直接左递归形式：PPPP|,左递归变右递归,一般而言，假定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,
14、(4.2),PP1 | P2 | | Pm | 1 | 2|nP1P | 2P | | nPP1P | 2P | | mP | ,例如文法G(S):SQc|cQRb|bRSa|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的所有规则) 消除关于P
15、i规则的直接左递归性 END3. 化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。,例 考虑文法G(S)SQc|cQRb|bRSa|a令它的非终结符的排序为R、Q、S。对于R，不存在直接左递归。把R代入到Q的有关候选后，把Q的规则变为 QSab | ab | b,例 考虑文法G(S)SQc|cQRb|bRSa|a令它的非终结符的排序为R、Q、S。Q的规则变为 QSab | ab | b现在的Q不含直接左递归，把它代入到S的有关候选后，S变成SSabc | abc | bc | c,例 考虑文法G(S)SQc|cQRb|bRSa|aS变成SSabc | abc | b
16、c | 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)的等价性是显然的。,
