詞法分析器課程設(shè)計(jì)

1、編譯原理結(jié)課論文題目： 詞法分析器 作者： 譚敬偉 電話： Email: 教師： 肖少擁 、 吳剛 遞交日期： 2013 年 11 月 28 日目錄摘要2詞法分析3定義：3待分析的簡(jiǎn)單語言的詞法3各種單詞符號(hào)對(duì)應(yīng)的種別碼3詞法分析器設(shè)計(jì)4輸入、預(yù)處理4超前搜索4狀態(tài)轉(zhuǎn)換圖4正規(guī)表達(dá)式與正規(guī)集5分析器的簡(jiǎn)單實(shí)現(xiàn)6分析6詞法分析程序的功能7參考代碼7程序測(cè)試11思考總結(jié)11參考文獻(xiàn)12摘要編譯，簡(jiǎn)單的說，就是把源程序轉(zhuǎn)換為可執(zhí)行程序。從hellow worl說程序運(yùn)行機(jī)制里面簡(jiǎn)單的說明了程序運(yùn)行的過程，以及一個(gè)程序是如何一步步變成可執(zhí)行文件的。在這個(gè)過程中，編譯器做了很多重要的工作。對(duì)于編譯的內(nèi)部

2、實(shí)現(xiàn)，也就是編譯的原理。這篇論文主要說的是編譯器前端，詞法分析器的原理，最后會(huì)給出一個(gè)詞法分析器的簡(jiǎn)單實(shí)現(xiàn)。編譯簡(jiǎn)單的說，就是把源程序轉(zhuǎn)化為另一種形式的程序,而其中關(guān)鍵的部分就是理解源程序所要表達(dá)的意思，才能轉(zhuǎn)化為另一種源程序?？梢杂靡粋€(gè)比喻來說明問題：人A和人B想要交談，但是他們都不知道彼此的語言，這就需要一個(gè)翻譯C，同時(shí)懂得A和B的語言。有了C做中間層，A和B才能正常交流。C的作用就有點(diǎn)像編譯器，它必須能理解源程序所要表達(dá)的意思，才能把信息傳遞給另一個(gè)。編譯器也一樣，它的輸入是語言的源文件（一般可以是文本文件）對(duì)于輸入的文件，首先要分離出這個(gè)輸入文件的每個(gè)元素（關(guān)鍵字、變量、符號(hào)、），然后

3、根據(jù)語言的文法，分析這些元素的組合是否合法，以及這些組合所表達(dá)的意思。程序設(shè)計(jì)語言和自然語言不一樣，都是用符號(hào)來描述，每個(gè)特定的符號(hào)表示特定的意思，而且程序設(shè)計(jì)語言是上下文無關(guān)的。上下文無關(guān)就是某一個(gè)特定語句所要表達(dá)的意思和它所處的上下文沒有關(guān)系，只有它自身決定。這篇論文主要說的就是詞法分析，也就是把輸入的符號(hào)串整理成特定的詞素。詞法分析定義：詞法分析器的功能輸入源程序，按照構(gòu)詞規(guī)則分解成一系列單詞符號(hào)。單詞是語言中具有獨(dú)立意義的最小單位，包括關(guān)鍵字、標(biāo)識(shí)符、運(yùn)算符、界符和常量等待分析的簡(jiǎn)單語言的詞法（1） 關(guān)鍵字：begin if then while do end所有關(guān)鍵字都是小寫。（2）

4、 運(yùn)算符和界符：:=+ * / = = = ; ( ) #（3） 其他單詞是標(biāo)識(shí)符（ID）和整型常數(shù)（NUM），通過以下正規(guī)式定義：ID=letter（letter| digit）*NUM=digit digit *（4） 空格由空白、制表符和換行符組成。空格一般用來分隔ID、NUM,運(yùn)算符、界符和關(guān)鍵字，詞法分析階段通常被忽略。各種單詞符號(hào)對(duì)應(yīng)的種別碼詞法分析器設(shè)計(jì)輸入、預(yù)處理詞法分析器工作的第一步是輸入源程序文本。在許多情況下，為了更好地對(duì)單詞符號(hào)識(shí)別，把輸入串預(yù)處理一下。預(yù)處理主要濾掉空格，跳過注釋、換行符等。超前搜索詞法分析過程中，有時(shí)為了確定詞性，需超前掃描若干個(gè)字符。對(duì)于FORTR

