2012年9月8日 星期六

lex 的使用

lex 能用來實做詞法分析器(lexical analyzer)
算是被蠻算廣泛使用的「詞法分析器產生器」
詞法分析器,簡單的說
其功能是將字串轉換為一個個的標記(token)

例如
int  A,B;
會被 lex 切割為
int  A,B;
如上所示,不同顏色分隔的區域就是不同 token

要使用 lex 將字串轉換為一個個的 token
使用者必須提供 lex
  1. 想要分析的(一個或以上的)正規表示法 (regex)
  2. 每種表示法的對應的動作
而若要描述上述兩者,必須撰寫 lex 描述檔,基本的 lex 的語法如下
(另外一提,lex 描述檔的附檔通常是 .l)


%{
一些定義,像是 include stdio.h
%}
%%
正規表示法 1 {動作 1}
正規表示法 2 {動作 2}
...
正規表示法 N {動作 N}
%%
這裡是自訂的 C code
可以將自己寫的 main() 放在這裡

注意程式中的 %% 是作為分隔用
而首段中  %{ %} 包住的區域會被放入產出來的 C code 的頂部
而最後一段會被放到 C code 的尾部
這個說明在 wikipedia 中文頁面 就有寫了
基礎的語法在 wiki 上面也有寫,作者就不多說明了

中間「動作 k」的部份便是 lex 找到符合第 k 條 regex 時所執行的的程式碼
以 C code 表示,不過有一些特殊的全域變數可以用(如 yytext,見後文)
附帶說明,如果找到多個允許的 regex 時,lex 會選擇其中一個
選擇的篩選順序如下,這些條件會唯一決定符合的字串:
  1. 長度長的優先
  2. 規則先在 lex 檔中出現的優先
lex 會將以上 lex 描述檔編譯為一份 C code
編譯後的檔案會包含下面這些比較重要的函數/變數

函數/變數 說明
int yylex() 最重要的函數,即是分析器函數
char *yytext 與當前正規表示法對應的字串
FILE *yyin lex 從這個 file pointer 讀取字元

lex 產生出來的 yylex() 函數流程大約像這樣
(當然實際的 code 不一定是這樣,但就我觀察到的流程應該是差不多的)
至於實際上如何的就別問了,因為作者也看不懂/懶得看


int yylex() {
 while (1) {
  /* 這個 switch 之前有複雜的 code 從 yyin 獲得字元
     ,並分析到底 match 到哪個規則,對應的 yytext 是啥
     作者也不清楚這邊怎麼實作的 XD */
  switch (regex matched) {
   /* 可使用 yytext 這個變數
      表示 lex 找到對應的字串 */
   case regex 1: {動作 1}
   case regex 2: {動作 2}
   ......
   case regex N: {動作 N}
   case EOF : {
    /* EOF 表示 yyin 到了檔案結尾
       而 yywrap() 是可以自己定義的函數
       如果不自己定義的話
       yywrap() 預設會 return 0 */
    if (!yywrap())
     return 0;
   }
  }
 }
}

因為前面說過「動作」對直接被複製到 C 程式碼內
從這個流程可以看出我們在每個 regex 對應到的動作內,可以:
  1. 自 yylex() return
  2. 不 return,讓 yylex() 繼續執行
因此,以下兩個寫法(就作者所知)會有一樣的結果:

☆☆寫法一☆☆


%{
/* yylex example 1 */
#include <stdio.h>
%}
%%
hello {return 1;}
world {return 2;}
. {return 3;}
%%
const char *printstr[3] = {"=w=.", ">Δ<", "=Δ="};
int main() {
 int c;
 while (c = yylex()) {
  printf(printstr[c-1]);
 }
 return 0;
}

☆☆寫法二☆☆


%{
/* yylex example 2 */
#include <stdio.h>
const char *printstr[3] = {"=w=.", ">Δ<", "=Δ="};
%}
%%
hello {printf(printstr[0]);}
world {printf(printstr[1]);}
. {printf(printstr[2]);}
%%
int main() {
 yylex();
 return 0;
}

這兩個最大的不同是把 printf() 這個動作
分別放在 yylex() 的裡面跟外面
效率上來說,作者認為後者比較快
因為每一次呼叫 yylex() 都要初始化一些有的沒的東西
另外 function call/return 也會損耗一些效率

如果作者時間夠多的話
之後可能會介紹基本的 lex 及 yacc 的合併使用
以及 yacc 的簡單原理

--
補充說明,以上的例子在 linux 下可以用以下命令編譯

lex <file.lex> && gcc lex.yy.c -ll

請記得安裝 lex 跟 gcc
不過因為我用全形空白取代 tab,請記得處理 XD

2 則留言: