第五章 LL1文法及其分析程序

第5章自顶向下语法分析方法主要内容：自上而下的语法分析预测分析程序递归下降子程序表驱动的预测分析程序LL(1)分析程序的生成LL(1)文法FIRST和FOLLOW集定义和计算非LL(1)文法的改造2021/5/91

5.1确定的自顶向下语法分析思想1.语法分析概念2.自上而下的语法分析的一般过程3.自上而下的语法分析面临的问题4.开始符号集5.后跟符号集6.select集7.LL(1)文法2021/5/921。语法分析在语言的编译实现中，把句子分析的过程称为语法分析，即完成这个任务的程序称为语法分析程序或称为识别程序。分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。2021/5/93（上下文无关文法）句型的分析句型分析就是识别一个符号串是否为某文法的句型的过程，或者说是某个推导的构造过程。2021/5/94语法树－推导的几何表示句型aabbaa的可能推导序列和语法树

例:G[S]: S→aAS A→SbA A→SS S→a A→baS

aASSbAa

a

b

aS

aAS

aAa

aSbAa

aSbbaa

aabbaaSaASaSbASaabASaabbaS

aabbaaSaASaSbAS

aSbAa

aabAa

aabbaa2021/5/95分析算法分类分析算法可分为：自上而下分析法：

从文法的开始符号出发，寻找与输入符号串匹配的推导，或者说，为输入串寻找一个最左推导。自下而上分析法：

从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。

2021/5/96两种方法反映了语法树的两种构造过程。自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树2021/5/972。自上而下分析方法

对任何输入串，试图用一切可能的办法，从文法开始符号着手，自上而下地为输入串构造一棵语法树，或者说，为输入串寻找一个最左推导。本质上是一个试探过程，反复使用不同地产生式谋求匹配输入串的过程。

2021/5/98自上而下的语法分析的一般过程例：文法G：S→cAd

A→ab

A→a

识别输入串w=cabd是否为该文法的句子 S S S

c A d

c A d

a

b推导过程：S

cAd

cAd

cabd2021/5/99

自上而下的语法分析的一般过程

(1)S→cAd(2)A→ab(3)A→a

识别输入串w=cad是否为

该文法的句子1.S

cAd2.后选择(2)扩展A，得到推导S

cAd

cabd这时

w的第二个符号可以与叶子结点a得以匹配，但第三个符号d却不能与下一叶子结点b匹配怎么办？-查看A有无另一个选择，有！回溯，把A为根的子树剪掉，扫描过的输入串中的a吐出来,再试探用产生式（3）构造推导S

cAd

cad识别输入串w=caa的过程：1.S

cAd2.选择(2)扩展A，得到推导S

cAd

cabd3.回溯回到推导S

cAd4.选择(3)扩展A，得到推导S

cAd

cad5.A没有选择了！回溯到推导S

cAd6.再回溯S有无另一个选择？没有！

宣告分析失败。（请思考若有

(4)S→cB

(5)B→aa会怎样?

）2021/5/910自上而下分析的进一步讨论自上而下分析也称面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的符号串完全匹配的句子，若能构造出推导则表明输入串是给定文法的句子，否则表明该输入不是给定文法的句子。自上而下分析对文法的要求－文法不能含有左递归规则。自上而下分析又可分为确定的和不确定的两种

不确定的分析方法称为带回溯的分析方法，这种方法实际上是一种穷举的试探方法

确定的分析方法需对文法有一定的限制2021/5/9113。自上而下的语法分析面临的问题-实现考虑回溯文法的左递归性

S→Sa2021/5/912自上而下分析对文法的要求例文法G0[S]:(1)S→Sa(2)S→b

分析baa是不是文法的句子按照自上而下的分析思想选用产生式(1)来推导SSa

语法树末端结点最左符号为非终结符，所以选用（1）继续推导SSaSaa

