自顶向下语法分析方法.pptVIP

第5章自顶向下语法分析方法;5.1确定的自顶向下分析思想;确定的自顶向下分析;

为了防止回溯,先研究三个定义：

符号串α的开始符号FIRST集

非终结符A后跟符号FOLLOW集

产生式的选择集合SELECT集;

定义：设G=(VT,VN,S,P)是上下文无关文法，

FIRST(α)={a|αaβ,a∈VT,α,β∈V*}

假设αε，那么规定ε∈FIRST(α);FIRST(Ap)={a,c}

FIRST(Bq)={b,d};2、非终结符A后跟符号FOLLOW集的定义：

定义：设G=(VT,VN,S,P)是上下文无关文法，A∈VN,S是开始符号。

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

假设S…A，那么规定#∈FOLLOW(A);3、产生式A→α的选择集合SELECT的定义：

〔确定选择那个产生式来推导〕

定义：给定上下文无关文法的产生式A→α，A∈VN,α∈V*，

假设αε，那么

SELECT(A→α)=FIRST(α)

如果αε，那么

SELECT(A→α)=(FIRST(α)-{ε})∪FOLLOW(A);例：S→aAS→dA→εA→bAS

SELECT(S→aA)=FIRST(aA)={a}

SELECT(S→d)=FIRST(d)={d}

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

SELECT(A→bAS)=FIRST(bAS)={b}

;定义：一个上下文无关文法是LL(1)文法的充要条件是：

对每个非终结符A的任两个不同产生式A→α和A→β，满足

SELECT(A→α)∩SELECT(A→β)=Φ

其中α,β不能同时ε;LL(1)文法的含义：;文法G[S]是否是LL(1)文法:

S→aA

S→d

A→bAS

A→ε;例：文法G[S]为:

S→aAS

S→b

A→bA

A→ε;5.2LL(1)文法的判别;例：设文法G[S]为:

S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→c

判断它是否是LL(1)文法。;1.求出能推出?的非终结符;S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→c;3.计算FOLLOW集;S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→c;4.计算SELECT集;5.3某些非LL(1)文法到LL(1)文法

的等价变换;1、提取左公共因子;例1：消除下面文法的左公共因子;例2：消除下面文法的左公共因子;说明：;〔2〕一个文法提取了左公共因子后，只解决了相同左部产生式右部的FIRST集不相交问题，当改写后的文法不含空产生式，且无左递归时，那么改写后的文法是LL(1)文法，否那么还需用LL(1)???法的判别方式进行判断才能确定是否为LL(1)文法。;2、消除左递归;〔1〕消除直接左递归;消除直接左递归的一般方法：

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

其中：αi不等于ε，βj不以A开头。

改为：

A→β1A|β2A|…|βnA

A→α1A|α2A|…|αmA|ε;〔2〕消除间接左递归;5.5确定的自顶向下分析方法;1.递归子程序法;假设有文法

Z→aBa

B→bB|c

那么相应的递归子程序可如下：

procedureZ()

begin

iftoken=athenMatch(a)；

B；

Match(a)

elseerror

end;;2.预测分析法;二、预测分析表的构造;置ip指向w#的第一个符号,#进栈，S(开始符号)进栈

????repeat

???令X是栈顶符号，a是ip所指向的符号；

???ifX是一个终结符号或#then

???????ifX=athen

???????????把X从栈中弹出，并且更新ip

?????????elseerror()

????else/*X是非终结符号*/

????ifM[X,a]＝X→Y1Y2…Ykthenbegin

??????????把X从栈中弹出；

??????????把Yk，Yk-1，…,Y1压入栈中，即Y1在顶上；

??????????输出产生式X→Y1Y2…Yk

????end

?????elsee