自顶向下语法分析方法

《自顶向下语法分析方法》由会员分享，可在线阅读，更多相关《自顶向下语法分析方法（147页珍藏版）》请在金锄头文库上搜索。

1、第5章自顶向下语法分析方法语法分析（Syntax Analysis）是编译程序 的核心部分。词法分析只是将字符形式的源 程序中的各个单词识别出来，形成单词的机 内表示形式，但是这些单词串如何构成更大 的语法成分语句，那就由语法分析来完 成。语法分析的主要任务就是“组词成句” ，即在词法分析识别出单词串的基础上，根 据语言的语法规则，识别出各类语法成分， 如“语句”、“程序”等。将完成语法分析任务的程序称为语法分析 程序，也称为语法分析器或简称分析器。 程序设计语言的语法结构是用上下文无 关文法描述的，因此，语法分析器的实 现原理就是按所给定的文法G，识别输 入符号串是否为一个句子（即 L(G)

2、成立吗？），同时检查和处理 语法错误。语法分析的关键是句型识别 问题。给定一串单词（即文法的终结符 ），怎样知道它是不是该文法产生的一 个句子呢？可以利用推导，或者利用语 法树来进行判断。一般来说，语法分析 的过程就是为一个句子建立语法树的过 程。 语法分析的方法很多，按照建立语法树 的不同方向，通常将语法分析分为两类 ，一类是自顶向下分析法，另一类是自 底向上分析法。 本章主要介绍自顶向下分析法，自底向 上分析法。第4章教学内容 语法分析的任务； 确定的自顶向下语法分析的基本思想 ； LL(1)文法的定义和判别方法； 非LL(1)文法到LL(1)文法的等价变换 ； 确定的自顶向下分析方法：

3、递归下降分析法 预测分析法 自底向上语法分析的基本思想； 短语、直接短语和句柄的定义，以及 如何利用语法树寻找短语、直接短语 和句柄。 自底向上语法分析方法： 优先分析法 LR分析法一、自顶向下的语法分析思想 【自顶向下（top - down ）分析法的基本思想 】自顶向下语法分析的基本思想是以文法的开 始符号为树根，采用最左推导，试图自上而下 地为输入的单词串构造一棵语法树。若语法树 的端末节点从左向右排列恰好是输入串，则该 输入串就是文法的句子，否则就不是。这种分析过程实质是一种试探过程，是反 复使用不同产生式来匹配输入串的过程。示例【例4.1】设有以下文法G1S:SaABAbA|cBdB

4、e|de 输入串abbcde的最左推导如下： S aAB abAB abbAB abbcB abbcde 因此，输入串abbcde是该文法G1的句子。 下面从建立语法树 来看句子的推导过 程。为了自顶向下 地构造输入串 abbcde的语法树， 首先按文法的开始 符号产生根节点S， 再根据产生式规则 自顶向下地生长这 棵语法树。语法树 的建立过程如图所 示。Sa A B b Ab Acd e自顶向下分析法也称面向目标的分析方法，在 对输入串进行最左推导的过程中，在选择产生式 时其实是一种试探方法，如果每一步选择产生式 来匹配的时候都能够每选必中，则这种方法称为 确定的分析方法；否则在选择产生式时

5、面临多种 可能，不知道选择哪一个产生式合适，就是不确 定的分析方法。因此自顶向下分析法又可分为确定的和不确定 的两种，确定的分析方法对文法有一定的限制， 但由于实现方法简单、直观，便于手工构造或自 动生成语法分析器，因而仍是目前常用的方法之 一。不确定的方法即带回溯的分析方法，这种方 法实际上是一种穷举的试探方法，因此效率低， 代价高，因而极少使用。1. 不确定的自顶向下分析 不确定的自顶向下分析法的基本思想是，对 任何输入串试图用一切可能的办法，从文法 的开始符号出发，自上而下的为它建立一棵 语法树。如果试探成功，则为相应文法的句 子，否则就不是文法句子。这种分析过程本 质上是一种穷举试探过

6、程，是反复使用不同 规则，谋求匹配输入串的过程。因此这种匹 配过程往往一次不能成功，需要重新匹配， 称为回溯。 引起回溯的原因在于文法中关于某个非终结 符的产生式有多个时，而根据面临的输入符 无法唯一确定选择哪个产生式来匹配，从而 引起回溯。自顶向下分析法中存在的问题 回溯问题 左递归问题 回溯问题 回溯时需要恢复到出错点位置，删去曾 经匹配过的符号，还包括一些语义处理 。因此处理回溯是一项复杂的工作，在 回溯时，要清除在回溯之前编译程序所 做的大量记录工作，然后重新开始记录 ，这就降低了语法分析的效率。避免回 溯是自顶向下语法分析中需要解决的问 题之一。 回溯的具体表现 回溯具体表现为下列两

7、种情况： 1. 由于相同左部的产生式的候选式的 FIRST集交集不为空而引起回溯。 2.由于相同左部非终结符的候选式存在能 推导出的产生式，且该非终结符的 FOLLOW集中含有其它候选式的FIRST集的 元素。表现一示例 由于相同左部的产生式的候选式的FIRST 集交集不为空而引起回溯： 【例46】设有文法G6S为： SxAy A*|*串x*y的分析过程Sx A y* *(S,x) 选择产生式SxAy 当前要替换 的非终结符当前要匹配 的输入符(A, *) 可选择两个产生式 A*或A*Sx A y*回溯：回到出错点，重新 选择产生式A*，成功原因 上述文法发生回溯的原因就在于A的两 个产生式的

