编译原理-蒋立源-第4章-语法分析

第四章语法分析

语法分析是编译过程的核心部分，它以词法分析输出的单词串形式的源程序作为输入和分析的对象,它的主要任务是按照程序语言的语法规则，分析源程序的语法结构，即分析如何由这些单词组成各种语法成分，同时进行语法检查，为语义分析和代码生成作准备。执行语法分析任务的程序叫语法分析程序或语法分析器。语法分析程序以词法分析输出的符号串作为输入，在分析过程中检查这个符号串是否为该程序语言的句子。若是，输出该句子的分析树；若不是，则表示源程序存在语法错误，需要报告错误的性质和位置。例如，对于C程序语句“IF(a<10)b=5；”，词法分析识别出了IF、(、标识符、…等单词符号，而语法分析则要检查这些单词之间的搭配、结构是否正确。IF后面是否为(，(后面是否为正确的表达式等等。常用的语法分析方法大体上可以分成自顶向下和自底向上两大类：自顶向下分析方法：语法分析从顶部(树根、语言的识别符号)到底部(叶子、语言的终结符号)为输入的符号串建立分析树。本章介绍的递归下降分析方法和LL分析方法就属于自顶向下分析方法。自底向上分析方法：语法分析从底部到顶部为输入的符号串建立分析树。最常见的LR分析方法采用的就是自底向上分析方法。无论采用哪种分析方法，语法分析都是自左向右地读入符号。4.1自顶向下的分析方法自顶向下的分析方法就是从文法的开始符号出发，按最左推导方式向下推导，试图推出要分析的输入串。自顶向下分析常用的方法有：递归下降分析(recursive-descentparsing)和LL(1)分析(LL(1)parsing)。一般而言,为了给w寻找一个最左推导,须对每一步直接推导应使用的产生式进行判断,即反复用各候选式进行试探,以便得到正确的选择。例如,文法G[E]:1.E→T|EAT2.T→F|TMF3.F→(E)|i4.A→＋|－

5.M→*|/给w=i+i*i建立最左推导。E=>T=>F=>(E)错误,退回到F,选用其他候选式E=>T=>F=>i错误,退回到T,选用其他候选式E=>T=>TMF错误,退回到E,选用其他候选式E=>EAT4.1自顶向下的分析方法上述自顶向下的分析过程有如下基本特点:由于采用了最左推导,故如果文法是左递归的,便会使语法分析过程陷入循环不已的状态。例如E=>EAT=>EATAT=>EATATAT=>…采用最左推导以实现对符号串w的匹配,实际上是用文法产生式的诸候选式反复进行试探的过程,这势必会出现大量的回溯,从而导致语法分析效率的大幅下降。当报告分析失败时,分析程序一般仅能给出输入串w不是句子这一结论,而难于指出出错的具体情况(错误性质和出错位置等)。因此,欲实现自顶向下的语法分析,其首要任务时改造程序设计语言的文法,以消除其中的左递归和避免回溯的出现。4.1.1消除文法的左递归另一种方法是对A引入一个新的非终结符号A’,改写为A→βA’A’→αA’|ε例如，前面文法的规则：E→EAT|T，T→TMF|F，消除左递归：方法一：E→T{AT}T→F{MF}方法二:E→TE’T→FT’E’→ATE’|εT’→MFT’|ε一般的,设文法中全部A-产生式为A→Aα1|Aα2|…|Aαn

|β1|β2|…|βm

改写为A→β1A’|β2A’|…|βmA’

A’→α1A’|α2A’|…|αnA’

|ε我们在第二章提到，不同的文法可描述相同的语言，这些文法称为等价文法。对于左递归问题，我们就是用等价文法来解决，即将文法中的左递归去掉。消除直接左递归的方法如下：对形如A→Aα|β的直接左递归文法规则，用扩充BNF表示来改写规则，即利用元符号“{”和“}”来改写规则，将规则改写成A→β{α}4.1.1消除文法的左递归

下面，再给出一种通过将文法G=(Vn,Vt,P,S)表示成矩阵形式而一次消除G的全部左递归的方法。首先,令Vn={X1,X2,…,Xn},且对G中的每个产生式

Xi→y1|y2|…|ym可将其写成

Xi=X1α1i+X2α2i+…Xnαni+βi于是,文法G的诸产生式便可写成如下的矩阵方程(X1,X2,…,Xn)=(X1,X2,…,Xn)α11

α12…α1n+(β1,β2,…,βn)

α21

α22…α2n…………αn1

αn2…αnn

如果一个非终结符号A是经两步或多步推导而出现的左递归,则可对相关产生式作代入操作，将A-产生式化成直接左递归的，再按上面的方法将左递归消除。例如，对于文法S→Aβ|yA→Sα代入后得到(见引理2.1)S→Sαβ|y消除直接左递归得到

S→yS’S’→αβS’|ε4.1.1消除文法的左递归或X=XA+B此方程有形如X=BA*的最小解,由于A*=I+AA*其中I=ε

ΦΦ…ΦΦεΦ…Φ……ΦΦΦ…ε若设A*=Z=z11z12…z1n

z21z22…z2n…………zn1zn2…znn则有

X=BZZ=I+AZ将上述两矩阵式写成分量式,便得到了一组等价的新的产生式,且消除了原文法的一切左递归。4.1.1消除文法的左递归例4.1考虑文法S→Sa|Ab|aA→Sc显然,S,A都是左递归的非终结符。首先写出文法的矩阵表示

(SA)=(SA)a

c+(aΦ)bΦ

设ac*=Z=z11z12

bΦ

z21z22

则有

(SA)=(aΦ)z11z12z21z22z11z12=εΦ+acz11z12z21z22ΦεbΦz21z22

于是得到新的等价文法S→az11A→az12z11→az11|cz21|εz12→az12|cz22z21→bz11z22→bz12|ε

删除无用产生式S→az11z11→az11|cz21|εz21→bz114.1.2回溯的消除及LL(1)文法对于给定的文法G[S]=(Vn,Vt,P,S)和给定的输入符号串w=a1a2…an(ai∈Vt)，为判断w是否为L(G)中的句子，现试图为w建立一个从S出发的最左推导，设经过若干步推导后得到

S=*>w1Aβ

A∈Vn，β∈(Vn∪Vt)*其中w1=a1a2…ai-1，即w的一个前缀w1已从上面的推导得到匹配，现须对Aβ继续进行推导，现设G中的全部A-产生式为

A→y1|y2|…|ym且对这m个候选式yk(1≤k≤m)，要么全部ykβ均不能推导出以ai打头的符号串(此时w不是句子)，要么存在一个yj，能使yjβ推导出以ai打头的符号串，而其余的ykβ则不能推出，这样上述推导过程在产生式选择上的试探将可避免。如果文法G中的全部产生式均满足上述要求,则消除回溯的问题自然就解决了。4.1.2回溯的消除及LL(1)文法可见,要实现无回溯的自顶向下分析,对相应文法须有一定的要求。为导出文法应满足的条件,需定义候选式y的终结首符集和非终结符号A的后继终结符号集如下:FIRST(y)={a|y=*>a…，a∈Vt}

当y=*>ε时,约定ε∈FIRST(y)

FIRST(y)就是从y可能推导出的句型的所有开头终结符和可能的ε。FOLLOW(A)={a|S#=*>…Aa…,a∈Vt}

当S=*>…A,约定#∈FOLLOW(A)FOLLOW(A)就是在所有的句型这紧接A之后的终结符或#。于是,对于一个已化简的非左递归文法G,在进行自顶向下语法分析时,不出现回溯的充分条件是对于G中的每个产生式A→y1|y2|…|ym,其各候选式均应满足:(1)不同的候选式不能推出以同一终结符号打头的符号串,即

FIRST(yi)∩FIRST(yj)=Φ1≤i,j≤m;i≠j(2)若有yj=>ε,则其余候选式yi所能推导出的符号串不能以FOLLOW(A)中的终结符号开头,即

FIRST(yi)∩FOLLOW(A)

=Φi≤1,2,…,m;i≠j通常,我们将满足上述条件的文法称为LL(1)文法。即对于此种文法,可采用从左到右扫视源程序P,并按最左推导的方式求得与P中各符号的匹配,而且每步推导只需向前查看一个输入符号,就可准确的选择所用的产生式。4.1.2回溯的消除及LL(1)文法下面,给出对给定文法G求各个FIRST集FOLLOW集的算法。由于每个产生式的各个候选式均是一个由文法符号所组成的符号串,因此仅须给出对单个文法符号求这两个集合的方法即可。文法符号的FIRST集合构造方法：对于文法中的符号X∈Vn∪Vt，其FIRST(X)集合可反复应用下列规则计算，直到其FIRST(X)集合不再增大为止：

1)若X∈Vt，则FIRST(X)={X}2)若X∈Vn，且具有形如X→aα的产生式(a∈Vt)，或具有形如X→ε的产生式，则把a或ε加进FIRST(X)。3)设G中有形如X→Y1Y2…Yk的产生式，若Y1∈Vn，则把FIRST(Y1)中的一切非ε符号加进FIRST(X)；对于一切2≤i≤k，若Y1，Y2，…，Yi-1均为非终结符号，且ε∈FIRST(Yj)，1≤j≤i-1，则将FIRST(Yi)中的一切非ε符号加进FIRST(X)；但若对一切1≤i≤k，均有ε∈FIRST(Yj)，则将ε符号加进FIRST(X)。

若X→Y1|Y2|…|Yk∈P,且Y1∈Vn,则把FIRST(Y1)\ε加进FIRST(X);若ε∈FIRST(Y1),则把FIRST(Y2)\ε加进FIRST(X);若ε∈FIRST(Y1)和FIRST(Y2),则把FIRST(Y3)\ε加进FIRST(X)…以此类推;但若对一切1≤i≤k,均有ε∈FIRST(Yi),则把ε加进FIRST(X)4.1.2回溯的消除及LL(1)文法例4.2设有文法S→abBA→SC|εB→AbAC→B|c求所有非终结符和符号串AABcab的FIRST集合。解:FIRST(S)={a}

FIRST(A)=FIRST(SC)∪{ε}=FIRST(S)∪{ε}={a,ε}FIRST(B)=FIRST(AbA)=FIRST(A)\ε∪FIRST(bA)={a,b}FIRST(C)=FIRST(B)∪c={a,b,c}FIRST(AABcab)=FIRST(A)\ε∪FIRST(A)\ε∪FIRST(Bcab)={a}∪FIRST(B)={a,b}4.1.2回溯的消除及LL(1)文法对于文法中的符号A∈Vn，其FOLLOW(A)集合可反复应用下列规则计算，直到其FOLLOW(A)集合不再增大为止：1)对于文法的开始符号，令#∈FOLLOW(S)2)若G中有形如A→αBβ的产生式，且β≠ε，则将FIRST(β)中的一切非ε符号加进FOLLOW(B)。3)若G中有形如A→αB或A→αBβ的产生式，且ε∈FIRST(β)，则FOLLOW(A)中的全部元素均属于FOLLOW(B)。注意：在FOLLOW集合中无ε。

