编译原理第四章自顶向下语法分析法.doc

第四章 自顶向下语法分析方法 自顶向下分析方法 带回溯的自顶向下分析算法 这是自顶向下分析的一般方法，即对任一输入符号串，试图用一切可能的方法，从识别符号出发，根据文法自上而下地为输入串建立一棵语法树。 用一个简单例子来说明这种过程： G[S]： S→cＡd 　　　　　　　　 A→ab|a 以及输入串w=cadw的语法树，我们首先按文法的识别符号产生根结点S，并让指示器IP指 向输入串的第一符号c。然后，用S的规则（此处左部为S的规则仅有一条）把这棵树发展为 （ a） （b） （c） 图3-1-1 图3-1-1a。我们希望用S的子结从左至右匹配整个输入串w。首先，此树的最左子结是终结符c为标志的子结，它和输入串的第一个符号相匹配。于是，我们就把IP调整为指向下一输入符号a，d并让A的第二个子结进入工作。但A的第二个子结为终结符号b，与IP当前指的符号d不一致。因此，A宣告失败。这意味着A的第一个选择此刻不适用于构造w的语法树。这时，我们应该回头（回溯）看A是否还有别的选择。 为了实现回溯，我们一方面应把A的第一个选择所生长的子树注销掉；另一方面，应把IP恢复为进入A时的原值，也就是让它重新指向第二输入符号a。现在我们试探用A的第二个选择，即考虑生成图3-1-1c的语法树。由于子树A只有一个子结a，而且，它和IP所指的符号相一致，于是，A完成了匹配任务。在A获得匹配后，指示器指向下一个未被触及的符号d。 在S的第二子结A完成匹配后，接着就轮到第三个子结d进行工作。由于这个子结和最后一个输入符号相符，于是，我们完成了构造语法树的任务，证明了w是文法G[ s]的一个句子。 上述自顶向下地为输入符号w建立语法树的过程，实际上也是设法建立一个最左推导序列，以便通过一步步推导将输入串推导出来。很明显，对于输入串w可以通过如下的推导过程将其推导出来：SCAdcad 所以用最左推导，是因为我们对输入串是自左向右扫描的，只有使用最左推导，才能保证按扫描顺序去匹配输入串。在上述推出符号串w的过程中，由于出现在符号串中的非终结符号只有一个，因此，未明显地表现出最左推导的性质。 根据以上分析，不难编出程序来实现这种分析的算法。但是，上述这种自顶向下的分析算法存在着一定的困难和缺点。困难表现在不能为左递归文法构造自顶向下的语法分析器（上述所举例子的文法G[s]是不具有在递归性的）。缺点主要表现在存在着回溯问题。当然，应用带回溯的自顶向下的分析算法还必须将文法规则存放于内存。下面将具体介绍这种分析算法所存在的问题及其解决办法。 二、存在问题及解决办法 （一）左递归问题 自顶向下分析法只有规则排列得合适时，才能正确工作。该法的一个基本缺点是不能处理具有左递归的文法。如下所示。 如：直接左递归 和 间接左递归 无法确定语法树的终止，清除直接左递归的较好方法是改为右递归 如：S→Sa|b 改为 S→bS′ S′→aS′|ε 一般情况 A→Aα1|Aα2| … Aαm|β1|β2…βn 清除左递归后改写为： A→β1A′|β2A′ … |βnA′ A′→α1A′|α2A′ … |αmA′|ε 对于间接左递归的消除，需先将间接左递归变为直接左递归，然后再接上述方法消除。 条件无AA　的有害规则和A→ε的空产生式 （二）回溯 当产生式有多个选择时，选那个输入串U→α1|α2|…|αn 该规则右部有n个选择,为了实现目的,我们对文法的要求是: FIRST（αi）∩FIRST（αj）=ф（i≠j） 定义1：设G=（VT，VN，S，P）是上下文无关文法FIRST（α）={a| α (aβ，a∈VT，α，β∈V*} 若α(ε，则规定α∈FIRST（α） 即对文法中的任意一个非终符号，其规则右部有多个选择时，那么，由各个选择所推出的终结符号串的头符号集合要两两不相交。这样，就可能根据当时读进的符号是属于哪个选择的FIRST（α），来唯一地确定应该选用哪个选择来匹配输入串。如当前的输入符号为b(b∈VT)， 若b∈FIRST（αi），则用第i个选择； 若b不∈FIRST（αi），其中i=1~n，则语法错，转出错处理。这样就避免了分析过程的回溯。 若文法的任一非终结符号，其规则右部的各个选择所能推出的终结符号串的头符号集合不满足两两相交的条件时，那么，要构造一个不带回溯的自顶向下的语法分析程序，需要采取什么措施呢？一般可采取改写文法的办法来解决。 （三）改写文法 当文法不满足，可改写文法 提因子 U→xv|xw U→x(v|w) 三、递归子程序法 此方