自底向上的解讀復(fù)習(xí)課程

自底向上的解讀5.1自底向上的語(yǔ)法分析概述思想從輸入串出發(fā)，反復(fù)利用產(chǎn)生式進(jìn)行歸約，如果最后能得到文法的開始符號(hào)，則輸入串是句子，否則輸入串有語(yǔ)法錯(cuò)誤。核心尋找句型中的當(dāng)前歸約對(duì)象——“句柄”進(jìn)行歸約,用不同的方法尋找句柄，就可獲得不同的分析方法2023/1/132例5.1一個(gè)簡(jiǎn)單的歸約過(guò)程設(shè)文法G為：S→aABeA→Abc|bB→d句子分析：

abbcdeaAbcdeaAdeaABeS語(yǔ)法樹的形成過(guò)程2023/1/133語(yǔ)法分析樹的生成演示abbcdeAABSA→bA→AbcB→dS→aAcBe2023/1/1345.1.1移進(jìn)-歸約分析系統(tǒng)框架采用表驅(qū)動(dòng)的方式實(shí)現(xiàn)輸入緩沖區(qū)：保存輸入符號(hào)串分析棧：保存語(yǔ)法符號(hào)—已經(jīng)得到的那部分分析結(jié)果控制程序：控制分析過(guò)程，輸出分析結(jié)果——產(chǎn)生式序列格局：棧+輸入緩沖區(qū)剩余內(nèi)容=“句型”2023/1/135移進(jìn)-歸約語(yǔ)法分析器的總體結(jié)構(gòu)

id+

id＊id#＋Ｅ#移進(jìn)-歸約控制程序輸出產(chǎn)生式序列棧內(nèi)容+輸入緩沖區(qū)內(nèi)容＝#“當(dāng)前句型”

#棧輸入緩沖區(qū)

分析表M2023/1/136與LL(1)的體系結(jié)構(gòu)比較

輸入緩沖區(qū)(符號(hào)序列)?？刂瞥绦騊132預(yù)測(cè)分析表M輸出產(chǎn)生式序列2023/1/137移進(jìn)-歸約分析的工作過(guò)程系統(tǒng)運(yùn)行開始格局棧：#；輸入緩沖區(qū)：w#存放已經(jīng)分析出來(lái)的結(jié)果,并將讀入的符號(hào)送入棧，一旦句柄在棧頂形成，就將其彈出進(jìn)行歸約，并將結(jié)果壓入棧問(wèn)題：系統(tǒng)如何發(fā)現(xiàn)句柄在棧頂形成？正常結(jié)束:棧中為#S，輸入緩沖區(qū)只有#2023/1/138輸出結(jié)果表示：

用產(chǎn)生式序列表示語(yǔ)法分析樹E→idid+id*idEEEEEE→idE→idE→E*EE→E+E例5.2E→E+E|E*E|(E)|id2023/1/139動(dòng)作棧輸入緩沖區(qū)1)#id1+id2*id3#id+id*id2)移進(jìn)#id1+id2*id3#例5.2分析過(guò)程3)歸約E→id#E+id2*id3#E4)移進(jìn)#E+id2*id3#5)移進(jìn)#E+id2*id3#6)歸約E→id#E+E*id3#EE7)移進(jìn)#E+E*id3#8)移進(jìn)#E+E*id3#9)歸約E→id#E+E*E#10)歸約E→E*E#E+E#E11)歸約E→E+E#E#12)接受E2023/1/1310分析器的四種動(dòng)作1)移進(jìn)：將下一輸入符號(hào)移入棧2)歸約：用產(chǎn)生式左側(cè)的非終結(jié)符替換棧頂?shù)木浔钞a(chǎn)生式右部）3)接受：分析成功4)出錯(cuò)：出錯(cuò)處理？？決定移進(jìn)和歸約的依據(jù)是什么—回頭看是否可以找到答案2023/1/1311移進(jìn)-歸約分析中的問(wèn)題1)移進(jìn)歸約沖突例5.2中的6)可以移進(jìn)*或按產(chǎn)生式E→E+E歸約2023/1/131212)接受1)#id1+id2*id3#id+id*id2)移進(jìn)#id1+id2*id3#例5.2分析過(guò)程3)歸約E→id#E+id2*id3#E4)移進(jìn)#E+id2*id3#5)移進(jìn)#E+id2*id3#6)歸約E→id#E+E*id3#EE7)移進(jìn)#E+E*id3#8)移進(jìn)#E+E*id3#9)歸約E→id#E+E*E#10)歸約E→E*E#E+E#E11)歸約E→E+E#E#E動(dòng)作棧輸入緩沖區(qū)2023/1/1313移進(jìn)-歸約分析中的問(wèn)題1)移進(jìn)歸約沖突例5.2中的6)可以移進(jìn)*或按產(chǎn)生式E→E+E歸約2)歸約歸約沖突存在兩個(gè)可用的產(chǎn)生式各種分析方法處理沖突的方法不同如何識(shí)別句柄？如何保證找到的直接短語(yǔ)是最左的?利用棧如何確定句柄的開始處與結(jié)束處？2023/1/13145.1.2優(yōu)先法根據(jù)歸約的先后次序?yàn)榫湫椭邢噜彽奈姆ǚ?hào)規(guī)定優(yōu)先關(guān)系句柄內(nèi)相鄰符號(hào)同時(shí)歸約，是同優(yōu)先的句柄兩端符號(hào)的優(yōu)先級(jí)要高于句柄外與之相鄰的符號(hào)a1…ai-1≮ai≡ai+1≡…≡aj-1≡aj≯aj+1…an定義了這種優(yōu)先關(guān)系之后，語(yǔ)法分析程序就可以通過(guò)ai-1≮ai和aj≯aj+1這兩個(gè)關(guān)系來(lái)確定句柄的頭和尾了2023/1/1315根據(jù)句柄的識(shí)別狀態(tài)（句柄是逐步形成的）用狀態(tài)來(lái)描述不同時(shí)刻下形成的那部分句柄因?yàn)榫浔钱a(chǎn)生式的右部，可用產(chǎn)生式來(lái)表示句柄的不同識(shí)別狀態(tài)例如：S→bBB可分解為如下識(shí)別狀態(tài)S→.bBB移進(jìn)bS→bB.B等待歸約出BS→b.BB等待歸約出BS→bBB.歸約采用這種方法，語(yǔ)法分析程序根據(jù)當(dāng)前的分析狀態(tài)就可以確定句柄的頭和尾，并進(jìn)行正確的歸約。

