程序设计语言与编译原理-自上而下的语法分析课件

语法分析对无关文法G=(VT，VN，S，P)及符号串ω，判断ω是否是文法G的一个合法句子。即

S*=>w？

符号串（二元式流）正确句子的语法树报告语法错误语法分析程序第七章自上而下的语法分析第一节引言一.语法分析的功能语法分析:自上而下(自顶而下)

自下而上(自底而上)二.语法分析方法的分类自上而下语法分析法:或从开始符号出发,找最左推导;或从根开始,构造推导树。自下而上语法分析法:从输入串开始,归约,直至文法开始符。自上而下的语法分析分析过程从文法开始符出发，能否找到一个最左推导序列，使得S=>*w

；或者从根结点S开始，根据最左推导，能否构造一棵语法树，使得该语法树的叶结点自左至右的连接正好是ω。给定文法G=(VT,

VN,S，P)以及输入串wVT*,自下而上的语法分析分析过程从ω出发，能否找到一个最左规约（最右推导的逆过程）序列，逐步向上规约，直至文法的开始符S；或者对生成ω的语法树，按最左规约对语法树进行剪枝，能否最后只剩下根结点S。给定文法G=(VT,

VN,S，P)以及输入串wVT*,自上而下的语法分析可分为不确定和确定的两类。回溯分析法是不确定的分析方法。递归下降分析法和预测分析法属于确定的分析方法。第二节回溯分析法一.一个实例S→xAyA→ab│a输入串为xay,说明分析过程。xAyabSxAyaS从文法的开始符号S出发，选取S的候选式进行推导，接着按最左推导进行下去；如果推导失败，再换用其他的候选式；若穷尽所有的候选式都失败，则表明w不是G的句子，w存在语法错语。

(1)公共左因子的存在

A→1|2(2)左递归

A→Aα或AAα+二.存在的问题—回溯直接左递归间接左递归(3)ε产生式可能产生回溯的原因有(1)公共左因子公共左因子，是指在文法的产生式集合中，某个非终结符的多个候选式具有相同的前缀。一般，公共左因子的产生式为

A→αβ1│αβ2存在公共左因子采取试探的方法来分析每一个候选式，分析的过程很可能产生回溯。若所有的候选式都没有公共左因子就可以选择惟一匹配的候选式，不会产生回溯。

(2)左递归左递归的形式为

A=>+Aβ特别地

A=>Aβ

就是直接左递归例子:S→SaS→b文法G(s)：符合串baa的推导过程。SbSaSbaSaSSbε产生式S→aASS→bA→bASA→ε文法G(S)：输入串ab的推导过程。SAaSAbSSAaSεb

例：将文法S→xAyA→ab│a改造成：S→xAyA→aBB→b│xay的推导过程如右图SxAyaB

三.解决回溯：提取公共左因子

一般方法A→1|2|…|n|δ提取公共左因子A→B|δB→1|2|…|n产生式：

四.消除左递归1.消除直接左递归改写为PPα|Pβ|γPγP’P’αP’|βP’|P→P’P’→αP’│εP→Pα│β改写为PPα|β|γ改写为P

βP’|γP’P’αP’|一般地:

A→A1|A2|…|Am|1|2|…|n

（iε，j不以A开头）改写为:A→1P’│2P’│...│nP’P’→1P’│2P’│...│mP’│ε

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

P→P1|P2|…|Pm|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→TEE→+TE|

T→FTT→*FT|F→(E)|i (4.2)P→P1|P2|…|Pm

|1|2|…|nP→1P|2P|…|nPP→1P|2P|…|mP|例如文法G(S):S→Qc|cQ→Rb|bR→Sa|a (4.3)虽没有直接左递归，但S、Q、R都是左递归的SQcRbcSabc例：设文法G(A):A→Ac|Aad|bd|e消去直接左递归：A→bdA’|eA’A’→cA’|adA’|

2.间接左递归的消除PPα+例子：A→Bc│aB→AbA→Abc│aA→aP’P’→bcP’│ε改为：

算法1.将文法G的所有非终结符按任一顺序排列，设为A1,…,An2.执行下面算法，消除可能的左递归：fori:=1tondoforj:=1toi-1dobegin

把一个形如AiAj的产生式改写为

