ch7.1-7.3lr-slr語(yǔ)法分析(張素琴)

《ch7.1-7.3lr-slr語(yǔ)法分析(張素琴)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、17.1LR分析概述7.2LR(0)分析7.3SLR(1)分析7.4LR(1)分析7.7語(yǔ)法分析器的自動(dòng)構(gòu)造工具yacc第7章LR分析法27.1LR分析概述分析器的邏輯結(jié)構(gòu)及工作過(guò)程LR(k)分析技術(shù)L----是指從左至右掃描輸入符號(hào)串R----是指構(gòu)造一個(gè)最右推導(dǎo)的逆過(guò)程，K----是指為了作出分析決定而向前看的輸入符號(hào)的個(gè)數(shù)。3LR分析方法是當(dāng)前最廣義的無(wú)回溯的“移進(jìn)-歸約”方法。LR(k)分析技術(shù)knuth于1965年首先提出來(lái)的。根據(jù)棧中的符號(hào)串和向右順序查看輸入串中的k(k?0)個(gè)符號(hào)，就能唯一確定分析器的動(dòng)作是

2、移進(jìn)還是歸約，以及用哪個(gè)產(chǎn)生式進(jìn)行歸約。優(yōu)點(diǎn)：限制少，適用范圍廣；分析速度快；報(bào)錯(cuò)準(zhǔn)確。4缺點(diǎn)：構(gòu)造分析器的工作量很大，不大可能手工構(gòu)造用軟件工具yacc-YetAnotherCompilerCompiler,Bell,1974.輸入LR上下文無(wú)關(guān)文法的BNF，輸出LR分析器。5一、LR分析器邏輯結(jié)構(gòu)輸入、輸出、棧、驅(qū)動(dòng)程序和分析表組成id+id*id#LR驅(qū)動(dòng)程序動(dòng)作轉(zhuǎn)移actiongoto輸出S1Xm…S1…X1S0#棧狀態(tài)文法符號(hào)產(chǎn)生式表ＬＲ分析特征:規(guī)范的符號(hào)棧中的符號(hào)是規(guī)范句型的前綴分析決策依據(jù)―棧頂狀態(tài)和現(xiàn)行輸

3、入符號(hào)．識(shí)別規(guī)范句型特定前綴(就到句柄為止)的DFA.四種技術(shù)LR(0)SLR(1)LR(1)LALR(1)7不同的語(yǔ)法分析器具有不同的分析表,驅(qū)動(dòng)程序都是一樣的LR(0)分析器LR(0)分析表SLR(1)分析器SLR(1)分析表LR(1)分析器LR(1)分析表LALR(1)分析器LALR(1)分析表分析表是LR分析法的核心，它包含兩部分：動(dòng)作表（ACTION）和狀態(tài)轉(zhuǎn)換表（GOTO）8動(dòng)作表動(dòng)作規(guī)定如下：移進(jìn)ai和s=action[sm,ai]進(jìn)棧action[sm,ai]=歸約rj:A?Xm-r+1Xm-r+2…Xms

4、=goto[sm-r,A]接受成功，規(guī)約到識(shí)別符號(hào)出錯(cuò)9二、LR分析器的工作過(guò)程主控程序根據(jù)輸入串、棧、產(chǎn)生式、分析表進(jìn)行相應(yīng)的移近、規(guī)約、接受或報(bào)錯(cuò)操作。id+id*id#LR主控程序動(dòng)作轉(zhuǎn)移actiongoto輸出S1Xm…S1…X1S0#棧狀態(tài)文法符號(hào)產(chǎn)生式表107.2LR(0)分析A→.XYZA→X.YZA→XY.ZA→XYZ.對(duì)于產(chǎn)生式A→XYZ對(duì)應(yīng)的句柄XYZ,其狀態(tài)劃分為：句柄識(shí)別態(tài)一、LR分析的基本原理把每個(gè)句柄的識(shí)別過(guò)程劃分為若干個(gè)狀態(tài),每個(gè)狀態(tài)下，自左向右地識(shí)別了句柄的一部分符號(hào)。11活前綴定義:規(guī)范推

5、導(dǎo)S?*?A?????，??的所有前綴稱為活前綴。即規(guī)范句型的前綴，但右端不超過(guò)該句型句柄末端。識(shí)別了句柄的一部分就相當(dāng)于識(shí)別了當(dāng)前規(guī)范句型的左起部分，這部分被識(shí)別的符號(hào)串稱之為規(guī)范句型的活前綴。對(duì)于文法G[S]1.S→vI:T2.I→I,i3.I→i4.T→realvi,i:real是該文法的一個(gè)句子S=>vI:T=>vI:real=>vI,i:real=>vi,i:real12vi,i:real#其活前綴是:#vi,iεvI,ivivvI,vIvI:vI:realvI:TSIIvIreal:T1.S→vI:T2.I→I

6、,i3.I→i4.T→realS13DFA的定義：M=（Q,Σ,δ,q0,Z)其中：Q--狀態(tài)集Σ—輸入字母表δ–QxΣ→Q的映射函數(shù)LR分析器使用有窮自動(dòng)機(jī)DFA識(shí)別各規(guī)范句型的活前綴LR(0)項(xiàng)目：14LR(0)項(xiàng)目:用圓點(diǎn)“?”表示識(shí)別一個(gè)產(chǎn)生式右部符號(hào)到達(dá)的位置，若有規(guī)則A?XYZ,則有下面四個(gè)項(xiàng)目：A→.XYZA→X.YZA→XY.ZA→XYZ.A???a?,a?VT移進(jìn)項(xiàng)目A???B?,B?VN待歸約項(xiàng)目A???歸約項(xiàng)目S’′?.S開(kāi)始項(xiàng)目項(xiàng)目A→X.YZ和A→XY.Z稱為后繼項(xiàng)目S’′?S?接受項(xiàng)目15拓廣文

7、法定義：為了使文法的“接受”狀態(tài)易于識(shí)別，且唯一，常對(duì)文法進(jìn)行拓廣改造。對(duì)于文法G，我們構(gòu)造一個(gè)G’，引進(jìn)一個(gè)不出現(xiàn)在G中的非終結(jié)符S’和一個(gè)產(chǎn)生式S’→S，S’為G’的開(kāi)始符號(hào),S’不出現(xiàn)在規(guī)則右部。對(duì)于文法G[E]1.E→aA

8、bB2.A→cA

9、d3.B→cB

10、d文法G’[S’]0.S’→E1.E→aA

11、bB2.A→cA

12、d3.B→cB

13、d拓廣文法161.S’→E2.S’→E3.E→aA4.E→aA5.E→aA6.A→cA7.A→cA8.A→cA9.A→d10.A→d11.E→bB12.E→b.B13.E→bB14.B

14、→cB對(duì)于上述文法G’,所有LR(0)項(xiàng)目如下：15.B→cB16.B→cB17.B→d18.B→d文法G’[S’]0.S’→E1.E→aA

15、bB2.A→cA

16、d3.B→cB

17、d17歸約項(xiàng)目：5、8、10、13、16、18接收項(xiàng)目：2移進(jìn)項(xiàng)目：3、6、9、11、14、17待約項(xiàng)目：4、7、12、15初始