4.1.2回溯的消除及LL(1)文法例4.3，有文法E→TE’，E’→+TE’，E’→ε，

T→FT’，

T’→*FT’，T’→ε，F→(E)|i，求各非终结符号的FOLLOW集。解：首先，我们需要求出某些符号的FIRST集：

FIRST(E)=FIRST(T)=FIRST(F)={(，i}FIRST(E’)={+，ε}，FIRST(T’)={*，ε}

接下来，按FOLLOW集定义求各非终结符号的FOLLOW集：

FOLLOW(E)={)，#}，FOLLOW(E’)=FOLLOW(E)={)，#}FOLLOW(T)=FIRST(E’)∪FOLLOW(E)∪FOLLOW(E’)={+，)，#}FOLLOW(F)=FIRST(T’)∪FOLLOW(T)∪FOLLOW(T’)={+，*，)，#}FOLLOW(T’)=FOLLOW(T)={+，)，#}前进4.1.3递归下降分析法

4.3.1递归下降分析的基本方法递归下降分析的概念极为简单，其方法是将文法中的每一个非终结符U的文法规则看作是识别U的一个过程定义，为每个非终结符号构造一个子程序，以完成该非终结符号所对应的语法成分的分析和识别任务。如果U的文法规则的右部只有一个侯选式，则按从左向右的顺序依次构造规则U的识别过程代码。如果有终结符号，判断能否与输入的符号相等，如果相等，表示识别成功，读入指针指向下一个输入符号；如果不等，则意味着输入串此时有语法错误。如果是非终结符号，则简单调用这个非终结符号的子程序，由这个子程序完成该非终结符号所对应的语法成分的分析和识别任务。当一条规则右部有多个侯选式时，则根据每个侯选式的第一个符号确定该侯选式分支。只有被调用的分析和识别某语法成分的子程序匹配输入串成功，且正确返回时，该语法成分才算真正获得识别。

例4.4，考虑文法Z::=(U)|aUb

，U::=dZ|e，为其构造递归下降分析子程序。并对输入串aeb进行语法分析。解：文法中有两个非终结符号Z和U，那么我们需要分别编两个过程来完成Z和U规则的识别。对于规则Z::=(U)|aUb，右部有两个候选式，因此，U的识别过程有两个分支，分别根据符号(和a来判别。同理对规则U::=dZ|e设计的过程也分为两个分支。见图4.1(a)和(b)所示。4.1.3递归下降分析法Z::=(U)|aUb过程ZINPUTSYM=下一个符号U出口语法错误：输入串少‘)’INPUTSYM=‘a’YNNNNYY语法错误：输入串少‘(’、‘a’语法错误：输入串少‘b’INPUTSYM=‘(’INPUTSYM=‘)’INPUTSYM=‘b’INPUTSYM=下一个符号INPUTSYM=下一个符号UY图4.1(a)非终结符号Z的分析程序过程UINPUTSYM=下一个符号Z出口INPUTSYM=‘e’YNNY语法错误：输入串少‘d’、‘e’INPUTSYM=‘d’INPUTSYM=下一个符号YU::=dZ|e图4.1(b)非终结符号U的分析程序4.1.3递归下降分析法每个非终结符号的子程序设计好后，就可以对输入串进行语法分析。假设输入串为aeb,从Z子程序开始识别，INPUTSYM

=a,由于INPUTSYM不等于(，等于a，所以选择Z子程序的右边分支，表示选择了Z::=aUb规则。读下一个符号，使INPUTSYM

=e，调U子程序，因INPUTSYM=e，所以，读下一个符号，使INPUTSYM

=b，表示使用U::=e规则，并返回调用程序Z子程序右边分支U的下方，接着判断INPUTSYM=b，读下一个符号，并退出Z，分析过程结束，从而判定输入串aeb语法分析成功。这个过程相当于构造了如下推导过程：

Z=>aUb=>aeb

4.1.3递归下降分析法E→T|E+T|E-TE→T{+T|-T}T→F|T*F|T/FT→F{*F|/F}ETYN出口INPUTSYM=下一个符号INPUTSYM=‘+’INPUTSYM=‘-’NYTFYN出口INPUTSYM=下一个符号INPUTSYM=‘*’INPUTSYM=‘/’NY图4.2

E和T的分析程序4.1.4预测分析法LL(1)分析方法也是常见的自顶向下分析，LL(1)分析使用一个下推栈而不是递归调用来完成分析。名称中第一个L表示自左向右顺序扫描输入符号串，第二个L表示分析过程产生一个句子的最左推导。括号中的1表示每进行一步推导，只需要向前查看一个输入符号，便能确定当前所应选用的规则。

LL(1)分析的基本方法LL(1)分析器由一个总控程序、一张分析表和一个分析栈组成，如图4.4所示。输入符号串：分析栈a1a2…………an#

XZS#LL（1）总控程序分析表输出流图4.4LL(1)分析器模型4.1.4预测分析法

输入符号串:指要分析的输入符号串。为了分析算法的统一，我们需要在输入串的末尾放置一个特殊符号#，这个符号不属于终结符号集。

分析表M:是一个二维表，可用一个二维数组M[A，a]来表示，它概括了文法的全部信息。分析表中的每一行与文法的一个非终结符号关联，即A可以是文法中的一个非终结符号；而每一列则与文法的一个终结符号或#关联，即a是文法的一个终结符号或#。分析表元素M[A，a]，指出了分析器应采取的动作:或是指出当前推导应使用的产生式,或是指出输入符号串存在语法错误。对于不同的LL(1)文法，LL(1)的分析算法是相同的，不同的仅仅是分析表。显然，如何根据文法来构造分析表是LL(1)分析的关键。对于任意给定的已化简的文法G，为了构造分析表，首先我们要求出每个非终结符号的FOLLOW集合和每个后选式的FIRST集合。然后对文法G中的每个产生式A→y1|y2|…|ym，按下列规则确定分析表中的元素M：1)若a∈FIRST(yi)，则置M[A，a]=“yi”。2)若ε∈FIRST(yj)，且a∈FOLLOW(A)，则置M[A，a]=“yj”。3)除上述两种情况外其余一切表元素均置为“ERROR”。

分析栈：用来存放一系列文法符号。分析开始时，先将#入栈，然后再将文法的开始符号入栈。

输出流：分析过程中使用的产生式序列。总控程序：分析器对输入串的分析靠总控程序完成.根据分析栈的栈顶符号X和当前的输入符号a，总控程序按照分析表的指示来决定分析器的动作.工作过程如下：第一步初始化:分析开始时，首先将符号#及文法的开始符号S依次置于分析栈的底部，并把各指示器调整至起始位置，如图4.5所示。然后，反复执行第二步的操作。输入符号串：

a1a2…………an#分析栈：

S#图4.5分析开始时状况第二步假设分析的某一步，分析栈及余留的符号串如图4.6，则根据栈顶的符号Xm，采取下列动作：aiai+1…………an##X1X2…Xm-1Xm

图4.6分析进行中的状况4.1.4预测分析法(1)若Xm∈Vn，则查分析表的Xm行ai列，假设M[Xm，ai]为产生式Xm→Y1Y2…Yk，则将Xm出栈，并将Y1Y2…Yk反序入栈，如图4.7；若M[Xm，ai]为ERROR，则出错。aiai+1…………an##X1X2…Xm-1YkYk-1…Y1

图4.7反序入栈(2)若Xm=ai≠#，表示栈顶与扫描的符号匹配，则栈顶符号Xm出栈，输入指示器指向下一个符号，否则(即Xm≠ai)出错。(3)若Xm=ai=#，表示输入串完全匹配，分析成功。

4.1.4预测分析法4.1.4预测分析法例4.5考虑算术表达式文法E→TE’，E’→+TE’，E’→ε，T→FT’，T’→*FT’，T’→ε，F→(E)|i对规则E→TE’：FIRST(TE’)={(，i}，那么在分析表的符号E所在的行、符号(和i所在的列对应的位置分别填入TE’,见表4.1的E行。对规则E’→+TE’：FIRST(+TE’)={+}，所以在分析表E’行+列对应的位置填入+TE’，见表4.1的E’行。对规则E’→ε：FOLLOW(E’)={)，#}，所以在分析表E’行)和#列对应的位置填入ε，见表4.1的E’行。……对于一个文法，若按上述方法构造的分析表M不含多重定义，则称它是一个LL(1)文法。返回表4.1算术表达式分析表符号输入符号i+*()#EE’TT’FTE’

FT’

i

+TE’ε

*FT’

TE’

FT’

(E)

ε

ε

ε

ε

表4.1算术表达式分析表4.1.4预测分析法根据表4.1给出的分析表，对符号串i+i*i进行分析。表4.2符号串i+i*i的分析过程步骤分析栈余留输入串所用产生式1234567891011121314151617#E#E’T#E’T’F#E’T’i#E’T’#E’#E’T+#E’T#E’T’F#E’T’i#E’T’#E’T’F*#E’T’F#E’T’i#E’T’#E’#i+i*i#i+i*i#i+i*i#i+i*i#+i*i#+i*i#+i*i#i*i#i*i#i*i#*i#*i#i#i####E→TE’T→FT’F→i

T’→εE’→+TE’

T→FT’F→i

T’→*FT’

F→i

T’→εE’→ε表4.2中输出的产生式序列构成对输入符号串的最左推导。按此产生式序列构造输入符号串i+i*i的最左推导过程如下：E=>TE’

=>FT’E’

=>iT’E’

=>iE’

=>i+TE’

=>i+FT’E’=>

i+iT’E’

i+i*FT’E’

i+i*iT’E’

i+i*iE’

i+i*i

4.1.4预测分析法4.1.5某些非LL(1)文法的改造

对于任何LL(1)文法G,我们总能按上述方法为G构造一个预测分析表,且构造出的分析表决不会含有多重定义的元素.然而,对于非LL(1)文法,或因为它们含有左递归,或因为它们存在二义性,归根结底因为它们不满足无回溯条件,则构造出的分析表必然会出现多重定义的元素.例如,S→abBA→SC|BAA|εB→AbAC→B|cFIRST(S)={a}FOLLOW(S)={a,b,c,#}FIRST(A)={a,b,ε}FOLLOW(A)={a,b,c,#}FIRST(B)={a,b}FOLLOW(B)={a,b,c,#}FIRST(C)={a,b,c}FOLLOW(C)={a,b,c,#}M[A,a]={A→SC,A→BAA}M[A,b]={A→BAA,A→ε}可见分析表含有多重定义元素,2、解决二义性问题这个问题有时可通过反复提取公因子解决。对形如A→αβ1|αβ2|…|αβm的产生式,可改写为A→αA’

A’→β1|β2|…|βm例如，规则：T→(E)|a(E)|a可改成：T→(E)|aT’，T’→(E)|ε

4.1.5某些非LL(1)文法的改造1、左递转成右递归

LL(1)分析不能处理左递归文法，但也不能像递归下降分析那样将左递归改为采用扩充BNF表示。在LL(1)分析中，必须将左递归文法变成右递归文法。例如，对左递归规则E→E+T|T，如果像递归下降分析那样改成E→T{+T}无法形成逆序入栈，但可改成右递归：令E’为新的非终结符号，则等价的右递归规则为：E→TE’，E’→+TE’|ε实际上，在递归下降分析方法中，也可将左递归规则改成右递归进行处理。4.1.5某些非LL(1)文法的改造但并非所有的文法都可用此法解决分析表的多重定义。考虑有文法G[S]：S→AU|BR,A→aAU|b,B→aBR|b,U→c,R→d对于规则S→AU|BR，因为FIRST(AU)∩FIRST(BR)≠φ，故该文法不是LL(1)文法。为了能够提取公因子，必须将非终结符号A、B的产生式带入S的产生式中，得到：S→aAUU|bU|aBRR|bR经提取公因子后，得到S→a(AUU|BRR)|b(U|R),令S’、S”分别代替括号中的左右部分，得如下等价文法：S→aS’|bS”,S’→AUU|BRR,S”→U|R,A→aAU|b,B→aBR|b,U→c,R→d显然，对于规则S’→AUU|BRR，因为FIRST(AUU)∩FIRST(BRR)≠φ，故它仍然不是LL(1)文法。且无论重复多少次提取公因子，都不能把它变成LL(1)文法。由于递归下降分析法也存在这类问题，所以，自顶向下分析方法无法对这类文法进行语法分析。4.1.5某些非LL(1)文法的改造我们把能由某一LL(1)文法产生的语言称为LL(1)语言。LL(1)文法具有下列性质：1)任何LL(1)文法都是无二义的。2)若文法中有左递归，肯定不是LL(1)文法。但有些左递归文法可转换成右递归文法，从而满足LL(1)文法的要求。3)存在一种算法，能判定文法是否为LL(1)文法。4)存在一种算法，能判定任意两个LL(1)文法是否产生相同的语言。5)不存在这样的算法，判定任意上下文无关语言能否由LL(1)文法产生。6)非LL(1)语言是存在的。在LL系列分析方法中，若每一步推导不是向前看一个字符，而是看K个字符才能确定要选用的产生式，则称为LL(K)分析，能满足LL(K)分析条件的文法叫LL(K)文法。习题4.1对下面文法，设计递归下降分析程序。