Aiδ1|δ2|…|δk

其中Ajδ1|δ2|…|δk是Aj的所有产生式;

消除Ai产生式的直接左递归;end3.化简：删除多余产生式，即在从文法开始符号的

任何推导中都不会出现的非终结符的产生式；以S→Qc│cQ→Rb│bR→Sa│a为例,按S,Q,R排列,或R,Q,S排列

S→Qc|cQ→Rb|bR→Sa|a步骤：1.将非终结符按R，Q，S排列2.执行算法i=1没有操作i=2,j=1，Ai=Q,Aj=R,有Q→Rb|b把R→Sa|a代入上式得:Q→Sab|ab|b该式无直接左递归i=3,j=2，Ai=S,Aj=Q，S→Qc|c将上面得到的Q的产生式代入得：S→Sabc|abc|bc|c消除上式的直接左递归得：

S→abcS’|bcS’|cS’S’→abcS’|i=3,j=1，Ai=S,Aj=R，无相应产生式，没有操作3.化简：经过上述算法，Q和R的产生式为多余的产生式，可删除。最后得：S→abcS’|bcS’|cS’S’→abcS’|1.按R、Q、S排列,代入后

R→Sa│aQ→Sab│ab│bS→Sabc│abc│bc│cS→Qc│cQ→Rb│bR→Sa│a2.消除S中的直接左递归文法产生的语言:(abc|bc|c)(abc)*S→abcS’│bcS’│cS’S’→abcS’│

1.按S、Q、R排列,代入后

S→Qc│cQ→Rb│bR→Qca│ca│aR→Rbca│bca│ca│aS→Qc│cQ→Rb│bR→Sa│a2.消除R中的直接左递归

R→bcaR’│caR’│aR’R’→bcaR’│文法产生的语言:(bca|ca|a)(bca)*bc|bc|c

文法产生的语言:(bca|ca|a)(bca)*bc|bc|c文法产生的语言:(abc|bc|c)(abc)*

对于文法G=（{a,b,c,d,},{S,A},S,P）;其中P为:S→Aa|Ac|bcA→Ad|Sbc|d请先提取文法G的公共左因子，再消除左递归。练习提取公共左因子S→AB|bcB→a|cA→Ad|Sbc|d

S→Aa|Ac|bcA→Ad|Sbc|d直接左递归S→AB|bcB→a|cA→SbcP|dPP→dP|间接左递归S→AB|bcB→a|cA→ABbcP|bcbcP|dPP→dP|间接左递归S→AB|bcB→a|cA→bcbcPQ|dPQQ→BbcPQ|P→dP|回顾

1.语法分析功能2.两大类3.回溯分析1.自上而下(自顶而下)2.自下而上(自底而上)a.公共左因子b.左递归c.空产生式

当文法改造为无公共左因子,无左递归时,让每个非终结符对应一个过程，该过程对相应的非终结符产生式的右部短语进行语法分析，这种分析方法称为递归下降分析法。这样的分析程序称为递归下降分析器。第三节递归下降分析法例:G(E)E→E+T│TT→T*F│FF→(E)│i消除左递归:E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│i

一.分析方法过程advance:匹配并把输入串指针后移一位变量sym:输入指针指向的符号Error():出错处理函数

procedureadvance(t:token);beginifsym==tthensym=nexttokenelseerror（）end;

procedureE;beginT;E’end;procedureT;beginF;T’end;E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│iprocedureE’;ifsym=‘+’thenbeginadvance(‘+’);T;E’end;procedureT’;ifsym=‘*’thenbeginadvance(‘*’);F;T’end;

E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│iprocedureF;ifsym=‘i’thenadvance(‘i’)elseifsym=‘(’thenbegin

advance(‘(’);E;ifsym=‘)’thenadvance(‘)’)elseerror()endelseerror();

i+i*i#的递归下降分析过程E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│iETTiiiii+++++**######FM(i)FM(i)FM(i)E’M(+)T’M()E’M()#T’M()#T’M(*)M()

二.扩充的BNF用花括号{α}表示闭包运算α*;α可以重复任意多次用{α}表示α可任意重复0次至n次

