編譯原理課程設(shè)計(jì)LR(1)分析法

1、精選優(yōu)質(zhì)文檔-傾情為你奉上課程設(shè)計(jì)說(shuō)明書(shū) 課程名稱:編譯原理課程設(shè)計(jì) 題 目: LR(1)分析法 院 系： 專業(yè)班級(jí)： 學(xué) 號(hào)： 學(xué)生姓名： 指導(dǎo)教師： 2012年 6 月 22 日安徽理工大學(xué)課程設(shè)計(jì)（論文）任務(wù)書(shū) 院系 教研室學(xué) 號(hào) 學(xué)生姓名 專業(yè)（班級(jí)）信計(jì)09-1 設(shè)計(jì)題目 LR（1）分析法設(shè)計(jì)技術(shù)參數(shù) Windows xp操作系統(tǒng) VC+6.0 設(shè)計(jì)要求 1掌握LR(1)分析法的基本原理2掌握LR(1)分析表的構(gòu)造方法3掌握LR(1)驅(qū)動(dòng)程序的構(gòu)造方法工作量 3kb的程序代碼 13頁(yè)的課程設(shè)計(jì)說(shuō)明書(shū)工作計(jì)劃 2012.6.14-2012.6.16 需求分析 2012.6.16-211

2、2.6.18 編寫(xiě)代碼 2012.6.19-2012.6.20 調(diào)試運(yùn)行參考 資料1 張素琴.呂映芝等.編譯原理M.清華大學(xué)出版.2004年2王宏.李玉東.李罡.Visual C+實(shí)戰(zhàn)演練M.人民郵電出版.2003年3月3胡元義等.編譯原理實(shí)踐教程M.西安電子科技大學(xué)出版社.2005年7月4 胡倫駿.編譯原理.M.電子工業(yè)出版社，20025 高仲儀.編譯原理及編譯程序構(gòu)造>.M.北京航空航天大學(xué)出版社.1990 指導(dǎo)教師簽字 教研室主任簽字 2012年6 月22 日 學(xué)生姓名： 學(xué)號(hào)： 專業(yè)班級(jí)： 課程設(shè)計(jì)題目： LR(1)分析法 指導(dǎo)教師評(píng)語(yǔ)： 成績(jī)： 指導(dǎo)教師： 年 月 日安徽理工大

3、學(xué)課程設(shè)計(jì)（論文）成績(jī)專心-專注-專業(yè)LR(1)分析法一、系統(tǒng)簡(jiǎn)介及需求分析1.1 設(shè)計(jì)目的及要求（1） 掌握LR(1)分析法的基本原理；（2） 掌握LR(1)分析表的構(gòu)造方法；（3）掌握LR(1)驅(qū)動(dòng)程序的構(gòu)造方法。（4） 構(gòu)造LR(1)分析程序，利用它進(jìn)行語(yǔ)法分析，判斷給出的符號(hào)串是否為該文法識(shí)別的句子.1.2實(shí)驗(yàn)內(nèi)容根據(jù)某一文法編制調(diào)試LR(1)分析程序，以便對(duì)任意輸入的符號(hào)串進(jìn)行分析。本次實(shí)驗(yàn)的目的主要是加深對(duì)LR(1)分析法的理解。 對(duì)下列文法，用LR(1)分析法對(duì)任意輸入的符號(hào)串進(jìn)行分析：（0）E->S（1）S->BB（2）B->aB（3）B->b程序輸入一

4、以#結(jié)束的符號(hào)串(包括a、b、#)，如：abb#。輸出過(guò)程如下：步驟 狀態(tài)棧 符號(hào)棧 輸入串ACTIONGOTO10#abb#S3. 圖1-1二、設(shè)備與環(huán)境 2.1硬件設(shè)備 內(nèi)存容量 2 GB 硬盤容量 320 GB 硬盤描述 7200轉(zhuǎn)，SATA 流處理器個(gè)數(shù) 32 2.2軟件環(huán)境 操作系統(tǒng)： WINDOWS XP 開(kāi)發(fā)平臺(tái)： C語(yǔ)言 開(kāi)發(fā)軟件: VC+ 6.03、 系統(tǒng)分析 3.1 LR(1)分析法定義LR分析法是一種有效的自底向上的語(yǔ)法分析技術(shù)，它能適用于大部分上下文無(wú)關(guān)文法的分析，一般叫LR(k)分析方法，其中L是指自左(Left)向右掃描輸入單詞串，R是指分析過(guò)程都是構(gòu)造最右(Rig