S→aAS|(A),A→Ab|c4.2设有文法G[Z]：

Z∷=(A),A∷=a|Bb,B∷=Aab若采用递归下降分析方法，对此文法来说，在分析过程中，能否避免回溯？为什么？4.3若有文法如下，设计递归下降分析程序。

<语句>→<语句><赋值语句>|ε<赋值语句>→Id=<表达式>；

<表达式>→<项>|<表达式>+<项>|<表达式>-<项><项>→<因子>|<项>*<因子>|<项>/<因子><因子>→ID|NUM|(<表达式>)4.4有文法G[A]：A::=aABe|εB::=Bb|b1)求每个非终结符号的FOLLOW集。

2)该文法是LL(1)文法吗？

3)构造LL(1)分析表。4.5若有文法A→(A)A|ε，

1)为非终结符A构造First集合和Follow集合。

2)说明该文法是LL(1)的文法。4.6利用分析表4.1识别以下算术表达式，请写出分析过程：

1)i+i*i+i2)i*(i+i+i)习题4.7考虑下面简化了的C声明文法：

<声明语句>→<类型><变量表>；

<类型>→int|float|char<变量表>→ID,<变量表>|ID1）

在该文法中提取左因子。2）

为所得的文法的非终结符构造First集合和Follow集合。3）

