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

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

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

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

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

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

5、導S?*?A?????，??的所有前綴稱為活前綴。即規(guī)范句型的前綴，但右端不超過該句型句柄末端。識別了句柄的一部分就相當于識別了當前規(guī)范句型的左起部分，這部分被識別的符號串稱之為規(guī)范句型的活前綴。對于文法G[S]1.S→vI:T2.I→I,i3.I→i4.T→realvi,i:real是該文法的一個句子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分析器使用有窮自動機DFA識別各規(guī)范句型的活前綴LR(0)項目：14LR(0)項目:用圓點“?”表示識別一個產(chǎn)生式右部符號到達的位置，若有規(guī)則A?XYZ,則有下面四個項目：A→.XYZA→X.YZA→XY.ZA→XYZ.A???a?,a?VT移進項目A???B?,B?VN待歸約項目A???歸約項目S’′?.S開始項目項目A→X.YZ和A→XY.Z稱為后繼項目S’′?S?接受項目15拓廣文

7、法定義：為了使文法的“接受”狀態(tài)易于識別，且唯一，常對文法進行拓廣改造。對于文法G，我們構(gòu)造一個G’，引進一個不出現(xiàn)在G中的非終結(jié)符S’和一個產(chǎn)生式S’→S，S’為G’的開始符號,S’不出現(xiàn)在規(guī)則右部。對于文法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對于上述文法G’,所有LR(0)項目如下：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歸約項目：5、8、10、13、16、18接收項目：2移進項目：3、6、9、11、14、17待約項目：4、7、12、15初始