5、ht)推導(dǎo)的逆過(guò)程(規(guī)范歸約)，括號(hào)中的k是指在決定當(dāng)前分析動(dòng)作時(shí)向前看的符號(hào)個(gè)數(shù)。 3.2 LR(1)分析方法的主要思想(1)嚴(yán)格地進(jìn)行最左歸約（識(shí)別句柄并歸約它）。(2)將識(shí)別句柄的過(guò)程劃分為由若干狀態(tài)控制，每個(gè)狀態(tài)控制識(shí)別出句柄的一個(gè)符號(hào)。(3)分析棧：存放已識(shí)別的文法符號(hào)和狀態(tài),描述的是分析過(guò)程中的歷史和展望信息;(4)由一個(gè)總控程序來(lái)控制整個(gè)識(shí)別過(guò)程。 3.3 LR(1)分析器的工作過(guò)程(1) 將初始狀態(tài)S0和輸入串的左邊界(#) 分別進(jìn)分析棧；(2) 根據(jù)狀態(tài)棧棧頂和當(dāng)前輸入符號(hào)查動(dòng)作表進(jìn)行如下工作;移進(jìn):若動(dòng)作表中對(duì)應(yīng)“移進(jìn)”，那么當(dāng)前輸入符號(hào)進(jìn)符號(hào)棧，并據(jù)狀態(tài)轉(zhuǎn)換表查得輸入符號(hào)

6、所對(duì)應(yīng)的新的狀態(tài)進(jìn)狀態(tài)棧，繼續(xù)掃描，即下一個(gè)輸入符號(hào)變成當(dāng)前得輸入符號(hào)；歸約:若動(dòng)作表中對(duì)應(yīng)“歸約”，則按指定產(chǎn)生式進(jìn)行歸約，若產(chǎn)生式右部的符號(hào)串長(zhǎng)度為n，則符號(hào)棧棧頂?shù)膎個(gè)符號(hào)為句柄，所以符號(hào)棧棧頂n個(gè)符號(hào)出棧，同時(shí)，狀態(tài)棧頂?shù)膎個(gè)元素也出棧，歸約后的文法符號(hào)(非終結(jié)符)進(jìn)符號(hào)棧，并據(jù)狀態(tài)轉(zhuǎn)換表查歸約后的文法符號(hào)所對(duì)應(yīng)的新?tīng)顟B(tài)進(jìn)狀態(tài)棧；接受:若動(dòng)作表中對(duì)應(yīng)“acc”，則分析成功；出錯(cuò):若動(dòng)作表中對(duì)應(yīng)空白，則報(bào)告錯(cuò)誤信息。(3) 重復(fù)以上(2)的工作直到接受或出錯(cuò)為止。 3.4 LR(1)的優(yōu)點(diǎn) (1)LR分析器能夠構(gòu)造來(lái)識(shí)別所有能用上下文無(wú)關(guān)文法寫(xiě)的程序設(shè)計(jì)語(yǔ)言的結(jié)構(gòu)。(2)LR分析方法是已

7、知的最一般的無(wú)回溯移進(jìn)-歸約方法，它能夠和其他移進(jìn)-歸約方法一樣有效地實(shí)現(xiàn)。(3)LR方法能分析的文法類是預(yù)測(cè)分析法能分析的文法類的真超集。(4)LR分析器能及時(shí)察覺(jué)語(yǔ)法錯(cuò)誤,快到自左向右掃描輸入的最大可能。為了使一個(gè)文法是LR的，只要保證當(dāng)句柄出現(xiàn)在棧頂時(shí)，自左向右掃描的移進(jìn)-歸約分析器能夠及時(shí)識(shí)別它便足夠了。當(dāng)句柄出現(xiàn)在棧頂時(shí)，LR分析器必須要掃描整個(gè)棧就可以知道這一點(diǎn)，因?yàn)?，如果這個(gè)識(shí)別句柄的有限自動(dòng)機(jī)自底向上讀棧中的文法符號(hào)的話，它達(dá)到的狀態(tài)正是這時(shí)棧頂?shù)臓顟B(tài)符號(hào)所表示的狀態(tài)，所以，LR分析器可以從棧頂?shù)臓顟B(tài)確定它需要從棧中了解的一切。 3.5 LR分析器的組成(1)總控程序，也可以稱

