编译原理第四章：语法分析-自上而下分析

第四章语法分析——自上而下分析4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL（1）分析法4.4递归下降分析程序构造4.5预测分析程序4.6LL（1）分析中的错误处理

复习题4.1语法分析器的功能语法分析是编译过程的核心部分，它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器工作本质：按文法的产生式，识别输入符号串是否为一个句子，判断是否能从文法的开始符号出发推导出这个输入串。语法分析方法种类

（按语法分析树建立方法）

自上而下分析

递归下降分析、预测分析

自下而上分析

算符优先分析、LR分析4.2自上而下分析面临的问题一.自上而下分析开始符号句子

从文法的开始符号出发，向下推导，推出句子；即对任何输入串，试图用一切可能的办法，从文法开始符号出发，自上而下地为输入串建立一棵语法树。

或者说，为输入串寻找一个最左推导。自上而下分析过程，本质是一种试探过程，是反复使用不同产生式，谋求匹配输入串的过程。

二．引例例4.1假定有文法（1）S→xAy

（2）A→**|*以及输入串x*y（记为α）自上而下构造α的语法树

SS

xAyxAy

**注销A的第一个候选所发展的子树

S

xAy试探用第二个候选

*

实现这种自上而下的带回溯试探法的一个简单途径是让每个非终结符对应一个递归子程序，每个这种子程序作为一个布尔过程。三．自上而下分析法存在的困难和缺点

1.文法的左递归问题（消除文法的左递归）

2.回溯问题（消除回溯）

3.当一个非终结符用某一候选式匹配成功时，这种成功可能仅是暂时的（从最长候选开始匹配，虚假现象会减少）

4.当最终报告分析不成功时，难于知道输入串出错的确切位置。

5.穷尽试探法，效率低，代价高。4.3LL（1）分析法一.左递归的消除1.直接左递归假定关于非终结符P的规则为P→Pα|ß,其中ß不以P开头可改写为P→ßP’，P’→αP’|ε(ε为空字)

一般而言，假定关于P的全部产生式是

P→Pα1|Pα2|…|Pαm|β1|β2|…βn

其中α都不等于ε

，且每个β不以P开头。则改写后为P→β1P´|β2P´|…|βnP´

P´→α1P´|α2P´|…|αmP´|ε例4.2文法E→E+T|T消去直接左递归。

T→T*F|FF→（E）|i解：

E→TE´E´→+TE´|εT→FT´T´→*FT´|εF→（E）|i

2．间接左递归例4.3文法S→Qc|cQ→Rb|bR→Sa|a在该文法中

有S

Qc

Rbc

Sabc3．消除左递归算法如果一个文法不含回路,也不含以ε为右部的产生式。1º排序把文法G的所有非终结符按任一种顺序排列P1、P2、…、Pn按序执行。2º代入及消除左递归

for(i=1;i<=n;i++)

for(j=1;j<=i－1;j++)把形如Pi→Pjγ的规则改写为

Pi→δ1

γ

|δ

2

γ|…|δ

k

γ

(其中Pj→δ

1|δ

2|…|δ

k

是关于Pj的所有规则)消除关于Pi规则的直接左递归性3º化简化简由2º所得文法，即去除那些从开始符号出发永远无法到达的非终结符的产生式规则。例4.3考虑文法S→Qc|c

Q→Rb|b

R→Sa|a

解:令它的非终结符排序为R，Q，S，对于R不存在直接左递归，把R代入Q则得Q→Sab|ab|b

再把Q代入S则得S→Sabc|abc|bc|c

经除去S直接左递归后，得

S→abcS´|bcS´|cS´

S´→abcS´|ε

Q→Sab|ab|b

R→Sa|a

其中关于Q和R的规则多余,

删除之若对文法排序S，Q，R，则得

S→Qc|c

Q→Rb|b

R→Sa|a将S代入到R，R→Sa|a

R→Qca|ca|a将Q代入到R，R→Rbca|bca|ca|a则得R→bcaR’|caR’|aR’R’→bcaR’|ε二．消除回溯（提公共左因子）

假定关于A的规则是A→δβ1|δβ2|……|δβn|γ1|γ2|……|γm(其中γi不以δ开头)提取公共左因子,改写为

