语法分析-自上而下分析

第4章语法分析（1）定义：设G[S]=(VT,VN,S,P)是上下文无关文法，则

FIRST(x)={a|xay,a∈VT,x,y∈V*}

若xε，则规定ε∈FIRST(x)

实际上，FIRST(x)是指由符号串x出发能够推导出来的所有符号串中，处于串头的终结符号的集合。4.1

常用终结符号集1、FIRST集（首符号集）**FIRST(X)可按以下算法求得：设：X=X1X2…Xn，FIRST(X)=Φ，i=1则有：1.若Xi∈VT,则Xi∈FIRST(X),进入第4步;2.若Xi∈VN,①若Xiε,则FIRST(Xi)∈FIRST(X),进入第4步;②若Xiε,则FIRST(Xi)\ε∈FIRST(X),然后令i=i+1,若i≤n，进入第1步,否则进入第3步；3.若

Xε，则ε∈FIRST(X)；4.退出***定义：设G[S]=(VT,VN,S,P)是上下文无关文法，A∈VN,则

FOLLOW(A)={a|S…Aa…,a∈VT}

若S…A，则规定#∈FOLLOW(A)

实际上，FOLLOW(A)是指文法G[S]的所有句型中，紧跟在非终结符A后的终结符号的集合。

#作为输入串的结束符，或称为句子括号，如：abc#2、FOLLOW集（后继符号集）**FOLLOW(A)可采用以下算法求得：1.对于文法G[S]的开始符号S，有#∈FOLLOW(S)；2.若文法G[S]中有形如U→xA的规则,其中x∈V﹡,则

FOLLOW(U)∈FOLLOW(A)3.若文法G[S]中有形如U→xAy的规则,其中x∈V﹡,y∈V﹡,

当yε时, FIRST(y)∈FOLLOW(A)

当yε时, FIRST(y)\ε∈FOLLOW(A) FOLLOW(U)∈FOLLOW(A)**定义:给定上下文无关文法的产生式A→x,A∈VN,x∈V*,则

若xε，则SELECT(A→x)=FIRST(x)

若xε，则SELECT(A→x)=FIRST(x)\ε∪FOLLOW(A)

实际上SELECT(A→x)是指，在推导过程中，如果采用了A→x进行推导，下一个可能推导出的终结符号。3、SELECT集（可选集）**一、自顶向下分析方法1.带回溯的自顶向下分析

所谓带回溯的自顶向下分析，实际上是指在推导过程中，总是试图用尽一切可能的方法进行推导。2.确定的自顶向下分析

所谓确定的自顶向下分析方法，是指若输入串是文法的句子，则从文法的开始符号出发，每一步直接推导都只有唯一的规则可以选择。条件：

对于文法，要能够进行确定的自顶向下分析，当且仅当对文法的任意非终结符号A，其所有的规则A→X1|X2|…|Xn满足：

SELECT(A→Xi)∩SELECT(A→Xj)=Φ

其中i,j=1,2,…,n,且i≠j.4.2

语法分析方法概述二、与自顶向下分析方法有关的文法变换1.SELECT集相交时的候选式提取左公因子；

只有当文法的每一非终结符的所有的规则SELECT集两两不相交时，才能进行确定的自顶向下分析。当文法不满足确定自顶向下分析的条件时，则须改造文法，即对SELECT集相交的候选式提取左公因子。提取公共左因子:

假定关于A的规则是

A→1|2|…|n|1|2|…|m (其中，每个不以开头)

那么，可以把这些规则改写成:

A→A|1|2|…|mA→1|2|…|n

经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。2.消除文法的左递归；

当采用最左推导的自顶向下的分析方法，如果文法具有左递归，将使分析过程陷入无限循环。在左递归文法中，对于左递归的非终结符，其规则的SELECT集必然相交。因此消除左递归，是进行确定的自顶向下分析的必然。4.3

递归子程序法递归子程序法也称为递归下降分析法，是一种简单直观易于构造的自顶向下分析方法，起方法思想是：对文法的每一个非终结符号编制一个处理子程序，而处理子程序的代码结构则由相应的非终结符号的规则右部所决定：规则右部的终结符号应与输入符号匹配，规则右部的非终结符号与相应的子程序调用相对应。4.4LL(1)分析法定义：所谓LL(1)分析，是指从左到右扫描输入源程序，同时采用最左推导，且对每次直接推导只需向前查看一个输入符号，便可以确定当前所应选择的规则。理解：第一个L表示：自顶向下分析是从左向右扫描输入串。第二个L表示：分析过程中将用最左推导。