说明所得的文法是LL(1)文法。4）

为所得的文法构造LL(1)分析表。5）

假设有输入串为:charx,y,z，写出相对应的LL(1)分析过程。习题4.8修改语法分析程序，使该程序能分析do语句和逻辑表达式,有关文法规则如下：

<statement>::=if_stat>|<while_stat>|<do_stat>|<for_stat>|<read_stat>

|<write_stat>|<command_stat>|<expression_stat><do_stat>::=do<statement>while<expression>;<expression>::=ID=<log_expr>|<log_expr><log_expr>::=<log_expr>(&&|||)<bool_expr>|!<log_expr>|<bool_expr>&&、||、!为逻辑运算符。习题4.2自底向上的语法分析主要内容：概述简单优先分析法算符优先分析法优先函数LR分析法自顶向下语法分析：对给定的输入符号串，从方法的开始符号出发，为其构造一个推导过程，试图自上而下地构造一棵语法树。最常用的推导方法最左推导，即对于一个推导过程中的每一步，被替换的总是当前句型中最左端的非终结符号。常用的自顶向下的语法分析方法：１）递归下降法２）LL(1)分析法概述

例：有文法G[S]：

(1)S→

aAcBe(2)A→

b(3)A→

Ab(4)B→

d试分析符号串abbcde是否为该文法的句子。