5.1.3狀態(tài)法2023/1/13165.2算符優(yōu)先分析法算術(shù)表達(dá)式分析的啟示算符優(yōu)先關(guān)系的直觀意義+≮*+的優(yōu)先級(jí)低于*(≡)(的優(yōu)先級(jí)等于)+≯++的優(yōu)先級(jí)高于+方法將句型中的終結(jié)符號(hào)當(dāng)作“算符”，借助于算符之間的優(yōu)先關(guān)系確定句柄2023/1/1317算術(shù)表達(dá)式文法的再分析E→E+EE→E-EE→E*EE→E/EE→(E)E→idE→E+T|E-T|TT→T*F|T/F|FF→(E)|id從如何去掉二義性,看對(duì)算符優(yōu)先級(jí)的利用句型的特征：(E+E)*(E-E)/E/E+E*E*E2023/1/1318算符文法如果文法G=（V，T，P，S）中不存在形如A→αBCβ的產(chǎn)生式，則稱之為算符文法(OG—OperatorGrammar)即：如果文法Ｇ中不存在具有相鄰非終結(jié)符的產(chǎn)生式，則稱為算符文法。2023/1/1319定義5.1假設(shè)G是一個(gè)不含ε-產(chǎn)生式的文法，A、B和C均是G的語(yǔ)法變量，G的任何一對(duì)終結(jié)符a和b之間的優(yōu)先關(guān)系定義為：⑴a≡b，當(dāng)且僅當(dāng)文法G中含有形如A→…ab…或A→…aBb…的產(chǎn)生式；⑵a≮b，當(dāng)且僅當(dāng)文法G中含有形如A→…aB…的產(chǎn)生式，而且Bb…或BCb…；⑶a≯b，當(dāng)且僅當(dāng)文法G中含有形如A→…Bb…的產(chǎn)生式，而且B…a或B…aC；⑷a與b無(wú)關(guān)系，當(dāng)且僅當(dāng)a與b在G的任何句型中都不相鄰。問(wèn)題：什么是算符優(yōu)先文法？5.2.1算符優(yōu)先文法2023/1/13205.2.1算符優(yōu)先文法設(shè)G=（V，T，P，S）為OG，如果

a,b∈VT,a≡b,a≮b,a≯b至多有一個(gè)成立，則稱之為算符優(yōu)先文法(OPG—OperatorPrecedenceGrammar)——在無(wú)ε產(chǎn)生式的算符文法Ｇ中，如果任意兩個(gè)終結(jié)符之間至多有一種優(yōu)先關(guān)系，則稱為算符優(yōu)先文法。2023/1/13215.2.2算符優(yōu)先矩陣的構(gòu)造優(yōu)先關(guān)系的確定根據(jù)優(yōu)先關(guān)系的定義a≮bA→…aB…∈P且(B+b…或者B+Cb…)需要求出非終結(jié)符B派生出的第一個(gè)終結(jié)符集a≯bA→…Bb…∈P且(B+…a或者B+…aC)需要求出非終結(jié)符B派生出的最后一個(gè)終結(jié)符集設(shè)G=（V，T，P，S）為OG，則定義FIRSTOP(A)={b|A+b…或者A+Bb…,b∈T,B

∈V}LASTOP(A)={b|A+…b或者A+…bB,b∈T,B

∈V}2023/1/1322算符優(yōu)先關(guān)系矩陣的構(gòu)造A→…ab…;A→…aBb…,則a≡bA→…aB…,則對(duì)b∈FIRSTOP(B),a≮bA→…Bb…,則對(duì)a∈LASTOP(B),a≯bifA→B…∈P,thenFIRSTOP(B)FIRSTOP(A)ifA→…B∈P,thenLASTOP(B)LASTOP(A)問(wèn)題：編程求FIRSTOP、LASTOP2023/1/1323算符優(yōu)先關(guān)系矩陣的構(gòu)造A→X1X2…Xn如果XiXi+1∈TT則：Xi≡Xi+1如果XiXi+1Xi+2∈TVT則：Xi≡Xi+2如果XiXi+1∈TV則：a∈FIRSTOP(Xi+1)，Xi≮a如果XiXi+1∈VT則：a∈LASTOP(Xi)，a≯Xi+12023/1/1324例5.6表達(dá)式文法的算符優(yōu)先關(guān)系≮ ≮ ≮ ≮ ≮ ≮ acc+ - * / ( ) id #+-*/（）id#≯≯ ≯ ≮ ≮ ≮≯ ≮ ≯≯ ≯ ≯ ≯ ≮≯ ≮ ≯≯

