编译原理第4章：语法分析-自上而下分析

第四章语法分析-自上而下分析22023/11/30

4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL(1)分析法

•

一、直接左递归的消除

•

二、提取左因子、消除回溯

•

三、LL(1)分析法4.4递归下降分析程序构造4.5LL(1)分析中的错误处理主要内容：32023/11/304.1语法分析器的功能语法分析是编译过程的核心部分。语法分析的任务：在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语言的语法结构用上下文无关文法描述。42023/11/30词法分析器符号表编译程序后续部分语法分析器源程序单词符号取下一单词符号语法分析树图4-1语法分析器在编译程序中的地位52023/11/30语法分析器的功能：按照文法的产生式，识别输入符号串是否为一个句子。这里所说的输入串是指由单词符号（文法的终结符）组成的有限序列。关键：对一个文法，当给你一串（终结）符号时，怎样知道它是不是该文法的一个句子呢？这就要判断，看是否能从文法的开始符号出发推导出这个字符串。或者，从概念上讲，就是要建立一棵与输入串相匹配的语法分析树。62023/11/30语法分析的方法：自下而上分析法 基本思想：从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；或者说，从语法树的末端开始，步步向上“归约”，直到根结。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。自上而下分析法

基本思想：从文法的开始符号出发，根据文法的产生式规则正向推导出给定句子的一种方法；或者说，从树根开始，往下构造语法树，直到建立每个叶的分析方法。72023/11/304.2自上而下分析面临的问题顾名思义，自上而下就是从文法的开始符号出发，向下推导，推出句子。带回溯的分析方法不带回溯的递归子程序（递归下降）分析方法自上而下分析的主旨： 对任意输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。82023/11/30这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。例4-1假定有文法：

(1)S→xAy

(2)A→**|*

分析输入串x*y(记为

)。

92023/11/30

实现这种自上而下的带回溯试探法的一个简单途径是让每个非终结符对应一个递归子程序。每个这种子程序可作为一个布尔过程。一旦发现它的某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值；否则，保持原来的语法树和IP值不变，并返回“假”值。102023/11/30面临的问题：首先，是文法的左递归性问题。一个文法是含有左递归的，如果存在非终结符P

含有左递归的文法将使上述的自上而下的分析过程陷入无限循环。即当试图用P去匹配输入串时，我们会发现，在没有识别任何输入符号的情况下，又得重新要求P去进行新的匹配。112023/11/30其次，由于回溯就碰到一大堆麻烦事情。如果我们走了一大段错路，最后必须回头，那么，就应把已经做的一大堆语义工作推倒重来。第三，在上述的自上而下分析过程中，当一个非终结符用某一个候选匹配成功时，这种成功可能仅是暂时的。第四，当最终报告分析不成功时，我们难于知道输入串中出错的确切位置。最后，由于带回溯的自上而下分析实际上采用了一种穷尽一切可能的试探法，因此效率很低，代价极高。122023/11/30一、左递归的消除

使用自顶向下的任何一种算法必须消除左递归和提取公共左因子。1、直接左递归的消除若文法中有形如P→Pα的产生式，则称直接左递归，如A→Ab|a。

设，有P→Pα|β，若α≠>ε，β不以P开头（否则不可能消除左递归）。则改写为： 可消除左递归。

4.3LL(1)分析法132023/11/30一般地，若

αi≠ε，βj不以P开头，则可改写为：从而消除直接左递归。例：S→Sabc|Sab|ab消除直接左递归得：142023/11/302、完全消除左递归分析虽不含直接左递归，但所以含有左递归。如果文法G不含回路（），也不含ε产生式，则下列算法可消除左递归（完全）①把G的非终结符按任意顺序排列成P1,…,Pn②fori:=1tondobeginforj:=1toi-1do

把形如的规则改写成，其中；消除关于Pi的直接左递归

end;③化简由②得到的文法（取消无用非终结符产生式）152023/11/30例：上述文法①排序：S,Q,R②循环：

i=1时，处理S→Qc|c，消除直接左递归，不变

i=2时，处理Q→Rb|b，j=1，把有关Q的产生式中以S开头的候选式替换（无），所以不变

i=3时，处理R→Sa|a，

j=1，把以S开头的候选式替换，得R→Qca|ca|a162023/11/30

j=2，把以Q开头的候选式替换，得：R→Rbca|bca|ca|a

消除R的直接左递归，得：

R→bcaR’|caR’|aR’

R’→bcaR’|ε③整理：

得：S→Qc|c

Q→Rb|b

