下載本文檔
版權(quán)說(shuō)明：本文檔由用戶(hù)提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
3.2
語(yǔ)言和文法
3.2.7
提左因子有左因子的文法
A
1|2提左因子
A
A A
1|2
3.2
語(yǔ)言和文法
例
懸空else的文法
stmt
ifexprthenstmtelsestmt
|ifexprthenstmt |other
3.2
語(yǔ)言和文法
例
懸空else的文法
stmt
ifexprthenstmtelsestmt
|ifexprthenstmt |other
提左因子
stmt
ifexprthenstmt
optional_else_part |other optional_else_partelsestmt |3.2
語(yǔ)言和文法
3.2.8
非上下文無(wú)關(guān)的語(yǔ)言結(jié)構(gòu)L1={wcw|w屬于(a|b)*}
標(biāo)識(shí)符的聲明應(yīng)先于其引用的抽象
L2={anbmcndm|n0,m0}形參個(gè)數(shù)和實(shí)參個(gè)數(shù)應(yīng)該相同的抽象
L3={anbncn|n0}早先排版描述的一個(gè)現(xiàn)象的抽象L1={wcwR|w(a|b)*}
SaSa|bSb|cL2={anbmcmdn|n1,m1}
SaSd|aAd AbAc|bcL
2={anbncmdm|n1，m1} SAB AaAb|ab
BcBd|cdL3
={anbn|n
1}
SaSb|ab3.2
語(yǔ)言和文法L3
={anbn|n
1}
SaSb|abL3是不能用正規(guī)式描述的語(yǔ)言的一個(gè)范例
若存在接受L3的DFAD，狀態(tài)數(shù)為k個(gè)。
設(shè)D讀完,
a,aa,
…,ak
分別到達(dá)狀態(tài)s0,s1,
…,sk至少有兩個(gè)狀態(tài)相同，例如是si和sj，則ajbi屬于L3
si…。。。fs0標(biāo)記為ai的路徑標(biāo)記為bi的路徑標(biāo)記為aj
i的路徑…。。?！?。。3.2
語(yǔ)言和文法
3.2.9
形式語(yǔ)言鳥(niǎo)瞰文法G=(VT
,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外，此時(shí)S不出現(xiàn)在任何產(chǎn)生式的右側(cè)。2型文法：A，AVN,(VN∪VT)*3型文法：AaB或Aa，A,BVN,aVT
短語(yǔ)文法上下文有關(guān)文法上下文無(wú)關(guān)文法正規(guī)式3.2
語(yǔ)言和文法
例：L3＝{anbncn|n1}的上下文有關(guān)文法S
aSBC
S
aBC
CB
BCaB
ab
bB
bb bC
bccC
ccanbncn的推導(dǎo)過(guò)程如下：S*an-1S(BC)n1S+an(BC)n
S+anBnCnS+anbBn1CnS+anbnCn
S+anbncCn-1S+anbncn溫故知新正規(guī)式上下文無(wú)關(guān)文法功能有限四元組定義推導(dǎo)分析樹(shù)圖形化表示最左推導(dǎo)最右推導(dǎo)二義性消除二義性左遞歸消除左遞歸左因子消除左因子A
1|2A+Aa
0型文法1型文法2型文法3型文法3.3
自上而下分析
3.3.1自上而下分析的一般方法例：
文法 S
aCb C
cd|c
為輸入串w=acb建立分析樹(shù)SSSaCbaaCCbbcdc
不能處理左遞歸、復(fù)雜的回溯技術(shù)、回溯導(dǎo)致語(yǔ)義工作推倒重來(lái)、難以報(bào)告出錯(cuò)的確切位置、效率低3.3
自上而下分析
3.3.2LL(1)文法
對(duì)文法加什么樣的限制可以保證沒(méi)有回溯？先定義兩個(gè)和文法有關(guān)的函數(shù)FIRST(
)={a|
*a…,a
VT}
1、特別是，
*時(shí)，規(guī)定
FIRST(
) 2、如果AB,則FIRST(B)應(yīng)該加入FIRST(A) 對(duì)A的任何兩個(gè)不同的選擇i
和j，希望有 FIRST(i)FIRST(j)=但有一個(gè)前提，F(xiàn)IRST(i)和FIRST(j)都不含3.3
自上而下分析
3.3.2LL(1)文法
對(duì)文法加什么樣的限制可以保證沒(méi)有回溯？先定義兩個(gè)和文法有關(guān)的函數(shù)FOLLOW(A)={a|S
*…Aa…，aVT}
1、如果A是某個(gè)句型的最右符號(hào)，那么$屬于FOLLOW(A) 2、如果存在AB或AB且*，則FOLLOW(A)的全體元素要加入FOLLOW(B)3.3
自上而下分析引起回溯的原因：由于相同左部的產(chǎn)生式的右部First集交集不為空而引起回溯例：
文法 S
aCb C
cd|c
為輸入串w=acb建立分析樹(shù)2.由于相同左部VN的右部存在能*的產(chǎn)生式，且該VN的Follow集中含有其他產(chǎn)生式右部First集的元素
例：S->aAS|bA->bAS|
輸入串a(chǎn)b#
（因?yàn)锳*
所以First(bAs)Follow(A)≠
）3.由于文法左遞歸引起回溯
例：S->Sa|b
輸入串baa#3.3
自上而下分析LL(1)文法 任何兩個(gè)產(chǎn)生式A|都滿(mǎn)足下列條件：
FIRST(
)FIRST()=若
*
，那么FIRST()FOLLOW(A)=LL(1)文法有一些明顯的性質(zhì)沒(méi)有公共左因子不是二義的不含左遞歸FIRST集合計(jì)算方法若Xa..，則將終結(jié)符ａ加入FIRST(X)中若X，則將加入FIRST(X)中若XY…，且Y屬于非終結(jié)符，則將FIRST(Y)\{}加入到FIRST(X)中若XY1Y2..YK,且Y1,Y2,..Yi-1都是非終結(jié)符，且Y1,Y2,..Yi-1的FIRST集合中均包含，則將FIRST(Yj)的所有非元素加入到FIRST(X)中，（j=1,2,..i）.特別地，若Y1~YK均有產(chǎn)生式，則將加到FIRST(X)中。FIRST集合及FOLLOW集合的計(jì)算方法SBAABS|dBaA|bS|cFIRST(B)={a,b,c}FIRST(A)={a,b,c,d}FIRST(S)={a,b,c}FOLLOW集合計(jì)算方法對(duì)文法開(kāi)始符號(hào)S,置$于FOLLOW(S)中。若有AB，則將FIRST()\{}加入FOLLOW(B)中。（此處可以為空）若AB或AB,且*（即屬于FIRST()）,則將
FOLLOW(A)加入FOLLOW(B)中（此處可以為空）。FIRST集合及FOLLOW集合的計(jì)算方法SBAABS|dBaA|bS|cFIRST(B)={a,b,c}FIRST(A)={a,b,c,d}FIRST(S)={a,b,c}FOLLOW(S)=?FOLLOW(A)=?FOLLOW(B)=?3.3
自上而下分析例 E
TE E
+TE
| T
FT T
*
FT
| F
(E)|id3.3
自上而下分析例 E
TE E
+TE
| T
FT T
*
FT
| F
(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}3.3
自上而下分析例 E
TE E
+TE
| T
FT T
*
FT
| F
(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E)={+,}3.3
自上而下分析
例 E
TE E
+TE
| T
FT T
*
FT
| F
(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E)={+,}FRIST(T)={*,}3.3
自上而下分析例 E
TE E
+TE
| T
FT T
*
FT
| F
(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E)={+,}FRIST(T)={*,}FOLLOW(E)=FOLLOW(E)={),$}3.3
自上而下分析
例 E
TE E
+TE
| T
FT T
*
FT
| F
(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E)={+,}FRIST(T)={*,}FOLLOW(E)=FOLLOW(E)={),$}FOLLOW(T)=FOLLOW(T)={+,),$}3.3
自上而下分析例 E
TE E
+TE
| T
FT T
*
FT
| F
(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E)={+,}FRIST(T)={*,}FOLLOW(E)=FOLLOW(E)={),$}FOLLOW(T)=FOLLOW(T)={+,),$}FOLLOW(F)={+,*,),$}3.3
自上而下分析
3.3.3遞歸下降的預(yù)測(cè)分析為每一個(gè)非終結(jié)符寫(xiě)一個(gè)分析過(guò)程這些過(guò)程可能是遞歸的例： type
simple |id |array[simple]oftype simpleinteger |char |numdotdotnum3.3
自上而下分析
一個(gè)輔助過(guò)程procedurematch(t:token);begin iflookahead==tthen lookahead:=nexttoken() elseerror()end;3.3
自上而下分析
proccduretype;begin iflookaheadin{integer,char,num}then simple() elseiflookahead=thenbegin match();match(id) end elseiflookahead=arraythenbegin match(array);match([);simple(); match(]);match(of);type() end elseerror()end;type
simple |id |array[simple]oftype3.3
自上而下分析
proceduresimple;begin iflookahead=integerthen match(integer) elseiflookahead=charthen match(char) elseiflookahead=numthenbegin match(num);match(dotdot);match(num) end elseerror()end;simpleinteger |char |numdotdotnumprocedurematch(t){if當(dāng)前輸入符號(hào)＝tthen取下一個(gè)符號(hào)作為當(dāng)前輸入符號(hào)else報(bào)錯(cuò)。}procedureA{ if當(dāng)前符號(hào)=‘a(chǎn)’then {match(a);調(diào)用A;} elsereturn;}procedureB{ if當(dāng)前符號(hào)=‘b’then {match(b);調(diào)用B;} elseif當(dāng)前符號(hào)=‘c’thenreturn;else報(bào)錯(cuò)。
}procedureS{ switch當(dāng)前符號(hào)
case‘a(chǎn)’:調(diào)用A; case‘b’:調(diào)用B;}SA|BAaA|
BbB|c
aaaaa,bbbbcaaaaa,aa,bbbc,bbc當(dāng)非終結(jié)符的產(chǎn)生式有多種選擇，即意味著分析過(guò)程有不同的展開(kāi)方式。而我們只能根據(jù)當(dāng)前輸入符號(hào)來(lái)決定采用哪種展開(kāi)方式（選擇），這樣就有了FIRST（）函數(shù)。1、LL(1)文法的自上而下分析及FIRST函數(shù)理解3.3
自上而下分析3.3.4非遞歸的預(yù)測(cè)分析a+b$輸入預(yù)測(cè)分析程序分析表M輸出
XYZ$棧3.3
自上而下分析非終結(jié)符輸
入
符
號(hào)
id+*
...EE
TE
E
E
+TE
T
T
FT
T
T
T
*FTF
F
id3.3
自上而下分析棧
輸
入
輸
出
$E
id*id+id$
預(yù)測(cè)分析器接受輸入id*id+id的動(dòng)作
3.3
自上而下分析棧
輸
入
輸
出
$E
id*id+id$$ET
id*id+id$E
TE
預(yù)測(cè)分析器接受輸入id*id+id的動(dòng)作
3.3
自上而下分析棧
輸
入
輸
出
$E
id*id+id$$ET
id*id+id$E
TE
$ETF
id*id+id$T
FT
預(yù)測(cè)分析器接受輸入id*id+id的動(dòng)作
3.3
自上而下分析棧
輸
入
輸
出
$E
id*id+id$$ET
id*id+id$E
TE
$ETF
id*id+id$T
FT
$ETidid*id+id$F
id
預(yù)測(cè)分析器接受輸入id*id+id的動(dòng)作
3.3
自上而下分析棧
輸
入
輸
出
$E
id*id+id$$ET
id*id+id$E
TE
$ETF
id*id+id$T
FT
$ETidid*id+id$F
id$ET
*
id+id$
預(yù)測(cè)分析器接受輸入id*id+id的動(dòng)作
3.3
自上而下分析棧
輸
入
輸
出
$E
id*id+id$
$ET
id*id+id$
E
TE
$ETF
id*id+id$
T
FT
$ETid
id*id+id$
F
id
$ET
*
id+id$
$ETF*
*
id+id$
T
*FT
預(yù)測(cè)分析器接受輸入id*id+id的動(dòng)作
3.3
自上而下分析棧
輸
入
輸
出
$E
id*id+id$$ET
id*id+id$E
TE
$ETF
id*id+id$T
FT
$ETidid*id+id$F
id$ET
*
id+id$$ETF*
*
id+id$T
*FT
$ETF
id+id$
預(yù)測(cè)分析器接受輸入id*id+id的動(dòng)作
3.3
自上而下分析棧
輸
入
輸
出
$E
id*id+id$$ET
id*id+id$E
TE
$ETF
id*id+id$T
FT
$ETidid*id+id$F
id$ET
*
id+id$$ETF*
*
id+id$T
*FT
$ETF
id+id$$ETidid+id$F
id預(yù)測(cè)分析器接受輸入id*id+id的動(dòng)作
棧
輸
入
輸
出
$E
id*id$
$ET
id*id$
E
TE
$ETF
id*id$
T
FT
$ETid
id*id$
F
id
$ET
*
id$
$ETF*
*
id$
T
*FT
$ETF
id$
$ETid
id$
F
id
$ET$$E$T$$EEE$2、LL(1)文法的自上而下的非遞歸分析方法理解深度優(yōu)先構(gòu)造分析樹(shù)E
TEE
+TE|T
FTT
*FT
|F
(E)|id輸入：id*id棧
輸
入
輸
出
$E
id*id$
$ET
id*id$
E
TE
$ETF
id*id$
T
FT
$ETid
id*id$
F
id
$ET
*
id$
$ETF*
*
id$
T
*FT
$ETF
id$
$ETid
id$
F
id
$ET$$E$T$$EETE
TE’$棧
輸
入
輸
出
$E
id*id$
$ET
id*id$
E
TE
$ETF
id*id$
T
FT
$ETid
id*id$
F
id
$ET
*
id$
$ETF*
*
id$
T
*FT
$ETF
id$
$ETid
id$
F
id
$ET$$E$T$$EETE
FT
FT’E’$棧
輸
入
輸
出
$E
id*id$
$ET
id*id$
E
TE
$ETF
id*id$
T
FT
$ETid
id*id$
F
id
$ET
*
id$
$ETF*
*
id$
T
*FT
$ETF
id$
$ETid
id$
F
id
$ET$$E$T$$EETE
FT
ididT’E’$棧
輸
入
輸
出
$E
id*id$
$ET
id*id$
E
TE
$ETF
id*id$
T
FT
$ETid
id*id$
F
id
$ET
*
id$
$ETF*
*
id$
T
*FT
$ETF
id$
$ETid
id$
F
id
$ET$$E$T$$EETE
FT
idT’E’$棧
輸
入
輸
出
$E
id*id$
$ET
id*id$
E
TE
$ETF
id*id$
T
FT
$ETid
id*id$
F
id
$ET
*
id$
$ETF*
*
id$
T
*FT
$ETF
id$
$ETid
id$
F
id
$ET$$E$T$$EETE
FT
id*T
F*FT’E’$棧
輸
入
輸
出
$E
id*id$
$ET
id*id$
E
TE
$ETF
id*id$
T
FT
$ETid
id*id$
F
id
$ET
*
id$
$ETF*
*
id$
T
*FT
$ETF
id$
$ETid
id$
F
id
$ET$$E$T$$EETE
FT
id*T
FFT’E’$棧
輸
入
輸
出
$E
id*id$
$ET
id*id$
E
TE
$ETF
id*id$
T
FT
$ETid
id*id$
F
id
$ET
*
id$
$ETF*
*
id$
T
*FT
$ETF
id$
$ETid
id$
F
id
$ET$$E$T$$EETE
FT
id*T
FididT’E’$棧
輸
入
輸
出
$E
id*id$
$ET
id*id$
E
TE
$ETF
id*id$
T
FT
$ETid
id*id$
F
id
$ET
*
id$
$ETF*
*
id$
T
*FT
$ETF
id$
$ETid
id$
F
id
$ET$$E$T$$EETE
FT
id*T
FidT’E’$棧
輸
入
輸
出
$E
id*id$
$ET
id*id$
E
TE
$ET
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間，僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年低壓電工作業(yè)復(fù)習(xí)題及參考答案
- 2025年國(guó)家基本公共衛(wèi)生服務(wù)規(guī)范第三版老年人健康管理考試試題含答案
- 設(shè)計(jì)師面試題目及答案：收納師的職業(yè)發(fā)展與技能提升
- 幼兒超市實(shí)踐教育活動(dòng)方案
- 醫(yī)院季度財(cái)務(wù)分析報(bào)告
- 中班兒歌活動(dòng)《落葉》
- 醫(yī)院網(wǎng)絡(luò)方案設(shè)計(jì)
- 運(yùn)輸合同核心條款解讀
- 網(wǎng)絡(luò)安全風(fēng)險(xiǎn)評(píng)估與管理服務(wù)創(chuàng)新創(chuàng)業(yè)項(xiàng)目商業(yè)計(jì)劃書(shū)
- 農(nóng)產(chǎn)品人工智能種植管理創(chuàng)新創(chuàng)業(yè)項(xiàng)目商業(yè)計(jì)劃書(shū)
- 2025版金屬材料買(mǎi)賣(mài)合同終止及廢舊材料回收利用協(xié)議
- 智慧監(jiān)獄AI大模型數(shù)字化平臺(tái)規(guī)劃設(shè)計(jì)方案
- 危大工程安全智能化管理措施
- 內(nèi)能的利用單元練習(xí) 2025-2026學(xué)年物理人教版（2024）九年級(jí)全一冊(cè)
- 醫(yī)療器械經(jīng)營(yíng)質(zhì)量管理規(guī)范培訓(xùn)
- 2025駕駛員交通安全培訓(xùn)
- 便血中醫(yī)護(hù)理方案
- 肝癌中西醫(yī)治療
- 商標(biāo)侵權(quán)培訓(xùn)課件
- 生豬屠宰獸醫(yī)衛(wèi)生檢驗(yàn)人員理論考試題庫(kù)及答案
- 我國(guó)核電發(fā)展前景分析課件
評(píng)論
0/150
提交評(píng)論