此时语法树末端结点最左符号仍为非终结符，所以选用（1）继续推导SSaSaaSaaa问题——试图用S匹配输入串时，出现：在没有读入任何输入符号的情况下，又得重新要求S去进行新的匹配.无法确定什么时候使用（2）产生式最适当，只能采用带回溯的不确定方法解决。原因——文法含有左递归。2021/5/913回溯的原因例G[S]:S→xAyA→ab｜a

若当前输入串为xay，首先构造的推导S

xAy

匹配进一步推导对A可选择A→ab替换，得S

xAy

xabyxayxaby

匹配xa都已匹配，当前面临输入符为y与b不能匹配，所以将输入串指针退回到a，对A的替换重新选用下一个产生式A→a进行试探，S

xAy

xay输入串中当前符a得到匹配，指针向前移动到y，与语法树中y匹配，匹配成功。由于相同左部的产生式的右部开始符号相同而引起回溯。2021/5/914在自上而下的分析方法中如何选择使用哪个产生式进行推导？ 假定要被代换的最左非终结符号是B，且有n条规则：B→A1|A2|…|An，那么如何确定用哪个右部去替代B？-------什么信息用于Parser做正确选择?(输入串,文法特点)2021/5/915可预测的试探推导过程例文法G’[S]:S→

pA|qBA→cAd|a

B→dB|c

识别输入串w=pccadd是否是G1[S]的句子可预测的试探推导过程：S

pApcAd

pccAdd

pccadd

试探成功。2021/5/9164。开始符号集---FIRST集设G=(VT,VN,P，S)是上下文无关文法FIRST（）={a|=>*a,a∈VT,、∈V*}

若

=>*ε则规定ε∈FRIST（）2021/5/917FOLLOW（A）={aS=>*A且a∈

FRIST（），∈V*，

∈V+}

若S=>*

uA,且

=>*

ε，则#∈FOLLOW(A)5。后跟符号集--FOLLOW集2021/5/9186。SELECT集给定上下文无关文法的产生式Ａ

αA∈VN,∈V*若α≠>*

，则SELECT(Ａ

α)=FIRST(α)若α=>*

,则SELECT(Ａ

α)=(FIRST(α)-{})∪FOLLOW(A)2021/5/919

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

α

β，下面的条件成立：

SELECT(Ａ

α)∩SELECT(Ａ

β)=Ф

其中α和β不能同时=>*

ε

2021/5/920书中例子2021/5/921

5.2LL（1）文法的判别判别步骤：1）。求出能推出ε的非终结符

2021/5/9222）。计算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(Yi)中的所有元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj,

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

,则把

加到FRIST(X)中.

2021/5/9233）。计算FOLLOW集1.对于文法的开始符号S,置#于FOLLOW(S)中;2.若Ａ

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

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

αB是一个产生式,或Ａ

αBβ是

一个产生式而β=>*

(即

FIRST(β)），

则把FOLLOW（A）加至FOLLOW（B）中．2021/5/924G[E]:(1)E–>TE’(2)E’–>+TE’(3)E’–>

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

(7)F–>(E)(8)F–>a·各非终结符的FIRST集合如下：FIRST(E)=｛(,a｝FIRST(E′)=｛+,ε｝FIRST(T)=｛(,a｝FIRST(T′)=｛*,ε｝FIRST(F)=｛(,a｝·各非终结符的FOLLOW集合为：FOLLOW(E)=｛),＃｝FOLLOW(E′)=｛)，＃｝FOLLOW(T)=｛＋，)，＃｝FOLLOW(T′)=｛＋,)，#}FOLLOW(F)=｛*,＋，),#}

2021/5/9254）。计算SELECT集计算产生式的SELECT集2021/5/926G[E]:(1)E–>TE’(2)E’–>+TE’(3)E’–>

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

(7)F–>(E)(8)F–>aE’–>+TE’|

FIRST(+TE’)=｛+｝

FOLLOW(E′)=｛)，＃｝T’–>*FT’|