≯ ≯ ≯ ≮≯ ≮ ≯≮≮≮ ≮ ≮≡≮≯ ≯ ≯ ≯ ≯ ≯≯ ≯ ≯ ≯ ≯ ≯≯≮≮≮≯≮≯2023/1/13255.2.3算符優(yōu)先分析算法

原理識(shí)別句柄并歸約各種優(yōu)先關(guān)系存放在算符優(yōu)先分析表中利用≯識(shí)別句柄尾，利用≮識(shí)別句柄頭，分析棧存放已識(shí)別部分，比較棧頂和下一輸入符號(hào)的關(guān)系，如果是句柄尾，則沿棧頂向下尋找句柄頭，找到后彈出句柄，歸約為非終結(jié)符。2023/1/1326例5.7E→E+T|E-T|TT→T*F|T/F|FF→(E)|id，試?yán)盟惴麅?yōu)先分析法對(duì)id+id進(jìn)行分析步驟棧輸入串優(yōu)先關(guān)系動(dòng)作1#id1+id2#2#id1+id2##≮id1移進(jìn)id13#F+id2##≮id1≯+用Fid歸約4#F+id2#≮移進(jìn)+5#F+id2#≮移進(jìn)id26#F+F#+≮id2≯#用Fid歸約7#E##≮+≯#用EE+T歸約2023/1/1327問(wèn)題有時(shí)未歸約真正的句柄（F）不是嚴(yán)格的最左歸約歸約的符號(hào)串有時(shí)與產(chǎn)生式右部不同仍能正確識(shí)別句子的原因OPG未定義非終結(jié)符之間的優(yōu)先關(guān)系，不能識(shí)別由單非終結(jié)符組成的句柄定義算符優(yōu)先分析過(guò)程識(shí)別的“句柄”為最左素短語(yǔ)LPP（LeftmostPrimePhase）2023/1/1328素短語(yǔ)與最左素短語(yǔ)什么是短語(yǔ)？當(dāng)前我們要找什么樣的短語(yǔ)？——至少有一個(gè)算符Ｓ*

αＡβandA+γ，γ至少含一個(gè)終結(jié)符，且不含更小的含終結(jié)符的短語(yǔ),則稱γ是句型αγβ的相對(duì)于變量A的素短語(yǔ)(PrimePhrase)句型的至少含一個(gè)終結(jié)符且不含其它素短語(yǔ)的短語(yǔ)2023/1/1329例E→E+T|TT→T*F|FF→(E)|id

句型T+T*F+i的短語(yǔ)有TT*FiT+T*FT+T*F+i

其中的素短語(yǔ)為T*FiT*F為最左素短語(yǔ)，是被歸約的對(duì)象問(wèn)題：按照文法E→E+E|E*E|(E)|id，求i+E*i+i的短語(yǔ)和素短語(yǔ)

EETTE FT+T*F+i2023/1/1330文法：E→E+E|E*E E→(E)|id句型i+E*i+i的短語(yǔ)

EEEE EEi+E*i+i問(wèn)題：歸約過(guò)程中如何發(fā)現(xiàn)“中間句型”的最左素短語(yǔ)？iiE*iii+E*ii+E*i+i其中的素短語(yǔ)為iii2023/1/1331素短語(yǔ)與最左素短語(yǔ)設(shè)句型的一般形式為#N1a1N2a2…

Nnan#(Ni∈V∪{ε},ai∈VT）它的最左素短語(yǔ)是滿足下列條件的最左子串

NiaiNi+1ai+1…

NjajNj+1其中：ai-1≮ai,,，

ai≡ai+1≡…≡aj-1≡aj

，

aj≯aj+12023/1/1332算符優(yōu)先分析的實(shí)現(xiàn)系統(tǒng)組成移進(jìn)歸約分析器+優(yōu)先關(guān)系表分析算法參照輸入串、優(yōu)先關(guān)系表，完成一系列歸約，生成語(yǔ)法分析樹——輸出產(chǎn)生式2023/1/1333算符優(yōu)先分析算法算法5.3算符優(yōu)先分析算法。輸入：文法G=(V,T,P,S)，輸入字符串w和優(yōu)先關(guān)系表;輸出：如果w是一個(gè)句子則輸出一個(gè)分析樹架子，否則指出錯(cuò)誤;步驟：begin S[1]:=’#’;i:=1; repeat 將下一輸入符號(hào)讀入R; ifS[i]Tthenj:=ielsej:=i-1; whileS[j]≯Rdobegin repeatQ:=S[j]; ifS[j-1]Tthenj:=j-1elsej:=j-2 untilS[j]≮Q;