解：首先，我们从文法的开始符号进行规范推导，依次使用1、4、3、2规则，就可得到符号串abbcde。规范推导过程如下：S=>aAcBe=>aAcde=>aAbcde=>abbcde

概述从符号串开始，向上归约，如果最终能够规约到文法的开始符号S，则同样可以说明该输入符号串是这个文法的句子。其归约过程如下图所示。ScBcAaAbdbScBcAaAbdScBcAadScBcAaS

(a)b归约为A(b)Ab归约为A(c)d归约为B(d)aAcBe归约为S(e)归约过程概述自底向上语法分析：从输入符号串开始，通过反复查找当前句型的句柄，并使用规则，将找到的句柄归约成相应的非终结符号，直到归约到开始符号，从而自底向上地为输入符号串构造一棵语法分析树。自底向上分析方法，也可称为移进-归约法

(1)四个动作：移进，归约，接受，报错

(2)分析栈：用于存放从输入符号串移进或归约生成的符号。

(3)从左到右读入输入符号串的各个符号，并依次入栈，当栈顶符号串形成一个句柄时，就进行一次归约，即把栈顶构成句柄的若干符号用相应产生式左部的非终结符号来代替，也就是把句柄符号串从出栈，再把产生式左部的非终结符入栈。

(4)最后，其分析栈里只有界符#及方法的开始符号，则所分析的符号串为合法的句子，报告成功；否则，输入串非法，报告错误。概述步骤

