Introduction to Lex 電資三 B9944205 盧逸峮

LEX YACC yacc（Yet Another Compiler Compiler），是Unix/Linux上一個用來生成編譯器的編譯器（編譯器代碼生成器）。yacc生成的編譯器主要是用C語言寫成的語法解析器（Parser），需要與詞法解析器Lex一起使用，再把兩部份產生出來的C程序一併編譯。yacc本來只在Unix系統上才有，但目前已普遍移植往Windows及其他平台 在 電腦科學裡面，lex是一個產生詞法分析器(lexical analyzer) ("掃描器"(scanners)或者"lexers")的程式。[1][2] Lex常常與yacc 語法分析器產生程式(parser generator)一起使用。 Lex(最早是埃里克·施密特和Mike Lesk製作)是許多UNIX系統的標準詞法分析器(lexical analyzer)產生程式，而且這個工具所作的行為被詳列為POSIX標準的一部分。 Lex讀進一個代表詞法分析器規則的輸入字串流，然後輸出以C語言實做的詞法分析器原始碼。

Lex 的常規表達式 Lex 的常規表達式 常規表達式是一種使用元語言的模式描述。表達式由符號組成。符號一般是字符和數字，但是 Lex 中還有一些具有特殊含義的其他標記。 下面兩個表格定義了 Lex 中使用的一些標記並給出了幾個典型的例子。 用 Lex 定義常規表達式

字符 含義 A-Z, 0-9, a-z 構成了部分模式的字符和數字。 . 匹配任意字符，除了 \n。 - 用來指定範圍。例如：A-Z 指從 A 到 Z 之間的所有字符。 [ ] 一個字符集合。匹配括號內的任意 字符。如果第一個字符是 ^ 那麼它表示否定模式。例如: [abC] 匹配 a, b, 和 C中的任何一個。 * 匹配0個或者多個上述的模式。 + 匹配1個或者多個上述模式。 ? 匹配0個或1個上述模式。 $ 作為模式的最後一個字符匹配一行的結尾。

字符 含義 { } 指出一個模式可能出現的次數。 例如: A{1,3} 表示 A 可能出現1次或3次。 \ 用來轉義元字符。同樣用來覆蓋字符在此表中定義的特殊意義，只取字符的本意。 ^ 否定。 | 表達式間的邏輯或。 "<一些符號>;" 字符的字面含義。元字符具有。 / 向前匹配。如果在匹配的模版中的「/」後跟有後續表達式，只匹配模版中「/」前面的部分。如：如果輸入 A01，那麼在模版 A0/1 中的 A0 是匹配的。 ( ) 將一系列常規表達式分組。

標記聲明舉例 標記 相關表達式 含義 數字(number) ([0-9])+ 1個或多個數字 字符(chars) [A-Za-z] 任意字符 空格(blank) " " 一個空格 字(word) (chars)+ 1個或多個 chars 變量(variable) (字符)+(數字)*(字符)*(數字)*

Lex 編程可以分為三步 以 Lex 可以理解的格式指定模式相關的動作。 在這一文件上運行 Lex，生成掃瞄器的 C 代碼。 編譯和鏈接 C 代碼，生成可執行的掃瞄器。 注意: 如果掃瞄器是用 Yacc 開發的解析器的一部分，只需要進行第一步和第二步。關於這一特殊問題的幫助請閱讀 Yacc 和 將 Lex 和 Yacc 結合起來部分。 現在讓我們來看一看 Lex 可以理解的程序格式。一個 Lex 程序分為三個段：第一段是 C 和 Lex 的全局聲明，第二段包括模式（C 代碼），第三段是補充的 C 函數。 例如, 第三段中一般都有 main() 函數。這些段以%%來分界。 那麼，回到字數統計的 Lex 程序，讓我們看一下程序不同段的構成。

lex檔案的結構 lex的檔案結構故意設計的與yacc的檔案格式相似；檔案分成三個區塊, 均以一個只有兩個百分比符號(%)的單行來分隔，如下： 定義區塊 %% 規則區塊 C程式碼區塊

C 和 Lex 的全局聲明 這一段中我們可以增加 C 變量聲明。這裡我們將為字數統計程序聲明一個整型變量，來保存程序統計出來的字數。我們還將進行 Lex 的標記聲明。 字數統計程序的聲明 %{ int wordCount = 0; %} chars [A-za-z] numbers ([0-9])+ delim [" "\n\t] whitespace {delim}+ words {chars}+ %% 兩個百分號標記指出了 Lex 程序中這一段的結束和三段中第二段的開始。

Lex 的模式匹配規則 讓我們看一下 Lex 描述我們所要匹配的標記的規則。（我們將使用 C 來定義標記匹配後的動作。）繼續看我們的字數統計程序，下面是標記匹配的規則。 字數統計程序中的 Lex 規則 [code] {words} { wordCount++; /* increase the word count by one*/ } {whitespace} { /* do nothing*/ } {numbers} { /* one may want to add some processing here*/ } %% [/code]

C 代碼 Lex 編程的第三段，也就是最後一段覆蓋了 C 的函數聲明（有時是主函數）。注意這一段必須包括 yywrap() 函數。 Lex 有一套可供使用的函數和變量。 其中之一就是 yywrap。一般來說，yywrap() 的定義如下例。我們將在 高級 Lex 中探討這一問題。 字數統計程序的 C 代碼段 void main() { yylex(); /* start the analysis*/ printf(" No of words: %d\n", wordCount); } int yywrap() { return 1; }

實作 撰寫一個Lex程式，該程式會將C語言做以下轉換： PROGRAM 1 VAR 2 BEGIN 3 END 4 END. 5 INTEGER 6 FOR 7 READ 8 WRITE 9 TO 10 DO 11 ; 12 : 13 ' 14 := 15

Resources Google directory of lexer and parser generators. Flex homepage: http://www.gnu.org/software/flex Lex/yacc Win32 port: http://www.monmouth.com/~wstreett/lex-yacc/lex-yacc.html

1. 安裝 MinGW-5. 1. 6. exe 在 C:\MinGW 網址:http://www. mingw. org/ 2 1.安裝 MinGW-5.1.6.exe 在 C:\MinGW 網址:http://www.mingw.org/ 2.安裝 flex-2.5.4a-1.exe 在 C:\GnuWin32 網址:http://gnuwin32.sourceforge.net/packages/flex.htm 3.安裝 bison-2.4.1-setup.exe 在 C:\GnuWin32 網址:http://gnuwin32.sourceforge.net/packages/bison.htm 4.複製C:\GnuWin32\lib裡的 (a) charset.alias (b) libfl.a (c) liby.a 到C:\MinGW\lib 5.設環境變數 Path C:\MinGW\bin; C:\GnuWin32\bin; #define yywrap() 1

How to use Cd C:\GnuWin32\bin flex.exe scal.l gcc lex.yy.c -lfl a.exe < data0.txt

lex檔案的範例 %% PROGRAM printf("1"); VAR printf("2"); BEGIN printf("3"); END printf("4"); END. printf("5"); INTEGER printf("6"); FOR printf("7"); READ printf("8"); WRITE printf("9"); TO printf("10"); DO printf("11"); ; printf("12"); : printf("13"); ' printf("14"); := printf("15");

參考 http://www.lslnet.com/linux/f/docs1/i36/big5267662.htm http://zh.wikipedia.org/wiki/Lex http://zh.wikipedia.org/zh-tw/Yacc