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

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

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

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

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

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

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

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

8、為驅(qū)動程序。對所有的LR分析器總控程序都是相同的。(2)分析表或分析函數(shù)，不同的文法分析表將不同，同一個文法采用的LR分析器不同時，分析表將不同，分析表又可以分為動作表（ACTION）和狀態(tài)轉(zhuǎn)換（GOTO）表兩個部分，它們都可用二維數(shù)組表示。(3)分析棧，包括文法符號棧和相應(yīng)的狀態(tài)棧，它們均是先進后出棧。分析器的動作就是由棧頂狀態(tài)和當前輸入符號所決定。 3.6 LR分析器結(jié)構(gòu)圖輸入串a(chǎn)1a2aiai+1an#Sm。S1S0Xn。X1#輸出總控程序Sp 分析表ACTION表GOTO 表 圖3-1 圖3-1(1)在總控程序的控制下，從左到右掃描輸入串根據(jù)分析棧和輸入符號的情況，查分析表確定分析動作

9、；(2) 分析表是LR分析器的核心，它跟文法有關(guān)，它包括動作表(Action)和狀態(tài)轉(zhuǎn)換表(Goto)兩部分，總控程序據(jù)分析表確定分析動作；(3) 分析棧包括文法符號棧Xi和相應(yīng)的狀態(tài)棧Si兩部分(狀態(tài)是指能識別活前綴的自動機狀態(tài))，LR分析器通過判斷棧頂元素和輸入符號查分析表確定下步分析動作。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. 求項目集合 圖3-22. 根據(jù)項目集合得到分析表如下表3-1狀態(tài) ACTION GOTOabcde#SA0S2S311acc2S543S764S85S9r56S107r5S118r19r310r211r44、 測試運行4.1 程序運行截圖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)過這個實驗的練習(xí)，通過對程序的分析，讓我進一步了解LR（1）算法的思想以及它的進一步程序?qū)崿F(xiàn)，讓我對它的了解從簡單的理

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

13、深刻使之在實驗過程中出現(xiàn)了大量的問題。由于課前的充分準備，加上同學(xué)和老師的幫助，最后順利完成了實驗。 編譯原理的在整個計算機體系課程中有著重要的地位，我現(xiàn)在才剛剛?cè)腴T，所以，我會在以后的課程和實驗中繼續(xù)努力，學(xué)好編譯原理課程，為以后的學(xué)習(xí)打下基礎(chǔ)。參考文獻1 張素琴.呂映芝等.編譯原理M.清華大學(xué)出版.2004年2王宏.李玉東.李罡.Visual C+實戰(zhàn)演練M.人民郵電出版.2003年3月3胡元義等.編譯原理實踐教程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è)計-n");printf(&qu

17、ot;-許濤-n");printf("-n");printf("-請輸入表達式-n");doscanf("%c",&c1);ctop3=c1;top3=top3+1;while(c1!='#');printf("步驟t狀態(tài)棧tt符號棧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) /*輸出符號棧*/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