一種簡單的編譯器的設計

摘要：基于編譯理論與虛擬機技術，經過詞法分析、語法分析、語義分析等過程，設計一個簡單的編譯器，將某一種源程序編譯成目標程序，以驗證結果的正確性。

關鍵詞：編譯器；詞法分析；語法分析；語義分析

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)33-1508-03

The Design of a Simple Compiler

CHENG Hua

(Jiangsu Food Science College， Huaian 223003， China)

Abstract: Based on compile theory and Virtual Machine technology，to transfer source program into destination program by Lexical analyse， Parse， Semantic analyse， and to test and verify the results.

Key words: compiler; lexical analyse; parse; semantic analyse

1 設計背景

目前，計算機無紙化考試系統的應用越來越廣，選擇題、判斷題的自動評分基本完善，但對程序修改題、編程題等考題來說，運用簡單地看結果或指定行、段等辦法評分，不能從根本上達到客觀、公正地評閱考生答案。要想讓計算機評分具有智能化，就必須讓計算機具備“思想”，即讓評分系統能“看懂”考生答案，能“感受”設計成果的優越之處與不足所在，能給“過程分”及“設計創新分”，而絕不單純依賴“運行結果”。本文以此為切入點，基于編譯理論與虛擬機技術，自主設計有限元編譯系統，分課程、分模塊，能自行分析、編譯考生答案（如程序代碼），進而判斷其正確性、合理性及優越性。

2 編譯程序的一般結構

編譯程序結構框圖如圖1。

3 編譯器的設計

3.1 建立符號表及其管理程序

建立符號表，收錄某種語言（C、PASCAL等）的所有字符集，允許在編譯的各個階段插入或查找名字的相關信息，并且能夠反映出名字所在的位置，編制相應的程序來實現對字符表的各種操作，主要操作有：查找操作、插入操作、定位操作、重定位操作。

3.2 建立一個詞法分析器

圖1

核心技術是處理單詞符號的種類及內部的編碼（需要設計翻譯表）、行計數器等，把詞法分析器作為語法分析器調用的函數，詞法分析器以二進制的形式輸出單詞符號的類別編碼和屬性值。詞法分析器依據源語言的構詞規則對源語言進行分析，依次讀入原程序中的每個字符，對構成原程序的字符串進行分解，識別出每個具有獨立意義的字符串（相對記號叫做單詞），為其構造記號，形成記號流，如果符號表中沒有各記號對應的單詞，則把單詞添加到符號表中，添加時為記號增加一個屬性值即一個指針，指向符號表中該記號對應的單詞。在詞法分析中，還進行詞法檢查。如果詞法分析器從源程序讀入不合法的字符要做錯誤處理，顯示或打印錯誤信息，并跳過這個字符，繼續識別和分析下一個字符。

3.3 建立一個語法分析器

先要消除文法中的左遞規，從而采用預測分析的方法實現一個語法分析器。把語法分析器設計成層次結構，它把記號流按語言的語法結構層次分組，以形成語法短語，源程序的語法短語用分析樹表示。然后根據源語言的語法規則進行語法分析，從源程序記號序列中識別出各類語法成分，同時進行語法檢查，為語義分析和代碼生成做準備。在分析過程中，分析器采用自頂向下的方法為詞法分析器生成的記號序列建立分析樹，驗證這個記號序列是不是該語言的一個句子，若是，則輸出該句子的分析樹，若不是，則表明輸入的記號序列中存在錯誤，需要報告錯誤的性質和位置。

3.4 建立一個語義分析器

該部分要對語句的意義進行檢查，以保證程序各部分能夠有機的結合在一起，并為以后生成目標代碼收集必要的信息。語義分析使用語法分析確定的層次結構來表示各語法成分（比如表達式和語句等），依據源語言的語義規則進行工作。其中一個重要的任務是類型檢查，按照語言的類型檢查規則檢查每個運算符相關的運算對象，看其類型是否一致、合法，如果類型不一致則進行類型轉換，可以做顯示或隱式轉換。

3.5 中間代碼生成及優化

經過詞法、語法、語義分析（這三個階段為分析階段）后，進入綜合階段。這個階段的任務是根據所制定的源語言到目標語言的對應關系，對分析階段所產生的中間形式進行綜合加工，從而得到與源程序等價的目標程序。經過語法分析和語義分析后將源程序生成一種中間表示形式，也就是中間代碼，然后對該中間代碼進行優化，使之占用內存少、運行快，從優化的中間代碼生成優化的目標代碼。

