语法分析—自上而下分析课件.ppt

1、第四章第四章 语法分析语法分析自上而下分析自上而下分析编译原理本章主要内容本章主要内容n本章主要介绍语法分析的处理本章主要介绍语法分析的处理语法分析的任务语法分析的任务自顶向下分析法自顶向下分析法四元式四元式单词符号单词符号语法单位语法单位四元式四元式目标代码目标代码词法分析器词法分析器语法分析器语法分析器语义分析与中间代码语义分析与中间代码生成器生成器优化段优化段源程序源程序表表格格管管理理出出错错处处理理目标代码生成器目标代码生成器语法分析的任务语法分析的任务n语法分析程序以单词串形式的源程序作为语法分析程序以单词串形式的源程序作为输入或分析的对象。输入或分析的对象。n它的基本任务是：它的

2、基本任务是： 根据语言的语法规则根据语言的语法规则 ，分析源程序的语法结，分析源程序的语法结构，即分析如何由这些单词组成各种语法范畴构，即分析如何由这些单词组成各种语法范畴 (如下标变量、各种表达式、各种语句、程序段如下标变量、各种表达式、各种语句、程序段或分程序，乃至整个源程序等等或分程序，乃至整个源程序等等)，并在分析过，并在分析过程中，对源程序进行语法检查。程中，对源程序进行语法检查。 n作为语法分析程序的输出，可以有多种不作为语法分析程序的输出，可以有多种不同的形式。在下面的讨论中，为简便起见，同的形式。在下面的讨论中，为简便起见，我们假定语法分析程序的输出，是用某种我们假定语法分析程

3、序的输出，是用某种方法表示的语法树方法表示的语法树 语法分析语法分析l如何精确描述和刻画语言中的基本语如何精确描述和刻画语言中的基本语法成分法成分-如表达式、语句和函数？如表达式、语句和函数？l如何识别语法成分及语法错误并执行如何识别语法成分及语法错误并执行某些相关的处理动作？某些相关的处理动作？ 什么是语言什么是语言自然语言自然语言(Natural Language)(Natural Language)n是人与人的通讯工具是人与人的通讯工具n语义语义(Semantics):(Semantics):环境、背景知识、语气、环境、背景知识、语气、二义性二义性难以形式化难以形式化计算机语言计算机语言

4、(Computer Language)(Computer Language)n计算机系统间、人机间通讯工具计算机系统间、人机间通讯工具n严格的语法严格的语法(Grammar)(Grammar)、语义、语义(Semantics) (Semantics) 易于形式化：严格易于形式化：严格语言是用来交换信息的工具语言是用来交换信息的工具功能性描述功能性描述什么是语言什么是语言语言语言单词单词(Token)(Token)：满足一定规则字符：满足一定规则字符(Character)(Character)串串句子句子(Sentence)(Sentence)：满足一定规则单词序列：满足一定规则单词序列语言语言

5、(Language)(Language)：满足一定条件的句子集合：满足一定条件的句子集合语言是字和组合字的规则语言是字和组合字的规则结构性描述结构性描述例：去吃我们中汉堡午例：去吃我们中汉堡午 中午我们去吃汉堡中午我们去吃汉堡如何描述一种语言？如何描述一种语言？1. 1. 如果语言是有穷的（只含有有穷多如果语言是有穷的（只含有有穷多个句子），可以通过个句子），可以通过枚举法枚举法将语言所有将语言所有的句子列出表示。的句子列出表示。n例如，只含两个句子的语言：例如，只含两个句子的语言：“I am “I am a teacher”, “You are students”;a teacher”, “

6、You are students”;如何描述一种语言？如何描述一种语言？ 2. 2. 如果语言是无穷的，描述语言有两种途径：如果语言是无穷的，描述语言有两种途径：l制定制定有限条规则有限条规则，用于产生所要描述的语言的，用于产生所要描述的语言的全部句子（可无限多），这些规则构成了该语全部句子（可无限多），这些规则构成了该语言的言的文法文法。l设计一种装置（算法或过程设计一种装置（算法或过程，它以某字母表，它以某字母表上的符号串为输入，判别该符号串是否为所描上的符号串为输入，判别该符号串是否为所描述语言的句子。此装置称为述语言的句子。此装置称为自动机。自动机。语言概述语言概述程序设计语言程序设计

