chap4-1自顶向下语法分析

检查由扫描器输出的单词符号序列是否符合该语言的文法——句子扫描器分析器语义处理单词符号分析树源程序分析器的输入：Token序列分析器的输出分析树出错处理分析方法自顶向下（递归下降、预测分析)自底向上（算符优先、LR分析器）第四章语法分析5/12/20241

4.1自顶向下的分析方法基本思想寻找输入符号串最左推导试图根据当前输入单词判断使用哪个产生式基本过程从根开始，按与最左推导相对应的顺序，构造输入符号串(Token)的分析树5/12/202421、重要概念推导:αＡβ

αγβ(依据：Ａ→γ)最左(Left-most)推导——最左分析左句型最左推导对应最右归约最右(Right-most)推导——最右分析规范推导、规范句型（右句型）最右推导对应最左归约（规范归约）自顶向下语法分析要解决的问题是?5/12/20243候选式的确定给定文法S→cAd A→ab|a?句子cad是该文法定义语言的句子

S S c A d c A d ab a产生式(候选式)的选择：当要进行关于某个语法变量的推导时，希望能够根据当前符号确定候选式。5/12/20244带回溯的自顶向下分析思想

给定文法G[S]和输入串W,从S出发自顶向下构造语法树:若存在某条推导路径,使得S=>*W,则W语法正确;若尝试所有推导路径,都无法得到S=>*W,则W语法错误.不确定的自顶向下分析需作回溯,效率很低.5/12/202452.确定的自顶向下分析思想

基本思想：每一步根据当前输入符号可唯一确定某条规则用于推导.由根向下构造语法树.构造最左推导.推导出的终结符是否与当前输入符匹配5/12/20246确定的自顶向下分析思想例1:S–>pA

[1]|qB[2]A–>cAd[3]|a

[4]

输入串：Ｗ＝pccadd分析结论：Ｗ语法正确且分析过程的每一步都唯一原因：本文法的非终结符（Ｓ，Ａ）的候选都以终结符开头，且两两不同．Ｓ：p≠qA:c≠a5/12/20247例2:S–>Ap

[1]|Bq

[2]

A–>a

[3]|cA

[4]B–>b

[5]|dB

[6]

输入串：Ｗ＝ccap分析结论:Ｗ语法正确且分析过程的每一步都唯一原因：本文法的A和B的候选以终结符开头，且两两不同．

A：a≠cB:b≠d;并且对于

S:FIRST（Ａp）∩FIRST(Bq)={a,c}∩{b,d}=

定义：FIRST（）={a|=>*a,a∈VT,,∈V*}

若

=>*

ε则规定ε∈FRIST()5/12/20248例3:S–>aA

[1]|d

[2]

A–>bAS

[3]|

[4]

输入串：Ｗ＝abd分析结论：W语法正确且分析过程的每一步都唯一原因：S：a≠d

A:{b}∩

FOLLOW（A）

={b}∩{a,d}=

定义：FOLLOW（A）={aS=>*A且a∈

FRIST（），∈V*，

∈V+}5/12/20249我们希望：从左到右扫描输入串——寻找它的一个最左推导对于G的每个非终结符A的任何两个不同的候选式A→α|β1)FIRST(α)∩FIRST(β)=φ2)如果β

*ε，则FISRT(α)∩FOLLOW(A)=φ

——文法Ｇ是LL(1)

的充要条件第一个L:从左到右扫描输入串第二个L:生成的是最左推导

1:向前看一个输入符号5/12/2024103.LL(1)文法的判别1.对于A∈Vn,计算First(A)2.对于A∈Vn,计算Follow(A)3.对于A–>

|β,计算

FIRST(

)∩FIRST(β)

FIRST(β)∩

follow(A)(若

=>*

成立)5/12/2024111.若Ａ=>*

，则

∈First(A)2.若A–>B…,则FIRST(A)=FIRST(A)∪(FIRST(B)-{ε})

若A–>a…,则FIRST(A)=FIRST(A)∪{a}

3.若A–>

B…及

A–>

a…,且

=>*