8、為驅(qū)動(dòng)程序。對(duì)所有的LR分析器總控程序都是相同的。(2)分析表或分析函數(shù)，不同的文法分析表將不同，同一個(gè)文法采用的LR分析器不同時(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)所決定。 3.6 LR分析器結(jié)構(gòu)圖輸入串a(chǎn)1a2aiai+1an#Sm。S1S0Xn。X1#輸出總控程序Sp 分析表ACTION表GOTO 表 圖3-1 圖3-1(1)在總控程序的控制下，從左到右掃描輸入串根據(jù)分析棧和輸入符號(hào)的情況，查分析表確定分析動(dòng)作

9、；(2) 分析表是LR分析器的核心，它跟文法有關(guān)，它包括動(dòng)作表(Action)和狀態(tài)轉(zhuǎn)換表(Goto)兩部分，總控程序據(jù)分析表確定分析動(dòng)作；(3) 分析棧包括文法符號(hào)棧Xi和相應(yīng)的狀態(tài)棧Si兩部分(狀態(tài)是指能識(shí)別活前綴的自動(dòng)機(jī)狀態(tài))，LR分析器通過(guò)判斷棧頂元素和輸入符號(hào)查分析表確定下步分析動(dòng)作。3.7 舉例構(gòu)造下面文法的LR(1)分析表(0)S'® S(1)S® aAd(2)S® bAc(3)S® aec(4)S® bed(5) A® e解：S0: S'®.S, # S®.aAd, # S®

10、;.bAc, # S®.aec, # S®.bed, #S1: S'®S., #SaS2:S®a.Ad, # S®a.ec, #A®.e,dS4: S®aA.d, #S5: S®ae.c, #A®e.,dAeS8:S®aAd.,#dS9:S®aec., #cS3: S®b.Ac, # S®b.ed, #A®.e,cbAS6: S®bA.c, #S10: S®bAc., #cS7:S®be.d, #A®e.,c

11、eS11;S®bed., #d1. 求項(xiàng)目集合 圖3-22. 根據(jù)項(xiàng)目集合得到分析表如下表3-1狀態(tài) ACTION GOTOabcde#SA0S2S311acc2S543S764S85S9r56S107r5S118r19r310r211r44、 測(cè)試運(yùn)行4.1 程序運(yùn)行截圖4.1.1 輸入字符串ABSD# 圖4-1 4.1.2輸入字符串a(chǎn)bbb# 圖4-2 4.1.3輸入字符串a(chǎn)babababab# 圖4-3 4.1.4 輸入i+i*i()i# 圖4-45、 總結(jié) 經(jīng)過(guò)這個(gè)實(shí)驗(yàn)的練習(xí)，通過(guò)對(duì)程序的分析，讓我進(jìn)一步了解LR（1）算法的思想以及它的進(jìn)一步程序?qū)崿F(xiàn)，讓我對(duì)它的了解從簡(jiǎn)單的理