R→bcaR’|caR’|aR’

R’→bcaR’|ε172023/11/30二、提取左因子、消除回溯1、FIRST（

）

设文法G是不含左递归的文法，对其任何非终结的候选式

定义：FIRST（

）={a|

a,a∈VT,,∈(VTUVn)*}

若

ε，则规定ε∈FRIST（

）182023/11/302．应用如果一个文法G的非终结符A的多个候选式之首符集两两不相交，那么在自上而下分析时便可消除回溯。设，而FIRST(α1),…,FIRST(αn)两两不相交，那么当分析时要A去匹配某输入串时，便可根据此输入串的输入符号a,准确地选用候选式αi（设a∈FIRST(αi),若ε∈FIRST(αi)以后讨论）。192023/11/30例：文法S→aSb|c，

输入串为aacbb时：3．公共左因子的提取：把文法改造为每个非终结符的所有候选式两两不相交的方法是提取公共左因子。可改造为：202023/11/30三、LL(1)分析法预测分析（LL(1)）法是实现自上而下分析的另一种有效方法。它使用一个分析栈和一张分析表。分析表矩阵元素M[A,a]指出非终结符A，面临输入符号a时，应选用的候选式（或产生式）。若A不该面临a，则放一出错标志。212023/11/301、LL(1)分析法的工作过程开始往输入串末尾和分析栈stack中放“＃”，然后把文法开始符号压栈。预测分析程序总是按stack栈顶符号X和当前输入符号a行事。

①若X=a=”#”，则分析成功，停止分析

②若X=a≠”#”，则把X从栈顶弹出，a指向下一个输入符号

③若X∈Vn，则查分析表。若M[X,a]为某候选式，则弹出X，把该候选式反序压栈；若M[X,a]=ε,则弹出X，什么也不压；若M[X,a]=error，则报错。

222023/11/30为了便于描述分析过程，我们定义：，代表栈X面临输入符号a采取第i条动作后，栈变为Y。例1．分析i*i#

232023/11/302、FIRST集和FOLLOW集的定义设G=(VT,VN,P，S)是上下文无关文法FIRST（

）={a|

a,a∈VT,,∈V*}

若

ε则规定ε∈FRIST（

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

FRIST（

），

∈V*，

∈V+}

若S

uA

,且

ε，则#∈FOLLOW(A)242023/11/30计算FIRST集1.若X

V

,则FIRST(X)={X}2.若X

VN,且有产生式X

a…，则把a加入到FIRST(X)中;若X

也是一条产生式,则把

也加到FIRST(X)中.3.若X

Y…是一个产生式且Y

VN,则把FIRST(Y)中的所有非元素都加到FIRST(X)中;若X

Y1Y2…YK

是一个产生式,Y1,Y2,…,Y(i-1)都是非终结符,而且,对于任何j,1≤j≤i-1,FIRST(Yj)都含有

(即Y1..Y(i-1)

),则把FIRST(Yj)中的所有非

元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj

,

j=1,2,…,K)均含有

,则把

加到FRIST(X)中.

252023/11/30计算FOLLOW集1.对于文法的开始符号S,置#于FOLLOW(S)中;2.若Ａ

αBβ是一个产生式,则把

FIRST(β)\{}加至FOLLOW(B)中;3.若Ａ

αB是一个产生式,或Ａ

αBβ是

一个产生式而β

(即

FIRST(β)），

则把FOLLOW（A）加至FOLLOW（B）中．262023/11/30

一个文法G是LL（1）的，当且仅当对于G的每一个非终结符Ａ的任何两个不同产生式Ａ

α

β，下面的条件成立：１．FIRST（α）∩FIRST(β)=,也就是α

和β推导不出以同一个终结符a为首的符号串；它们不应该都能推出空字

．２.假若β

，那么，

FIRST（α)∩FOLLOW（A）＝.也就是，若β.则α所能推出的串的首符号不应在FOLLOW(A）中．．

272023/11/30例：G[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)=｛*,＋，),#}

282023/11/30例：G[E]:(1)E–>TE’(2)E’–>+TE’

(3)E’–>

(4)T–>FT’

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

(7)F–>(E)(8)F–>a

试判断文法G是不是LL(1)文法。分析：

E’–>+TE’|

FIRST(+TE’)=｛+｝

FOLLOW(E′)=｛)，＃｝

T’–>*FT’|

FIRST(*FT’)=｛*｝

FOLLOW(T′)=｛+,)，＃｝