，则类似于步骤2处理求FIRST(A)的算法5/12/202412FIRST(F)={（,id}FIRST(T)=FIRST(F)={（,id}FIRST(E)=FIRST(T)={（,id}FIRST(E')={+，ε}FIRST(T')={*,ε}FIRST(+)={+},FIRST(*)={*}FIRST(（)={（}FIRST(）)={）}FIRST(id)={id}E→TE'E'→+TE’|εT→FT'T'→*FT’|εF→(E)|id例5/12/202413例:S–>AＢ|bC

A–>

|bB–>

|aDC–>AD|bD–>aS|cNFirst(N)Sa,b,

Ab,Ba,

Ca,b,cDa,c5/12/202414求FOLLOW(A)的算法对于所有非终结符,重复进行以下计算1)将#加入到FOLLOW(S)#为句子的结束符2)若A→αBβ，则FOLLOW(B)=FOLLOW(B)∪FIRST(β)–{ε}3)如果A→αB或A→αBβ，且β

*ε，A≠B，则FOLLOW(B)=FOLLOW(B)∪FOLLOW(A)5/12/202415FOLLOW(E)={),#}FOLLOW(E')=FOLLOW(E)={),#}FOLLOW(T)={+,),#}FOLLOW(T')=FOLLOW(T)={+,),#}FOLLOW(F)={*,+,),#}E→TE' E'→+TE’|ε T→FT'T'→*FT’|ε F→(E)|id例5/12/202416NFollow(N)S#Aa,c,#B#C#D#例:S–>AＢ|bC

A–>

|bB–>

|aDC–>AD|bD–>aS|c5/12/202417对于A–>

|β∈Ｐ，计算交集S–>AＢ|bC

A–>

|bB–>

|aDC–>AD|bD–>aS|cNFirst(N)Sa,b,

Ab,Ba,

Ca,b,cDa,cFollow(N)#

a,c,###

#First(AB)=First(A)∪First(B)∪{b}={b,a,}

First(bC)={b}∵{b,a,}

∩{b}={b}≠

∴G[Ｓ]不是LL(1)文法5/12/2024184.非LL(1)文法到LL(1)文法的变换LL(1)文法的性质：LL(1)文法是无二义的LL(1)文法不含左递归LL(1)文法不含公共左因子5/12/202419(1)消除左递归直接左递归

A→Aα 间接左递归 A

+Aα

例:S→Aa

A→Sb无法根据左递归文法进行自顶向下的分析左递归的消除方法将A→Aα|β替换为A→βA’和A’

→αA’

｜ε5/12/202420例：表达式文法直接左递归的消除E→E+T｜TT→T*F｜FF→(E)｜idE→TE’E’→+TE’|εT→FT’T’→*FT’｜εF→(E)｜id5/12/202421间接左递归的消除S→Ac|c A→Bb|b B→Sa|a将B的定义代入A产生式得：A→Sab|ab|b将A的定义代入S产生式得:S→Sabc|abc|bc|c消除直接左递归： S→abcS’|bcS’|cS’

S’→abcS’|ε删除“多余的”产生式：A→Sab|ab|b和B→Sa|a结果：

S→abcS’|bcS’|cS’

S’→abcS’|ε

5/12/202422消除左递归的一般方法已知左递归产生式组A→Aα1|Aα2|…|Aαn|β1|β2|…|βm

替换为产生式组A

β1B|β2B

|…|βnBB

α1B|α2B

|…|αnB|ε其中：B为新变量，相当于A’5/12/202423

将产生式Ａ

β|

变换为：Ａ

BB

β|

例:S→ifCtS|

ifCtSeSC→b

提左因子得:S→ifCtSAA→eS|

C→b

(2)提取左因子5/12/202424左因子提取方法将形如A→αβ1|αβ2|…|αβn

|γ1|γ2|…|γm的规则改写为A→αA’|γ1|γ2|…|γm和A'→β1|β2|…|βn5/12/202425注意!文法G[S]中消除了左递归和公共左因子后并不能保证其一定变换为LL(1)文法.需进行判别后才能下结论.5/12/202426

G’[E]:(1)E–>TE’(2)E’–>+TE’

(3)E’–>

(4)T–>FT’(5)T’–>*FT’(6)T’–>