12、論上升到程序?qū)崿F(xiàn)的級(jí)別，有理論上升到實(shí)際，讓我更清楚它的用途。 在對(duì)實(shí)驗(yàn)的分析的時(shí)候，也遇到很多的問(wèn)題，剛開(kāi)始根本想不到用程序怎么實(shí)現(xiàn)這么繁雜的LR（1）文法，后來(lái)看了程序才知道，才轉(zhuǎn)過(guò)來(lái)彎，通過(guò)對(duì)這個(gè)程序的分析與揣摩，讓自己對(duì)這方面文法的實(shí)現(xiàn)有了一定的頭緒，對(duì)以后的的一些文法的程序?qū)崿F(xiàn)會(huì)有很大的幫助，通過(guò)練習(xí)我也感到理論僅留在理論是遠(yuǎn)遠(yuǎn)不行的，用通過(guò)一定方式實(shí)現(xiàn)才有實(shí)用價(jià)值。 通過(guò)本次課程設(shè)計(jì)，我加深了對(duì)預(yù)測(cè)分析LR（1）分析法的理解，同時(shí)體驗(yàn)到了編譯原理中一些算法的巧妙。由于LR（1）分析法程序是一個(gè)相當(dāng)復(fù)雜的程序，它需要利用到大量的編譯原理，編程技巧和數(shù)據(jù)結(jié)構(gòu)。由于先前掌握的知識(shí)不夠牢固

13、深刻使之在實(shí)驗(yàn)過(guò)程中出現(xiàn)了大量的問(wèn)題。由于課前的充分準(zhǔn)備，加上同學(xué)和老師的幫助，最后順利完成了實(shí)驗(yàn)。 編譯原理的在整個(gè)計(jì)算機(jī)體系課程中有著重要的地位，我現(xiàn)在才剛剛?cè)腴T，所以，我會(huì)在以后的課程和實(shí)驗(yàn)中繼續(xù)努力，學(xué)好編譯原理課程，為以后的學(xué)習(xí)打下基礎(chǔ)。參考文獻(xiàn)1 張素琴.呂映芝等.編譯原理M.清華大學(xué)出版.2004年2王宏.李玉東.李罡.Visual C+實(shí)戰(zhàn)演練M.人民郵電出版.2003年3月3胡元義等.編譯原理實(shí)踐教程M.西安電子科技大學(xué)出版社.2005年7月4 胡倫駿.編譯原理.M.電子工業(yè)出版社，20025 高仲儀.編譯原理及編譯程序構(gòu)造>.M.北京航空航天大學(xué)出版社.1990 源代

14、碼#include<stdio.h>#include<string.h>char *action103="S3#","S4#",NULL, /*ACTION表*/ NULL,NULL,"acc", "S6#","S7#",NULL, "S3#","S4#",NULL, "r3#","r3#",NULL, NULL,NULL,"r1#", "S6#",&q

15、uot;S7#",NULL, NULL,NULL,"r3#", "r2#","r2#",NULL, NULL,NULL,"r2#"int goto1102=1,2, /*QOTO表*/ 0,0, 0,5, 0,8, 0,0, 0,0, 0,9, 0,0, 0,0, 0,0;char vt3='a','b','#' /*存放非終結(jié)符*/char vn2='S','B' /*存放終結(jié)符*/char *LR4="E->

16、;S#","S->BB#","B->aB#","B->b#"/*存放產(chǎn)生式*/int a10;char b10,c10,c1;int top1,top2,top3,top,m,n;void main()int g,h,i,j,k,l,p,y,z,count;char x,copy10,copy110;top1=0;top2=0;top3=0;top=0;a0=0;y=a0;b0='#'count=0;z=0;printf("-編譯原理課程設(shè)計(jì)-n");printf(&qu

17、ot;-許濤-n");printf("-n");printf("-請(qǐng)輸入表達(dá)式-n");doscanf("%c",&c1);ctop3=c1;top3=top3+1;while(c1!='#');printf("步驟t狀態(tài)棧tt符號(hào)棧tt輸入串ttACTIONtGOTOn");doy=z;m=0;n=0; /*y,z指向狀態(tài)棧棧頂*/g=top;j=0;k=0;x=ctop;count+;printf("%dt",count);while(m<=top1)

18、 /*輸出狀態(tài)棧*/printf("%d",am); m=m+1;printf("tt");while(n<=top2) /*輸出符號(hào)棧*/printf("%c",bn); n=n+1;printf("tt");while(g<=top3) /*輸出輸入串*/printf("%c",cg); g=g+1;printf("tt");while(x!=vtj&&j<=2) j+;if(j=2&&x!=vtj) printf("errorn"); return; if(actionyj