1、實(shí)驗(yàn)三 LR分析實(shí)驗(yàn)名稱LR語(yǔ)法分析實(shí)驗(yàn)要求(1)輸入任意文法(2)輸出LR分析表(3)輸入任意測(cè)試語(yǔ)句(4)輸出分析過(guò)程，判定結(jié)果要求提供：(1)數(shù)據(jù)結(jié)構(gòu)描述(2)算法說(shuō)明(3)測(cè)試截圖數(shù)據(jù)結(jié)構(gòu)描述主要列舉了如下幾個(gè)：1 產(chǎn)生式存儲(chǔ)結(jié)構(gòu)s文法開(kāi)始符號(hào)line產(chǎn)生式的個(gè)數(shù)Gi0產(chǎn)生式的標(biāo)號(hào)Gi1Vt終結(jié)符Vn非終結(jié)符2 項(xiàng)目集存儲(chǔ)結(jié)構(gòu)prjset結(jié)構(gòu)：id項(xiàng)目集編號(hào) Prjt *next指示下一個(gè)項(xiàng)目集 Prjt存儲(chǔ)項(xiàng)目的編號(hào) ，prjt0項(xiàng)目編號(hào)的個(gè)數(shù) Pointafter圓點(diǎn)后的字符， pointafter0為字符個(gè)數(shù)Prjset*actorgo存儲(chǔ)出度pointbefore圓點(diǎn)前面的字符

2、3 LR(0)分析表存儲(chǔ)結(jié)構(gòu)form動(dòng)態(tài)數(shù)組下標(biāo)，同時(shí)作為符號(hào)的編號(hào)Vn非終結(jié)符序列Vt終結(jié)符序列（3）存放LR分析表的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)方法一：用一個(gè)二維整數(shù)數(shù)組表示數(shù)組元素為表示動(dòng)作的整數(shù)。數(shù)組的行下標(biāo)為狀態(tài)號(hào)，列下標(biāo)用來(lái)表示終結(jié)符與非終結(jié)符的整數(shù)表示。數(shù)組元素可作如下約定： 正整數(shù)：表示移進(jìn)動(dòng)作，如S6用數(shù)6表示； 負(fù)整數(shù)：表示歸約動(dòng)作，如R5用數(shù)-5表示；：表示接受，通常為按產(chǎn)生式0歸約；狀態(tài)號(hào)也用整數(shù)表示；用不可能是狀態(tài)號(hào)的較大的整數(shù)表示錯(cuò)誤轉(zhuǎn)移。 請(qǐng)將上述LALR(1)分析表用這種表示方法，完成LR分析器的程序設(shè)計(jì)，并添加輸出狀態(tài)棧內(nèi)容的功能。用上述表達(dá)式文法G的一個(gè)句子作為輸入，進(jìn)行測(cè)

3、試。實(shí)現(xiàn)方法二：采用壓縮表示法動(dòng)作Action表的每一行用一個(gè)數(shù)組表示，數(shù)組的第一個(gè)元素是本數(shù)組中存放的數(shù)偶個(gè)數(shù)，第二個(gè)元素到最后一個(gè)元素都以終結(jié)符，動(dòng)作的數(shù)偶的形式存放。再用一個(gè)以狀態(tài)號(hào)為下標(biāo)的下標(biāo)數(shù)組，每個(gè)元素含一個(gè)指向數(shù)偶數(shù)組的指針。若數(shù)組元素的值為NULL，則表示從此狀態(tài)無(wú)轉(zhuǎn)移弧發(fā)出。若分析表有幾行相同，則只需保存一行，其它元素則都指向存放這一行表的數(shù)組即可。轉(zhuǎn)移Goto表也按同樣方式組織，只是這個(gè)行數(shù)組的數(shù)偶為非終結(jié)符，下一狀態(tài)號(hào)。 每個(gè)行數(shù)組Yyan表示動(dòng)作表Yy_action的一行，每個(gè)行數(shù)組Yygn表示轉(zhuǎn)移表Yy_goto的一行。假定上述表達(dá)式文法G中終結(jié)符及非終結(jié)符的整數(shù)值為

4、： 終結(jié)符： # ID + * ( ) 非終結(jié)符： S E T F 整數(shù)值： 0 1 2 3 4 5 整數(shù)值： 0 1 2 3 Yy_action數(shù)組是以狀態(tài)號(hào)為下標(biāo)的下標(biāo)數(shù)組，每個(gè)元素含有指向數(shù)組Yyan的指針；下標(biāo)數(shù)組Yy_goto的每個(gè)元素含有指向數(shù)組Yygn的指針。表達(dá)式文法G的LALR(1)分析表的具體壓縮表示如下：24,2 1,1Yya000Yy_action. 045,-63,-62,-60,-6Yya001 1Yya003 220,02,7 345,-22,-20,-23,8Yya004 4Yya005 45,-43,-42,-40,-4 525,92,7Yya006 6 7Y

