软件工程 编译原理 第五章 自顶向下的语法分析方法

第5章自顶向下的语法分析方法语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序)。目前语法分析常用的方法有:1、自顶向下（自上而下）分析2、自底向上（自下而上）分析5.3非LL(1)文法到LL(1)文法的等价转换确定的自顶向下分析要求给定语言的文法必须是LL(1)形式。然而，不一定每个语言都是LL(1)文法，对一个语言的非LL(1)文法是否能变换为等价的LL(1)形式以及如何变换是我们讨论的主要问题。由LL(1)文法的定义可知若文法中含有左递归或含有左公共因子，则该文法肯定不是LL(1)文法，因而，我们设法消除文法中的左递归，提取左公共因子对文法进行等价变换。1、提取公共左因子

若文法中含有形如：A→αβ|αγ的产生式，这导致了对相同左部的产生式其右部的FIRST集相交，也就是

SELECT(A→αβ)∩SELECT(A→αγ)≠φ

，不满足LL(1)文法的充分必要条件。1、提取公共左因子方法：假定关于A的规则是：

A→

1|

2|…|

n|

1|

2|…|

m (其中，每个

不以

开头)

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

A

|

1|

2|…|

mA

→

1|

2|…|

n经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。例1：若文法G的产生式为：

(1)S→aSb

(2)S→aS

(3)S→ε

请提取文法中的左公因子对产生式(1)、(2)提取左公因子后得：

S→aS(b|ε)

S→ε

进一步变换为文法G′：

S→aSA

A→b

A→ε

S→ε例2：若文法G的产生式为：

(1)A→ad

(2)A→Bc

(3)B→aA

(4)B→bB

请提取文法中的隐式左公因子。对文法G2分别用(3)、(4)的右部替换(2)中的B，可得：

(1)A→ad

(2)A→aAc

(3)A→bBc

(4)B→aA

(5)B→bB

提取产生式(1)、(2)的左公共因子得：

A→a(d|Ac)

A→bBc

B→aA

B→bB例2：若文法G的产生式为：

(1)A→ad

(2)A→Bc

(3)B→aA

(4)B→bB

请提取文法中的隐式左公因子。引进新非终结符A′，后得G′为：

(1)A→aA′

(2)A→bBc

(3)A′→d

(4)A′→Ac

(5)B→aA

(6)B→bB提取产生式(1)、(2)的左公共因子得：

A→a(d|Ac)

A→bBc

B→aA

B→bB文法中不含左公共因子只是LL(1)文法的必要条件。值得注意的是对文法进行提取左公共因子变换后，有时会使某些产生式变成无用产生式，在这种情况下必须对文法重新压缩(或化简)例3：若文法G的产生式为：

(1)S→aSd

(2)S→Ac

(3)A→aS

(4)A→b

用产生式(3)、(4)中右部替换产生式(2)中右部的A，文法变为：

(1)S→aSd

(2)S→aSc

(3)S→bc

(4)A→aS

(5)A→b对(1)、(2)提取左公共因子得：

S→aS(d|c)

引入新非终结符A′后为：

(1)S→aSA′

(2)S→bc

(3)A′→d|c

(4)A→aS

(5)A→b显然，原文法G3中非终结符A变成不可到达的符号，产生式(4)、(5)也就变为无用产生式，所以应删除。此外也存在某些文法不能在有限步骤内提取完左公共因子。例：若文法G4的产生式为：

(1)S→Ap|Bq

(2)A→aAp|d

(3)B→aBq|e

用(2)、(3)产生式的右部替换(1)中产生式的A、B使文法变为：

(1)S→aApp|aBqq

(2)S→dp|eq

(3)A→aAp|d

(4)B→aBq|e对(1)提取左公共因子得：

S→a(App|Bqq)

再引入新非终符S′结果得等价文法为：

(1)S→aS′

(2)S→dp|eq

(3)S′→App|Bqq

(4)A→aAp|d

(5)B→aBq|e同样分别用(4)、(5)产生式的右部替换(3)中右部的A、B再提取左公共因子最后结果得：

(1)S→aS′

(2)S→dp|eq

(3)S′→aS″

(4)S′→dpp|eqq

(5)S″→Appp|Bqqq

(6)A→aAp|d

(7)B→aBq|e

可以看出若对(5)中产生式A、B继续用(6)、(7)产生式的右部替换，只能使文法的产生式愈来愈多无限增加下去，但不能得到提取左公共因子的预期结果。由上面所举例子可以说明以下问题：