5、AN 語言，關(guān)鍵字不作為保留字，可作為標(biāo)識(shí)符使用， 空格符號(hào)沒有任何意義。為了確定詞性，需超前掃描若干個(gè)字符。在FORTRAN中 1 DO99K=1,10 2 IF(5.EQ.M) I=10 3 DO99K=1.10 4 IF(5)=55這四個(gè)語句都是正確的語句。語句1和2 分別是DO和IF語句，語句3和4是賦值語句。為了正確區(qū)別1和3，2和4語句，需超前掃描若干個(gè)字符。 1 DO99K=1,10 2 IF(5.EQ.M) I=10 3 DO99K=1.10 4 IF(5)=55語句1和3的區(qū)別在于符號(hào)之后的第一個(gè)界符：一個(gè)為逗號(hào)，另一個(gè)為句末符。語句2和4的主要區(qū)別在于右括號(hào)后的第一個(gè)字符：

6、一個(gè)為字母，另一個(gè)為等號(hào)。為了識(shí)別1、2中的關(guān)鍵字，必須超前掃描多個(gè)字符。超前到能夠肯定詞性的地方為止。為了區(qū)別1和3，必須超前掃描到等號(hào)后的第一個(gè)界符處。對(duì)于語句2、4來說，必須超前掃描到與IF后的左括號(hào)相對(duì)應(yīng)的那個(gè)右括號(hào)之后的第一個(gè)字符為止。狀態(tài)轉(zhuǎn)換圖詞法分析器使用狀態(tài)轉(zhuǎn)換圖來識(shí)別單詞符號(hào)。狀態(tài)轉(zhuǎn)換圖是一張有限方向圖。在狀態(tài)轉(zhuǎn)換圖中，有一個(gè)初態(tài)，至少一個(gè)終態(tài)。其中0為初態(tài)，2為終態(tài)。這個(gè)轉(zhuǎn)換圖識(shí)別（接受）標(biāo)識(shí)符的過程是：從初態(tài)0開始，若在狀態(tài)0之下輸入字符是一個(gè)字母，則讀進(jìn)它，并轉(zhuǎn)入狀態(tài)1。在狀態(tài)1之下，若下一個(gè)輸入字符為字母或數(shù)字，則讀進(jìn)它，并重新進(jìn)入狀態(tài)1。一直重復(fù)這個(gè)過程直到狀態(tài)1發(fā)

7、現(xiàn)輸入字符不再是字母或數(shù)字時(shí)（這個(gè)字符也已被讀進(jìn)）就進(jìn)入狀態(tài)2。狀態(tài)2是終態(tài)，它意味著到此已識(shí)別出一個(gè)標(biāo)識(shí)符，識(shí)別過程宣告終止。終態(tài)結(jié)上打個(gè)星號(hào)意味著多讀進(jìn)了一個(gè)不屬于標(biāo)識(shí)符部分的字符，應(yīng)把它退還給輸入口中 。如果在狀態(tài)0時(shí)輸入字符不為“字母”，則意味著識(shí)別不出標(biāo)識(shí)符，或者說，這個(gè)轉(zhuǎn)換圖工作不成功。正規(guī)表達(dá)式與正規(guī)集正規(guī)表達(dá)式是說明單詞的一種重要的表示法(記號(hào))，是定義正規(guī)集的工具。在詞法分析中，正規(guī)表達(dá)式用來描述標(biāo)示符可能具有的形式。定義(正規(guī)式和它所表示的正規(guī)集)：設(shè)字母表為S，1. e和都是S上的正規(guī)式，它們所表示的正規(guī)集分別為e和 ；2. 任何a S，a是S上的一個(gè)正規(guī)式，它所表示的正