將S[j+1]…S[i]歸約為N;i:=j+1;S[i]:=Nend; ifS[j]≮RorS[j]≡Rthenbegini:=i+1;S[i]:=Rend elseerror untili=2andR=’#’end;2023/1/1334id+id*id的分析過(guò)程id+id*id#算符優(yōu)先分析控制器E→idE→idE→idE→E*EE→E+E算符優(yōu)先關(guān)系表#id##+#id+#+#*+#id*+#*+#+##2023/1/13355.2.4優(yōu)先函數(shù)為了節(jié)省存儲(chǔ)空間（n2→2n）和便于執(zhí)行比較運(yùn)算，用兩個(gè)優(yōu)先函數(shù)f和g，它們是從終結(jié)符號(hào)到整數(shù)的映射。對(duì)于終結(jié)符號(hào)a和b選擇f和g，使之滿足：

f(a)<g(b)，如果a≮b

f(a)=g(b)，如果a≡b

f(a)>g(b)，如果a≯b。損失錯(cuò)誤檢測(cè)能力降低如：id≯id不存在，但f(id)>g(id)可比較2023/1/1336表5.2對(duì)應(yīng)的優(yōu)先函數(shù)：1)構(gòu)造優(yōu)先函數(shù)的算法不是唯一的。2)存在一組優(yōu)先函數(shù)，那就存在無(wú)窮組優(yōu)先函數(shù)。+-*/()id#f22440440g113350502023/1/1337優(yōu)先函數(shù)的構(gòu)造算法5.4優(yōu)先函數(shù)的構(gòu)造。輸入：算符優(yōu)先矩陣;輸出：表示輸入矩陣的優(yōu)先函數(shù)，或指出其不存在;步驟：1.對(duì)aT∪{#}，建立以fa和ga為標(biāo)記的頂點(diǎn)；2.對(duì)a,bT∪{#}，若a≯b或者a≡b，則從fa至gb畫一條有向??；若a≮b或者a≡b，則從gb至fa畫一條有向??；3.如果構(gòu)造的有向圖中有環(huán)路，則說(shuō)明不存在優(yōu)先函數(shù)；如果沒有環(huán)路，則對(duì)aT∪{#}，將f(a)設(shè)為從fa開始的最長(zhǎng)路經(jīng)的長(zhǎng)度，將g(a)設(shè)為從ga開始的最長(zhǎng)路經(jīng)的長(zhǎng)度。2023/1/1338例5.10Ges:E→E+T|T

T→T*F|F

F→id+*id#+≯≮≮≯*≯≯≮≯id≯≯≯#≮≮≮+*id#f2440g1350根據(jù)Ges的優(yōu)先矩陣建立的有向圖和優(yōu)先函數(shù)

Ges的優(yōu)先矩陣2023/1/13395.2.5算符優(yōu)先分析的出錯(cuò)處理⑴棧頂?shù)慕K結(jié)符號(hào)和當(dāng)前輸入符號(hào)之間不存在任何優(yōu)先關(guān)系；⑵發(fā)現(xiàn)被“歸約對(duì)象”，但該“歸約對(duì)象”不能滿足歸約要求。對(duì)于第⑴種情況，為了進(jìn)行錯(cuò)誤恢復(fù)，必須修改棧、輸入或兩者都修改。對(duì)于優(yōu)先矩陣中的每個(gè)空白項(xiàng)，必須指定一個(gè)出錯(cuò)處理程序，而且同一程序可用在多個(gè)地方。對(duì)于第⑵種情況，由于找不到與“歸約對(duì)象”匹配的產(chǎn)生式右部，分析器可以繼續(xù)將這些符號(hào)彈出棧，而不執(zhí)行任何語(yǔ)義動(dòng)作。2023/1/1340算符優(yōu)先分析法小結(jié)優(yōu)點(diǎn)簡(jiǎn)單、效率高能夠處理部分二義性文法缺點(diǎn)文法書寫限制大——強(qiáng)調(diào)算符之間的優(yōu)先關(guān)系的唯一性占用內(nèi)存空間大不規(guī)范、存在查不到的語(yǔ)法錯(cuò)誤算法在發(fā)現(xiàn)最左素短語(yǔ)的尾時(shí)，需要回頭尋找對(duì)應(yīng)的頭2023/1/13415.3LR分析法5.3.1LR分析算法LR(k)分析法可分析LR(k)文法產(chǎn)生的語(yǔ)言L：從左到右掃描輸入符號(hào)R：最右推導(dǎo)對(duì)應(yīng)的最左歸約k：超前讀入k個(gè)符號(hào)，以便確定歸約用的產(chǎn)生式使用語(yǔ)言的文法描述內(nèi)涵解決句柄的識(shí)別問(wèn)題，從語(yǔ)言的形式描述入手，為語(yǔ)法分析器的自動(dòng)生成提供了前提和基礎(chǔ)分析器根據(jù)當(dāng)前的狀態(tài)，并至多向前查看k個(gè)輸入符號(hào)，就可以確定是否找到了句柄，如果找到了句柄，則按相應(yīng)的產(chǎn)生式歸約，如果未找到句柄則移進(jìn)輸入符號(hào)，并進(jìn)入相應(yīng)的狀態(tài)2023/1/1342LR語(yǔ)法分析器的總體結(jié)構(gòu)a1…ai…an#LR分析程序動(dòng)作表action轉(zhuǎn)移表goto產(chǎn)生式序列狀態(tài)/符號(hào)棧輸入緩沖區(qū)分析表SmSm-1………S1S0XmXm-1………X1#2023/1/1343LR分析表：action[s,a]；goto[s,X]