7、语言形式化的内容提取形式化的内容提取程序设计语言程序设计语言(Programming Language)(Programming Language)：组：组成程序的所有语句的集合成程序的所有语句的集合程序程序(Program)(Program)：满足语法规则的语句序列：满足语法规则的语句序列语句语句(Sentence) (Sentence) ：满足语法规则的单词序列：满足语法规则的单词序列单词单词(Token) (Token) ：满足词法规则的字符串：满足词法规则的字符串文法和语法分析文法和语法分析正规式的局限性：不能用于描述配正规式的局限性：不能用于描述配对或嵌套的结构对或嵌套的结构l例例1

8、 1：配对括号串的集合：配对括号串的集合l例例2 2：wcwwcw | w | w是是a a和和b b的串的串 仅能表示给定结构的仅能表示给定结构的固定次数的重复或者没有固定次数的重复或者没有指定次数的重复指定次数的重复 适合描述和识别语言适合描述和识别语言的单词符号；的单词符号；文法和语法分析文法和语法分析高级语言的语法结构适合使用高级语言的语法结构适合使用上下文无关文法描述。上下文无关文法描述。文法及语言的形式定义文法及语言的形式定义文法是对语言结构的定义与描述（或文法是对语言结构的定义与描述（或称为称为“语法语法”），即用适当条数的规），即用适当条数的规则把语言的全部句子描述出来。则把语

9、言的全部句子描述出来。文法是以有穷的集合刻划无穷的集合文法是以有穷的集合刻划无穷的集合的工具。的工具。文法文法l文法能清晰地描述程序设计语言的语法构文法能清晰地描述程序设计语言的语法构成易于理解。成易于理解。 l文法能自动地构造有效的语法分析器，检文法能自动地构造有效的语法分析器，检查源程序是否符合语言规定的语法形式。查源程序是否符合语言规定的语法形式。 l文法定义可以了解程序设计语言的结构，文法定义可以了解程序设计语言的结构，有利于将源程序转化为目标代码，以及检有利于将源程序转化为目标代码，以及检查出语法错误。查出语法错误。 l基于文法实现的语言易于扩展。基于文法实现的语言易于扩展。文法及语

10、言的形式定义文法及语言的形式定义例：有一句子：例：有一句子：“He has a pen.”He has a pen.”这这是一个在语法、语义上都正确是一个在语法、语义上都正确的的句子，句子，该句子的结构（称为语法结构）是由该句子的结构（称为语法结构）是由它的语法决定的它的语法决定的 。在本例中它为。在本例中它为“主主谓谓宾宾结构结构”。文法的形式定义文法的形式定义 语法规则：我们通过建立一组语法规则：我们通过建立一组规则，来描述句子的语法结构。规则，来描述句子的语法结构。文法的形式定义文法的形式定义 := := := := := he := he := a := a := pen := pen

11、 := := := has := has := := := pen := pen括起来的括起来的部分是语言部分是语言的一个语法的一个语法实体（称为实体（称为语法单位、语法单位、语法范畴、语法范畴、语法变量等）语法变量等）规定用规定用“:=”:=”表示表示“由由组组成成”l终结符号集终结符号集V VT T = he, has, a, pen= he, has, a, penl非终结符号集非终结符号集V VN N = = 句子句子 ， 主语主语 ， 谓语谓语 ， 冠词冠词 ， 形容词形容词 ， 名词名词 ， 动词动词 ， 宾语宾语 ， 名词名词 l产生式集合产生式集合P P = = 句子句子 主语