分析栈

余留符号串

下步动作

０123456*7*89101112##b#bb#bba#bbA#bA#A#Aa#Aac#AaS#AaSb#AB#Sbbaacb#baacb#aacb#acb#acb#acb#acb#cb#b#b####移进移进移进按A→a归约用A→bA归约用A→bA归约移进移进用S→c归约移进用B→aSb归约用S→AB归约分析成功表4.４输入串bbaacb的“移进-归约“分析过程通过上述分析可看出，每次归约的句柄都出现在符号栈的栈顶，不会出现在栈的中间，因为我们的算法是自左向右扫描输入符号串，进行的是最左归约。概述

方法G[S]:(1)S→

AB(2)S→

c(3)A→

bA(4)A→

a(5)B→

aSb(6)B→

c两个关键问题：１）如何确定句柄２）句柄确定后，如何确定选用哪一条规则，即产生式两种常用的自底向上语法分析方法：１）优先分析法（简单优先分析法、算符优先分析法）２）LR分析法概述4.2.1简单优先分析法

优先法的基本思想是根据归约的先后次序为同一句型中的相邻文法符号规定相应的优先关系(<,=,>），从而构造一个优先矩阵。以后在分析一个句型(指规范句型)

α=X1X2…Xi-1XiXi+1…Xi+kXi+k+1…Xm

时，将从左到右一次扫视α中的符号，且每扫视一个符号Xi都以其后继符号Xi+1查优先矩阵，判明它们之间的优先关系，以期找到α的句柄之尾符号，然后再从尾符号开始进行反向扫描，直至找到α的句柄之头符号为止。可以证明，此时α中满足Xi-1<XiXi=Xi+1=…Xi+kXi+k>Xi+k+1的最左子串XiXi+1…Xi+k便是规范句型α的句柄。于是按相应产生式A→XiXi+1…Xi+k将句柄规约为A，则得到新的句型

α’=X1X2…Xi-1AXi+k+1…Xm再对α’重复上述操作，并最终将其归约为文法的开始符号。简单优先文法：

(1)每一对文法符号U和R之间，至多只有一种优先关系;

(2)任意两个不同的产生式均无相同的右部。4.2.1简单优先分析法设G=(VN,VT,P,S)是一已化简的文法，V=VN

∪VT，并设Si和Sj是V中的任意两个符号，若G中存在这样的规范句型

α=…SiSj…则此相邻符号Si，Sj和α的句柄之间的关系必然是下述情况之一:(1)若Si在句柄中，而Sj不在句柄中(如图(a)所示)，则Si显然为句柄的尾符号，故G中必有形如A→…Si的产生式，使Si先于Sj被归约。记为Si>Sj。

(2)若Si与Sj同时处于句柄中(如图(b)所示)，则G中必有形如A→…SiSj…的产生式，使Si和Sj同时被归约。记为Si=Sj。当且仅当G中有形如U→…ASj…的产生式,且有A=+>…Si当且仅当G中有形如U→…SiSj…的产生式4.2.1简单优先分析法(3)若Sj在句柄中，而Si不在句柄中(如图(c)所示)，则Sj显然为句柄的头符号，故G中必有形如A→Sj…的产生式，使Sj先于Si被归约。记为Si<Sj。(a)(b)(c)ASiSj………ASiSj……ASiSj………当且仅当G中有形如U→…SiA…的产生式,且有A=+>Sj…需要注意的是：上述三种优先关系都是对方法中的符号序偶来定义的，都不具有对称性，即若Sr>St，并不一定有St<Sr，即使存在Sr＝St，也并不意味着St<Sr4.2.1简单优先分析法

解:显然有E1=++=T1T=**=F(=EE=)

考虑E1→E1+T1∵E1=+>E1+T1E1=+>T1

E1=+>TE1=+>T*FE1=+>FE1=+>(E)E1=+>i

∴T1,T,F,),i>+∵T1=+>TE1=+>T*FE1=+>FE1=+>(E)E1=+>i

∴+<T,F,(,i

考虑T→T*F∵T=+>T*FT=+>FT=+>(E)T=+>i∴F,),i>*∵F=+>(E)F=+>i