(7)F–>(E)(8)F–>i例:G[E]:E→E+T｜TT→T*F｜FF→i｜(E)G[E]是否为LL(1)文法？5/12/202427G’[E]:(1)E–>TE’(2)E’–>+TE’(3)E’–>

(4)T–>FT’(5)T’–>*FT’(6)T’–>

(7)F–>(E)(8)F–>i·各非终结符的FIRST集合如下：FIRST(E)=｛(,i｝FIRST(E′)=｛+,ε｝FIRST(T)=｛(,i｝FIRST(T′)=｛*,ε｝FIRST(F)=｛(,i｝·各非终结符的FOLLOW集合为：FOLLOW(E)=｛),＃｝FOLLOW(E′)=｛)，＃｝FOLLOW(T)=｛＋，)，＃｝FOLLOW(T′)=｛＋,)，#}FOLLOW(F)=｛*,＋，),#}

5/12/202428G’[E]:(1)E–>TE’(2)E’–>+TE’(3)E’–>

(4)T–>FT’(5)T’–>*FT’(6)T’–>

(7)F–>(E)(8)F–>aE’–>+TE’|

FIRST(+TE’)=｛+｝

FOLLOW(E′)=｛)，＃｝T’–>*FT’|

FIRST(*FT’)=｛*｝