12、主语谓语谓语 ， l开始符号开始符号S S = = 句子句子 句子的语法组成句子的语法组成句子的推导句子的推导_根据规则根据规则n由规则推导句子：有了一组规则之由规则推导句子：有了一组规则之后，可以按照一定的方式用它们去后，可以按照一定的方式用它们去推导或产生句子。推导或产生句子。n推导方法：从一个要识别的符号开推导方法：从一个要识别的符号开始推导，即用相应产生式的右部来始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条替代产生式的左部，每次仅用一条规则去进行推导。规则去进行推导。 = = = he = he has = he has = he has a = he has a pe

13、n := := := he := a := pen := := has := := pen上下文无关文法的形式定义上下文无关文法的形式定义一个上下文无关文法一个上下文无关文法G G是一个四元式是一个四元式 G=(VG=(VT T，V VN N，S S，P)P)，其中，其中V VT T：终结符集合：终结符集合( (非空非空) )V VN N：非终结符集合：非终结符集合( (非空非空) )，且，且V VT T V VN N= =S S：文法的开始符号，：文法的开始符号，S S V VN NP P：产生式集合：产生式集合( (有限有限) )，每个产生式形式为，每个产生式形式为P P， P P V V

14、N N， ( (V VT T V VN N) )* *开始符开始符S S至少必须在某个产生式的左部出现一至少必须在某个产生式的左部出现一次。次。n例，定义只含例，定义只含+，*的算术表达式的文法的算术表达式的文法 G=， 其其中，中，P由下列产生式组成：由下列产生式组成：E iE E+EE E*EE (E)4.1 语法分析器的功能语法分析器的功能n语法分析的任务是分析一个文法的句子语法分析的任务是分析一个文法的句子结构。结构。n语法分析器的功能：按照文法的产生式语法分析器的功能：按照文法的产生式( (语言的语法规则语言的语法规则) )，识别输入符号串是，识别输入符号串是否为一个句子否为一个句子

15、( (合式程序合式程序) )。源程序源程序单词符号单词符号取下一单词取下一单词.语法分语法分析树析树词法分词法分析器析器语法分语法分析器析器符号表符号表编译程序编译程序后续部分后续部分n语法分析的方法：语法分析的方法：n自下而上分析法自下而上分析法(Bottom-up)(Bottom-up)基本思想：从输入串开始，逐步进行基本思想：从输入串开始，逐步进行“归归约约”，直到文法的开始符号。即从树末端，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换文法的产生式规则，把产生式的右部替换成左部符号。成左部符号。

16、算符优先分析法：按照算符的优先关系和算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。结合性质进行语法分析。适合分析表达式。LRLR分析法：规范归约分析法：规范归约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 Ei+ +* *EiiEEEEn语法分析的方法：语法分析的方法：n自上而下分析法自上而下分析法(Top-down)(Top-down)基本思想：它从文法的开始符号出发，基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找反复使用各种产生式，寻找 匹配匹配 的的推推导导。递归下

17、降分析法递归下降分析法预测分析程序预测分析程序F优点：直观、简单和宜于手工实现。优点：直观、简单和宜于手工实现。4.24.2自顶向下分析法自顶向下分析法4.2.1 自顶向下分析的一般过程自顶向下分析的一般过程从从S S出发采用最左推导，试图逐步推出输入串出发采用最左推导，试图逐步推出输入串, L(GS)?S S作为语法树的根，试图自上而下地为作为语法树的根，试图自上而下地为构造一棵语法构造一棵语法树树若叶结点从左向右排列恰好若叶结点从左向右排列恰好，则表示，则表示是文法的是文法的句子，而这棵语法树就是句子句子，而这棵语法树就是句子的语法结构的语法结构若构造不出语法树，则若构造不出语法树，则不是

18、文法的句子不是文法的句子 【例【例4.1】 =acbGS:SaAbAcd|c 分析过程是设法建立一分析过程是设法建立一棵语法树棵语法树,使语法树的末端结使语法树的末端结点与给定符号串相匹配点与给定符号串相匹配.1.开始开始:令令S为根结点为根结点 S2.用用S的右部的右部,符号串去匹配输入串符号串去匹配输入串 SaAb完成一步推导完成一步推导SaAb 检查检查 a-a匹配匹配 A是非终结符是非终结符,将匹配任务交给将匹配任务交给A3.选用选用A的右部符号串匹配输入串的右部符号串匹配输入串 A有两个右部有两个右部,选第一个选第一个 aAbcdS完成进一步推导完成进一步推导Acd 检查检查,c-c