A→δA′|γ1|γ2|……|γmA′→β1|β2|……|βn三.LL(1)分析条件第一个L表示从左到右扫描,第二个L表示最左推导,1表示分析时,每步只需向前查看一个符号。First(α)和Follow(A)定义(1)First(α)

令G是一个不含左递归的文法,对G的所有非终结符的每个候选α定义它的终结首符集First(α)为

First(α)={a|…,a∈VT}

若,规定ε∈First(α)(2)Follow(A)

假定S是文法G的开始符号,对于G的任何非终结符A.

定义:Follow(A)={a|S

…Aa…,a∈VT

}.

若S…A,则规定#∈Follow(A)

即Follow(A)是所有句型中出现在紧接A之后的终结符或”#”2.LL(1)文法三个条件:（1）文法不含左递归（2）对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交,若A→α1|α2|…|αn，则

First(αi)∩First(αj)=(其中i不等于j)（3）对文法中每个非终结符A,若它存在某个候选首符集包含εFirst(αi)∩Follow(A)=1≤i≤n

如果一个文法G满足以上条件，则称该文法G为LL（1）文法3.LL（1）分析假设要用非终结符A进行匹配，面临的输入符号为a,A的所有产生式为A→α1|α2|…|αn(1)若a∈First(αi),则指派αi去执行匹配任务(2)若a不属于First(αi)（i=1,2,…,n）,则若ε∈First(αi)且a∈Follow(A)，则让A与ε自动匹配否则，a的出现是一种语法错误4.4递归下降分析程序构造当一个文法满足LL（1）条件时，可为它构造一个不带回溯的自上而下分析程序，这个分析程序由一组递归过程组成，每个过程对应文法的一个非终结符，这样的分析程序为递归下降分析器。

ADVANCE指输入串指示器IP调至指向下一个输入符号

SYM指IP当前所指的那个输入符号

ERROR出错诊察处理程序文法E→TE′

E′→+TE′|εT→FT′T′→*FT′|ε

F→(E)|i递归子程序PROCEDUREE;PROCEDURE

T;BEGINBEGIN

T;

E′F;

T′END;END;PROCEDURE

E′;PROCEDURET′IFSYM=’+’THEN

IFSYM=’*’THENBEGIN

BEGINADVANCE;

ADVANCET;

E′

F;

T′END;

END;PROCEDUREF;IFSYM=’i’THENADVANCEELSEIFSYM=’(‘THEN

BEGIN

ADVANCE;

E;

IFSYM=’)’THENADVANCE

ELSEERRORENDELSEERROR;4.5预测分析程序一、预测分析程序思想二、First(α)和Follow(A)的求法三、预测分析表的构造四、预测分析程序的总控程序五、实例4.5预测分析程序使用一张分析表和一个栈进行联合控制一.预测分析程序思想

输入串．．．a．．．#

Ｘ总控程序输出

预测分析表M

#STACK匹配推导成功报错

栈STACK用于存放文法符号，分析开始时，栈底先放一个“#”，后放进文法开始符号，假定输入串后总有一个“#”，标志输入串结束。当栈顶元素为X，a为当前输入符号

X∈VT①X=a=’#’成功

②X=a≠’#’X退栈，a指向下一个输入符号匹配

X∈VN①查看分析表M。M（X,a）中的X→α,X退栈，α反序入栈，对X→ε,X退栈，无符号进栈，a保持推导

②当M(X,a)不存在，出错标志报错二.First(α)和Follow(A)的求法1.FIRST（α）的求法定义：假定α是文法G的任一符号串，α∈（VT∪VN）*，则FIRST(α)={a|αa……,a∈VT},若αε,则ε∈FIRST（α）FIRST(X)求法X∈(VT∪VN)1’若X∈VT,则FIRST(X)＝｛X｝2’若X∈VN,且有产生式X→a…,则a加入FIRST（X）,若X→ε，则ε加入FIRST（X）3’若X→Y…

是一产生式且Y∈VN,则把FIRST（Y）中所有的非