動(dòng)作表轉(zhuǎn)移表狀態(tài) action gotoab#SB0s3s4121acc2s3s453s3s464r3r3r35 r1r1r16r2r2r2LR(0)、SLR(1)、LR(1)、LALR(1)將以不同的原則構(gòu)造這張分析表約定：sn:將符號(hào)a、狀態(tài)n壓入棧rn:用第n個(gè)產(chǎn)生式進(jìn)行歸約2023/1/1344LR分析器的工作過(guò)程書上的下式（格局）

(s0s1…sm，X1X2…Xm，

aiai+1…an#)在這里表示為s0s1…sm#X1…Xm aiai+1…an#2023/1/1345LR分析器的工作過(guò)程1.初始化s0#

a1a2…an#

對(duì)應(yīng)“句型”a1a2…an2.在一般情況下，假設(shè)分析器的格局如下：s0s1…sm#X1…Xmaiai+1…an#對(duì)應(yīng)“句型”X1…Xmaiai+1…an①Ifaction[sm,ai]=si(shifti)

then

格局變?yōu)閟0s1…smi#X1…Xmaiai+1…an#2023/1/1346s0s1…sm

#X1…Xmaiai+1…an#③Ifaction[sm,ai]=accthen分析成功④Ifaction[sm,ai]=errthen

出現(xiàn)語(yǔ)法錯(cuò)②Ifaction[sm,ai]=ri(Reducei)

then

表示用第i個(gè)產(chǎn)生式A→Xm-(k-1)…Xm進(jìn)行歸約，格局變?yōu)閟0s1…sm-k#X1…Xm-kA

aiai+1…an#查goto表，如果goto[sm-k,A]=ithen

格局變?yōu)閟0s1…sm-ki#X1…Xm-kA

aiai+1…an#2023/1/1347LR分析算法

算法5.5LR分析算法。輸入：文法G的LR分析表和輸入串w;輸出：如果wL(G)，則輸出w的自底向上分析，否則報(bào)錯(cuò);步驟：1．將#和初始狀態(tài)S0壓入棧，將w#放入輸入緩沖區(qū)；2．令輸入指針ip指向w#的第一個(gè)符號(hào)；3．令S是棧頂狀態(tài)，a是ip所指向的符號(hào);4．repeat5．ifaction[S,a]=Sithen/*Si表示移進(jìn)a并轉(zhuǎn)入狀態(tài)i*/6．begin7． 把符號(hào)a和狀態(tài)i先后壓入棧；8． 令ip指向下一輸入符號(hào)9．end2023/1/1348

10．elseifaction[S,a]=rkthen/*ri表示按第k個(gè)產(chǎn)生式A→β歸約*/11．begin12． 從棧頂彈出2*|β|個(gè)符號(hào)；13． 令S'是現(xiàn)在的棧頂狀態(tài)；14． 把A和goto[S',A]先后壓入棧中；15． 輸出產(chǎn)生式A→β16．end17．elseifaction[S,a]=accthen18．return19．else20．error();2023/1/1349例5.12文法1)S→BB2)B→aB3)B→b分析表

動(dòng)作表轉(zhuǎn)移表狀態(tài) action gotoab#SB0s3s4121acc2s3s453s3s464r3r3r35r1r1r16r2r2r2請(qǐng)跟隨講解，快速抄下右側(cè)的表格！2023/1/1350bab的分析過(guò)程:

1)S→BB

2)B→aB

3)B→b0236#BaB#action(6,#)=r202#BB#goto(2,B)=5025#BB#action(5,#)=r10#S#goto(0,S)=101#S#action(1,#)=acc棧輸入動(dòng)作說(shuō)明0#bab#action(0,b)=s404#bab#action(4,a)=r30#Bab#goto(0,B)=202#Bab#action(2,a)=s3023#Bab#action(3,b)=s40234#Bab#action(4,#)=r3023#BaB#goto(3,B)=62023/1/1351規(guī)范句型活前綴分析棧中內(nèi)容+剩余輸入符號(hào)=規(guī)范句型分析棧中內(nèi)容為某一句型的前綴來(lái)自分析棧的活前綴(ActivePrefix)不含句柄右側(cè)任意符號(hào)的規(guī)范句型的前綴例：id+id*id的分析中句型E+id.*id和E+E*.id活前綴活前綴S*rmαAwrm

αβ1β2w

2023/1/1352規(guī)范句型活前綴規(guī)范歸約所得到的規(guī)范句型(CanonicalSententialForm)的活前綴是出現(xiàn)在分析棧中的符號(hào)串，所以，不會(huì)出現(xiàn)句柄之后的任何字符，而且相應(yīng)的后綴正是輸入串中還未處理的終結(jié)符號(hào)串?；钋熬Y與句柄的關(guān)系包含句柄A→.包含句柄的部分符號(hào)A→1.2

不含句柄的任何符號(hào)A→.2023/1/13535.3.2LR(0)分析表的構(gòu)造LR(0)項(xiàng)目——從產(chǎn)生式尋找歸約方法右部某個(gè)位置標(biāo)有園點(diǎn)的產(chǎn)生式稱為相應(yīng)文法的LR(0)項(xiàng)目（Item）例S→.bBBS→bB.BS→b.BBS→bBB.歸約（Reduce）項(xiàng)目:S→aBB.移進(jìn)（Shift）項(xiàng)目：S→.bBB待約項(xiàng)目：S→b.BB