8、規(guī)集為a；3. 假定U和V都是S上的正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(U)和L(V)，那么，(U), U|V, UV, U*也都是正規(guī)式,它們所表示的正規(guī)集分別為L(zhǎng)(U), L(U)L(V), L(U)L(V)和(L(U)*；4. 僅由有限次使用上述三步驟而定義的表達(dá)式才是S上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是S上的正規(guī)集。正規(guī)式的運(yùn)算符的“”讀為“或” ,“ ”讀為“連接”；“*”讀為“閉包”(即，任意有限次的自重復(fù)連接)。在不致混淆時(shí)，括號(hào)可省去，但規(guī)定算符的優(yōu)先順序?yàn)椤?”、“)”、“*”、“ ”、“” 。連接符“ ”一般可省略不寫。“*”、“ ”和“” 都是左結(jié)合的。例 令S=

9、a,b， S上的正規(guī)式和相應(yīng)的正規(guī)集的例子有：正規(guī)式 正規(guī)集a aab a,bab ab(ab)(a aa,ab,ba,bba * e ,a,a, 任意個(gè)a的串ba* b, ba, baa, baaa, (ab)* e ,a,b,aa,ab 所有由a和b 組成的串(ab)*(aabb)(ab)* S*上所有含有兩個(gè)相繼的a 或兩個(gè)相繼的b組成 的串定理：若兩個(gè)正規(guī)式U和V所表示的正規(guī)集相同,則說U和V等價(jià),寫作U=V。證明b(ab)*=( ba)*b證明：因?yàn)長(zhǎng)(b(ab)*)=be, ab, abab, ababab, =b, bab, babab, bababab, L(ba)*b) =e

10、, ba, baba, bababa, b =b, bab, babab, bababab, = L(b(ab)*)所以, b(ab)*=( ba)*b設(shè)U，V，W為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律有：(1) UV=VU (交換律)(2) U(VW)=(UV)W (結(jié)合律)(3) U(VW)=(UV)W (結(jié)合律)(4) U(VW)=UVUW (VW)U=VUWU (分配律)(5) eU=U e=U分析器的簡(jiǎn)單實(shí)現(xiàn)雖然說是語法分析器，但實(shí)現(xiàn)的功能很簡(jiǎn)單，只是對(duì)輸入的程序把注釋去掉，其中用到了上面關(guān)于狀態(tài)轉(zhuǎn)換圖部分的知識(shí)。分析一般的程序設(shè)計(jì)語言， 注釋部分的形式為； /* 注釋部分、*/我們的程序總

11、是順序的一個(gè)一個(gè)字符讀取輸入文件的。我們的目的是把注釋部分去掉，那么對(duì)于輸入的字符流，我們只要識(shí)別出“/*”就知道后面的部分是注釋部分，直到識(shí)別輸入流中出現(xiàn)*/為止。對(duì)字符流的處理是一個(gè)一個(gè)進(jìn)行的，每讀入一個(gè)字符，就判斷，如果字符是“/”,就說明后面 的部分可能是注釋，再看下一個(gè)輸入字符，如果是“*”, 就是上面所說的情況：“ /*”那么后面的部分就是注釋部分，然后再用相同的方法找出*/就可以了。這個(gè)識(shí)別的過程就可以用狀態(tài)轉(zhuǎn)換圖來清晰的表示:對(duì)于讀入的每個(gè)符號(hào)都要進(jìn)行判斷，如果是“/”說明后面的部分有可能是注釋，進(jìn)入狀態(tài)1。如果后面的輸入是“*”那么就可以確定以后的內(nèi)容為注釋內(nèi)容，如果后面的輸