F–>(E)|aFIRST((E))=｛(｝

FIRST(a)=｛a｝所以G[E]是LL（1）的292023/11/303、LL(1)分析表的构造1.对文法G的每个产生式Ａ

执行第2步和第3步；2.对每个终结符a

FIRST(

)，把Ａ

加

至

[A,a]中，3.若

FIRST(

)，则对任何bFOLLOW(A)

把Ａ

加至

[A,b]中，4.把所有无定义的

[A,a]标上“出错标志”。可以证明，一个文法G的预测分析表不含多重入口，当且仅当该文法是LL(1)的。302023/11/30例1：文法，试用LL(1)分析法分析输入串abbcde。解：①消除左递归得文法：

②求必要的FIRST和FOLLOW。

FIRST(aAcBe)={a}

FIRST(bA’)={b}FIRST(

)={

}FIRST(d)={d}FOLLOW(A’)=FOLLOW(A)={c}312023/11/30③构造LL(1)分析表④分析abcde#SaAcBeAbA’A’bA’

Bd322023/11/304、LL(1)文法分析表有多重入口。若一个文法G的分析表不含多重入口，则称它为LL(1)文法。一个文法是LL(1)的，当且仅当G的每个非终结符A的任何两个侯选式α和β有

①FIRST(α)∩FIRST(β)=

②若εFIRST(β)，则有FIRST(α)∩FOLLOW(A)=

332023/11/30

LL(1)文法的性质：

LL(1)文法是无二义的

LL(1)文法不含左递归非LL(1)文法的改造消除左递归提左公因子将产生式Ａ

β|

变换为：

Ａ

BB

β|

342023/11/30例1：文法G（E）：E→E+T｜TT→T*F｜FF→i｜(E)FIRST(E)=｛(,i｝FIRST(T)=｛(,i｝FIRST(F)=｛(,i｝消左递归

E–>TE’E’–>+TE’E’–>

例2：S→ifCtS|

ifCtSeSC→b提左因子

S→ifCtSAA→eS|

First集Follow集Sif#,eAe,

#,eCbtM[A,e]={A→eSA→

}352023/11/304.4递归下降分析程序构造一、递归子程序法的原理：对文法中每个非终结符U（它们代表一定的语法成分）都编出一个子程序，以完成该非终结符号所对应的语法成分的分析和识别任务。每个非终结符号的子程序功能是：用该非终结符的产生式规则右部符号串去匹配输入串。注:

可匹配任何终结符，但搜索指针不前进。使用自上而下的方法时前提是：消除左递归；提取公共左因子。

362023/11/30当一个文法满足LL(1)条件时，我们就可以为它构造一个不带回溯的自上而下分析程序，这个分析程序是由一组递归过程组成的，每个过程对应文法的一个非终结符。这样的一个分析程序称为递归下降分析器。如果用某种高级语言写出所有递归过程，那就可以用这个语言的编译系统来产生整个的分析程序。372023/11/30例如，考虑文法：

E→TE

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|i它的每个非终结符都有对应的递归过程，在分析过程中，当需要从某个非终结符出发进行展开时，就调用这个非终结符对应的子程序。382023/11/30几个全局过程和变量ADVANCE：是指把输入串指示器IP调至指向下一个输入符号SYM：是指IP当前所指的那个输入符号ERROR：为出错诊察处理程序392023/11/30对应的递归过程如下：PROCEDUREE；BEGIN T；E

END；PROCEDUREE

；IFSYM=‘+’THEN BEGIN ADVANCE；

T；E

END402023/11/30PROCEDURET；BEGIN F；T

ENDPROCEDURET

；IFSYM=‘*’THENBEGINADVANCE；

F；T

END；412023/11/30

PROCEDUREF；

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

IFSYM=‘)’THEN ADVANCE ELSEERROR END ELSEERROR;422023/11/30二、文法的另一种表示法

在元符号“→”和“|”的基础上，扩充几个元语言符号：1.用花括号{

}表示闭包运算

*。2.用{}n0表示

可任意重复0次至n次。3.用方括号[

]表示{}10

，即表示

的出现可有可无(等价于

|

)。引入上述元符号的文法亦称扩充的巴科斯范式。432023/11/30例如，通常的“实数”可定义为：

decimal→[sign]integer.{digit}[exponent]exponent→E[sign]integerinteger→digit{digit}sign→+|-用扩充的巴科斯范式来描述语法的好处是，直观易懂，便于表示左递归消去和因子提取。对于构造自上而下分析器来说，采用这种定义系统描述文法显然是非常可取的。442023/11/30例4.5文法