S→bB.B2023/1/1354項(xiàng)目的意義用項(xiàng)目表示分析的進(jìn)程(句柄的識(shí)別狀態(tài))方法：在產(chǎn)生式右部加一園點(diǎn)以分割已獲取的內(nèi)容和待獲取的內(nèi)容：構(gòu)成句柄babBBBSS→B.BB→.aB2023/1/1355拓廣(Augmented)文法需要一個(gè)對(duì)“歸約成S”的表示（只有一個(gè)接受狀態(tài)）文法G=(V,T,P,S)的拓廣文法G'：G'=（V∪{S'}，T，P∪{S'→S}，S'）S'V對(duì)應(yīng)S'→.S（分析開始）和S'→S.（分析成功）例5.130)S'→S1)S→BB2)B→aB3)B→b2023/1/1356構(gòu)造識(shí)別G的所有規(guī)范句型活前綴的DFA問(wèn)題：如何設(shè)計(jì)能夠指導(dǎo)分析器運(yùn)行，并且能夠根據(jù)當(dāng)前狀態(tài)（棧頂）確定句柄——?dú)w約對(duì)象的頭——的裝置2023/1/1357項(xiàng)目集I的閉包（Closure）CLOSURE(I)=I∪{B→.γ|A→α.Bβ∈I,B→γ∈P}

算法J:=I;repeatJ=J∪{B→.η|A→α.Bβ∈J,B→η∈P}untilJ不再擴(kuò)大項(xiàng)目集閉包的計(jì)算2023/1/1358閉包之間的轉(zhuǎn)移后繼項(xiàng)目（SuccessiveItem）A→α.Xβ的后繼項(xiàng)目是A→αX.β閉包之間的轉(zhuǎn)移go(I,X)=CLOSURE({A→αX.β|A→α.Xβ∈I}2023/1/1359狀態(tài)轉(zhuǎn)移的計(jì)算確定在某狀態(tài)遇到一個(gè)文法符號(hào)后的狀態(tài)轉(zhuǎn)移目標(biāo)functionGO(I,X);begin J:=;forI中每個(gè)形如A→α.Xβ的項(xiàng)目do beginJ:=J∪{A→αX.β}end; returnCLOSURE(J)end;2023/1/1360識(shí)別拓廣文法所有規(guī)范句型活前綴的DFA識(shí)別文法G=（V，T，P，S）的拓廣文法G'的所有規(guī)范句型活前綴的DFA: M=(C,V∪T,go,I0,C)I0=CLOSURE({S'→.S}C={I0}∪{I|J∈C,X∈V∪T,I=go(J,X)}稱為G'的LR(0)項(xiàng)目集規(guī)范族(CanonicalCollection)2023/1/1361計(jì)算LR(0)項(xiàng)目集規(guī)范族Ｃ

即：分析器狀態(tài)集合beginC:={closure({S'→.S})};repeatforI∈C，X

∈V∪Tifgo(I,X)≠Φ&go(I,X)Cthen C=C∪{go(I,X)}untilC不變化end.2023/1/13622023/1/1363例4-13

S→BB

B→aB

B→bI0:S'→.SS→.BBB→.aBB→.b I1:S'→S.SBI2:S→B.BB→.aBB→.b

aI4:B→a.BB→.aBB→.b bI3:B→b. BI5:S→BB.abBI6:B→aB.ab核心項(xiàng)目KernelItemLR(0)分析表的構(gòu)造算法算法5.6LR(0)分析表的構(gòu)造。輸入：文法G=(V,T,P,S)的拓廣文法G

';輸出：G

'的LR(0)分析表，即action表和goto表;步驟：1.令I(lǐng)0=CLOSURE({S

'

→.S})，構(gòu)造G

'的LR(0)項(xiàng)目集規(guī)范族C={I0,I1,…,In}2．讓Ii對(duì)應(yīng)狀態(tài)i，I0對(duì)應(yīng)狀態(tài)0，0為初始狀態(tài)。3．fork=0tondobegin⑴ifA→α.aβIk&aT&GO(Ik,a)=Ijthenaction[k,a]:=Sj;⑵ifA→α.BβIk&BV&GO(Ik,B)=Ijthengoto[k,B]:=j;⑶ifA→α.Ik&A→α為G的第j個(gè)產(chǎn)生式thenforaT∪{#}doaction[k,a]:=rj;⑷ifS'→S.Ik

thenaction[k,#]:=accend;4．上述⑴到⑷步未填入信息的表項(xiàng)均置為error。2023/1/1364LR(0)不是總有效的(S'

→S)1)S→A|B2)A→aAc3)A→a4)B→bBd5)B→b上下文無(wú)關(guān)文法不是都能用LR(0)方法進(jìn)行分析的，也就是說(shuō)，CFG不總是LR(0)文法.2023/1/1365I0:S’→.SS→.AS→.BA→.aAcA→.aB→.bBdB→.bSI1:S'→S.AI2:S→A.BI3:S→B.aI4:A→a.AcA→a.A→.aAcA→.abI5:B→b.BdB→b.B→.bBdB→.bAI6:A→aA.cabBI7:B→bB.dcI8:A→aAc.dI7:B→bBd.S'