FIRST(*FT’)=｛*｝

FOLLOW(T′)=｛+,)，＃｝F–>(E)|aFIRST((E))=｛(｝

FIRST(a)=｛a｝所以G[E]是LL（1）的2021/5/9275）。判断文法是否LL（1）文法若文法所有具有相同左部产生式的SELECT集两两不相交，则文法是LL(1)文法。2021/5/928

LL(1)文法的性质：

LL(1)文法是无二义的

LL(1)文法不含左递归2021/5/9295.3某些非LL(1)文法的改造1。提取左公共因子提左公因子：将产生式Ａ

β|

变换为：Ａ

BBβ|

2021/5/930一般形式：Ａ

β1|

β2|…|

βn提取左公共因子后：

AA’A’β1|β2|…|βn2021/5/9312。消除左递归左递归－关于非终结符P的规则直接左递归：

P→Pα|βα、β∈V*且α、β不以P开头一般左递归：P=>*Pα

例：

S→AaA→Sb…2021/5/932消除文法中左递归规则1）消除直接左递归：形如：P→Pα|βα非，α，β不以P打头

改写为：P→

βQ

Q

→

αQ|

其中Q为新增加的非终结符2021/5/933消除文法中左递归规则举例例:E→E+T|TT

→T*F|FF

→(E)|a

G[E]:(1)E→TE’(2)E’→+TE’(3)E’→

(4)T→FT’(5)T’→*FT’(6)T’→

(7)F→(E)(8)F→a2021/5/934消除一般左递归对文法要求:

1.无回路(A(=>+(A)2.无空产生式2）消除一般左递归的方法：（1）

.以某种顺序将文法非终结符排列A1,A2…An（2）

fori:=1tondobegin

forj:=1toi-1do

用Aj-->

1|2…|k

替代形如Ai-->Ajr的规则,

其中Aj-->

1|

2…|k是关于Aj的全部产生式;

消除Ai规则的直接左递归;

end;（3）化简由（2）得到的文法:去掉无用产生式2021/5/935例P902021/5/936消除左递归和提左公因子并不一定都能将非LL(1)文法改造为LL(1)的S→ifCtS|

ifCtSeSC→b提左因子

S→ifCtSAA→eS|

First集Follow集Sif#,eAe,

#,eCbtSelect(A→eS)∩Select(A→

)={e}∩{#,e}≠

Φ改造后文法不是LL(1)文法2021/5/9375.5确定的自顶向下分析方法特征——根据下一个(几个）输入符号为当前要处理的非终结符选择产生式要求——文法是LL(1)的第一个L从左到右扫描输入串第二个L生成的是最左推导

1向前看一个输入符号（lookahead)2021/5/938无回溯的自顶向下分析程序预测分析程序的实现技术

1.递归（下降）子程序

2.表驱动分析程序2021/5/939例：递归下降子程序ParseFunction()BNF（Backus-NaurForm）描述program–>function_listfunction_list–>functionfunction_list|

function–>FUNCidentifier(parameter_list)statement…voidParseFunction(){MatchToken(T_FUNC);ParseIdentifier();MatchToken(T_LPAREN);ParseParameterList();MatchToken(T_RPAREN);ParseStatement();}2021/5/940例：递归下降子程序ParseFunction()（续）voidMatchToken(intexpected){if(lookahead!=expected){printf("syntaxerror\n");exit(0);}else//ifmatch,consumetokenandmoveonlookahead=yylex();//读入一个单词}2021/5/941预测分析程序的实现

表驱动预测分析程序模型Input#总控程序预测分析表stack2021/5/942预测分析表构造算法1.对文法G的每个产生式Ａ

执行第二步

和第三步；2.对每个终结符a

FIRST(

)，把Ａ

加

至

[A,a]中，3.若

FIRST(

)，则对任何bFOLLOW(A)

把Ａ

加至

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

[A,a]标上“出错标志”。可以证明，一个文法G的预测分析表不含多重入口，当且仅当该文法是LL(1)的2021/5/943

例：表驱动予测分析程序G[E]:(1)E–>TE’(2)E’–>+TE’(3)E’–>

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

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

用预测分析表表示状态转换。2021/5/944

a+*()#E(1)(1)E’(2)(3)(3)T(4)(4)T’(6)(5)(6)(6)F(8)(7)G[E]:(1)E–>TE’(2)E’–>+TE’(3)E’–>

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

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

预测分析表2021/5/945表驱动预测分析程序分析算法

首先把’#‘然后把文法开始符号推入栈；把第一个输入符号读进b;

FLAG：=TRUE；

WHILEFLAGDOBEGIN

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

IFX

VtTHENIFX=bTHEN

把下一个输入符号读进bELSEERRORELSEIFX=‘#’THENIFb=‘#’THENFLAG:=FALSEELSEERRORELSEIF

[X,b]={X–>

X1X2..XK}THEN把XK，XK-1,..,X1一一推进栈ELSEERRORENDOFWHILE;STOP/*分析成功，过程完毕*／2021/5/946分析输入串#a+a#的步骤栈内容栈顶符号当前输入余留串M[X,b]1#EEa+a#E–>

TE’2#E’TTa+a#T–>

FT’3#E’T’FFa+a#F–>

a4#E’T’aaa+a#5#E’T’T’+a#T’–>

6#E’E’+a#E’–>

+TE’7#E’T+++a#8#E’TTa#T–>

FT’9#E’T’FFa#F–>

a10#E’T’aaa#11#E’T’T’#T’–>

12#E’E’#E’–>

13###2021/5/947LL(1)分析中的一种错误处理办法发现错误1栈顶的终结符与当前输入符不匹配2非终结符A于栈顶，面临的输入符为a，但分析表M的M[A,a]为空“应急”恢复策略跳过输入串中的一些符号直至遇到“同步符号”为止。同步符号的选择1把FOLLOW(A)中的所有符号作为A的同步符号。跳过输入串中的一些符号直至遇到这些“同步符号”，把A从栈中弹出，可使分析继续2把FIRST(A)中的符号加到A的同步符号集，当FIRST(A)中的符号在输入中出现时，可根据A恢复分析2021/5/948review---parsingThesyntaxanalysisphaseofacompilerverifiesthatthesequenceoftokensreturnedfromthescannerrepresentvalidsentencesinthegrammaroftheprogramminglanguage.Therearetwomajorparsingapproaches:top-downandbottom-up.Intop-downparsing,youstartwiththestartsymbolandapplytheproductionsuntilyouarriveatthedesiredstring.Inbottom-upparsing,youstartwiththestringandreduceittothestartsymbolbyapplyingtheproductionsbackwards.2021/5/949Inthetop-downparsing,webeginwiththestartsymbolandateachstep,expandoneoftheremainingnonterminalsbyreplacingitwiththerightsideofoneitsproductions.Werepeatuntilonlyterminalsremain.Thetop-downparseprintsaleftmostderivationofthesentence.Abottom-upparseworksinreverse.Webeginwiththesentenceofterminalsandeachstepappliesaproductioninreverse,replacingasubstringthatmatchestherightsidewiththenonterminalontheleft.Wecontinueuntilwehavesubstitutedourwaybacktothestartsymbol.Ifyoureadfromthebottomtotop,thebottom-upparseprintsoutarightmostderivationofthesentence.2021/5/950

lookaheadsymbol.Thelookaheadsymbolisthenextsymbolcomingupintheinput.backtracking.Basedontheinformationtheparsercurrentlyhasabouttheinput,adecisionismadetogowithoneparticularproduction.Ifthischoiceleadstoadeadend,theparserwouldhavetobacktracktothatdecisionpoint,movingbackwardsthroughtheinput,andstartagainmakingadifferentchoiceandsoonuntiliteitherfoundtheproductionthatwastheappropriateoneorranoutofchoices.2021/5/951predictiveparserandLL(1)grammarPredictiveparserisanon-backtrackingtop-downparser.Apredictiveparserischaracterizedbyitsabilitytochoosetheproductiontoapplysolelyonthebasisofthenextinputsymbolandthecurrentnonterminalbeingprocessed.Toenablethis,thegrammarmusttakeaparticularform.WecallsuchagrammarLL(1).Thefirst“L”meanswescantheinputfromlefttoright;thesecond“L”meanswecreatealeftmostderivation;andthe1meansoneinputsymboloflookahead.2021/5/952recursive-descentThefirsttechniqueforimplementingapredictiveparseriscalledrecursive-descent.Arecursivedescentparserconsistsofseveralsmallfunctions(procedures),oneforeachnonterminalinthegrammar.Asweparseasentence,wecallthefunctions(procedures)thatcorrespondtotheleftsidenonterminaloftheproductionsweareapplying.Iftheseproductionsarerecursive,weendupcallingthefunctionsrecursively.2021/5/953Table-drivenLL(1)parsingInarecursive-descentparser,theproductioninformationisembeddedintheindividualparsefunctionsforeachnonterminalandtherun-timeexecutionstackiskeepingtrackofourprogressthroughtheparse.Thereisanothermethodforimplementingapredictiveparserthatusesatabletostorethatproductionalongwithanexplicitstacktokeeptrackofwhereweareintheparse.2021/5/954Howatable-drivenpredictiveparserworksWepushthestartsymbolonthestackandreadthefirstinputtoken.Astheparserworksthroughtheinput,therearethefollowingpossibilitiesforthetopstacksymbolXandtheinputtokennonterminala:1.IfX=aanda=endofinput(#):parserhaltsandparsecompletedsuccessfully2.IfX=aanda!=#:successfulmatch,popXandadvancetonextinputtoken.Thisiscalledamatchaction.3.IfX!=aandXisanonterminal,popXandconsulttableat[X,a]toseewhichproductionapplies,pushrightsideofproductiononstack.Thisiscalledapredictaction.4.Ifnoneoftheprecedingcasesappliesorthetableentryfromstep3isblank,therehasbeenaparseerror2021/5/955Thefirstsetofasequenceofsymbolsu,writtenasFirst(u)isthesetofterminalswhichstartallthesequencesofsymbolsderivablefromu.Abitmoreformally,considerallstringsderivablefromubyaleftmostderivation.Ifu=>*v,wherevbeginswithsometerminal,thatterminalisinFirst(u).Ifu=>*

,then

isinFirst(u).2021/5/956ThefollowsetofanonterminalAisthesetofterminalsymbolsthatcanappearimmediatelytotherightofAinavalidsententialform.Abitmoreformally,foreveryvalidsententialformS=>*uAv,wherevbeginswithsometerminal,thatterminalisinFollow(A).2021/5/957CalculatingfirstsetTocalculateFirst(u)whereuhastheformX1X2...Xn,dothefollowing:1.IfX1isaterminal,thenaddX1toFirst(u),otherwiseaddFirst(X1)-

toFirst(u).2.IfX1isanullablenonterminal,i.e.,X1=>*

,addFirst(X2)-

toFirst(u).Furthermore,ifX2canalsogoto

,thenaddFirst(X3)-

andsoon,throughallXnuntilthefirstnonnullableone.3.IfX1X2...Xn=>*

,add

tothefirstset.2021/5/958Calculatingfollowsets.Foreachnonterminalinthegrammar,dothefollowing:1.Place#

inFollow(S)whereSisthestartsymboland#

istheinput'srightendmarker.Theendmarkermightbeendoffile,itmightbenewline,itmightbeaspecialsymbol,whateveristheexpectedendofinputindicationforthisgrammar.Wewilltypicallyuse#astheendmarker.2.ForeveryproductionA–>uBvwhereuandv