8、候选式的第一个符号都是* ，从而根据输入符*来选择A的产生式时 有多种可能，因此会引起回溯。 即：关于A的产生式的可选集交集不为 。 SELECT(A*)SELECT(A*)=*表现二示例 由于相同左部非终结符的候选式存在能推导 出的产生式，且该非终结符的FOLLOW集中 含有其它候选式的FIRST集的元素。 【例如】例4.5的文法G5：SaASSbAbAA对输入串ab#的试探推导过程Sa A SSa A Sb ASa A Sb原因 上述文法发生回溯的原因就在于选择产 生式A相当于与A的后随符号 FOLLOEW（A）a,b匹配，但是由于A 的后随符号b与A的第一个候选式的第一 个符号b相同，从

9、而根据输入符b来选择 A的产生式时有多种可能，因此会引起 回溯。 即：关于A的产生式的可选集交集不为 。 SELECT(AbA)SELECT(A)=b左递归问题 【例4.7】算术表达式的文法G7E为： E ET|T T T*F| F F i |（E）对输入串i*i+i进行试探推导 EE + TE + TEE + TEE + TE + TE + T结论 当一个文法是左递归的，采用自顶向下 分析法会使分析过程陷入无限循环之中 。 回溯会使语法分析动作不确定，而左递 归会使语法分析程序陷入无限循环之中 ，这些都使得语法分析的动作是不确定 的。 不确定的语法分析方法带回溯的自顶向 下分析法实际上是一种

10、穷举的试探方法 ，当分析不成功时则推翻以前的分析退回到 适当位置再重新试探其余候选式可能的推导 ，这样需要记录已选过的产生式，直到把所 有可能的推导序列都试完仍不成功才能确认 输入串不是该文法的句子而报错。由于在编 译程序真正实现时往往是边分析边插入语义 动作，因而带回溯的语法分析方法代价很高 ，效率很低，在实用编译程序中几乎不用， 因此对它实现的详细算法不做介绍。2.确定的自顶向下的分析确定的自顶向下分析方法，首先要解决 从文法的开始符号出发，如何根据当前的输 入符号(单词符号)唯一地确定选用哪个产生 式替换相应非终结符往下推导，或构造一棵 相应的语法树。 【例4.2】若有文法G2S： Sa

11、AB AbB AcA Ba Bd 文法G2的句子acbad的自顶向下分析过程如下 ：示例一注意：#是输入结束符 最左推导 过程所选产生式输入串(当前要替换的非 终结符,输入符)1 Sacbad# (S,a)2 aABSaABacbad#(A,c)3 acAB AcAacbad#(A,b)4 acbBBAbBacbad#(B,a)5 acbaBBaacbad#(B,d) 6 acbadBdacbad#推导成功以上最左推导所建立输入串acbad的语法树如图 所示。Sa A B c Ab Bad选择产生式是唯一的在第2步推导时，当前要替换的非终结 符为A，面临的输入符为c，所以选择A 的产生式来推导

12、时，只能选产生式 AcA，而不能选AbB。同样，在第5 步推导时，当前要替换的非终结符为B ，面临的输入符为d，所以选择B的产生 式来推导时，只能选产生式Bd，而不 能选Ba。这样就保证上述每一步推导 都是确定的。文法的特点文法G2有以下两个特点：(1)每个产生式的右部都由终结符号开始；(2)如果两个产生式有相同的左部，那么它 们的右部由不同的终结符开始。对于这样的文法显然在推导过程中完全 可以根据当前要替换的非终结符和输入符 号决定选择哪个产生式往下推导，因此分 析过程是唯一确定的。 示例二【例4.3】若有文法G3S为： SAa SBb Ac AdA Be BfB文法G3的句子ddca的自顶

13、向下分析 过程如下：最左推导 过程所选产生式输入串(当前要替换的非 终结符,输入符)1 Sddca#(S,d)2 AaSAaddca#(A,d)3 dAa AdAddca#(A,d)4 ddAaAdAddca#(A,c)5 ddcaAcddca#推导成功以上最左推导所建立输入串ddca的语法树如图 所示。SA a d Ad Ac文法的特点 这个文法的特点是： （1）产生式的右部不全是由终结符开始。 （2）如果两个产生式有相同的左部，它们的 右部是由不同的终结符或非终结符开始。 （3）文法中无空产生式。讨论 对于产生式中相同左部含有非终结符开始的 产生式，在推导过程中选用哪个产生式不像G2 文法

14、那样直观。 对于输入串ddca，其第一个符号是d，这时从 S出发选择SAa还是选择SBb时，需要知道 Aa或Bb能推导出的首终结符号集合是什么（ 即Aad，还是Bbd）。若Aad成立 ，则选择SAa往下推导；若Bbd成立， 则选择SBb往下推导；其它情况则为不确定 推导或出错。 首终结符号集 【定义4.1】设G( VN, VT , P, S)是上下 文无关文法，是由非终结符与终结符 组成的任意符号串，用FIRST()表示 的首终结符集，则 FIRST() a|a, aVT,(VNVT ) * 若，则规定FIRST() (空集) 。* 求符号串Aa与Bb的首终结符集： 因为Aaca，AadAa，所以FIRST(Aa)=c,d。 因为Bbeb，BbfBb，所以FIRST(Bb)=e,f。 但是FIRST(Aa) FIRST(Bb)= 因而可以根据当前的输入符号是属于哪个产生式 右部的首终结符集而决定选择相应产生式进行推 导，即当前要替换的非终结符为S，面临的输入 符为d时，只能选择产生式SAa（因为 dFIRST(Aa)）。这样仍然是确定的自顶向下分 析。 假如考虑文法中有_产生式时,将会产 生什么问题呢？先看下面的例子： 【例4.4】若有文法G4S： SaAB AbB AcA A Ba Bd 文法G4的句子aca的自顶向下分析过程如 下：最左推导 过程所选产生