→SS→A|BA→aAcA→aB→bBdB→b2023/1/1366項(xiàng)目集I的相容如果I中至少含兩個(gè)歸約項(xiàng)目，則稱I有歸約—?dú)w約沖突（Reduce/ReduceConflict）如果I中既含歸約項(xiàng)目，又含移進(jìn)項(xiàng)目，則稱I有移進(jìn)—?dú)w約沖突（Shift/ReduceConflict）如果I既沒有歸約—?dú)w約沖突，又沒有移進(jìn)—?dú)w約沖突，則稱I是相容的(Consistent)，否則稱I是不相容的對(duì)文法G，如果

I∈C,都是相容的，則稱G為L(zhǎng)R(0)文法2023/1/1367I0:S’→.SS→.AS→.BA→.aAcA→.aB→.bBdB→.bSI1:S'→S.AI2:S→A.BI3:S→B.aI4:A→a.AcA→a.A→.aAcA→.abI5:B→b.BdB→b.B→.bBdB→.bAI6:A→aA.cabBI7:B→bB.dcI8:A→aAc.dI7:B→bBd.S'

→SS→A|BA→aAcA→aB→bBdB→b問(wèn)題:如何構(gòu)造其分析表?2023/1/13685.3.3SLR(1)分析表的構(gòu)造算法

算法5.6LR(0)分析表的構(gòu)造。輸入：文法G=(V,T,P,S)的拓廣文法G';輸出：G'的LR(0)分析表，即action表和goto表;步驟：1.令I(lǐng)0=CLOSURE({S'→.S})，構(gòu)造G'的LR(0)項(xiàng)目集規(guī)范族C={I0,I1,…,In}2．讓Ii對(duì)應(yīng)狀態(tài)i，I0對(duì)應(yīng)狀態(tài)0，0為初始狀態(tài)。3．fork=0tondobegin⑴ifA→α.aβIk&aT&GO(Ik,a)=Ijthenaction[k,a]:=Sj;⑵ifA→α.BβIk&BV&GO(Ik,B)=Ijthengoto[k,B]:=j;⑶ifA→α.Ik&A→α為G的第j個(gè)產(chǎn)生式thenforaFOLLOW(A)doaction[k,a]:=rj;⑷ifS'→S.Ik

thenaction[k,#]:=accend;4．上述⑴到⑷步未填入信息的表項(xiàng)均置為error。2023/1/1369識(shí)別表達(dá)式文法的所有活前綴的DFA

拓廣文法

0)Ｅ'→Ｅ

1)Ｅ→Ｅ+Ｔ

2)Ｅ→Ｔ

3)Ｔ→Ｔ*Ｆ

4)Ｔ→Ｆ

5)Ｆ→(Ｅ)6)Ｆ→idI0:E’→.EE→.E+TE→.TT→.T*FT→.FF→.(E)F→.idEI1:E’→E.E→E.+TTI2:E→T.T→T.*FFI3:T→F.(I4:F→(.E)E→.E+TE→.TT→.T*FT→.FF→.(E)F→.ididI5:F→id.+I6:E→E+.TT→.T*FT→.FF→.(E)F→.id*I7:T→T*.FF→.(E)F→.idEI8:F→(E.)E→E.+TTF(idTI9:E→E+T.T→T.*FF(idFI10:T→T*F.()I11:F→(E).+*id2023/1/1371表達(dá)式文法的

LR(0)分析表含有沖突在狀態(tài)2、9采用歸約，出現(xiàn)移進(jìn)歸約沖突2023/1/1372表達(dá)式文法的SLR(1)分析表求非終結(jié)符的FISRT集和FOLLOW集FIRST(F)={id,(}FIRST(T)={id,(}FIRST(E)={id,(}FOLLOW(E)={),+,#}FOLLOW(T)={),+,#,*}FOLLOW(F)={),+,#,*}1)Ｅ→Ｅ+Ｔ

2)Ｅ→Ｔ

3)Ｔ→Ｔ*Ｆ

4)Ｔ→Ｆ

5)Ｆ→(Ｅ)6)Ｆ→id2023/1/1373si表示移進(jìn)到狀態(tài)i,ri表示用i號(hào)產(chǎn)生式歸約2023/1/1374SLR(1)分析的特點(diǎn)描述能力強(qiáng)于LL(1)

SLR(1)還考慮Follow集中的符號(hào)LL(1)僅考慮產(chǎn)生式的首符號(hào)SLR(1)文法：SLR(1)分析表無(wú)沖突的CFG2023/1/1375SLR(1)分析的局限性如果SLR(1)分析表仍有多重入口（移進(jìn)歸約沖突或歸約歸約沖突），則說(shuō)明該文法不是SLR(1)文法；說(shuō)明僅使用LR(0)項(xiàng)目集和FOLLOW集還不足以分析這種文法2023/1/1376I0:S’→.SS→.L=RS→.RL→.*RL→.idR→.LI1:S’→S.I2:S→L.=RR→L.LI3:S→R.RI4:L→*.RR→.LL→.*RL→.idI5:L→id.*idI6:S→L=.RR→.LL→.*RL→.id=I7:L→*R.RI8:R→L.LI9:S→L=R.R*LidS2023/1/1377SLR分析中的沖突——需要更強(qiáng)的分析方法

I2={S→L.=R,R→L.}輸入符號(hào)為=時(shí)，出現(xiàn)了移進(jìn)歸約沖突：

S→L.=R∈I2andgo(I2,=)=I6

action[2,=]=Shift6R→L.∈I2and=∈FOLLOW(R)={=,#}

action[2,=]=ReduceR→L說(shuō)明該文法不是SLR(1)文法，分析這種文法需要更多的信息。2023/1/1378SLR分析中存在沖突的原因SLR（1）只孤立地考察輸入符號(hào)是否屬于歸約項(xiàng)目A→α.相關(guān)聯(lián)的集合FOLLOW（A），而沒有考察符號(hào)串α所在規(guī)范句型的“上下文”。所以試圖用某一產(chǎn)生式A→α歸約棧頂符號(hào)串α?xí)r，不僅要向前掃描一個(gè)輸入符號(hào)，還要查看棧中的符號(hào)串δα，只有當(dāng)δAa的確構(gòu)成文法某一規(guī)范句型的活前綴時(shí)才能用A→α歸約。亦即要考慮歸約的有效性：?jiǎn)栴}：怎樣確定δAa是否是文法某一規(guī)范句型的活前綴2023/1/13795.3.4LR(1)分析表的構(gòu)造LR(0)不考慮后繼符(搜索符)，SLR(1)僅在歸約時(shí)考慮后繼符(搜索符)，因此，對(duì)后繼符(搜索符)所含信息量的利用有限，未考慮棧中內(nèi)容。希望在構(gòu)造狀態(tài)時(shí)就考慮后繼符(搜索符)的作用：考慮對(duì)于產(chǎn)生式A→α的歸約，不同使用位置的A會(huì)要求不同的后繼符號(hào)2023/1/1380后繼符(搜索符)的概念EE+T(E)T*F