{α}=α0=ε;用[α]表示{α},即[α]表示α的出现可有可无(等价于α│ε)；1.表示形式n00010例一：标识符的定义利用扩充BNF表示为E→T{+T}T→F{*F}F→i|(E)E→E+T│TT→T*F│FF→(E)│i例二：文法I→L│LSS→T│STT→L│DL→a│b│...│zD→0│1│2│...│9I→L{L|D}L→a|b|…|zD→0|1|…|9

decimal→[sign]integer.{digit}[exponent]exponent→E[sign]integerinteger→digit{digit}sign→+│-digit→0│1│…│9例三：实数可定义为

p→x│y│…│z│pv改写成:p→(x│y│…│z){v}2.左递归的消除

3.文法的转换图表示E→T{+T}T→F{*F}F→i|(E)E→E+T│TT→T*F│FF→(E)│i+012T关于E的转换图012F*关于T的转换图013（）i2E关于F的转换图

procedureE;BeginT;whilesym=’+’dobeginadvance(‘+’);TendendE→T{+T}+012T关于E的转换图E→T{+T}T→F{*F}F→i|(E)三.改进的递归下降分析法F

procedureT;beginF;whilesym=’*’dobeginadvance(‘*’);Fendend;T→F{*F}012F*关于T的转换图

procedureF;ifsym=‘i’thenadvance(‘i’)elseifsym=‘(’thenbeginadvance(‘(’);E;ifsym=‘)’thenadvance(‘)’)elseerrorendelseerror；013（）i2E关于F的转换图F→i|(E)

i+i*i#的递归下降分析过程E→T{+T}T→F{*F}F→(E)│iETTFFFiii++i##i*M(i)M(*)M(i)M(+)M(i)

第四节预测分析法

预测分析（LL(1)分析法）是一种表驱动方法，由下推栈、预测分析表和控制程序组成。它实际上一种下推自动机的实现模型。LL(1)分析法是一种不带回溯的非递归自上而下分析法。

LL(1)的含义:

第一个L表明自左至右扫描输入串;第二个L表明最左推导;1表明向右查看一个符号。类似地,可有LL(k)文法,即向前查看k个符号才能确定选用哪个产生式,不过LL(k)(k>1)在实际中极少使用。

LL(1)分析法的基本思想:

根据输入串的当前输入符确定选用某一个产生式进行推导,当该输入符与推导的第一个符号相同时，再取输入串的下一个符号,继续确定下一个推导应选的产生式,如此下去,直到推出被分析的输入串为止。一个LL(1)分析器由一张LL(1)分析表(预测分析表)、一个先进后出分析栈和一个控制程序(表驱动程序)组成。a1a2…ai…an#分析表M控制程序输入串：栈顶#x1…xj输出分析栈图LL(1)分析器对图

的LL(1)分析器说明如下：

(1)输入串是待分析的符号串,它以“#”作为结束标志。(注:#∈VT但不是文法符号,是由分析程序自动添加的)(2)分析栈存放分析过程中的文法符号。分析开始时栈底先放一个“#”,再压入文法开始符;当分析栈中仅剩“#”且输入串指针指向串尾的“#”时,分析成功。

(3)分析表用一个矩阵M(二维数组)表示,它概括了文法的全部信息。矩阵的每一行与文法的一个非终结符相关联,而每一列与文法的一个终结符或“#”关联。分析表元素M[A,a]中的内容为一条A的产生式,表明当A面临输入符a时应采用的候选式;当元素内容为空时,表明A不应面临输入符a,即输入串含语法错误。(4)控制程序根据分析栈栈顶符号x和当前输入符a决定分析器的动作:①若x＝a＝“#”,则分析成功。②若x＝a≠“#”,即栈顶符号x与当前输入符a匹配,则将x从栈顶弹出,输入串指针后移,继续对下一个字符进行分析。③若x为非终结符A,则查分析表M[A,a]:i.若M[A,a]为一产生式,则A自栈顶弹出,M[A,a]中产生式的右部符号逆序压栈;若M[A,a]为A→ε,则只将A自栈顶弹出。

ii.若M[A,a]为空,则发现语法错误,调用出错处理程序进行处理。控制程序描述如下:

将“#”和文法开始符依次入栈;