FOLLOW(T′)=｛+,)，＃｝F–>(E)|aFIRST((E))=｛(｝

FIRST(a)=｛a｝所以G’[E]是LL（1）的5/12/202429习题：1、改写以下文法，消除左递归并判断改写后的文法是否LL(1)文法。

M→MaH|H H→b(M)|(M)|b2、判断以下文法是否LL(1)文法,求该文法中各非终结符的FIRST集和FOLLOW集,并构造预测分析表。a. A→baB|

b.S→bA|a B→Abb|a A→bB

B→bB|3、判断该文法是否LL(1)文法？如不是，请将其改写为LL(1)文法。

a.S→A|B

A→aA|a

B→bB|b

b.S→i|(E)E→E+S|E-S|S

C.E→E+T|TT→T*F|FF→（E）|i5/12/202430确定的自顶向下分析方法递归子程序法预测分析方法5/12/2024314.1.2递归子程序法方法:对于每一A∈Vn,构造一个子程序.设A→α,对α中各个符号X:若X∈Vt,则匹配当前输入符号a,判断Ｘ=a

?;若X∈Vn,则转而调用Ｘ所对应的子程序．语法分析开始时，调用开始符号Ｓ对应的子程序5/12/202432递归子程序法例：G’[E]:E–>TE’E’–>+TE’｜

T–>FT’T’–>*FT’｜

F–>(E)F–>iProcedureE;{T;E’}ProcedureT;{F;T’}ProcedureE’;{ifsym=‘+’then{advance;T;E’}}ProcedureT’;{ifsym=‘*’then{advance;F;T’}}5/12/202433递归子程序法例：G’[E]:E–>TE’E’–>+TE’｜

T–>FT’T’–>*FT’｜

F–>(E)F–>iProcedureF;{ifsym=‘i’thenadvanceelseifsym=‘(’then{advance;E;ifsym=‘)’thenadvanceelseerror1}elseerror2}5/12/202434递归子程序法ProcedureF;{ifsym=‘i’thenadvanceelseifsym=‘(’then{advance;E;ifsym=‘)’thenadvanceelseerror1}elseerror2}ProcedureE;{T;E’}ProcedureT;{F;T’}ProcedureE’;{ifsym=‘+’then{advance;T;E’}}ProcedureT’;{ifsym=‘*’then{advance;F;T’}}i1+i2*i3的分析过程5/12/202435语法图和递归子程序法例表达式文法的描述+TE’ETE’E’+TE’语法图的化简5/12/202436+T

TE语法图的化简5/12/202437简化的语法图+TE＊ＦＴidＥＦ

（）5/12/202438Ｅ的子程序(E→T|E+T)procedureE;beginT; Ｔ的过程调用

whilelookhead='+'dobegin 当前符号等于＋时

match(‘+’); 处理终结符＋

T Ｔ的过程调用

endend; lookhead：当前符号

例简单算术表达式的分析器+TE5/12/202439Ｔ的子程序(T→F|T*F)procedureT;beginF; Ｆ的过程调用whilelookhead='*'thenbegin 当前符号等于＊时match('*');处理终结符＊F Ｆ的递归调用endend;5/12/202440Ｆ的子程序(F→(E)|id)procedureF;beginiflookhead='('thenbegin 当前符号等于（

match('(');处理终结符（

E; Ｅ的递归调用

match(')');处理终结符）

endelseiflookhead=idthen match(id)处理终结符idelseerror出错处理

end5/12/202441主程序begin lookhead:=nexttoken; 调词法分析程序

E Ｅ的过程调用end procedurematch(t:token);beginiflookhead=tthenlookhead:=nexttokenelseerror出错处理程序

end;5/12/2024424.1.3预测分析法系统维持一个分析表和一个分析栈，根据当前扫描到的符号，选择当前语法变量（处于栈顶）的候选式进行推导——希望找到相应的输入符号串的最左推导.如图所示。一个通用的控制算法一个统一形式的分析表M一个分析栈，#为栈底符号一个输入缓冲区，#为输入串结束符5/12/202443对图所示的预测分析器说明如下：

(1)输入串是待分析的符号串，它以界符“#”作为结束标志。(注：#∈VT但不是文法符号，是由分析程序自动添加的。)(2)分析栈中存放分析过程中的文法符号。分析开始时栈底先放入一个“#”，然后再压入文法的开始符号；当分析栈中仅剩“#”，输入串指针也指向串尾的“#”时，分析成功。5/12/202444分析表用一个矩阵(或二维数组)M表示，矩阵的每一行与文法的一个非终结符相关联，而每一列与文法的一个终结符或界符“#”相关联。分析表元素M[A,a]中的内容为一条关于A的产生式，表明当A面临输入符号a时当前推导所应采用的候选式；当元素内容为空白(空白表示“出错标志”)时，则表明A不应该面临这个输入符号a，即输入串含有语法错误。5/12/202445控制程序根据分析栈顶符号x和当前输入符号a来决定分析器的动作：

①若x＝a＝“#”，则分析成功，分析器停止工作。

②若x＝a≠“#”，即栈顶符号x与当前扫描的输入符号a匹配；则将x从栈顶弹出，输入指针指向下一个输入符号，继续对下一个字符进行分析。

③若x为一非终结符A，则查M[A,a]：5/12/202446i．若M[A,a]中为一个A的产生式，则将A自栈顶弹出，并将M[A,a]中的产生式右部符号串按逆序逐一压入栈中；如果M[A,a]中的产生式为A→ε，则只将A自栈顶弹出。

ii．若M[A,a]中为空，则发现语法错误，调用出错处理程序进行处理。5/12/202447构造分析表M①对文法G[S]的每个产生式A→α执行以下②、③步。②对每个终结符a∈FIRST(A)，把A→α加入到M[A,a]中，其中α为含有首字符a的候选式或为惟一的候选式。③若ε∈FIRST(A), 则对任何属于FOLLOW(A)的终结符b，将A→ε加入到M[A,b]中。④把所有无定义的M[A,a]标记为“出错”。5/12/202448例:LL(1)分析表

i+*()#EE→TE'

E→TE'

E'

E'→+TE'

E'→εE'→εTT→FT'

T→FT'

T'

T'→εT'→*FT'

T'→εT'→εFF→i

F→(E)

E→TE'E'→+TE’|εT→FT'T'→*FT’|εF→(E)|id5/12/202449分析算法BEGIN

首先把’#‘然后把文法开始符号推入栈；把第一个输入符号读进b;FLAG：=TRUE；WHILEFLAGDO

BEGIN

把栈顶符号上托出去并放在Ｘ中；

IFX

VtTHENIFX=bTHEN

把下一个输入符号读进b

ELSEERROR

ELSEIFX=‘#’THENIFX=bTHENFLAG:=FALSEELSEERRORELSEIF

[X,b]={X–>

X1X2..XK}THEN把XK，XK-1,..,X1一一