3 自顶向下语法分析概述

第三章：语法分析

自顶向下语法分析概述

三个重要的集合第一个难点~！！语法分析的任务是什么？

开始符+程序语句？

程序序列是否能够由开始符经过一系列推导来得到。结论：

每个句子都有相应的最右和最左推导。非二义性文法，则最左推导的序列唯一。1.自顶向下语法分析概述自顶向下语法分析方法，亦称面向目标的分析方法。思想：从文法的开始符出发企图用最左推导推导出与输入的单词串完全相匹配的句子。若输入的单词串是给定文法的句子，则必能推出，反之必然以推导失败而终止。自顶向下语法分析方法分为：

1、非确定的自顶向下语法分析方法;2、确定的自顶向下语法分析方法：实现方法简单、直观，便于手工构造和自动生成，是目前常用的语法分析方法。

递归下降方法；LL（1）方法。1.自顶向下语法分析概述对文法有要求！4非确定的自顶向下语法分析方法（带回溯过程的自顶向下语法分析方法）已知G[S]:

S→Ay|BAy A→aA│a B→xB│x输入串为xay是否正确。

AyBAy

aAya

xBAyx

xxBAyx

xxAyS

xAya

xaAya

xaaAy

xaay

xay

ay

BAy过程伴有大量回溯！效率低！添加启发式输入的字符流：看的越多越准确；

但也越复杂！1.自顶向下语法分析概述选择规则的策略穷举的方法效率非常的差考虑更多的信息，如输入流根据输入流选取规则考察输入流中的几个符号2.简述三个集合目标：预测（Predict）利用该规则所产生的所有串的头符的集合！如何确定是否选择它？对于一条规则：A

两种情况：1)

*

就是

所能推导出的串的头符First()1)

*

就是A后面能紧接着的串的头符Follow(A)2.1First集的定义设G=(VT，VN，S，P)是上下文无关文法,(VT

VN)*

First(

)={a

VT|

*a...}

(if

*

then{

}else

)2.2Follow集的定义设G=(VT，VN，S，P)是上下文无关文法，AVN，S是开始符号Follow(A)={a

VT|S

+...Aa...}

(ifS

*...Athen{#}else

)为了判断结束，人为添加的符号。2.3Predict集的定义Predict(A→

)=First(

)，当First(

)不含

=First(

)-{

}

Follow(A)，当First(

)含

2.简述三个集合First集和Follow集都是为了计算Predict集一条规则：A

First集一个串：

Follow集一个非终极符：A可含空Predict集3.1计算First(X)集若XVT,First(X)={X}若XVN则

First(X)={a|Xa…P,aVT}若XVN,且有产生式X,则

First(X)若XVN,有产生式XY1Y2…Yn，且Y1,Y2,…,YiVN

当Y1,Y2,…,Yi-1*，

则First(Y1)-{},First(Y2)-{},…First(Yi-1)-{},First(Yi)都包含在First(X)中。当Yi*(i=1,2,…n),若i≠n，则将First(Yi+1)并入First(X)中，否则，将{

}并入First(X)中。必考~！！！3.2计算First(

)集设符号串=X1X2…Xn，当X1,X2,…,Xi-1*，Xi不能

*，则:First()=1i-1(First(Xj)-{})First(Xi)若所有Xi都能*，则:First()=1nFirst(Xj)13例：

ETE’E’+TE’|

TFT’T’*FT’|

Fid|(E)符号串First集TE’{id,(}文法符号First集EE’TT’F{id,(}{id,(}{id,(}{+,

}{*,

}{id,(}FT’E’T’T{+,*,

id,(}E’T’{+,*,

}上节课算数表达式消除二义性的文法4.计算Follow集对于非终极符：B已知条件：①A→XBY②S*

A

求Follow(B)能跟在B后面的串的头符

若Y

*

②S*

A

XBY

*

XB

能跟在A后面的串都能跟在B后面

1:

对所有A

VN且A非开始符:

令Follow(A):={}；

对开始符S:令Follow(S)={#}；2:

若有产生式A→xBy：如果

First(y)则：

Follow(B)=Follow(B)

(First(y)－{

})

Follow(A)

否则：

Follow(B) =Follow(B)

First(y)

3:重复2，直至对所有A

VN，Follow(A)收

敛为止。4.计算Follow集例：

ETE’E’+TE’

|

TFT’T’*FT’

|

Fid|(E)文法符号First集EE’TT’F{id,(}{id,(}{id,(}{+,

}{*,

}{{{{{}}}}}#Follow集,)#,),#,)+,#,)+,#,),+*Follow集的计算，一般至少走两遍！！！5.计算Predict集Predict(A

)

First(

)，当First(

)不含

=

(First(

)-{

})

Follow(A)，当First(

)含

18例：

ETE’E’+TE’|

TFT’T’*FT’|

Fid|(E)文法符号First集Follow集E{id,(}{),#}E’{+,

}{),#}T{id,(}{+,),#}T’{*,

}{+,),#}F{id,(}{*,+,),#}Predict(ETE’)=first(TE’)={id,(}Predict(E’+TE’)=first(+TE’)={+}Predict(E’

)=follow(E’)={),#}Predict(TFT’)=first(FT’)={id,(}19例：

ETE’E’+TE’|

TFT’T’*FT’|

Fid|(E)文法符号First集Follow集E{id,(}{),#}E’{+,

}{),#}T{id,(}{+,),#}T’{*,

}{+,),#}F{id,(}{*,+,),#}Predict(T’*FT’)=first(*FT’)={*}Predict(T’

)=follow(T’)={+,),#}Predict(Fid)=first(id)={id}Predict(F(E))=first((E))={(}20非确定的自顶向下语法分析方法主要问题：虚假匹配而引起回溯，原因是：1.由于相同左部的产生式的右部的FIRST集的交集不为空而引起回溯。例：有如下文法G[Z]：ZcAe|cAd Aeb|a分析字符串cad。First(cAe)∩First(cAd)≠

Predict(ZcAe)∩

Predict(ZcAd)≠

至多有一个产生式被选择的条件是：predict(A

βk)

predict(A

βj)=

，当kj含公共前缀的规则Predict集交集必定不为空2.由于某非终极符的产生式的右部能推导出，且该非终极符的FOLLOW集中含有其某个产生式右部的FIRST集中的元素。例：有如下文法G[S]：SaAS|b A

bAS|

|d分析字符串ab。First(bAS)∩First(d)=

Predict(AbAS)∩

Predict(A

)≠

至多有一个产生式被选择的条件是：predict(A

βk)

predict(A

βj)=

，当kjFirst(bAS)∩First(

)=

First(d)∩First(

)=

Follow(A)={b,a}满足该条件的文法称为LL(1)文法，递归下降子程序文法。非LL(1)文法到LL(1)文法的等价转换消除左公共前缀消除直接左递归消除左递归注意1：即使文法没有公共前缀和左递归也并不意味着文法一定是LL(1)文法，有时还需要其它的转换方法。注意2：通常程