19、匹配匹配,b-d不匹配不匹配(失败失败)但是还不能冒然宣布但是还不能冒然宣布 L(GS) 4.回溯回溯 即砍掉即砍掉A的子树的子树 改选改选A的第二右部的第二右部SaAbcAc 检查检查 c-c匹配匹配 b-b匹配匹配建立语法树建立语法树,末端结点为末端结点为acb与输入与输入acb相匹配相匹配,建立了推导序列建立了推导序列 SaAbacbacb L(GS)=acbGS: SaAbAcd|c自顶向下分析方法分类自顶向下分析方法分类确定的确定的不确定的不确定的回溯回溯1.回溯问题回溯问题什么是回溯（什么是回溯（backtracking）?分析工作要部分地或全部地退回去重做叫分析工作要部分地或全部

20、地退回去重做叫回溯回溯造成回溯的条件：造成回溯的条件： 文法中，对于某个非终结符号的规则其右部文法中，对于某个非终结符号的规则其右部有多个选择，并根据所面临的输入符号不能准确有多个选择，并根据所面临的输入符号不能准确的确定所要选择时，就可能出现回溯。的确定所要选择时，就可能出现回溯。回溯带来的问题：回溯带来的问题：严重的严重的低效率低效率，只有在理论上的意义而无实际意义，只有在理论上的意义而无实际意义自顶向下分析存在的主要问题自顶向下分析存在的主要问题n例如：例如： 假定有文法假定有文法G(S): (1) SxAy (2) A*|* 分析分析输入串输入串x*y(记为记为 )。Sx*yIPSx*

21、yIPAxySx*yIPAxySx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*效率低的原因效率低的原因1)语法分析要重做语法分析要重做2)语义处理工作要推倒重来语义处理工作要推倒重来因此我们要想办法消除回溯！因此我们要想办法消除回溯！2.左递归问题左递归问题【例】文法【例】文法GE：EE+T|TTT*F|FF(E)|i给出给出i*i+i自顶向下的分析过程。自顶向下的分析过程。 左递归文法会使自顶向下分析法陷入死循环左递归文法会使自顶向下分析法陷入死循环 如果文法具有间接左递归，则也将发生上述问题，只不过循如果文法具有间接左递归，则也将发生上述问题，只不过循环的圈

22、子兜的更大环的圈子兜的更大要实行自顶向下分析，必须要消除文法的左递归要实行自顶向下分析，必须要消除文法的左递归从左向右扫描源程从左向右扫描源程序，同时实施最左序，同时实施最左推导推导 3.在上述自上而下分析过程中，当一个非终在上述自上而下分析过程中，当一个非终结符用某一候选式匹配成功时，这种成功结符用某一候选式匹配成功时，这种成功可能只是暂时的。由于这种虚假现象，我可能只是暂时的。由于这种虚假现象，我们需要采用更复杂的回溯。们需要采用更复杂的回溯。4.当最终报告分析不成功时，我们难于知道当最终报告分析不成功时，我们难于知道输入串中出错的确切位置。输入串中出错的确切位置。4.3 LL(1)分析法

23、分析法n构造不带回溯的自上而下分析算法构造不带回溯的自上而下分析算法要消除文法的左递归性要消除文法的左递归性克服回溯克服回溯1.递归规则：产生式右部有与左部相同的符号递归规则：产生式右部有与左部相同的符号 左递归规则：左递归规则：AA 右递归规则：右递归规则：AA 自嵌入递归规则：自嵌入递归规则：AA递归文法递归文法递归文法递归文法2.递归文法：含有递归规则的递归文法：含有递归规则的文文法，为法，为直接递归直接递归文文法法GS：SL|SL|SDLa|b|zD0|1|9递归文法递归文法ABaBAb 间接递归间接递归文文法法4.3.1 左递归的消除左递归的消除n直接消除见诸于产生式中的左递归：假直