ε元素加到FIRST(X)中；若X→Y1Y2…YK是一个产生式，Y1,Y2,…,Yi-1∈VN,且对于,,FIRST(Yj)都含有ε(Y1…Yi-1ε),则把FIRST(Yi)中所有非ε元素都加到

FIRST(X)中；若所有FIRST(Yi)均含有ε,j=1,2,…,k,则把ε加到FIRST(X)中。4’重复2’,3’直到所有FIRST(X)不再扩大为止。2．FOLLOW(A)的求法定义：假定S是文法G的开始符号，对于G的任何非终结符AFOLLOW(A)={a|S

…

Aa…,a∈VT}

若S…A,规定#∈FOLLOW(A)。即：FOLLOW(A)是所有句型中出现在紧接A之后的终结符或“#”。

FOLLOW(B)的求法1’对于文法的开始符号S，置#于FOLLOW(S)中2’若A→αBβ是一个产生式，则把FIRST(β)\{ε}加到FOLLOW(B)中。3’若A→αB是一个产生式，或A→αBβ且βε时（即ε∈FIRST(β)）则把FOLLOW(A)加到FOLLOW(B)中。4’重复2’,3’直到FOLLOW集不再增大为止。例：对于文法G:E→E+T|T,T→T*F|F,F→(E)|i求FIRST(α)和FOLLOW(A)解:消除左递归得G’:E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|iRFIRST(R)FOLLOW(R)E(,i#,)T(,i#,),+E’+,ε#,)T’*,ε#,),+F(,i#,),+,*三．预测分析表的构造1.对文法G的每个产生式A→α

执行2，32.对任意a∈FIRST(α),把A→α加至M[A,a]中3.若ε∈FIRST(α),则对任意b∈FOLLOW(A),把A→α加至M[A,b]中4.把所有无定义的M[A,a]标上“出错标志”结论:一个文法G的预测分析表M不含多重定义入口,当且仅当该文法为LL(1)的。四．预测分析程序的总控程序BEGIN

首先把“#”然后把文法的开始符号推进STACK栈；把第一个输入符号读进a;FLAG:=TURE;WHILEFLAGDOBEGIN

把STACK栈顶符号上托出去并放在X中;IFX∈VTTHENIFX=aTHEN把下一个输入符号读进aELSEERRORELSEIFX=‘#’THENIFX=aTHENFLAG:=FALSEELSEERRORELSEIFM[X,a]={X→X1X2…XK}THEN

把XK,XK-1,…X1一一推进STACK栈

ELSEERRORENDOFWHILESTOP/*分析成功,过程完毕*/END．例.对于文法G’输入串为i1*i2+i3,利用分析表进行预测分析步骤符号栈输入串所用产生式0#Ei1*i2+i3#E面临i1#EˊTi1*i2+i3#E→TEˊ2#EˊTˊFi1*i2+i3#T→FTˊ3#EˊTˊii1*i2+i3#F→i4#EˊTˊ*i2+i3#Tˊ面临*5#EˊTˊF**i2+i3#Tˊ→*FTˊ6#EˊTˊFi2+i3#F面临i7#EˊTˊii2+i3#F→i8#EˊTˊ+i3#Tˊ面临+9#Eˊ+i3#Tˊ→ε10#EˊT++i3#Eˊ→+TEˊ11#EˊTi3#T面临i12#EˊTˊFi3#T→FTˊ13#EˊTˊii3#F→i14#EˊTˊ#Tˊ面临#15#Eˊ#Tˊ→ε##Eˊ→ε五、实例已知文法G：A→aABl|a

B→Bb|d①试给出与Ｇ等价的LL(1)文法G’②构造文法G’的预测分析表,并给出输入串aadl的分析过程解:对A→aABl|a

来说:First(aABl)First(a)={a}≠ф.

对B→Bb|d

存在有左递归。故文法G不是LL(1)文法。提取公共左因子

及消除左递归得

A→aT

T→ABl|ε

B→dB’

B’→bB’|ε此时

First(A)={a}Follow(A)={d,#}

First(T)={a,ε}Follow(T)={d,#}

First(B)={d}Follow(B)={l}

First(B’)={b,ε}Follow(B’)={l}对于T→ABl|ε来说，F