把第一个输入符读入a;do{把栈顶符号弹出并放入x中;if(x∈VT){if(x＝＝a)将下一输入符读入a;elseerror();}elseif(M[x,a]＝＝“x→y1y2…yk”){把y1y2…yk按逆序入栈;

输出“x→y1y2…yk”;}elseerror();}while(x!=“#”)一.预测分析过程1.预测分析表形式:M[A,a]矩阵,AVN,aVT{#}

内容:A→α或出错标志(空白表示)

预测分析表EE’TT’Fi+*()#E→TE’E→TE’E’→+TE’T→FT’T→FT’T’→*FT’F→iF→(E)E’→εE’→εT’→εT’→εT’→εE→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│i

2.分析方法初始时,#和开始符入栈,输入指针指向第一个符号,然后根据下推栈栈顶符x和当前输入符a进行工作:①x=a=#,成功②x=a#,匹配③xVN,查表并把产生式右部符号按逆序推进栈

例：文法G2’E→TE’E’→+TE’|T→FT’T’→*FT’|F→(E)|i如何对输入串i+i*i按照预测分析法进行语法分析?

下推栈输入串查分析表i+i*i##E#E’T#E’T’F#E’T’#E’T’i#E’#E’T#E’T+i+i*i#+i*i#i+i*i#i+i*i#+i*i#+i*i#i*i#E→TE’T→FT’T→FT’F→iT’→εE’→+TE’

匹配匹配#E’T’Fi*i##E’T’i#E’T’#E’T’F*#E’T’i#E’T’F#E’T’##E’*i#i#*i#i####T’→*FT’结束F→iT’→εi*i#F→iE’→ε

匹配匹配匹配例7

一个文法的LL(1)分析表如下所示,

试给出输入串aadl的分析过程。输入串aadl的分析过程如下:符号栈当前输入符输入串说明

#Aaadl#弹出栈顶符,将A→aA'右部反序压栈

#A'aaadl#匹配,弹出栈顶符a,读出下一输入符a

#A'a

dl#弹出栈顶符,将A'→ABl右部反序压栈

#lBAa

dl#弹出栈顶符,将A→aA'右部反序压栈#lBA'aa

dl#匹配,弹出栈顶符a,读出下一输入符d

#lBA'd

l#由A'→ε仅弹出栈顶符号A'

#lBd

l#弹出栈顶符,将B→dB'右部反序压栈

#lB'dd

l#匹配,弹出栈顶符d,读出下一输入符l

#lB'l

#由B'→ε仅弹出栈顶符号B'

#ll

#匹配,弹出栈顶符l,读出下一输入符#

##

匹配,分析成功内容回顾预测分析

1.下推堆栈2.总控程序3.预测分析表总控程序①x=a=#,成功②x=a#,匹配③xVN,查表6363基本思想是:当文法中某一非终结符呈现在栈顶时,根据当前的输入符号,分析表应指示要用该非终结符里的哪一条规则取匹配输入串(即进行下一步最左推导)

根据这个思想,我们不难把构造分析表算法构造出来!终结符号非终结符号分析表M[A，a]的构造分析表M[A，a]的构造构造FIRST()和FOLLOW(A)构造分析表M[A，a]二.FIRST集和FOLLOW集1.FIRST集定义:假定是文法任一符号串,对α(VTVN)*,有

FIRST（α）＝{a|αa...,aVT}.

若αε,则εFIRST(α）**即FIRST()是的所有可能推出的首终结符或可能的ε组成的集合。*

FIRST集的构造方法对每个文法符号XVTVN，连续使用入下规则，直到每个FIRST(X)不再增大XVT,则FIRST(X)={X};XVN,分三种情形:1.Xa…2.XY…3.XY1Y2…Yk1.若有X→a…,把a加入FIRST(X);

若有X→ε,把ε加入FIRST(X);2.若有X→Y…,Y∈VN,把FIRST(Y)的

所有非ε元素都加入FIRST(X);3.若有X→Y1Y2…Yk,而Y1~Yi−1都有ε,

则把FIRST(Yj)(j=1,2,…,i)的所有非

ε元素都加入FIRST(X);

特别地,若Y1～Yk均有ε产生式,

则把ε也加入到FIRST(X)。

首先把FIRST(X1)-{}加入FIRST()；若对任何1ji-1,FIRST(Xi),则把FIRST(Xi)加入FIRST()中；如果所有FIRST(Xi)均包含，则把加入FIRST()中=X1X2…XnXiV,i=1,2,3,...n例:G(E)E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│iEE’TT’FFIRST(i(i(i+*

FIRST(E')={+,ε};FIRST(T')={*,ε};FIRST(F)＝{(,i};

由T→F…知,把FIRST(F)的所有非ε元素加入FIRST(T),故FIRST(T)={(,i};

由E→T…知,把FIRST(T)的所有非ε元素加入FIRST(E),故FIRST(E)={(,i}FIRST(Y1)={y1,}FIRST(Y2)={y2,}FIRST(A)={a}FIRST(X)={y1,y2,a}例子：XY1Y2AY1y1│Y2y2│Aa

定义:对AVN,有

FOLLOW(A)={a│S...Aa...,aVT}

若S...A,则规定#FOLLOW(A),其中S为开始符号.**2.Follow集FOLLOW(A)是所有句型中出现在紧随A之后的终结符或#。#FOLLOW(S)A→αBβ:将FIRST()-{}加入FOLLOW(B)A→αB:将FOLLOW(A)加入FOLLOW(B)A→αBβ且βε:将FOLLOW(A)加入FOLLOW(B)*求法注意:求FOLLOW(B)实际上是考察B在产生式右端的每一次出现

FOLLOW(X)={#}FOLLOW(Y1)={y2,a}FOLLOW(Y2)={a}FOLLOW(A)={#}例子：XY1Y2AY1y1│Y2y2│Aa

例:G(E)E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│iEE’TT’FFIRST(i(i(i+*

试构造文法G[E]的FOLLOW集。解:1)FOLLOW(E)={#};2)由E→TE'知,FIRST(E')\{ε}属于FOLLOW(T),

即FOLLOW(T)＝{+};{由E'→+TE'|ε,FIRST(E')\{ε}属于…}

由T→FT'知,FIRST(T')\{ε}属于FOLLOW(F),

即FOLLOW(F)＝{*};{由T'→*FT'|ε知,FIRST(T')\{ε}属于…}

由F→(E)|i知,FIRST(')')属于FOLLOW(E),

即FOLLOW(E)＝{),#};3)由E→TE'知,FOLLOW(E)属于FOLLOW(E'), 即FOLLOW(E')＝{),#};

由E→TE'且E'→ε知, FOLLOW(E)属于FOLLOW(T),

即FOLLOW(T)＝{+,),#};

{由E'→+TE'知,FOLLOW(E')属于FOLLOW(E')}{由E'→+TE'且E'→ε知,FOLLOW(E')属于FOLLOW(T)}

由T→FT'知,FOLLOW(T)属于FOLLOW(T')，

即FOLLOW(T')＝{+,),#};

由T→FT'且T'→ε知,FOLLOW(T)属于FOLLOW(F),

即FOLLOW(F)＝{*,+,),#}；

{由T'→*FT'

知,FOLLOW(T')属于FOLLOW(T')}{由T'→*FT'且T'→ε知,FOLLOW(T')属于FOLLOW(F)}{考虑F→(E)|i}例:G(E)E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│iEE’TT’FFIRSTFOLLOW(i(i(i+*)#)#+)#+)#*+)#

练习:S->ABA->Ab|εB->a|ε试求出S、A、B的FIRST和FOLLOW集。SABFIRSTFOLLOWaba

b#b##练习:G=（{a,b,c,（,）},{S,A,B},S,P）,P为S->bAbA->(B|a|εB->Aa)|Ac)设上下文无关文法G的产生式形如A→1|2|…|n,当G满足下述条件时则称为LL(1)文法:①FIRST(i)FIRST(j)=Φ,ij,i,j=1,2,...,n②若i,则FIRST(j)FOLLOW(A)=Φ,ji，j=1,2,...,n

于是,在自顶向下分析时,可根据当前输入符号a选择aFIRST(i)的A→i。*三.LL(1)文法

在自上而下分析时，若当前输入字符为a,分析栈待匹配的非终结符为A，A→1|2|…|n，则当:aFIRST(i)，或若i,aFOLLOW(A)则A→i便是惟一与a匹配的产生式，即LL（1）文法中的两个条件保证了自上而下匹配的唯