第4章 自上而下的语法分析.ppt

4.1 带回溯的自上而下分析法概述 4.2 直接左递归的消除 4.3 不带回溯的自上而下分析法的基本原理 4.4 提取左因子 4.5.1 first集的定义及构造算法 4.5.2 follow集的定义及构造算法 4.6 递归下降分析法 4.7 预测分析法 * 从根结点出发，试图用一切可能的办法，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。 ㈠分析过程概述 例已知文法G： S→xAy A→**|* 和输入串α=x*y。 ①初始时，指示器P指向α的第一个符号x。 ②从S推导，因最左子结和输入串第1个符号相匹配，故P指向下一符号*。 ③因第二个子结是非终结符A，从A采用第一个候选进行推导。从A推导出的左子结和指示器P所指的符号一致，故P指向下一个符号y。 ④因A的第二个子结*和指示器P所指的符号不一致，这意味着A的第一个候选不适用于构造α的语法树，应该回溯。将A的子树注销，P恢复进入A时的值。 ⑤用A的第二个候选进行推导，因子树A的子结和指示器P所指的符号*一致，则P指向下一个符号y。 ⑥因S的第三个子结和指示器P所指的符号一致，故α是一个句子。 显然上述分析过程本质上是一个试探过程，是反复使用不同产生式谋求匹配输入串的过程。 ㈡问题和困难 ①对于左递归文法定义的语言，不能采用自上而下的语法分析法。 ②存在虚假匹配，回溯不可避免。 ③编译程序的语法分析和语义分析通常是同时进行的。由于回溯，编译程序所做的一大堆语义分析工作必须推倒重来。 ④当选用所有的不同候选组合，都不能为输入串建立一棵语法树，那么输入串存在语法错误。这种分析法最终只能告知输入串不是文法的一个句子，而无法告知输入串错在何处。 ⑤带回溯的自上而下分析法实际上是一种穷尽一切可能的试探法，因此效率很低，这种分析法几乎没有实用价值。 总上所述，必须消除分析过程中的回溯，只有不带回溯的分析方法才是实际可使用的。 程序设计语言文法的左递归性通常是由左递归规则直接引起的，由规则推导所产生的间接左递归的情况较少见。 ㈠实例引入 例：已知左递归文法G：S→Sa|b，构造文法G的等价文法G，G不含左递归。 解：文法G如下所示 S→bS S→aS|ε ∵SSaSaa…ban 或 Sb ∴L(G)={ ban∣n≥0} ∵SbSbaS…ban 或 SbSb ∴L(G)={ ban∣n≥0} ∵L(G)= L(G) ∴文法G和G等价，而文法G不含左递归。 ㈡直接左递归消除方法 假定关于非终结符P的规则为 P→Pα|β 其中，β不以P开头。可以把关于P的规则变换为如下形式： P→βP P→αP|ε 由于二者推导出的句型均为βαn(n≥0)，故上述变换是等价的。 例文法G： E→E+T|T T→T*F|F F→(E)|i|x|y 经消除直接左递归后变成 E→TE E→+TE|ε T→FT T→*FT|ε F→(E)|i|x|y ㈢直接左递归消除一般规则及等价性证明 设非终结符P的产生式如下 P→Pα1|Pα2|…|Pαm|β1|β2|…|βn 其中，βi（1≤i≤n）不以P开头。可将P的规则改成如下等价形式，即可消除左递归。 P→β1P|β2P|…|βnP P→α1P|α2 P|…|αm P |ε 证： P→Pα1| Pα2|…| Pαm|β1|β2|…|βn 等价于 P→P（α1|α2|…|αm）|（β1|β2|…|βn） 令α=α1|α2|…|αm、β=β1|β2|…|βn，则上式为： P→Pα|β。 消除直接左递归后变成 P→βP P→αP|ε 证： P→Pα1| Pα2|…| Pαm|β1|β2|…|βn 等价于 P→P（α1|α2|…|αm）|（β1|β2|…|βn） 令α=α1|α2|…|αm、β=β1|β2|…|βn，则上式为： P→Pα|β。 消除直接左递归后变成 P→βP P→αP|ε 用α1|α2|…|αm替代α，用β1|β2|…|βn替代β，则有 P→（β1|β2|…|βn）P P→（α1|α2|…|αm）P |ε 等价于 P→β1P|β2P|…|βnP P→α1P|α2 P|…|αm P |ε 设文法G有产生式：A→α1|α2|…|αn ㈠带回溯的自上而下的分析法 采用试探法，对于α1、α2直至αn逐一试探。 ㈡不带回溯的自上而下的分析法 在推导时，根据面临的输入符号去找出A的那个唯一正确的候选式。