詞法分析器的實現

開篇

編譯，簡單的說，就是把源程序轉換為可執行程序。從hello world 說程序運行機制里面簡單的說明了程序運行的過程，以及一個程序是如何一步步變成可執行文件的。在這個過程中，編譯器做了很多重要的工作。對底層該興趣的我，自然的，也就迫切想搞清楚編譯的內部實現，也就是編譯的原理。

這篇文章主要說的是編譯器前端，詞法分析器的原理，最后會給出一個詞法分析器的簡單實現。

介紹

編譯簡單的說，就是把源程序轉化為另一種形式的程序,而其中關鍵的部分就是理解源程序所要表達的意思，才能轉化為另一種源程序。

可以用一個比喻來說明問題：人A和人B想要交談，但是他們都不知道彼此的語言，這就需要一個翻譯C，同時懂得A和B的語言。有了C做中間層，A和B才能正常交流。C的作用就有點像編譯器，它必須能理解源程序所要表達的意思，才能把信息傳遞給另一個。

編譯器也一樣，它的輸入是語言的源文件（一般可以是文本文件）對于輸入的文件，首先要分離出這個輸入文件的每個元素（關鍵字、變量、符號、、）

然后根據語言的文法，分析這些元素的組合是否合法，以及這些組合所表達的意思。

程序設計語言和自然語言不一樣，都是用符號來描述，每個特定的符號表示特定的意思，而且程序設計語言是上下文無關的。上下文無關就是某一個特定語句所要表達的意思和它所處的上下文沒有關系，只有它自身決定。

這篇博文主要說的就是詞法分析，也就是把輸入的符號串整理成特定的詞素。

詞法分析

定義：

詞法分析器的功能輸入源程序，按照構詞規則分解成一系列單詞符號。單詞是語言中具有獨立意義的最小單位，包括關鍵字、標識符、運算符、界符和常量等

(1) 關鍵字是由程序語言定義的具有固定意義的標識符。例如，Pascal 中的begin，end，if，while都是保留字。這些字通常不用作一般標識符。

(2) 標識符用來表示各種名字，如變量名，數組名，過程名等等。

(3) 常數常數的類型一般有整型、實型、布爾型、文字型等。

(4) 運算符如+、-、*、/等等。

(5) 界符如逗號、分號、括號、等等。

輸出：

詞法分析器所輸出單詞符號常常表示成如下的二元式：

(單詞種別，單詞符號的屬性值)

單詞種別通常用整數編碼。標識符一般統歸為一種。常數則宜按類型（整、實、布爾等）分種。關鍵字可將其全體視為一種。運算符可采用一符一種的方法。界符一般用一符一種的方法。對于每個單詞符號，除了給出了種別編碼之外，還應給出有關單詞符號的屬性信息。單詞符號的屬性是指單詞符號的特性或特征。

示例：

比如如下的代碼段：

while(i>=j) i--

經詞法分析器處理后，它將被轉為如下的單詞符號序列：

<while, _>

<(, _>

<id, 指向i的符號表項的指針>

<>=, _>

<id, 指向j的符號表項的指針>

<), _>

<id, 指向i的符號表項的指針>

<--, _>

<;, _>

詞法分析分析器作為一個獨立子程序

詞法分析是編譯過程中的一個階段，在語法分析前進行。詞法分析作為一遍，可以簡化設計，改進編譯效率，增加編譯系統的可移植性。也可以和語法分析結合在一起作為一遍，由語法分析程序調用詞法分析程序來獲得當前單詞供語法分析使用。

詞法分析器設計

輸入、預處理

詞法分析器工作的第一步是輸入源程序文本。在許多情況下，為了更好地對單詞符號識別，把輸入串預處理一下。預處理主要濾掉空格，跳過注釋、換行符等。

超前搜索

詞法分析過程中，有時為了確定詞性，需超前掃描若干個字符。

對于FORTRAN 語言，關鍵字不作為保留字，可作為標識符使用，空格符號沒有任何意義。為了確定詞性，需超前掃描若干個字符。

在FORTRAN中

1 DO99K=1,10

2 IF(5.EQ.M) I=10

3 DO99K=1.10

4 IF(5)=55

這四個語句都是正確的語句。語句1和2 分別是DO和IF語句，語句3和4是賦值語句。為了正確區別1和3，2和4語句，需超前掃描若干個字符。

1 DO99K=1,10 2 IF(5.EQ.M) I=10

3 DO99K=1.10 4 IF(5)=55

語句1和3的區別在于符號之后的第一個界符：一個為逗號，另一個為句末符。語句2和4的主要區別在于右括號后的第一個字符：一個為字母，另一個為等號。為了識別1、2中的關鍵字，必須超前掃描多個字符。超前到能夠肯定詞性的地方為止。為了區別1和3，必須超前掃描到等號后的第一個界符處。對于語句2、4來說，必須超前掃描到與IF后的左括號相對應的那個右括號之后的第一個字符為止。

