版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
自底向上分析思想第一頁,共三十四頁,編輯于2023年,星期三6.1自底向上優(yōu)先分析法概述優(yōu)先分析法可分為:簡單優(yōu)先分析法算符優(yōu)先分析法第二頁,共三十四頁,編輯于2023年,星期三簡單優(yōu)先分析法基本思想:對一個文法按一定原則求出該文法所有符號之間的優(yōu)先關(guān)系。按照這種關(guān)系確定規(guī)約過程中的句柄。這種規(guī)約實(shí)際上是一種規(guī)范規(guī)約。第三頁,共三十四頁,編輯于2023年,星期三算符優(yōu)先分析法基本思想:只規(guī)定算符之間的優(yōu)先關(guān)系,即只考慮終極符之間的優(yōu)先關(guān)系。由于不考慮非終極符之間的關(guān)系,在規(guī)約過程中只要找到句柄就規(guī)約,并不考慮規(guī)約到哪個非終極符,所以不是規(guī)范規(guī)約。第四頁,共三十四頁,編輯于2023年,星期三6.2簡單優(yōu)先分析法6.2.1優(yōu)先關(guān)系X=Y表示X和Y的優(yōu)先關(guān)系相等。
(iffG中存在產(chǎn)生式A→…XY…)X<.Y表示X的優(yōu)先性比Y的優(yōu)先性小。
(iffG中存在產(chǎn)生式A→…XB…,
且B=>+Y…)X.>Y表示X的優(yōu)先性比Y的優(yōu)先性大。
(iffG中存在產(chǎn)生式A→…BD…,
且B=>+…X和D=>*Y)第五頁,共三十四頁,編輯于2023年,星期三6.2.1優(yōu)先關(guān)系例:若有文法G[S]1.S→bAb2.A→(B|a3.B→Aa)根據(jù)定義,可求得文法符號之間的優(yōu)先關(guān)系:第六頁,共三十四頁,編輯于2023年,星期三SSSS
bAbbAb
bAb
bAb(Ba(BAa)(BAa)(BaAa)優(yōu)先關(guān)系實(shí)例第七頁,共三十四頁,編輯于2023年,星期三表6.2文法的簡單優(yōu)先關(guān)系矩陣SbA(Ba)#S.>b1.>A11(<.<.1<.Ba1)#=.第八頁,共三十四頁,編輯于2023年,星期三
簡單優(yōu)先關(guān)系矩陣從上表可看出:矩陣中元素要么只有一種關(guān)系,要么為空,元素為空時表示該文法的任何句型中不會出現(xiàn)該符號對的相鄰關(guān)系。若出現(xiàn),則為出錯。
‘#’表示語句括號,‘#’的優(yōu)先級<.所有符號的優(yōu)先級,僅對所有與‘#’有相鄰關(guān)系的文法符號而言。第九頁,共三十四頁,編輯于2023年,星期三6.2.2簡單優(yōu)先文法的定義簡單優(yōu)先文法必須滿足以下條件:(1)在文法符號集V中,任意兩個符號之間最多只有一種優(yōu)先關(guān)系成立。(2)在文法中任意兩個產(chǎn)生式?jīng)]有相同的右部。(若不滿足會出現(xiàn)規(guī)約不唯一。)第十頁,共三十四頁,編輯于2023年,星期三6.2.3簡單優(yōu)先分析法算法:首先構(gòu)造優(yōu)先關(guān)系矩陣。(1)將輸入符號串a(chǎn)1a2..an#依次逐個存入符號棧S中,直到遇到棧頂符號ai的優(yōu)先性.>下一個待輸入符號aj時為止。(2)棧頂當(dāng)前符號ai為句柄尾,由此向左在棧中找句柄的頭符號ak,即找到ak-1<.ak為止。(3)由句柄akak+1…ai在文法的產(chǎn)生式中查找右部為akak+1…ai的產(chǎn)生式,若找到,則用相應(yīng)左部代替句柄,若找不到則為出錯,這時可斷定輸入串不是該文法的句子。(4)重復(fù)(1)(2)(3)直到歸約完輸入符號串,棧中只剩文法的開始符號為止。第十一頁,共三十四頁,編輯于2023年,星期三6.3算符優(yōu)先分析法算符優(yōu)先分析法只考慮算符(廣義為終結(jié)符)之間的優(yōu)先關(guān)系,例如:(1)E→E+E(2)E→E-E(3)E→I對輸入串i1+i2*i3的歸約過程可表示如下:第十二頁,共三十四頁,編輯于2023年,星期三表6.3對輸入串i1+i2*i3的歸約過程步驟棧S當(dāng)前輸入符輸入串剩余部分動作1#i1+i2*i3#移進(jìn)2#i1+i2*i3#歸約(3)3#E+i2*i3#移進(jìn)4#E+i2*i3#移進(jìn)5#E+i2*i3#歸約(3)6#E+E*i3#移進(jìn)7#E+E*i3#移進(jìn)8#E+E*i3#歸約(3)9#E+E*E#歸約(2)10#E+E#歸約(1)11#E#接受第十三頁,共三十四頁,編輯于2023年,星期三6.3.1
直觀算符優(yōu)先分析法算符間的優(yōu)先關(guān)系的表示:
a<.b表示a的優(yōu)先性低于ba=.b表示a的優(yōu)先性等于ba>.b表示a的優(yōu)先性高于b我們可以對表達(dá)式的文法按公認(rèn)的計(jì)算順序規(guī)定優(yōu)先級和結(jié)合性如下:第十四頁,共三十四頁,編輯于2023年,星期三算符優(yōu)先分析法表達(dá)式:
E→E+E|E-E|E*E|E/E|E^E|(E)|i(1)^優(yōu)先級最高,遵循右結(jié)合。相當(dāng)^<.^(2)*,/優(yōu)先級其次,服從左結(jié)合。相當(dāng)*>.**>.//>.//>.*(3)+,-優(yōu)先級最低,服從左結(jié)合。相當(dāng)
+>.++>.-->.-->.+
(4)對‘(’,‘)’規(guī)定括號的優(yōu)先性大于括號外的運(yùn)算符,小于括號內(nèi)的運(yùn)算符,內(nèi)括號的優(yōu)先性大于外括號。附加:對運(yùn)算對象的終結(jié)符i其優(yōu)先級最高。
‘#’
優(yōu)先級最低。第十五頁,共三十四頁,編輯于2023年,星期三算符優(yōu)先關(guān)系表+-*/^()i#+>.>.>.<>.-<>.*>>>>><>./<>.^>>>><<><>.(>>>>><=.<)>>>>>>>.i>>>>>>>.#<<<<<<<=.第十六頁,共三十四頁,編輯于2023年,星期三6.3.2
算符優(yōu)先文法的定義 定義1算符文法
:設(shè)有一文法G,如果G中沒有形如A→
…BC…的產(chǎn)生式,其中B和C為非終結(jié)符,則稱G為算符文法(OperaterGrammar)也稱OG文法。第十七頁,共三十四頁,編輯于2023年,星期三算符文法的性質(zhì)性質(zhì)1在算符文法中任何句型都不包含兩個相鄰的非終結(jié)符。性質(zhì)2如果Ab或(bA)出現(xiàn)在算符文法的句型中,其中A∈VN,b∈VT,則該句型中任何含b的短語必含有A。第十八頁,共三十四頁,編輯于2023年,星期三算符優(yōu)先關(guān)系的定義定義2設(shè)G是一個不含ε產(chǎn)生式的算符文法,a和b是任意兩個終結(jié)符,A、B、C是非終結(jié)符,算符優(yōu)先關(guān)系=.、<.、.>定義如下:(1)a=.b當(dāng)且僅當(dāng)G中含有形如
A→
…ab…
或A→
…aBb…的產(chǎn)生式第十九頁,共三十四頁,編輯于2023年,星期三算符優(yōu)先關(guān)系的定義(2)a<.b當(dāng)且僅當(dāng)G中含有形如
A→
…aB…
的產(chǎn)生式且
B=>+b…或B=>+Cb…(3)a>.b當(dāng)且僅當(dāng)G中含有形如
A→
…Bb…的產(chǎn)生式且
B=>+…a或B=>+…aC第二十頁,共三十四頁,編輯于2023年,星期三算符優(yōu)先文法的定義定義3:設(shè)G是一個不含ε產(chǎn)生式的算符文法,如果對任意兩個終結(jié)符對a,b之間,至多只有=.、<.、.>三種關(guān)系的一種成立,則稱G是一個算符優(yōu)先文法。(OperatorPrecedenceGrammar)即OPG文法。第二十一頁,共三十四頁,編輯于2023年,星期三6.3.3算符優(yōu)先關(guān)系表的構(gòu)造(1)由定義直接構(gòu)造(通過算法實(shí)現(xiàn))(2)由關(guān)系圖法構(gòu)造(手工構(gòu)造)第二十二頁,共三十四頁,編輯于2023年,星期三
LR分析法
自底向上分析的最終目的是:試圖將輸入串歸約為文法的開始符號。分析過程實(shí)際上是一種移進(jìn)—?dú)w約過程,即當(dāng)被分析的(棧頂)符號串形成句柄時就采取歸約動作,自底向上分析的關(guān)鍵問題就是如何確定句柄。LR分析法就是一種自底向上分析法。LR分析法的歸約過程是規(guī)范推導(dǎo)的逆過程,所以LR分析過程是一種歸范歸約過程。第二十三頁,共三十四頁,編輯于2023年,星期三LR(K)的含義LR(K)分析法是1965年Knuth先生提出的,括號內(nèi)的K表示向右查看輸入串中符號的個數(shù)?!癓”表示從左(L)向右掃描輸入串,“R”表示自下而上地建立它的最右(R)推導(dǎo)。第二十四頁,共三十四頁,編輯于2023年,星期三LR分析法的優(yōu)點(diǎn)LR文法是非歧義文法中能夠自底向上進(jìn)行確定分析的最大文法類。這種方法比起自頂向下的LL(K)分析方法和自底向上的優(yōu)先分析方法對文法的限制要少得多。也就是說:凡是能夠用LL分析的文法都能用LR進(jìn)行分析,LR分析器可以識別大多數(shù)用非歧義上下文無關(guān)文法描述的語言。因此,LR方法的適用范圍比LL方法更加廣泛。具有速度快、準(zhǔn)確即時指錯的優(yōu)點(diǎn)。
第二十五頁,共三十四頁,編輯于2023年,星期三LR分析LR分析器的構(gòu)造工作量相當(dāng)大,實(shí)現(xiàn)相當(dāng)困難。目前真正實(shí)用的編譯器,其LR分析器大多采用美國Bell實(shí)驗(yàn)室1974年推出的“一個編譯器的編譯器——YACC”來實(shí)現(xiàn)。它能接受一個用BNF描述的滿足LALR(1)的上下文無關(guān)文法并將自動構(gòu)造出LALR(1)語法分析器。第二十六頁,共三十四頁,編輯于2023年,星期三LR分析我們主要介紹K≤1時,LR分析器的基本構(gòu)造原理和方法。其中LR(0)分析器在分析時不需向右查看輸入符號,因而對文法的限制較大,但它是構(gòu)造其它LR分析器的基礎(chǔ);當(dāng)K=1時,已能滿足大多數(shù)高級語言編譯程序的需要。首先,了解一下LR分析法的基本概念。第二十七頁,共三十四頁,編輯于2023年,星期三LR方法的一般概念LR分析器也是下推自動機(jī)的特例(圖4.8)。它是一個帶有下推棧的有窮自動機(jī)。輸入帶存放被分析的串,帶的右端(即串尾)總是放上一個界限符“#”。
下推棧分為兩部分:狀態(tài)棧和文法符號棧。
分析器的控制器由一個總控(驅(qū)動)程序和一張分析表組成。
第二十八頁,共三十四頁,編輯于2023年,星期三一個LR分析器的組成:
(1)總控程序
對所有的LR分析器都是一樣的,易于實(shí)現(xiàn)。(2)分析表(或分析函數(shù))
對不同的文法是不同的。分析表由兩部分組成:動作表(ACTION)和狀態(tài)轉(zhuǎn)換表(GOTO),都可用二維數(shù)組表示。動作表f(S,a)規(guī)定了當(dāng)狀態(tài)S遇到輸入符號a時應(yīng)采取的行動;轉(zhuǎn)換表g(S,X)規(guī)定了狀態(tài)S遇到非終極符X時應(yīng)進(jìn)入的下一個狀態(tài)。(3)分析棧
包括文法符號棧和相應(yīng)的狀態(tài)棧,它們都是后進(jìn)先出棧。第二十九頁,共三十四頁,編輯于2023年,星期三LR分析器分析器的動作就是由棧頂狀態(tài)和當(dāng)前輸入符號決定的LR(0)分析器不需向前查看輸入符號。第三十頁,共三十四頁,編輯于2023年,星期三LR分析器工作過程
LR分析器按下列方式動作:假定當(dāng)前棧為狀態(tài)棧S0S1…Sm,文法符號棧X0X1…Xm。任一時刻棧頂狀態(tài)Sm與當(dāng)前輸入符號a都決定了分析器的下一步動作,這個動作是由動作表的f(Sm,a)所決定。動作表f的表項(xiàng)可規(guī)定下列4種動作之一:第三十一頁,共三十四頁,編輯于2023年,星期三動作表f可規(guī)定的四種動作(1)移進(jìn)如果f(Sm,a)=Si,則分析器首先把a(bǔ)移入到文法符號棧,再把狀態(tài)Si壓入狀態(tài)棧頂。(i為
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年度牛羊養(yǎng)殖場安全生產(chǎn)與應(yīng)急管理合同3篇
- 2025年度環(huán)保服務(wù)合同:環(huán)保服務(wù)內(nèi)容與要求3篇
- 2025年生化分析儀項(xiàng)目申請報告
- 2025年玻璃布增強(qiáng)塑料項(xiàng)目規(guī)劃申請報告模稿
- 2025年腫瘤科護(hù)理工作計(jì)劃
- 二零二五年公務(wù)車客運(yùn)包車合同2篇
- 2024版市區(qū)交通圍擋施工及維護(hù)協(xié)議版
- 2025社會調(diào)查報告范文
- 幼兒園度膳食工作計(jì)劃
- 2025年生物法殼聚糖項(xiàng)目立項(xiàng)申請報告模范
- 2024解讀《弘揚(yáng)教育家精神》全文
- TCI 373-2024 中老年人免散瞳眼底疾病篩查規(guī)范
- TCCIAT 0046-2022 混凝土剪力墻結(jié)構(gòu)裝配式組合殼體系技術(shù)規(guī)程
- GB/Z 44118.1-2024電能質(zhì)量技術(shù)管理第1部分:總則
- 2024年銀行招聘筆試真題題庫
- 小區(qū)物業(yè)續(xù)聘方案
- 石油鉆采專用設(shè)備制造考核試卷
- 法人變更股權(quán)轉(zhuǎn)讓協(xié)議書(2024版)
- 研究生中期考核匯報模板幻燈片
- 2024年浙江省嘉興市交通運(yùn)輸局所屬事業(yè)單位招聘人才5人歷年(高頻重點(diǎn)提升專題訓(xùn)練)共500題附帶答案詳解
- 儲能項(xiàng)目工具【Excel計(jì)算表】儲能系統(tǒng)投資Excel計(jì)算表
評論
0/150
提交評論