大三下課程編譯原理

12式語言與自動機第3章詞法分析 第4章語法分析 ——自上而下分析第5章語法分析 ——自下而上分析6中間代碼生成78碼優(yōu)化Ch4Ch4語法第4章語法分析(Syntax——自上而下分析LL(1)分析法與LL(1)分析2Ch4Ch4語法分 語法分析程序綜語法分析綜上而下分析下而上3Ch4語法分 語法分析程序綜

語法分析程序的功源程序

語法分析 yzer

源程源程

源程序語法分語法分

分析語義分中語義分中間代碼Ch4Ch4語法分 語法分析程序綜 給給定文法G和字符串(∈VT*)，檢查、判定∈L(G)？即檢查、判定是否是文法G所能產(chǎn)生的合法的句子告和處5源程序串（L1）源語言的文法

Ch4語法分 語法分析程序綜 Ch4語法分 語法分析程序綜 6Ch4Ch4語法分 語法分析程序綜上而下分析下而上7Ch4語法分 語法分析程序綜 語法分析方.非終結符進行替換(推導)，逐步推導出r。式進行推導，逐步使推導結果與r8Ch4Ch4語法分 語法分析程序綜 語法分析方例 設有文法G和輸入rG：S→A→BaA|B→+|–|*| 分析方式1(推導S=>aA=>aBaA=> =>=> => =r9CCh4 分析樹的從左到右葉結點=r，則r∈L(G)S→A→BaA|B→+|–|*|

r10Ch4Ch4語法分 語法分析程序綜上而下分析下而上11Ch4語法分 語法分析程序綜 語法分析方式進行匹配，直到歸約到G的S為止。12Ch4語法分 語法分析程序綜 語法分析方.非終結符進行替換(推導)，逐步推導出r。式進行推導，逐步使推導結果與r匹配13Ch4語法分 語法分析程序綜 語法分析方二.自下而上語法分析式進行匹配，直到歸約到G的S為止。14 G：S→aAA→BaA|B→+|-|*|

SABAABAB上A下Ar *a+aCh4Ch4語法分 語法分析程序綜 語法分析方15 G：S→aAA→BaA|B→+|–|*| 分析方式2(推導r=a*a+a<=<=aBaBaε<=<=aBaA<=aA<=

SAAABAB *a+aABABCh4Ch4語法分 語法分析程序綜 語法分析方16Ch4語法分 4.1語法分析程序綜 語法分析兩大類方自上而下分析法； r(一般、遞歸下降、自下而上分析法rReduceS(一般S-R、OPG、 17Ch4Ch4語法第4章語法分析(Syntax——自上而下分析LL(1)分析法與LL(1)分析18Ch4Ch4語法分析 不確定的自上而下分析19例

S→A→ab

r=Ch4語法分析Ch4語法分析 不確定的自上而下分析法 一般自上而下分析 20S→S→A→ab

a

r=Ch4Ch4語法分析 不確定的自上而下分析法 一般自上而下分析 分析的本質(zhì)是一種帶回溯的自上而下分析,21Ch4Ch4語法分析 不確定的自上而下分析法 一般自上而下分析 I→I0r：按照自按照自上而下分析輸入串r產(chǎn)生分析樹，對終結符的替換使分析休止的延伸，使自析陷入死循環(huán) …22…Ch4Ch4語法分析 不確定的自上而下分析23不確定性的假匹 回G的左遞 無止境的匹提 因

消除G的左遞24一.消除文法的 A +假定關于非終結符P 其中，不以P不分析：P→P不P→PP→P′→假定關于非終結符P 其中，不以P把P的規(guī)則改寫成如下等價的非直接左PPP′→27例 設有簡單表達式文法E→E+E|E*E|（E）|對G(E)消除二義性后，得到文法G'(E)E→E+T|T→T*F|F→(E)|E→TE′EE→TE′E′→+TE′|εT→FT′T′→*FT′|εF→(E)|i假定關于非終結符PP→P1|P2|…|Pn|β1|β2|…其中，每個i不等于 ,…,βn不以PPPP′→1P′|2P′|…|29例 設有文法I→I0|Ia|Ib|a|對左遞歸文法G改寫后的文法G′II→aI'|bII'→0I'|aI'|bI'30間接左遞歸的消除：A→Ba|B→Cb|C→Ac|經(jīng)若干步推導替換，有A=>Ba=>Cba=>B=>Cb=>Acb=>C=>Ac=>Bac=>31用消除直接左遞歸的方法改寫P+>P的推導）且不含以ε為右部的產(chǎn)生式32算法4.1除文法左遞給定文法①對文法Ｇ的所有非終結符按任一種順序排列例如A1，A2，…，An。消除A1中的直接左遞②for(i=1;i=n;i++{for(j=1;j=i-1;j++{Ai其中Aj→δ1│δ2│……│δk是關于Aj的全部規(guī)}消除Ai規(guī)則中的直接左遞歸③簡34 令文法G(A)的非終結符排序為C，B，A對于C，不存在直接左遞歸，把C代入BB的規(guī)G(A):A→Ba|B→Cb|C→Ac|代換后的B不含直接左遞歸，將其代入的規(guī)則變A→A存在直接左遞歸，消除A的直接左遞A→dAbaA′|caA′|bBA′A′→cbaA′|ε35文法G(A)改寫A→dAbaA′|caA′|bBA′A′→cbaA′|εBCC→Ac|無左遞歸的等價文法G′(A)為A→dAbaA′|A′→B36 對于B，候選式中不包含A不存在直接G(A):A→Ba|B→Cb|C→Ac|將A，B帶入C，代換后的C的規(guī)則變?yōu)镃→C→C存在直接左遞歸，消除C的直接左遞C→cacC′|bBcC′|dAC′C′→bacC′|ε37→Ba|→Cb|C→cacC′|bBcC′|dAC′C′→bacC′|ε二.消除P→1|2|…| 當前前輸入ai匹配成功則替換，否則選2，依此類39定義FIRST()={a|>a……，a∈VT,則ε∈FIRST()不帶回溯的條件：(充分非必要式，設為： A→1|2|…|n如果它的每個候選式i均不存在i的情況而且FIRST(i)兩兩彼此互不相40式設為：A→1|2|…|滿足不帶回溯則據(jù)當前掃描單詞a，若a∈FIRST(i)其中i是1…n中之一，選取A→進行41計算FIRST(X)(XV)的算法描述為構造FIRST(X)可反復應用如下規(guī)1、若X是終結符,則2、若X是非終結符，且XX1X2Xk是一個產(chǎn)生式②若對于某個i，aFIRST(Xi)且X1X2Xi－1，則③若對于所有的j＝1，2，，k，F(xiàn)IRST(Xj)將加到FIRST(X)42計算FIRST()(V*)的算法描設=X1X2Xk1、FIRST(X1)中的所有終結符號加到FIRST()2、若對于某個i，aFIRST(Xi)且X1X2Xi－1，43計算FIRST(X)(XV)的算法描述為構造FIRST(X)可反復應用如下規(guī)1、若X是終結符,則、X的、X的FIRST為其所有候選式的FIRST集合的并集44例

設有文法S→Ap|A→a|B→b|對 FIRST(Ap∩對 FIRST(a∩對 FIRST(b∩45若給出r=cap,則有S

r:capr:

S→Ap|A→a|B→b| r:46對非終結符A的多個候選式的FIRST(i)的相互兩若有文法A→δβ1|δβ2|…|彼此交集≠Φ，一般是因為i中有公共左因子若有文法A→δβ1|δβ2|…|δ(β1|β2|…|可可以使用下面規(guī)則改寫文法Ｇ為AA′→β1|β2|…|47若文法G2(1|2|…|mA→11|12|…|1n|22(1|2|…|m1(1|2|…|n A→δ1A'A'→β1|β2|…|βn48Ch4Ch4第4章語法分析(Syntax——自上而下分析LL(1)分析法與LL(1)分析49ch4語法分 一個VN的分析程序。(將一個非終結符的文 遞歸下降分析器對文法要求：LL(1對文法的每個非終結符號，都根據(jù)其產(chǎn)50ch4ch4語法分 例 設有文法G(E)E→TE′E′→+TE′|εT→FT′T′→*FT′|εF→(E)|i文法G(Ｅ)的遞歸51E()主程{E()主程{T;E′({if{n++;T;E’;}F({if(c=‘i’)elseif(c=‘(’{n++;if(c=‘)’)elseelseT→*FT|εF→(E)|ich44.3TT({F;T′({if(c=‘*’){n++;F;T′}cch44.3T→FTT→*FT|εF→(E)|iTTFT

查查ii+i*ipoppopi+i+i*iT匹配E',Push匹配E',Pushcch44.3Ti+Ti+i*i查TTFpop匹配匹配i,popTi+i*iT

i+i*i分析完成匹配T',Push匹配T',PushE→+TE|εT→FTT→*FT|εF→(E)|iTFpopT,匹配i,popT,匹配i,popT

54cch44.3r1=（+iTPushPushT

查查E→+TE|εT→FTT→*FT|εF→(E)|i（+iE'T'E'T'匹配popF,Push)E)TpopE,PushE'TT55ch4語法分 E‘T’）E'（+i查E‘T’)E'T'（+iE→+TE T→FTT→*FT F→(E)|（+i分析完成56—狀態(tài)狀態(tài)圖構造：為文法G的每個建立1個初態(tài)和1個終態(tài)(函數(shù)返回態(tài)為每個產(chǎn)生式Ax1x2xn建立從初態(tài)到終態(tài)的路徑，弧標記為x1，x2…，xn；12**其中12ch4語法分 ch4語法分 E'→+TE'

0

1T 1Tε23ch4ch4語法分 開始處于圖的初態(tài)t在某狀態(tài)tT S TSAt當前輸入符號為a，分析器掃描指針+1，進入tSAt tttS S若直接進入t狀態(tài)，掃描指針不變5812通過狀態(tài)圖的化簡來化簡遞歸下降分12例如，E 1Tε23E 1Tε23T

0

入E′的FA的開 1T2ε3ch4ch4語法分 0 0 1359ch4ch4語法分 0T10T1+2 3E′代入E+0T1ε2*3F4ε5F：(7E8)9iEE→E'→+TE'|εT→FT′T'→F→（E）|60Ch4Ch4第4章語法分析(Syntax——自上而下分析LL(1)分析法與LL(1)分析61ch4ch4語法分析4.4LL(1)分析法與LL(1)分析LL(1)分析法與LL(1)LL(1)LL(1)關于LL(1)62ch4語法分析4.4LL(1)分析法與LL(1)分析器4.4.1LL(1)分析器的結LL

預測在分析中最多向前看1個輸入字掃描模式：自 63ch4ch4語法分析4.4LL(1)分析法與LL(1)分析器4.4.1LL(1)分析器的結LL(1)分析器的邏#X總控（分#X總控（分析表#…輸…總控 64ch4ch4語法分析4.4LL(1)分析法與LL(1)分析器4.4.1LL(1)分析器的結分析#S句子界#S句子界符(棧底標志文法開始符65文法的一條產(chǎn)生式規(guī)則(候選式唯一出錯（空白

文法的 M(A1,a1) …文法

預測分析函ch4ch4語法分析4.4LL(1)分析法與LL(1)4.4.1LL(1)分析器66算法#S初始化工作#S

pa1a2…anch4ch4語法分析4.4LL(1)分析法與LL(1)4.4.1LL(1)分析器的結①X＝ai＝“?！保硎痉治龀晒?，停止分析67ch4語法分析4.4LL(1)分析法與LL(1)4.4.1LL(1)分析器的結若Ｘ∈ＶN，則查分析表。此時對Ｍ(X,①若Ｍ(Ｘ,ai)中為一個產(chǎn)生式規(guī)則，則將X從 出)。②若Ｍ(Ｘ,ai)中為空白，表示出錯，可法出錯處理子程序68例 設有文法E’→+TE’│ε

ch4ch4語法分析4.4LL(1)分析法與LL(1)分析器4.4.1LL(1)分析器的結69 文法G(E)的LL(1)分析+*()#ETFF→返 返回 第701#E步 分析1#E#E#E’T’#E#Eid#E#E#E#E#E’T’#E#E56789

idid

ch4ch4語法分析4.4LL(1)分析法與LL(1)分析器4.4.1LL(1)分析器的結表下71表下ch4ch4語法分析4.4LL(1)分析法與LL(1)分析器4.4.1LL(1)分析器的結表表#E #E #E #E T##分析成#E##分析成72ch4ch4語法分析4.4LL(1)分析法與LL(1)分析LL(1)分析法與LL(1)LL(1)LL(1)關于LL(1)73LL(1)分析LL(1)分析器構造關 分析表的構分析表的構造關 預測函74第一種情式形如A→且沒=>ε的情況，則產(chǎn)生對 則A若a∈FIRST()，那么要匹配輸入單詞a時，Ｍ(A，a)={A→75Ｍ(A，a)前例

設有文法S→Ap|A→a|B→b|對 FIRST(Ap∩對 FIRST(a對B FIRST(b77S→Ap| A→a|對S：FIRST(Ap)={a,c}對A：FIRST(a)={a}

B→b|對B文法G的LL(1)分析abcdpqSAB若有ε∈FIRST()怎么辦？此時aFIRST()時并不一定78定義FOLLOW(A)＝｛a|S>…Aa…，a∈VTS*>…A，句型中，能夠緊跟著A之后的一切終結符“?！?9構造FOLLOW集方算法對文法的開始符S，令?！蔉OLLOW(S)②若文法G中有形如A→Bβ的規(guī)則，且β≠ε，③若G中有形ABABβ的規(guī)則80例 設有文法G[S]為S→AB|bCB→ε|aDD→aS|

A→ε|bC→AD|b據(jù)算法4.3計算文法G[S]所有VN的FOLLOW#由規(guī)則S→AB|bCFOLLOW(S)FOLLOW(B)；FOLLOW(S)FOLLOW(A)；FOLLOW(S)FOLLOW(C)；FIRST(B){}FOLLOW(A)

FOLLOW(B)={#}；81

FOLLOW(B)={#}；

S→AB|bCA→ε|bFOLLOW(B)

B→ε|aDC→AD|bD→aS|由規(guī)則C→AD|b得

FOLLOW(B)FOLLOW(C)FOLLOW(D)，F(xiàn)IRST(D){}FOLLOW(A), FOLLOW(B)={#}；FOLLOW(A)={#，a，c}，F(xiàn)OLLOW(C)＝{#}FOLLOW(D)所有的FOLLOW集合無變化 S→AB|A→ε|FOLLOW(B)B→ε|C→AD| |所以上面的即為最后求得的FOLLOW832.構造FOLLOW集方法二——W和。⑵從開始符號S的FOLLOW(S)結點到”#”⑶如果文法中有產(chǎn)生式A→BX,當X∈VN時，則從結點到FIRST(X)結點連一條弧，當X∈VT時，則與X相連⑷如果文法中有產(chǎn)生式A→Bβ,且>,則從FOLLOW(B)結點FOLLOW(A)結點連一條箭則與X1相連;當X1∈VN時,從FIRST(A)到FIRST(X1)結點連一條箭)84

#

S→AB|bCA→ε|bB→ε|aDC→AD|b |c

85 所以分析表的構造A→|且和均不推出ε，則可產(chǎn)生LL(1)分析表的A行對a∈FIRST()，a列即Ｍ(A，a)={A→86設對文法G求出FIRST和FOLLOW，對A1| 如果滿則惟一候選為若a∈FIRST(1)M(AaA1；若b∈FIRST(2)或b∈FOLLOW(A)，則置M(AbA2

87分=>…Aa…，a∈ＶT｝b∈FOLLOW(A)則必有=>…Ab…(b∈ＶT S=*>…Ab…由于對文法規(guī)則存在A→2，A自動獲得匹 中才可能從棧中退掉A。88算法 LL(1)分析表構{ifa∈FIRSTγi)置Ｍ(AaA→γi ε∈FIRST(γifor置Ｍ(AbA→γi}89前例 設有文法E’→+TE’│εF→(E)│i對E：FIRST(TE(，i對T：FIRST(FT’(，i對F：FIRST((E))={( FIRST(i)={i∩=90 對E’：FIRST(TEE→E'→FIRST(ε)={εFOLLOW(E’)={#,)T→T'→ F→（E）|滿足：+}ε}∪對T’FIRST(*FT’*FIRST(ε)={ε}FOLLOW(T’)={#,),+}滿足：{*}ε}∪91 E'→+TE'|ε:FIRST(+TE’)={+}FIRST(ε)={ε}FOLLOW(E’)={#,)T→FT’:FIRST(FTT'→*FT'|ε:FIRST(*FT’)={*}FIRST(ε)={ε}FOLLOW(T’)={#,),+F→(E)|i FIRST(i文法G(E)的LL(1)分析+*()i#ETFF→92ch4ch44.3r1=（+iE→+TEE→+TE|εT→FTT→*FT|εF→(E)|i（+iE'T )E'T'PushTTE'T'E'T'匹配popF,Push)E)TpopE)TpopE,PushE'popT,PushTT）T93#TF##TF#E#T#T)E（#T)Ech4語法分 文法G(E)的LL(1)分析+*()i#ETFF→r1=（+i 94例 設有文法S→iCtSS’│aS’→eS│εＣ→對S：FIRST(iCtSSiFIRST(a)={a對 FIRST(eS)={e對CFIRST(bbFIRST(ε)={ε} FIRST(eS)∩(FIRST(ε)對CFIRST(bb95S→iCtSS’│a:FIRST(iCtSS’)={i} FIRST(a)={a}S’→eS│ε:FIRST(eS)={e} Ｃ→b: FIRST(b)=文法G(S)的LL(1abeit#abeit#SS S’→C C多重

96ch4ch4語法分析4.4LL(1)分析法與LL(1)LL(1)分析法與LL(1)LL(1)LL(