24、接消除见诸于产生式中的左递归：假定关于非终结符定关于非终结符P的规则为的规则为PP | 其中其中 不以不以P开头。开头。 我们可以把我们可以把P的规则等价地改写为如下的的规则等价地改写为如下的非直接左递归形式：非直接左递归形式：P P P P | 左递归变右递归n一般而言，假定一般而言，假定P关于的全部产生式是关于的全部产生式是PP 1 | P 2 | | P m | 1 | 2| n其中，每个其中，每个 都不等于都不等于 ，每个，每个 都不以都不以P开头开头 那么，消除那么，消除P的直接左递归性就是把这些规的直接左递归性就是把这些规则改写成：则改写成： P 1P | 2P | | nP P

25、1P | 2P | | mP | 左递归变右递归n例例 文法文法G(E):EET | TTT*F | FF(E) | i经消去直接左递归后变成：经消去直接左递归后变成： ETE E +TE | TFT T *FT | F(E) | i(4.2)PP 1 | P 2 | | P m | 1 | 2| nP 1P | 2P | | nP P 1P | 2P | | mP | n例如文法例如文法G(S):SQc|cQRb|bRSa|a (4.3)虽没有直接左递归，但虽没有直接左递归，但S、Q、R都是左递归的都是左递归的SQcRbcSabc一个文法消除左递归的条件：一个文法消除左递归的条件：F不含以不

26、含以 为右部的产生式为右部的产生式F不含回路。不含回路。PPn消除左递归的算法消除左递归的算法:1. 把文法把文法G的所有非终结符按任一种顺序排列成的所有非终结符按任一种顺序排列成P1，P2，Pn；按此顺序执行；按此顺序执行；2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如把形如PiPj 的规则改写成的规则改写成 Pi 1 | 2 | k ; (其中其中Pj 1| 2| k是关于是关于Pj的所有规则的所有规则) 消除关于消除关于Pi规则的直接左递归性规则的直接左递归性 END3. 化简由化简由2所得的文法。去除那些从开始符号出发永所得的文法。去除

27、那些从开始符号出发永远无法到达的非终结符的产生规则。远无法到达的非终结符的产生规则。n例例 考虑文法考虑文法G(S)SQc|cQRb|bRSa|an令它的非终结符的排序为令它的非终结符的排序为R、Q、S。n对于对于R，不存在直接左递归。，不存在直接左递归。n把把R代入到代入到Q的有关候选后，把的有关候选后，把Q的规则的规则变为变为 QSab | ab | bn例例 考虑文法考虑文法G(S)SQc|cQRb|bRSa|an令它的非终结符的排序为令它的非终结符的排序为R、Q、S。nQ的规则变为的规则变为 QSab | ab | bn现在的现在的Q不含直接左递归，把它代入到不含直接左递归，把它代入到

28、S的有关候选后，的有关候选后，S变成变成SSabc | abc | bc | cn例例 考虑文法考虑文法G(S)SQc|cQRb|bRSa|anS变成变成SSabc | abc | bc | cn消除消除S的直接左递归后：的直接左递归后：SabcS | bcS | cS S abcS | QSab |ab | bRSa|an例例 考虑文法考虑文法G(S)SQc|cQRb|bRSa|an消除消除S的直接左递归后：的直接左递归后：SabcS | bcS | cS S abcS | QSab |ab | bRSa|an关于关于Q和和R的规则已是多余的，化简为：的规则已是多余的，化简为：SabcS | bcS | cS S abcS | (4.4)n注意，由于对非终结符排序的不同，最注意，由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但后所得的文法在形式上可能不一样。但不难证明，它们都是等价的。不难证明，它们都是等价的。n例如，若对文法例如，若对文法(4.3)的非终结符排序选的非终结符排序选为为S、Q、R，那么，最后所得的无左递，那么，最后所得的无左递归文法是：归文法是：SQc | cQRb | bRbcaR | caR |a R (4.5)R bca R | n文法文法(4.4)和和(4.5)的等价性是显然的。的等价性是显然的。