不同的歸約中有不同的后繼符。特定位置的后繼符是FOLLOW集的子集2023/1/1381LR(k)項(xiàng)目定義5.11

[A→α.β,a1a2…ak]為L(zhǎng)R（k）項(xiàng)目，根據(jù)圓點(diǎn)所處位置的不同又分為三類：歸約項(xiàng)目:[A→α.,a1a2…ak]移進(jìn)項(xiàng)目：[A→α.aβ,a1a2…ak]待約項(xiàng)目：[A→α.Bβ,a1a2…ak]利用LR(k)項(xiàng)目進(jìn)行(構(gòu)造)LR(k)分析(器)，當(dāng)k=1時(shí)，為L(zhǎng)R(1)項(xiàng)目，相應(yīng)的分析叫LR(1)分析(器)2023/1/1382LR(1)項(xiàng)目的有效性形式上稱LR(1)項(xiàng)目[A→α.β,a]對(duì)活前綴γ=δα是有效的，如果存在規(guī)范推導(dǎo)S*δAwδαβw其中a為w的首字符，如果w=ε，則a=#與LR(0)文法類似，識(shí)別文法全部活前綴的DFA的每一狀態(tài)也是用一個(gè)LR(1)項(xiàng)目集來(lái)表示，為保證分析時(shí)，每一步都在棧中得到規(guī)范句型的活前綴，應(yīng)使每一個(gè)LR(1)項(xiàng)目集僅由若干個(gè)對(duì)相應(yīng)活前綴有效的項(xiàng)目組成2023/1/1383識(shí)別文法全部活前綴的DFALR(1)項(xiàng)目集族的求法CLOSURE（I）：求I的閉包，目的是為了合并某些狀態(tài)，節(jié)省空間GO（I，X）：轉(zhuǎn)移函數(shù)2023/1/1384閉包的計(jì)算CLOSURE(I)的計(jì)算(核心位置：A→α.Bβ,a擴(kuò)展成閉包)同時(shí)考慮可能出現(xiàn)的后繼符b∈FIRST(βa)2023/1/1385閉包的計(jì)算如果[A→α.Bβ,a]對(duì)γ=δα有效

/*即存在S*δAaxδαβax*/假定βax*by，則對(duì)任意的B→η有：[B→.η，b]對(duì)γ=δα也是有效的，其中b∈FIRST（βa）2023/1/1386閉包的計(jì)算J:=I; repeat J=J∪{[B→.η,b]|[A→α.Bβ,a]∈J,b∈FIRST(βa)} untilJ不再擴(kuò)大當(dāng)β+ε時(shí)，此時(shí)b=a叫繼承的后繼符，否則叫自生的后繼符2023/1/1387狀態(tài)I和文法符號(hào)X的轉(zhuǎn)移函數(shù)go(I,X)=closure([A→αX.β,a]|[A→α.Xβ,a]∈I)2023/1/1388計(jì)算LR(1)項(xiàng)目集規(guī)范族Ｃ

即：分析器狀態(tài)集合C={I0}∪{I|J∈C，X∈V∪T，I=go(J,X)}稱為G’的LR(1)項(xiàng)目集規(guī)范族（算法：P185)beginC:={closure({S'→.S,#})};repeatforI∈C，X

∈V∪Tifgo(I,X)≠Φ&go(I,X)Cthen C=C∪go(I,X)untilC不變化end.2023/1/1389識(shí)別活前綴的關(guān)于LR(1)的DFA識(shí)別文法G=（V，T，P，S）的拓廣文法G’的所有活前綴的DFAM=(C,V∪T,go,I0,C)I0=CLOSURE({S’→.S,#}如果CFGG的LR(1)分析表無(wú)沖突則稱G為L(zhǎng)R(1)文法2023/1/1390LR(1)分析表的構(gòu)造1．令I(lǐng)0=CLOSURE({S'→.S