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

1第四章自顶向下语法分析方法语法分析是编译过程的核心部分。语法分析的任务是：按照文法，从源程序符号串中识别出各类语法成份，同时进行语法检查，为语义分析和代码生成作准备。执行语法分析任务的程序称为分析程序。也称为语法分析器，它是编译程序的主要子程序之一。在第二章中我们已经介绍过。通过语法分析可建立起相应的语法树。按语法树的建立方法，我们将语法分析方法分成两大类，即自顶向下分析和自底向上分析。下面，我们先介绍自顶向下分析。本章重点：自顶向下分析、LL（1）分析第一节自顶向下分析方法一、带回溯的自顶向下分析算法这是自顶向下分析的一般方法，即对任一输入符号串，试图用一切可能的方法，从识别符号出发，根据文法自上而下地为输入串建立一棵语法树。下面用一个简单例子来说明这种过程：假定有文法G[S]：S→cＡdA→ab|a以及输入串w=cad为了自上而下地构造w的语法树，我们首先按文法的识别符号产生根结点S，并让指示器IP指向输入串的第一符号c。然后，用S的规则（此处左部为S的规则仅有一条）把这棵树发展为（a）（b）（c）图3-1-1图3-1-1a。我们希望用S的子结从左至右匹配整个输入串w。首先，此树的最左子结是终结符c为标志的子结，它和输入串的第一个符号相匹配。于是，我们就把IP调整为指向下一输入符号a，并让第二个子结A去进行匹配，非终结符A有二个选择，我们试着用它的第一个选择去匹配输入串，于是把语法树发展为图3-1-1b。子树A的最左子结和IP所指的符号相符，然后我们再把IP调为指向下一符号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可以通过如下的推导过程将其推导出来：SCAdcad所以用最左推导，是因为我们对输入串是自左向右扫描的，只有使用最左推导，才能保证按扫描顺序去匹配输入串。在上述推出符号串w的过程中，由于出现在符号串中的非终结符号只有一个，因此，未明显地表现出最左推导的性质。根据以上分析，不难编出程序来实现这种分析的算法。但是，上述这种自顶向下的分析算法存在着一定的困难和缺点。困难表现在不能为左递归文法构造自顶向下的语法分析器（上述所举例子adcASbadcASdcAS2S→Sa|bSSaSaSaSaAABAcBbAcA→aB|BbB→Ac|d的文法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′|ε对于间接左递归的消除，需先将间接左递归变为直接左递归，然后再接上述方法消除。条件是文法中无A→A的有害规则和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，则语法错，转出错处理。这样就避免了分析过程的回溯。若文法的任一非终结符号，其规则右部的各个选择所能推出的终结符号串的头符号集合不满足两两相交的条件时，那么，要构造一个不带回溯的自顶向下的语法分析程序，需要采取什么措施呢？一般可采取改写文法的办法来解决。（三）改写文法当文法不满足，可改写文法3提因子U→xv|xwU→x(v|w)三、递归子程序法此方法的主要做法是：对文法中每个非终结符号U,都编出一个子程序，以完成该非终结符号所对应的语法成分的分析和识别任务。某个非终结符号的语法分析子程序的功能是：用该非终结符号的规则的右部符号串去匹配输入串。分析过程是按文法规则自顶向下一级一级地分配任务，即调用有关的子程序来完成。当编译程序根据文法和当前输入符号预测到下一个语法成分为U时，即预测到待匹配的输入符号串可以为从U出发所推导出的符号串相匹配时，就确定U为目标，并调用分析和识别U的子程序。在分析和识别U的过程中，有可能还要确立其他子目标并调用相应的子程序，只有在被调用的分析和识别某语法成分的子程序匹配输入串成功并正确返回时，该语法成分才算真正的获得了识别，并确定输入串无语法错误。。为什么针对某些非终结符号所编出的分析程序要编成递归子程序?因为文法具有递归性。前面已讲过，自顶向下分析不能处理左递归文法，若有左递归，则应改写文法予以消除。但是，消除了左递归不等于消除了文法的所有递归性质，此时，文法仍可以有右递归性或自嵌入性。如在文法中有规则U→…U或U→…U…此仍为递归规则，故分析U的子程序要编成递归子程序。因为该子程序在用规则右部符号串去匹配输入串的过程中，又要调用U自己。即在通过该子程序正常出口返回调用程序以前，又要重新直接进入该子程序，这就是直接递归。此外，还有间接递归，如在文法中有规则：U→…VV→…UW那么U…V…UW即U+⇒…UW在该情况下，在分析U的子程序中要调用分析V的子程序；而在分析U的子程序中又要调用分析V的子程序。这样，对U的分析程序就要编成递归子程序，因在进入U的分析程序以后，在返回调用程序以前，又可能间接地进入自己。第二节LL(1)分析方法本节，我们将介绍实现自顶向下分析的另一种方法，即所谓LL(1)分析方法。如此命名该分析方法的原因在于相应的语法分析将按自左至右的顺序扫描输入符号串，并在此过程中产生一个句子的最左推导。至于括号中的“1”，则表示在分析过程中，每进行一步推导，只要向前查看一个输入符号，便能确定当前所应选用的产生式（规则）。因此，我们通常把按上述方法执行语法分析任务的程序称为LL(1)分析程序或LL(1)分析器，使用这种方法进行语法分析，可借助于一张分析表及一个语法分析栈，在一个总控程序控制下很方便地实现。下面，我们将首先介绍LL(1)分析器的逻辑结构和工作过程，然后再介绍LL(1)分析器的构造方法。（一）LL(1)分析器的逻辑结构及工作过程在逻辑上，一个LL(1)分析器由一个总控程序、一张分析表和一个分析栈组成，如图4-2-1所示。其中：1、“输入”即待分析的符号串（注意，#∈VT，我们之所以在输入串的末尾放置一个#，仅为了分析算法格式的统一）。2、分析表M可用一个矩阵（或二维数组）来表示，它概括了相应文法的全部信息。矩阵的每一行与文法的一个非终结符号A相关联，而每一列则与文法的一个终结符号或#相关联。分析表元素M[A,a]或者指示了当前推导所应使用的产生式，或者指出了输入串中含有语法错误。分析器对每一输入串的分析在总控程序控制下进行。其算法如下（为书写方便。在下面的叙述中，我们将分析栈按顺时钟旋转九十度）：第一步分析开始时，首先将符号#及文法的开始符号S依次置于分析栈底部，并把各指示器调整至起始位置，即初始格局为a1a2…ai…an#X分析栈#图4-2-1总控程序分析表m4然后，反复执行第二步所列的工作。第二步设在分析的某一步，分析栈及余留的输入符号串处于如下的格局其中，X1，X2，…Xm为分析过程中所得的文法符号，此时，可视栈顶符号Xm的不同情况，分别做如下的动作：1、若Xm∈VN，则以Xm及ai组成符号对（Xm,ai）查分析表M，设M[Xm,ai]为一产生式，譬如说Xm→UVW，此时将Xm从分析栈中退出，并将UVW按反序推入栈中（即用该产生式推导一步），从而得到新的格局但若M[Xm,ai]=“ERROR”，则调用出错处理程序进行处理；2、若Xm=ai≠#，则表明栈顶符号已与当前正扫视的输入符号得到匹配，此时应将Xm（即ai）从栈中退出，并将输入符号指示器向前推进一个位置；3、若Xm=ai=#，则表明输入串已完全得到匹配，此时即可宣告分析成功而结束分析工作。例考虑文法G[E]：E→TE'E'→+TE'|εT'→*FT'|εF→(E)|iT→FT'相应的分析表如图4-2-2所示（其构造方法，在后面叙述）。现以输入符号串i+i*i为例，列出利用上述算法对此符号串的分析过程如图4-2-3所示。i+*()#EE→TE'E→TE'E'E'→+TE'E'→εE'→εTT→FT'T→FT'T'T'→εT'→*FT'T'→εT'→εFF→iF→(E)图4-2-2#Sa1a2…an#分析栈输入串aiai+1…##X1X2…Xm-1Xmaiai+1…##X1X2…Xm-1WVU步骤分析栈余留输入串所用产生式1#Ei+i*i#E→TE'2#E'Ti+i*i#T→FT'3#E'T'Fi+i*i#F→i4#E'T'ii+i*i#5#E'T'+i*i#T'→ε6#E'+i*i#E'→+TE'7#E'T++i*i#8#E'Ti*i#T'→FT'9#E'T'Fi*i#F→i10#E'T'ii*i#11#E'T'*i#T'→*FT'12#E'T'F**i#13#E'T'Fi#F→i14#E'T'ii#15#E'T'#T'→ε16#E'#E'→ε17##成功图4-2-35（二）LL(1)分析表的构造方法上述LL(1)分析算法对于不同的LL(1)文法都是相同的。也就是说，对不同的LL(1)分析器而言，它们的总控程序都是相同的，不同的仅仅是分析表。再者总控程序十分简单，非常容易实现，所以我们只着重讨论构造分析表的问题。为了构造分析表，我们需要预先定义和构造两个与文法有关的集合FIRST和FOLLOW。假定α是文法G的任一符号串，或者说α∈(VTUTN)*，我们定义：FIRST(α)={a|α*⇒aβ,a∈VT}特别是，若α*⇒ε，则规定ε∈FIRST(α)，换句话说，FIRST(α)是从α可能推导出的所有开头终结符号或可能的ε。假定S是文法的开始符号，对于G的任何非终结符A，我们定义：FOLLOW(A)={a|S*⇒…Aa…，a∈VT}特别是，若S*⇒…A，则规定#∈FOLLOW(A)。换句话说，FOLLOW(A)是所有句型中出现在紧接A之后的终结符或#。下面，我们将首先给出构造集合FIRST及FOLLOW的算法，然后再给出构造分析表的算法。1、计算F1RST集根据定义计