狀態轉換圖

詞法分析器使用狀態轉換圖來識別單詞符號。狀態轉換圖是一張有限方向圖。在狀態轉換圖中，有一個初態，至少一個終態。

其中0為初態，2為終態。這個轉換圖識別（接受）標識符的過程是：從初態0開始，若在狀態0之下輸入字符是一個字母，則讀進它，并轉入狀態1。在狀態1之下，若下一個輸入字符為字母或數字，則讀進它，并重新進入狀態1。一直重復這個過程直到狀態1發現輸入字符不再是字母或數字時（這個字符也已被讀進）就進入狀態2。狀態2是終態，它意味著到此已識別出一個標識符，識別過程宣告終止。終態結上打個星號意味著多讀進了一個不屬于標識符部分的字符，應把它退還給輸入口中。如果在狀態0時輸入字符不為“字母”，則意味著識別不出標識符，或者說，這個轉換圖工作不成功。

正規表達式與正規集

正規表達式是說明單詞的一種重要的表示法(記號)，是定義正規集的工具。在詞法分析中，正規表達式用來描述標示符可能具有的形式。

定義(正規式和它所表示的正規集)：

設字母表為S，

1. e和?都是S上的正規式，它們所表示的正規集分別為{e}和{ }；

2. 任何a? S，a是S上的一個正規式，它所表示的正規集為{a}；

3. 假定U和V都是S上的正規式，它們所表示的正規集分別為L(U)和L(V)，那么，(U), U|V, U·V, U*也都是正規式,它們所表示的正規集分別為L(U), L(U)èL(V), L(U)L(V)和(L(U))*；

4. 僅由有限次使用上述三步驟而定義的表達式才是S上的正規式，僅由這些正規式所表示的字集才是S上的正規集。

正規式的運算符的“?”讀為“或” ,“· ”讀為“連接”；“*”讀為“閉包”(即，任意有限次的自重復連接)。

在不致混淆時，括號可省去，但規定算符的優先順序為“(”、“)”、“*”、“· ”、“?” 。連接符“· ”一般可省略不寫。

“*”、“· ”和“?” 都是左結合的。

例令S={a,b}， S上的正規式和相應的正規集的例子有：

正規式正規集

a 　　　　　{a}

a?b {a,b}

ab {ab}