∴*<(,i

考虑F→(E)∵E=+>E1E=+>E1+T1E=+>T1E=+>TE=+>T*FE=+>FE=+>(E)E=+>i∴(<E1,T1,T,F,(,i∴E1,T1,T,F,),i>)例4.4给出文法G’[E]的全部优先关系和符号串i+i*i的分析过程

E→E1E1→E1+T1∣T1T1→TT→T*F∣FF→(E)∣i按照这种方式建立的优先矩阵如图4-4所示。需要指出的是用这种方式优先矩阵虽然直观，但对于规模稍大的方法而言显然是不可行的。4.2.1简单优先分析法

在简单优先方法中，进行语法分析时，为了寻找一个句型的句柄的头符号和尾符号，只须逐次查看相邻两个符号间的优先关系即可。具体方法：从左至右依次扫描句型中的符号X1X2…Xm，并在扫描过程中检查相信两符号间的优先关系，一旦出现Xi+k>Xi+k+1时，此Xi+k即为句柄的尾符号。接下来从Xi+k开始，从右至左逐个查看已扫过的符号，直到某相邻两个符号间有优先关系Xi-1<Xi时，此Xi为句柄的头符号。即对于简单优先方法的任何规范句型X1X2…Xm而言，其句柄是该句型中，满足：

Xi-1<Xi

Xi=Xi+1=…=Xi+k

Xi+k>Xi+k+1的最左子串XiXi+1…Xi+k具体算法如程序4-4所示4.2.1简单优先分析法

程序4-4简单优先分析驱动程序#defineSUCCESS1#defineERROR0#defineMAXINPUT300#defineMAXSTACK100#defineSTARTSYMBOL‘S’int

stack[MAXSTACK],a[MAXINPUT];int

IsHigherThan(int,int);int

IsLowerThan(int,int);int

RightSideOfAProduction(int

begin,int

end,int

len);int

parser(void){int

i,k,r;i=0;k=0;stack[0]=‘#’;r=a[k++];

do{int

j,LeftSide;

while(!IsHigherThan(stack[i],r)){stack[++i]=r;r=a[k++];}j=i;while(!IsLowerThan(stack[j-1],stack[j]))j--;

LeftSide=RightSideOfAProduction(stack[j],stack[i],i-j+1);

if(LeftSide){i=j;stack[i]=LeftSide;}elseifi==1&&r==‘#’&&stack[i]==STARTSYMBOL)returnSUCCESS;elsereturnERROR;}while(1);}4.2.1简单优先分析法表4.５符号串i+i*i的移进-归约分析过程步骤分析栈优先关系r余留输入串句柄归约产生式0#<i+i*i#1#i>+i*i#iF→i2#F>+i*i#FT→F3#T>+i*i#TT1→T4#T1>+i*i#T1E1→T15#E1=+i*i#6#E1+<i*i#7#E1+i>*i#iF→i8#E1+F>*i#FT→F9#E1+T=*i#10#E1+T*<i#11#E1+T*i>#iF→i12#E1+T*F>#T*FT→T*F13#E1+T>#TT1→T14#E1+T1>#E1+T1E1→E1+T115#E1>#E1E→E116#E>#(分析成功)4.2.1简单优先分析法

简单优先分析的局限性简单优先分析对文法有较强的要求，通常文法的符号对间的优先关系会多于一种，特别是递归文法。例如，文法中同时存在形如

U→…SiSj…Sj→Sj…的产生式，在符号Si和Sj之间，便同时存在Si=Sj和Si<Sj两种关系。有的文法可通过分层法(析出法)来消除多重优先关系。改写为

U→…SiW…W→Sj…但当两者间既有“<”关系也有“>”关系，上述方法就不能奏效。简单优先分析局限性的根本原因在于局限于考察相邻两个符号的优先关系，如果我们查看更多的符号(如LR(K)分析)，或者考察不相邻的两个符号(如算府优先分析)，则上述矛盾的情况将会得到改善。4.2.2算符优先分析法算符优先分析法，仅在广义运算符(即文法的终结符号)间定义优先关系。定义4.2

若在一个文法G中，不含有形如

U→…AB…的产生式，其中A，B∈VN

，则称G为算符文法。可见,算符文法G的任何产生式右部,都不会出现两非终结符号相邻的情况。在算符文法的任何句型中,两相邻终结符之间的非终结符至多只有一个。中缀表达式是满足这一条件的一种广义运算，事实上程序设计语言中广泛使用的也恰是中缀表达式，但也有些语法成分的定义不满足这一条件。定义4.3

当且仅当G中有形如

U→…ab…或U→…aAb…的产生式时，a=b。4.2.2算符优先分析法定义4.4

当且仅当G中有形如U→…aA…的产生式,且有

A=+>b…或A=+>Bb…时，

a<b。定义4.5

当且仅当G中有形如U→…Ab…的产生式,且有

A=+>…a或A=+>…aB时，a>b。定义4.6

设G为一算符文法，若G的任何一对终结符号之间，至多只有三种算符优先关系=、<和>之一成立，则称G为算符优先文法。FIRSTVT(A)={b∣A=+>b…或A=+>Bb…}LASTVT(A)={a∣A=+>…a或A=+>…aB}4.2.2算符优先分析法

在用算符优先分析法进行语法分析时，每次归约的不再是句型的句柄，而是它的最左素短语。所谓素短语，是指其中至少还有一个终结符号,且不再含有其他素短语的短语。例如EE+TE+TTT*FFi句型T+T*F+i的语法树对于句型T+T*F+i：短语：T,T*F,T+T*F,T+T*F+i,i素短语：T*F,I句柄：T4.2.2算符优先分析法

可以证明，对于G的句型

α=#N1a1N2a2…NjajNj+1aj+1…Nj+kaj+k…NnanNn+1#其中#为界符，ai∈VT，Ni∈VN，它的最左素短语是满足关系

aj-1<ajaj=aj+1=…aj+kaj+k>aj+k+1的最左子串NjajNi+1aj+1…Nj+kaj+kNj+k+1。因此，可按与简单优先分析相似的过程找到一个句型的最左素短语。算符优先文法仅在终结符号之间定义优先关系，完全不考虑非终结符号，故显然不能识别句型中只由一个非终结符号组成的句柄，也就是全然不考虑按单产生式进行归约，因此，每次找到的最左素短语就不一定是句型的句柄，因而此最左素短语也就可能不是相应文法的任何产生式的右部。所以,我们按“同形即可归约”的策略来归约。4.2.2算符优先分析法构造算符优先矩阵的一般方法(1)对文法的每一非终结符号构造FIRSTVT集和LASTVT集，算法分别如下

ⅰ)构造FIRSTVT集，置FIRSTVT(A)=φ

若文法中有形如A→b…或A→Bb…的规则，则b∈FIRSTVT(A)

若文法中有形如A→B…的规则，则FIRSTVT(B)∈FIRSTVT(A)ⅱ)构造LASTVT集，置LASTVT(A)=φ

若文法中有形如A→…a或A→…aB的规则，则a∈LASTVT(A)

若文法中有形如A→…B的规则，则LASTVT(B)∈LASTVT(A)(2)ⅰ)形如…aA…的规则右部，a<FIRSTVT(A)ⅱ)形如…Ab…的规则右部，LASTVT(A)>bⅲ)形如…ab…或…aAb…的规则右部，a=b(3)#<FIRSTVT(S)LASTVT(S)>#4.2.2算符优先分析法考虑E→E+T

