六.例1:L1={wcw|w∈L((a|b)*)} 例2:L2={ dm|n≥0和m≥0}非上下文無關(guān)語言例3:L3={ |n≥0} L1’={wcwR|w∈L((a|b)*wR文法:S→aSa|bSb|cL2’={anbmcmdn|n≥1m≥1}S→aSd|A→bAc|bcL3’={anbn|n≥1}文法S→aSb|0型文法G=(VT,VN,S,P)是文法,并且它的每個產(chǎn)生式形如:β∈(VN∪VT)*.G0型文法,也叫短語文法.1﹑2﹑3型文法0型文法加上以下第i條限制,就可以得到i型文法G的任何產(chǎn)生式α→β都滿足|α|≤|β|,S→ε例外G的任何產(chǎn)生式形如A→βA∈VN,G的任何產(chǎn)生式形如A→aB或A→aA,B∈VN,a∈VT1型文法叫上下文有關(guān)文法,2型文法叫上下文無關(guān)文法,3例: *aaabbbccc見黑板§3.4自上而下分析(Top-Down思想:自上而下分析對任何輸入串,試圖用一切可能的辦例子:設(shè)有文法A→ab|cad文法不能有左遞歸(left(predictive**FIRST(α)={a|αa…,a∈VT若αε,則ε∈FIRST(α).**A的任意兩個產(chǎn)生式αi和αj,FIRST(αi)∩FIRST(αj)=φ,那么當要求用A匹配輸入串時,A遞歸下降分析程序(Recursive-descent|array[simple]oftype|numdotdotprocedurematch(t:token);iflookahead=tthenlookahead:=nexttokenelseerrorproceduretype;iflookaheadisin{integer,char,num}thenelseiflookahead=‘↑’thenmatch(‘↑’);match(id)elseiflookahead=arraythenmatch(array);simple;match(‘)’);match(of);type;elseproceduresimple;iflookahead=integerthenelseiflookahead=charthenelseiflookahead=numthenmatch(dotdot);match(num);else(NonrecursivePredictive組成:程序根據(jù)當前棧頂?shù)姆朮aX=a≠$,X,推進輸入指針,指 如果X是非終結(jié)符,程序分析表M.若M[X,a]是XYkYk-1…Y1X,Y1在棧頂.M[X,a]指示出parsingtable*預(yù)測分析程序關(guān)鍵是構(gòu)造分析表.構(gòu)造分析表需要兩個集*FIRST(α)={a|αa…,***若αε,則ε∈FIRST(α)FOLLOW(A)={a|S…Aa…,a∈VT}**如果A可以是某個句型的最右符號,那么計算所有文法符號X的FIRST(X),直到每個FIRST集合不X是非終結(jié)符,X→Y1Y2…Yk是產(chǎn)生式,iaFIRST(Yi),并且ε*…,FIRST(Yi-1),Y1Y2…Yi-1ε,aFIRST(X).*果對所有的j=1,2,…,k,有ε屬于FIRST(Yj),那么把ε加入*計算串X1X2…Xn的FIRST集.若對某個ia∈FIRST(Xi),并且εFIRST(X1),FIRST(X2),…,FIRST(Xi-1),即*

ε,則把a加入FIRST(X1X2…Xn).AFOLLOW(A).應(yīng)用下面規(guī)則,直FOLLOW集不再增大為止.把$FOLLOW(S),S是開始符號,$是輸入結(jié)束如果有產(chǎn)生式A→αBβ,那么除ε外,把FIRST(β)中的FOLLOW(B).A→αB,A→αBβ且FIRST(β)含ε,那么,FOLLOW(A)中的一切元素加入F→(E)|id計算FIRSTFOLLOW(見書P222)predictiveparsingG;如果εFIRST(α)中,FOLLOW(A)b(包括$),A→αM[A,b].M中其它沒有定義的條目是F→(E)|idFIRST,FOLLOW預(yù)測分析程序或遞歸下降分析程序可以不需要回溯地分LL(1)文法.*L表示從左到右掃描輸入,L表示產(chǎn)生最左推導(dǎo)“1”表示每一步向前看一個輸入符號來作出分析換句話說,預(yù)測分析表沒有多重定義條目的文法叫做文法GLL(1)G沒有終結(jié)符a能使α和β推出的串都以a開始,FIRST(α)∩FIRS