5、ya009 845,-53,-52,-50,-5 945,-12,-10,-13,8Yya010 10 Yya011 45,-35,-32,-30,-3 11Yyg000 Yy_goto.NULL.NULLNULL NULLNULL.NULLNULLNULL33,52,41,3 0Yyg002 133,52,41,6 2 3 4 5Yyg007 623,52,10 713,11Yyg008 8 9 10 11 實(shí)驗(yàn)原理及算法描述LR分析器由三個(gè)部分組成：(1)總控程序，也可以稱為驅(qū)動(dòng)程序。對(duì)所有的LR分析器總控程序都是相同的。(2)分析表或分析函數(shù)，不同的文法分析表將不同，同一個(gè)文法采用的LR

6、分析器不同時(shí)，分析表將不同，分析表又可以分為動(dòng)作表（ACTION）和狀態(tài)轉(zhuǎn)換（GOTO）表兩個(gè)部分，它們都可用二維數(shù)組表示。(3)分析棧，包括文法符號(hào)棧和相應(yīng)的狀態(tài)棧，它們均是先進(jìn)后出棧。分析器的動(dòng)作就是由棧頂狀態(tài)和當(dāng)前輸入符號(hào)所決定。2. LR分析器的結(jié)構(gòu)為：其中:SP為棧指針，Si為狀態(tài)棧，Xi為文法符號(hào)棧。狀態(tài)轉(zhuǎn)換表用GOTOi，X=j表示，規(guī)定當(dāng)棧頂狀態(tài)為i，遇到當(dāng)前文法符號(hào)為X時(shí)應(yīng)轉(zhuǎn)向狀態(tài)j，X為終結(jié)符或非終結(jié)符。1 識(shí)別文法的LR(0)項(xiàng)目集規(guī)范族的構(gòu)造采用（閉包）的構(gòu)造一個(gè)文法的項(xiàng)目規(guī)范簇。假定是文法的任一項(xiàng)目集，定義和構(gòu)造的閉包的算法：（1）的任何項(xiàng)目都屬于；（2）若屬于，那么

7、，對(duì)任何關(guān)于的產(chǎn)生式，項(xiàng)目也屬于；（3）重復(fù)執(zhí)行上述兩個(gè)步驟直至不再增大。其中初始 ，為對(duì)文法進(jìn)行拓廣構(gòu)造而引進(jìn)的不出現(xiàn)在中的非終結(jié)符。定義狀態(tài)轉(zhuǎn)換函數(shù)，的第一個(gè)變?cè)且粋€(gè)項(xiàng)目集，第二個(gè)變?cè)且粋€(gè)文法符號(hào)。函數(shù)值定義為。其中 = 任何形如的項(xiàng)目| 屬于2 LR(0)分析表的構(gòu)造 假定。令每個(gè)項(xiàng)目集的下標(biāo)作為分析器的狀態(tài)。特別是，令那個(gè)包含項(xiàng)目的集合的下標(biāo)為分析器的初態(tài)。分析表的子表和子表可按如下方法構(gòu)造： （1）若項(xiàng)目屬于且，為終結(jié)符，則置為“把移近?！?，簡(jiǎn)記為“”。 （2）若項(xiàng)目屬于，那么對(duì)于任何終結(jié)符（或結(jié)束符#），置為“用產(chǎn)生式進(jìn)行規(guī)約”，簡(jiǎn)記為“”（假定產(chǎn)生式是文法的第j個(gè)產(chǎn)生式） （3）若項(xiàng)目屬于，則置為“接受”，簡(jiǎn)記為“acc”。 （4）若，則置。 （5）分析表中凡不能用規(guī)則14填入信息的空白處均置上“報(bào)錯(cuò)標(biāo)志”。如果分析表中任何一項(xiàng)被重復(fù)填入，則說(shuō)明分析表的入口不是唯一的，項(xiàng)目集中存在沖突項(xiàng)目，該文法不是文法。3 LR(0)分析器總控程序構(gòu)造分析表包括量部分，“動(dòng)作”表和“狀態(tài)轉(zhuǎn)換”表。規(guī)定了當(dāng)狀態(tài)面臨輸入符號(hào)時(shí)應(yīng)采取什么動(dòng)作。規(guī)定了狀態(tài)面對(duì)文法符號(hào)時(shí)下一狀態(tài)是什么。每一項(xiàng)所規(guī)定的動(dòng)作不外乎是下述四種可能之一。（1）移進(jìn) 把的下一狀態(tài)和輸入符號(hào)推進(jìn)棧，下一輸入符號(hào)變成現(xiàn)行輸入符號(hào)。（2）歸約 指用某一產(chǎn)生式進(jìn)行規(guī)約