(a?b)(a {aa,ab,ba,bb}

a * {e ,a,a, ……任意個a的串}

ba* {b, ba, baa, baaa, …}

(a?b)* {e ,a,b,aa,ab ……所有由a和b

組成的串}

(a?b)*(aa?bb)(a?b)* {S*上所有含有兩個相繼的a

或兩個相繼的b組成的串}

定理：若兩個正規式U和V所表示的正規集相同,則說U和V等價,寫作U=V。

證明b(ab)*=( ba)*b

證明：因為L(b(ab)*)={b}{e, ab, abab, ababab, …}

={b, bab, babab, bababab, …}

L((ba)*b) ={e, ba, baba, bababa, …}{b}

={b, bab, babab, bababab, …}

= L(b(ab)*)

所以, b(ab)*=( ba)*b

設U，V，W為正規式，正規式服從的代數規律有：

(1) U?V=V?U (交換律)

(2) U?(V?W)=(U?V)?W (結合律)

(3) U(VW)=(UV)W (結合律)

(4) U(V?W)=UV?UW (V?W)U=VU?WU (分配律)

(5) eU=U e=U

分析器的簡單實現

上文主要介紹了詞法分析的一些相關的知識，而對詞法分析器的具體實現還沒有具體提到，為了能更好的理解詞法分析，我寫了一個簡單的詞法分析器。

雖然說是語法分析器，但實現的功能很簡單，只是對輸入的程序把注釋去掉，其中用到了上面關于狀態轉換圖部分的知識。

分析：

一般的程序設計語言，注釋部分的形式為；

/* 注釋部分、、、、*/

我們的程序總是順序的一個一個字符讀取輸入文件的。我們的目的是把注釋部分去掉，那么對于輸入的字符流，我們只要識別出“/*”就知道后面的部分是注釋部分，直到識別輸入流中出現"*/"為止。

對字符流的處理是一個一個進行的，每讀入一個字符，就判斷，如果字符是“/”,就說明后面的部分可能是注釋，再看下一個輸入字符，如果是“*”, 就是上面所說的情況：“ /*”那么后面的部分就是注釋部分，然后再用相同的方法找出"*/"就可以了。

這個識別的過程就可以用狀態轉換圖來清晰的表示:

對于讀入的每個符號都要進行判斷，如果是“/”說明后面的部分有可能是注釋，進入狀態1。如果后面的輸入是“*”那么就可以確定以后的內容為注釋內容，如果后面的輸入不是"*"，說明后面的內容不是注釋，前面出現的"/"可能是做除號使用，如“5/3”

其實上面的流程圖也就對應了程序實現的邏輯，可以用switch-case 來實現，對于每個輸入，判斷后跳轉到相應的狀態，然后繼續判斷。

下面是程序偽代碼：

while((ch=getchar())!=EOF)

　　switch(state)

　　　　case 1 :if ch=="/",state=2,break;

　　　　case 2: if ch=="*",state=3

　　　　　　　　else state=1;break;

　　　　case 3:..........

　　　　case 4:..........

詞法分析器

這個程序比較簡單，就不給出源代碼了。接下來是一個簡單的詞法分析器的代碼，可以實現對關鍵字（如 while end if 等），對數字的識別，去掉空格符等。

下面是這個分析器的功能：

1、 待分析的簡單語言的詞法

（1）關鍵字：

begin if then while do end

所有關鍵字都是小寫。

（2）運算符和界符：

:= + – * / < <= <> > >= = ; ( ) #

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

ID=letter（letter| digit）*

NUM=digit digit *

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

2、 各種單詞符號對應的種別碼

詞法分析程序的功能

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

輸出：二元組（syn，token或sum）構成的序列。

其中：syn為單詞種別碼；

token為存放的單詞自身字符串；

sum為整型常數。

下面是程序源代碼，基于上面的討論，應該比較好了解了。

#include<stdio.h>
#include<string.h>
#include<iostream.h>
char prog[80],token[8];
char ch;
int syn,p,m=0,n,row,sum=0;
char *rwtab[6]={"begin","if","then","while","do","end"};
 
void scaner()
{
    /*
        共分為三大塊，分別是標示符、數字、符號，對應下面的 if   else if  和 else 
        
    
    */ 
    for(n=0;n<8;n++) token[n]=NULL;
    ch=prog[p++];
    while(ch==' ')
    {
        ch=prog[p];
        p++;
    }
    if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))  //可能是標示符或者變量名 
    {
        m=0;
        while((ch>='0'&&ch<='9')||(ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))
        {
            token[m++]=ch;
            ch=prog[p++];
        }
        token[m++]='\0';
        p--;
        syn=10;
        for(n=0;n<6;n++)  //將識別出來的字符和已定義的標示符作比較， 
            if(strcmp(token,rwtab[n])==0)
            {
                syn=n+1;
                break;
            }
    }
    else if((ch>='0'&&ch<='9'))  //數字 
    {
        {
            sum=0;
            while((ch>='0'&&ch<='9'))
            {
                sum=sum*10+ch-'0';
                ch=prog[p++];
            }
        }
        p--;
        syn=11;
        if(sum>32767)
            syn=-1;
    }
    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=23;
                p--;
            }
            break;
        case'>':m=0;token[m++]=ch;
            ch=prog[p++];
            if(ch=='=')
            {
                syn=24;
                token[m++]=ch;
            }
            else
            {
                syn=20;
                p--;
            }
            break;
        case':':m=0;token[m++]=ch;
            ch=prog[p++];
            if(ch=='=')
            {
                syn=18;
                token[m++]=ch;
            }
            else
            {
                syn=17;
                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=25;token[0]=ch;break;
        case';':syn=26;token[0]=ch;break;
        case'(':syn=27;token[0]=ch;break;
        case')':syn=28;token[0]=ch;break;
        case'#':syn=0;token[0]=ch;break;
        case'\n':syn=-2;break;
        default: syn=-1;break;
    }
}

int main()
{
    p=0;
    row=1;
    cout<<"Please input string:"<<endl;
    do
    {
        cin.get(ch);
        prog[p++]=ch;
    }
    while(ch!='#');
    p=0;
    do
    {
        scaner();
        switch(syn)
        {
        case 11: cout<<"("<<syn<<","<<sum<<")"<<endl; break;  
        case -1: cout<<"Error in row "<<row<<"!"<<endl; break;
        case -2: row=row++;break;
        default: cout<<"("<<syn<<","<<token<<")"<<endl;break;
        }
    }
    while (syn!=0);
}

改程序在C-free5上調試通過

下面是程序截圖:

小結

這里主要說的是編譯器中的詞法分析，還介紹了詞法分析的一些相關知識，最后給出了一個很簡單的詞法分析器的實現。

參看資料：編譯原理

如有轉載請注明出處：http://www.rzrgm.cn/yanlingyin/

一條魚、尹雁鈴@ 博客園 2012-17

E-mail：yanlingyin@yeah.net

posted @ 2012-04-17 12:25 Geek_Ling 閱讀(132688) 評論(20) 收藏舉報

刷新頁面返回頂部

Geek_Ling

Get busy living, Or get busy dying.

詞法分析器的實現

公告