12、入不是*，說明后面的內(nèi)容不是注釋，前面出現(xiàn)的/可能是做除號(hào)使用，如“5/3”其實(shí)上面的流程圖也就對(duì)應(yīng)了程序?qū)崿F(xiàn)的邏輯，可以用switch-case 來實(shí)現(xiàn)，對(duì)于每個(gè)輸入，判斷后跳轉(zhuǎn)到相應(yīng)的狀態(tài)，然后繼續(xù)判斷。下面是程序偽代碼：while(ch=getchar()!=EOF)switch(state)case 1 :if ch=/,state=2,break;case 2: if ch=*,state=3else state=1;break;case 3:.case 4:.詞法分析程序的功能輸入：所給文法的源程序字符串。輸出：二元組（syn，token或sum）構(gòu)成的序列。其中：syn為單詞種別

13、碼；token為存放的單詞自身字符串；sum為整型常數(shù)。參考代碼#include#include#include #include char prog80,token8;char ch;int syn,p,m=0,n,row,sum=0;char *rwtab6=begin,if,then,while,do,end; void scaner() /* 共分為三大塊，分別是標(biāo)示符、數(shù)字、符號(hào)，對(duì)應(yīng)下面的 if else if 和 else */ for(n=0;n=a&ch=A&ch=0&ch=a&ch=A&ch=Z) tokenm+=ch; ch=progp+; tokenm+=0; p-;

14、syn=10; for(n=0;n=0&ch=0&ch32767) syn=-1; else switch(ch) /其他字符 case) syn=21; tokenm+=ch; else if(ch=) syn=22; tokenm+=ch; else syn=23; p-; break; case:m=0;tokenm+=ch; ch=progp+; if(ch=) syn=24; tokenm+=ch; else syn=20; p-; break; case:m=0;tokenm+=ch; ch=progp+; if(ch=) syn=18; tokenm+=ch; else syn=

15、17; p-; break; case*:syn=13;token0=ch;break; case/:syn=14;token0=ch;break; case+:syn=15;token0=ch;break; case-:syn=16;token0=ch;break; case=:syn=25;token0=ch;break; case;:syn=26;token0=ch;break; case(:syn=27;token0=ch;break; case):syn=28;token0=ch;break; case#:syn=0;token0=ch;break; casen:syn=-2;bre

16、ak; default: syn=-1;break; int main() p=0; row=1; printf(Please input string:n); do ch=getchar(); progp+=ch; while(ch!=#); p=0; do scaner(); switch(syn) case 11: printf(%d,%d)n,syn,sum); break; case -1: printf(Error in row %d !,row); break; case -2: row=row+;break; default: printf(%d,%s)n,syn,token)

17、;break; while (syn!=0);程序測(cè)試輸入 begin x:=9; if x0 then x:=2*x+1/3; end#調(diào)試通過，程序截圖:思考總結(jié)在該實(shí)驗(yàn)的設(shè)計(jì)中，遇到了一些問題。特別是最后調(diào)試的時(shí)候，總是出不來答案，最后通過同學(xué)的幫助總算解決了，更使我意識(shí)到計(jì)算機(jī)的嚴(yán)謹(jǐn)行，就因?yàn)橐粋€(gè)%d和%s的關(guān)系，就是出不來。使我知道以后，一定要嚴(yán)謹(jǐn)，一定要仔細(xì)。 詞法分析是夠潮編譯器的起始階段，也是相應(yīng)比較簡(jiǎn)單的一個(gè)環(huán)節(jié)。詞法分析的主要任務(wù)是：根據(jù)構(gòu)造的狀態(tài)轉(zhuǎn)換圖，從左到右逐個(gè)字符的對(duì)源程序進(jìn)行掃描，識(shí)別源程序中具有獨(dú)特含義的最小語法單位-符號(hào)或者單詞，如變量標(biāo)識(shí)符，關(guān)鍵字，常量，運(yùn)算符，界符等。然后將提取的標(biāo)識(shí)符以內(nèi)碼的形式表示