本篇內容

• 介紹Lex的基本原理介紹Lex檔案格式
• 基礎Lex程式編寫
  • 範例:DNA字母統計
• 介紹Lex程式的編譯與執行

Lex介紹

Lex代表Lexical Analyzer，是一種詞法分析的工具。其主要的功能是識別字符序列中的詞彙模式，並為其做token(可以把它想成是一種標籤)。當Lex接收到一段字符序列時，會一次讀取一個字元，並與已定義的詞彙模式進行比對，直到找到一個匹配的模式。成功匹配後，Lex便會為這個字詞加上一個token，並執行與此詞彙模式相對應的程序。若是沒有匹配的詞彙模式，Lex將會停止進一步的處理，並顯示錯誤訊息。

Lex檔案初探 - 格式介紹

接著，我們來看看lex檔案中的語法架構。

Lex檔案的結尾副檔名為.l，主要分成以下三個區塊：

... Definitions ...
%%
... Rules ...
%%
... Subroutines ...

Definitions

定義的區塊主要含有以下內容

1. C語言的定義或宣告

   通常在整個檔案的最頂端，用來匯入一些資料庫或是標頭檔。
   這部分需要用%{與%}包起來。

2. 起始狀態的定義

   在一份文件中，可能在不同的區塊會有不同的格式，因此需要定義一開始要以甚麼模式開始讀取檔案。若只有一種狀態，則此處不須額外定義。

3. 特定記號的格式定義

   若是在文件中，有一種類型的字詞出現頻率很高，可以在這裡為其命名(有點像幫變數命名的感覺)。之後在其他部分，可以直接使用。

Rules

這裡主要列出lex的regular expressions以及相對應的操作。也就是說，在讀取檔案中，偵測到指定樣式的字詞時，該如何標記token，供後續yacc的規則匹配。

在語法上，要注意以下幾點：

1. 每一種不同的樣式(pattern)需要列在該行的最前面
2. 樣式跟後續的操作函式需要以空白隔開
3. 若該操作函式有複數行C語言，則應以大括號包起來

Subroutines

在完成整個檔案的讀取後，如果需要進行後續的流程，則可以在此定義。

範例 - DNA字母統計

說明

給定一段DNA核酸序列(由A, T, C, G組成)，試著計算各個字母(含氮鹼基)的數量。

程式實作

Definitions

在這個範例中，我們需要定義變數來記錄各種字母的數量，故我們在此定義四個全域變數。

%{
    int numA, numT, numC, numG; 
%}

Rules

當我們讀取到字母的時候，要將對應的變數加1。

若是檔案中出現其他字母時，我們則直接忽略，不進行任何處理。

%%

A    { numA++; }
T    { numT++; }
C    { numC++; }
G    { numG++; }
.    { ; }  

在lex中，我們使用 . 來表示其他所有情況。所以，該規則應該列在所有其他規則之後，不然程式不會執行該規則之後的所有規則判斷。

Subroutines

我們將主程式寫在這裡。

在讀取檔案後，呼叫lex來執行數量統計，最後印出統計結果。

%%

int yywrap(void) {
    return 1;
}

int main(void) {
    const char* sFile = "file.txt";
    FILE* fp = fopen(sFile, "r");
    if (fp == NULL)
    {
        printf("cannot open %s\n", sFile);
        return -1;
    }
    yyin = fp;
    yylex();
    printf("Counter :\nA: %d\nT: %d\nC: %d\nG: %d\n", numA, numT, numC, numG);
    return 0;
}

在這個部分，出現了一個lex自定義的變數yyin，與一個函式yylex()。

yyin是lex所要讀取的檔案，type為FILE*。在本範例中，檢查完檔案是否可以開啟之後，便將yyin指向該檔案。

yylex()則是呼叫lex的function，主程式運行至此便開始讀取檔案或文字。

最後則是另一個lex自定義的function - yywrap()。在 yylex() 讀取完成後，會呼叫此函式，可以在這裡定義後續的執行動作。由於我們讀取完便沒有其他動作了，故直接return。這裡要注意的是，若不再繼續執行lex，返回值預設為1；若要繼續使用lex，則返回0。yywrap()的用法，我們之後會再提到。

💡 部分的編譯器不需要特別定義yywrap，預設即為return 1。

完整程式碼

以下的內容在lex檔案中，檔案命名為lex.l。

%{
    int numA, numT, numC, numG; 
%}

%%

A    { numA++; }
T    { numT++; }
C    { numC++; }
G    { numG++; }
.    { ; } 

%%

int yywrap(void) {
    return 1;
}

int main(void) {
    const char* sFile = "file.txt";
    FILE* fp = fopen(sFile, "r");
    if (fp == NULL)
    {
        printf("cannot open %s\n", sFile);
        return -1;
    }
    yyin = fp;
    yylex();
    printf("Counter :\nA: %d\nT: %d\nC: %d\nG: %d\n", numA, numT, numC, numG);
    return 0;
}

程式編譯與執行

接下來，我們要進行程式的編譯。編譯的方法如下。

flex lex.l
g++ -c lex.yy.c -o main

首先，我們用flex對lex.l編譯，並產生一個C檔案，名稱為lex.yy.c。如此一來，這個檔案便可以用C語言編譯器進行編譯了。使用C++的編譯器對此檔案進行編譯後，即可產生一個執行檔。

程式的執行則與一般的C++程式相同：

#linux
./main
#windows
./main.exe

執行完畢後，便能得到各字母的數量統計了。

執行結果

輸入內容

AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT

輸出結果

Counter :
A: 15
T: 3
C: 11
G: 3

結語

我們今天介紹了Lex的基本原理與檔案格式，並撰寫了第一份lex的程式。

接下來，我們要來看更多Lex的單詞辨識功能。

參考資料

• Levine, John R., Tony Mason and Doug Brown [1992]. Lex & Yacc. O’Reilly & Associates, Inc. Sebastopol, California.