①不一定每个文法的左公共因子都能在有限的步骤内替换成无左公共因子的文法，上面文法G4就是如此。

②一个文法提取了左公共因子后，只解决了相同左部产生式右部的FIRST集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法是LL(1)文法，否则还需用LL(1)文法的判别方式进行判断才能确定是否为LL(1)文法。2.消除左递归设一个文法含有下列形式的产生式。

直接左递归

1)A→AβA∈VN，β∈V*

间接左递归

2)A→Bβ

B→AαA,B∈VN,α,β∈V*

一个文法是左递归时不能采用自顶向下分析法。2、消除左递归（1）直接消除产生式中的左递归：假定关于非终结符P的规则为：

P→P

|

其中

不以P开头。可以把P的规则等价地改写为如下的非直接左递归形式：

P→

P

P

→

P

|

左递归变右递归

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

P→P

1|P

2|…|P

m

|

1|

2|…|

n

其中，每个

都不等于

，每个

都不以P开头那么，消除P的直接左递归性就是把这些规则改写成：

P→

1P

|

2P

|…|

nP

P

→

1P

|

2P

|…|

mP

|

左递归变右递归例文法G(E):E→E＋T|TT→T*F|FF→(E)|i

经消去直接左递归后变成：

E→TE

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|i P→P

1|P

2|…|P

m

|

1|

2|…|

nP→

1P

|

2P

|…|

nP

P

→

1P

|

2P

|…|

mP

|

（2）消除间接左递归

对于间接左递归的消除需先将间接左递归变为直接左递归，然后再按a)消除直接左递归。例：文法G为例：

(1)A→aB

(2)A→Bb

(3)B→Ac

(4)B→d

用产生式(1)、(2)的右部代替产生式(3)中的非终结符A得到左部为B的产生式为：

(1)B→aBc

(2)B→Bbc

(3)B→d消除左递归后得：

B→(aBc|d)B′

B′→bcB′|ε

再把原来其余的产生式A→aB，A→Bb加入，最终文法为：

(1)A→aB

(2)A→Bb

(3)B→(aBc|d)B′

(4)B′→bcB′|ε

可以检验改写后的文法不是LL(1)文法。（3）消除间接左递归的算法把文法G的所有非终结符按任一种顺序排列成P1，P2，…，Pn；按此顺序执行；

FORi:=1TOnDOBEGINFORj:=1TOi-1DO

把形如Pi→Pj

的规则改写成

Pi→

1

|

2

|…|

k;(其中Pj→

1|

2|…|

k是关于Pj的所有规则)

消除关于Pi规则的直接左递归性

END化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。

例考虑文法G(S)S→Qc|cQ→Rb|bR→Sa|a令它的非终结符的排序为R、Q、S。对于R，不存在直接左递归。把R代入到Q的有关候选后，把Q的规则变为Q→Sab|ab|b例考虑文法G(S)S→Qc|cQ→Rb|bR→Sa|a令它的非终结符的排序为R、Q、S。Q的规则变为Q→Sab|ab|b现在的Q不含直接左递归，把它代入到S的有关候选后，S变成S→Sabc|abc|bc|c例考虑文法G(S)S→Qc|cQ→Rb|bR→Sa|aS变成S→Sabc|abc|bc|c消除S的直接左递归后：

S→abcS

|bcS

|cS

S

→abcS

|

Q→Sab|ab|b R→Sa|a例考虑文法G(S)S→Qc|cQ→Rb|bR→Sa|a消除S的直接左递归后：

S→abcS

|bcS

|cS

S

→abcS

|

Q→Sab|ab|b R→Sa|a关于Q和R的规则已是多余的，化简为：

S→abcS

|bcS

|cS

S

→abcS

|

(4.4)注意，由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但不难证明，它们都是等价的。例如，若对文法(4.3)的非终结符排序选为S、Q、R，那么，最后所得的无左递归文法是：

S→Qc|c

Q→Rb|b

R→bcaR

|caR

|aR

(4.5) R

→bcaR

|

文法(4.4)和(4.5)的等价性是显然的。5.5确定的自顶向下分析5.5.1、递归下降分析程序不带回溯的自上而下分析器分析程序由一组递归过程组成，文法中每个非终结符对应一个过程；所以这样的分析程序称为递归下降分析器。(因为文法的定义通常是递归的)几个全局过程和变量：ADVANCE，把输入串指示器IP指向下一个输入符号，即读入一个单字符号SYM，IP当前所指的输入符号ERROR，出错处理子程序例:文法G(E):E→TE

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|i 每个非终结符有对应的子程序的定义，首先在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。例:文法G(E):E→TE

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|i对应的递归下降子程序为:

PROCEDUREE；BEGIN T；E

END；

PROCEDUREE

；IFSYM=‘+’THEN BEGIN ADVANCE；T；E

ENDPROCEDURET；BEGIN F；T

ENDPROCEDURET

；IFSYM=‘*’THENBEGINADVANCE；F；T

END；例:文法G(E):E→TE

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|i对应的递归下降子程序为:

例:文法G(E):E→TE

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|i对应的递归下降子程序为:

PROCEDUREF；IFSYM=‘i’THENADVANCEELSE IFSYM=‘(’THEN BEGIN ADVANCE; E； IFSYM=‘)’THENADVANCE ELSEERROR END ELSEERROR;主程序:PROGRAMPARSER;BEGINADVANCE;E;IFSYM<>’#’THENERROREND;对应的递归下降子程序为:

E→TE

|BCPROCEDUREE；BEGIN IFSYMFIRST(TE’) THEN T；E

ELSEIFSYMFIRST(BC) THEN B;C ELSEERROREND；

E→TE

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|I对应的递归下降子程序为:

PROCEDUREE；BEGIN T；E

END；

PROCEDURET；BEGIN F；T

ENDE→TE

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|I对应的递归下降子程序为:

PROCEDUREE

；

IFSYM=‘+’THEN BEGIN ADVANCE；

T；E

ENDELSEIFSYM<>‘#’ANDSYM<>’)’THENERRORE→TE

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|I对应的递归下降子程序为:

PROCEDURET

；

IFSYM=‘*’THENBEGINADVANCE；

F；T

ENDELSEIFSYM<>‘#’ANDSYM<>’)’ANDSYM<>’+’THENERRORE→TE

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|i对应的递归下降子程序为:

PROCEDUREF；

IFSYM=‘i’THENADVANCEELSE IFSYM=‘(’THEN BEGIN ADVANCE; E；

IFSYM=‘)’THENADVANCE ELSEERROR END ELSEERROR;E→TE

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|i对应的递归下降子程序为:

主程序:PROGRAMPARSER;BEGINADVANCE;EEND;5.5.2、预测分析方法或LL(1)分析法一、预测分析程序工作原理总控程序预测分析表M[A，a]矩阵，A

VN

，a

VT是终结符或‘＃’，先进后出分析栈STACK用于存放文法符号总控程序分析表X

#输入串分析栈STACKa1a2...ai…#预测分析程序的工作图#Sa1a2...ai…#分析开始时：总控程序根据现行栈顶符号X和当前输入符号a，执行下列三种动作之一:1.若X＝a＝‘＃’，则宣布分析成功，停止分析。2.若X＝a

‘＃’，则把X从STACK栈顶逐出，让a指向下一个输入符号。匹配成功3.若X是一个非终结符，则查看分析表M。

若M[X，a]中存放着关于X的一个产生式，把X逐出STACK栈顶，把产生式的右部符号串按反序一一推进STACK栈(若右部符号为

，则意味不推什么东西进栈)。在把产生式的右部符号推进栈的同时应做这个产生式相应的语义动作。若M[X，a]中存放着“出错标志”，则调用出错诊察程序ERROR。推导预测分析程序的总控程序：BEGIN

首先把‘＃’然后把文法开始符号推进STACK栈；把第一个输入符号读进a；

FLAG:=TRUE;WHILEFLAGDO BEGIN

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

IFX

VTTHEN IFX=aTHEN把下一输入符号读进a ELSEERROR

匹配成功

ELSEIFX=‘#’THEN IFX=aTHENFLAG:=FALSEELSEERRORELSEIFM[X,a]={X→X1X2…Xk}THEN

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

/*若X1X2…Xk=

，不推什么进栈*/ELSEERRORENDOFWHILE;STOP/*分析成功，过程完毕*/END分析成功推导预测分析程序的框图

例

对于文法G(E)E→TE

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|i 输入串为i1*i2+i3，利用分析表进行预测分析：步骤

符号栈

输入串

所用产生式0 #E i1*i2+i3#1 #E

T i1*i2+i3# E→TE

2 #E

T

F i1*i2+i3# T→FT

3 #E

T

i i1*i2+i3# F→i步骤

符号栈

输入串

所用产生式3 #E

T

i i1*i2+i3# F→i4 #E

T

*i2+i3#5 #E

T

F* *i2+i3# T

→*FT

6 #E

T

Fi2+i3#7 #E

T

i i2+i3#F→i步骤

符号栈

输入串

所用产生7 #E