+,*,),i>++<*,(,i考虑T→T*F*,(,i>**<(,i考虑F→(E)(<+,*,(,I+,*,),i>)(=)考虑##<+,*,(,i+,*,),i>#例：构造文法G[E]的算符优先矩阵和符号串i+i*i的分析过程

E→E+T∣TT→T*F∣FF→(E)∣i解:首先求各非终结符号的FIRSTVT集和LASTVT集FIRSTVT(F)={(,i}FIRSTVT(T)={*}∪FIRSTVT(F)={*,(,i}FIRSTVT(E)={+}∪FIRSTVT(T)={+,*,(,i}LASTVT(F)={),i}LASTVT(T)={*}∪LASTVT(F)={*,),i}LASTVT(E)={+}∪LASTVT(T)={+,*,),i}+*()i#+><<><>*>><><>(<<<=<)>>>>i>>>>#<<<<表4.8G[E]的算符优先矩阵4.2.2算符优先分析法表4.6符号串i+i*i的算符优先分析过程步骤当前句型及优先关系当前应被归约的最左子串归约所得到符号1#<i>+i*i#iF2#<F+<i>*i#iF3#<F+<F*<i>#iF4#<F+<F*F>#F*FT5#<F+T>#F+TE6#E#分析成功4.2.2算符优先分析法算符优先分析中的重要事实：１）按算符优先关系所确定的应被归约的子串恰好是当前句型的最左素短语。２）尽管算符优先分析也属于自底向上语法分析的范畴，但却不严格从左至右的规范分析，每步所得的句型自然也不是一个规范句型３）尽管分析时，指出了每一个最左素短语应归约到的非终结符号，但每次在查找最左素短语时，起主导作用的是终结符号间的优先关系，两终结符号间空间是哪种优先关系与非终结符号并无关联，故在进行算符优先分析时，随意给归约到的非终结符号命名也是可以的。４）具体算法如程序4-5所示。4.2.3优先函数为了节省存储空间，同时便于比较，我们将优先矩阵线性化，构造两个离散函数f和g，满足

当Si<Sj时，f(Si)<g(Sj)

当Si=Sj时，f(Si)=g(Sj)

当Si>Sj时，f(Si)>g(Sj)f和g分别称为入栈(前)优先函数和比较(后)优先函数。(1)不是所有的优先矩阵都能线性化。(2)若优先函数存在，则不唯一。(3)当一个优先矩阵线性化后，就对每一对符号都赋予了一对优先数。这样，对于原先不存在优先关系的符号对，也可以比较优先关系了,就可能掩盖(至少推迟发现)输入串中的语法错误。对此问题，需通过其他语法检查手段解决。4.2.3优先函数下面介绍两种优先矩阵线性化的方法。一.有向图法(Bell方法)设已给的优先文法G[S]有n个符号S1

，S2

，…Sn

，如果优先函数存在，则可如下构造:(1)对于每一Si

，分别作以fi和gi为标记的结点，并按如下方式构造以f1

，f2

，…fn及g1

，g2

，…gn为结点的有向图:

若有Si>Sj或Si=Sj

，则从结点fi引一条至结点gj的矢线;若有Si<Sj或Si=Sj，则从结点gj引一条至结点fi的矢线。(2)对每个结点都赋予一个整数，此整数就是从该结点出发，沿着矢线所能到达的结点个数(包括出发结点在内)

，赋给结点fi的整数就是f(Si)

;赋给结点gi的整数就是g(Si)。(3)对f和g进行检验，若它们与原优先关系相容，则f和g即为所求的优先函数;否则，原优先矩阵就不能线性化。4.2.3优先函数二.构造优先函数的Floyd方法(1)首先，给f和g赋初值，即对每一符号Si

，置

f(Si)=g(Si)=1(2)进行迭代，即对每一符号对(Si,Sj):ⅰ)若有Si>Sj，但有f(Si)≤f(Sj)，则执行f(Si)=g(Sj)+1;ⅱ)若有Si<Sj，但有f(Si)≥f(Sj)，则执行g(Sj)=f(Si)+1;ⅲ)若有Si=Sj

，但有f(Si)≠f(Sj)，则令f(Si)和g(Sj)中的最小者等于最大者

。(3)重复步骤(2)，直到过程收