3.6 錯誤處理

在編譯的各個階段都可能檢測到源程序中的錯誤，發現錯誤則要向用戶報告，并做適當的處理，使編譯繼續下去，以便對源程序中可能存在的其它錯誤進行檢查。

4 編譯程序的實現

本文僅以詞法分析為例，給出詞法分析程序的設計過程。

4.1 待分析的簡單語言的詞法

1) 關鍵字：為了簡單起見，僅取5個關鍵字 begin、if、while、do、end，所以的關鍵字均為小寫。

2) 運算符和界符：:: = + - * /〈〈=〈 〉〉〉== ; ( ) #

3) 其他單詞是標識符（ID）和整型常數（NUM），通過以下正規式定義：

ID=letter(letter|digit)*

NUM=digitdigit*

4) 空格由空白、制表符和換行符組成，一般用來分隔ID、NUM、運算符和關鍵字，詞法分析階段通常被忽略。

4.2 為上述各種單詞和符號設置對應的種別碼

4.3 詞法分析程序的功能

輸入：所給文法的源程序字符串。

輸出：二元組（syn，token或sum）構成的序列。其中，syn為單詞種別碼，token為存放的單詞自身字符串。

4.4 詞法分析程序的算法思想

算法的基本任務是從字符串表示的源程序中識別出具有獨立意義的單詞符號，其基本思想是根據掃描到單詞符號的第一個字符的種類，拼出相應的單詞符號。部分源代碼如下：

#include ＜stdio.h＞

#include ＜string.h＞

char prog[80]，token[8];

int typenn[6]={1，2，3，4，5，6};

char ch;

int syn，p=0，m=0，n=0，sum=0;

char *rwtab[6]={\"begin\"，\"if\"，\"then\"，\"while\"，\"do\"，\"end\"};

scaner()

{for (n=0;n＜8;n++)token[n]='\\0';

ch=prog[p++];

while (ch=='') ch=prog[p++];

m=0;

if (ch＜='z'ch＞='a'||ch＜='Z'ch＞='A')

{while (ch＜='z'ch＞='a'||ch＜='Z'ch＞='A'||ch＞='0'ch＜='9')

{token[m++]=ch;ch=prog[p++];}

m--;token[m]='\\0'; p--; syn=10;

for(n=0;n＜6;n++)

if (strcmp(token，rwtab[n])==0)

{syn=typenn[n]; break;}

}

else

if (ch＞='0'ch＜='9')

{while (ch＞='0'ch＜='9')

{sum=sum*10+ch-'0';ch=prog[p++];}

p--; syn=11;}

else

switch(ch)

{case '＜': m=0;

token[m++]=ch;

ch=prog[p++];

if (ch=='＞')

{syn=21; token[m++]=ch; }

else

if (ch=='=')

{syn=22; token[m++]=ch;}

else

{syn=20; p--;}

break;

……

case '+': syn=13; token[0]=ch; break;

case '-': syn=14; token[0]=ch; break;

case '*': syn=15; token[0]=ch; break;

case '/': syn=16; token[0]=ch; break;

case '#': syn=0; token[0]=ch; break;

default:syn=-1;

}}

main()

{

p=0;

printf(\"\ please input string:\\");

while ((ch=getchar())!='#')prog[p++]=ch;

p=0;

do

{ scaner();

switch(syn)

{case 11:printf(\"%d，%d\\"，sum，syn);break;

case -1:printf(\"\\error!\\");break;

default:

printf(\"%s，%d\\"，token，syn);

}

}while (syn!=0);

}

5 結束語

本文說明了一種簡單的編譯器的設計及實現方法，特別是對詞法分析程序進行了較深入的剖析。利用此思想及方法，生成了C語言的編譯器，對PASCAL、BASIC等語言編譯器的設計，也具有一定的借鑒作用。

參考文獻：

[1] Wilhelm R， Maurer D. Compiler Design[M]. Addison-Wesley Pub.Co.， 1995.

[1] 張素芹，呂映芝， 等. 編譯原理[M]. 2版. 北京：清華大學出版社，2006.

[2] 胡倫俊，徐蘭芳， 等. 編譯原理[M]. 2版. 北京：電子工業出版社，2007.

[3] Dick Grune，Henri E.Bal等. 現代編譯程序設計[M]. 北京：人民郵電出版社，2003.

[4] Steven S. Muchnic. 高級編譯器設計與實現[M]. 北京：機械工業出版社，2003.