1表示：只需向右看一个符号便可决定如何推导（即选择哪个产生式进行推导）。a1a2a3…ai…an#输入串分析表M总控程序X1…Xn-1Xn#分析栈1、LL(1)分析器的逻辑结构2、LL（1）分析过程3、LL(1)分析表的构造

LL(1)分析表M[A,a]实际上是要表明要由A推导出终结符a所应采用的产生式。我们可以利用SELECT集来构造LL(1)分析表，具体构造算法如下：设有文法G[S]=(VN,NT,P,S),VN={A1,A2,…,Am},令i=11.若关于Ai的规则有：Ai→x1|x2|…|xn

则求的各规则的SELECT集。2.若a∈SELECT(Ai→xj),则

M[Ai,a]=Ai→xj3.i=i+1,重复1、2，直到i>m,即对文法的所有的非终结符号求完为止。E→TE'

E'→+TE'|εT→FT'

T'→*FT'|εF→i|(E)例：已知文法，构造LL(1)分析表E→TE'E'→+TE'|εT→FT'

T'→*FT'|εF→i|(E)SELECT(E→TE') ={(,i }SELECT(E'→+TE') ={+ }SELECT(E'→ε) ={ε,),#}SELECT(T→FT') ={(,i }SELECT(T'→*FT') ={*}SELECT(T'→ε) ={ε,+,),#}SELECT(F→(E)) ={(

}SELECT(F→i) ={i

}FIRST(E)={(,i}FIRST(E')={+,ε}FIRST(T)={(,i}FIRST(T')={*,ε}FIRST(F)={(,i}FOLLOW(E)={),#}FOLLOW(E')={),#}FOLLOW(T)={+,),#}FOLLOW(T')={+,),#}FOLLOW(F)={*,+,),#}它是LL(1)文法。1)各产生式的SELECT集：2）构造分析表SELECT(E→TE') ={(,i }SELECT(E'→+TE') ={+ }SELECT(E'→ε) ={),# }SELECT(T→FT') ={(,i }SELECT(T'→*FT') ={* }SELECT(T'→ε) ={+,),# }SELECT(F→(E)) ={( }SELECT(F→i) ={i }i+*()#E→TE'→TE'E'→+TE'→ε→εT→FT'→FT'T'→ε→*FT'→ε→εF→i→(E)i+*()#E→TE'→TE'E'→+TE'→ε→εT→FT'→FT'T'→ε→*FT'→ε→εF→i→(E)分析栈#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→ii匹配T'→εE'→+TE'+匹配T→FT'F→ii匹配T→*FT'*匹配F→ii匹配T'→εE'→ε接受例：输入i+i*i#

E→TE'

E'→+TE'|εT→FT'

T'→*FT'|εF→i|(E)4、LL(1)文法1）LL(1)文法的判定定义：对文法G[S]，如果其LL(1)分析表M不含多重定义元素，则称该文法是LL(1)文法。等价定义：对文法G[S]，若其每个非终结符号的所有的规则的SELECT集都两两不相交，则称该文法是LL(1)文法。例：文法G[S]是否是LL(1)文法:

S→aA

S→d

A→bAS

A→ε分析：

SELECT(S→aA) ={a}

SELECT(S→d)={d}

SELECT(A→bAS)={b}

SELECT(A→ε)={a,d,#}

SELECT(S→aA)∩SELECT(S→d)={a}∩{d}=Φ

SELECT(A→bAS)∩SELECT(A→ε)={b}∩{a,d,#}=Φ所以该文法是LL(1)文法。2）非LL(1)文法到LL(1)文法的变换提取左公共因子例：文法G[A]为:

A→ad

A→Bc

B→aA

B→bB1.化为：

A→adA→aAcA→bBcB→aA

B→bB2.化为：A→a(d|Ac)A→bBcB→aA

B→bB3.化为：A→aA'A→bBcA'→dA'→AcB→aA

B→bB结果是LL(1)文法。例：文法G[A]