lex

它被設計用來對輸入字元流進行詞法處理。它接受一種高級的、面向問題的說明書，並用它匹配字元串中的字元、生成能夠識別正則表達式的程序。正則表達式通過用戶輸入的代碼說明書給入。Lex識別這些表達式，並且將輸入流分成一些匹配這些表達式的字元串。在這些字元串的分界處，用戶提供的程序片段被執行。Lex代碼文件將正則表達式和程序片斷關聯。對每一條輸入到由Lex生成程序的表達式，相應的代碼片段被執行。

為了完成任務，除了需要提供匹配的表達式以外，用戶還需要提供其它代碼，甚至是由其他生成器產生的代碼。用戶提供一般程序設計語言的代碼片斷完成程序識別表達式。因此，用戶自由編寫動作時，並不影響其編寫高層的表達式語言來匹配字元串表達式。這就避免迫使用戶使用字元串語言來進行輸入分析時，也必須使用同樣的方法來編寫字元處理程序，而這樣做有時是不合適的。Lex不是完整的語言，但是是一個新語言的生成器，它可以插入到各種不同的被叫做“宿主語言”的程序設計語言中。就像大多數目的語言可以生成在不同計算機硬體上運行的代碼，Lex可以生成不同的宿主語言。宿主語言用於Lex生成輸出代碼，也用於用戶插入程序片斷。這使得Lex適用於不同的環境和不同的使用者。每一個應用程序可以是硬體、適用於該任務的宿主語言、用戶背景和局部介面屬性的直接結合。現在，Lex唯一支持的宿主語言是C，儘管Fortran（形式為Ratfor）在過去也被支持。Lex自身存在於UNIX、GCOS和OS/370上；但是Lex生成的代碼可以在任何適當的編譯器上使用。

Lex將用戶輸入的表達式和動作actions（在這篇文章中被稱作 源代碼）轉換為宿主語言；生成的程序叫做 yylex。 yylex識別字元流中的表達式（本文稱作 輸入流），並且當每一個表達式被檢測出來后，輸出相應的動作。

過程如圖。

讓我們來仔細研究一下這個奇妙的工具吧。先看看Lex文件的結構。 Lex文件結構簡單，分為三個部分：

declarations

%%

translation rules

%%

auxiliary procedures

分別是聲明，轉換規則和其它函數。

聲明段包括變數的聲明、符號常量的聲明和正則表達式聲明。希望出現在目標C源碼中的代碼，用%{…%}擴在一起。比如：

%{

#include

#include "y.tab.h"

typedef char * YYSTYPE;

char * yylval;

%}

正則表達式聲明如下

delim [ \t\n]ws +letter [A-Za-z]digit [0-9]id ()*number +(\.+)?(E[+\-]?+}?

這段正則表達式描述識別數(number)、標識符(id)的“規則”。過一會我們再細說正則表達式。

規則段是由正則表達式和相應的動作組成的。

p1 p2 …… pn

值得注意的是，lex 依次嘗試每一個規則，儘可能地匹配最長的輸入流。如果有一些內容根本不匹配任何規則，那麼 lex 將只是把它拷貝到標準輸出。比如

%%A {printf("you");}AA {printf("love ");}AAAA {printf("I ");}%%

編譯后運行一下，

$ ./sample3AAAAAAAI love you

可以看出lex的確按照最長的規則匹配。

程序段部分放一些掃描器的其它模塊，比如一些動作執行時需要的模塊。也可以在另一個程序文件中編寫，最後再鏈接到一起。生成C代碼后，需用C的編譯器編譯。連接時需要指定鏈接庫。gcc的連接參數為 -ll。

正則表達式可以描述有窮狀態自動機(finite automata)接受的語言，也就是定義一個可以接受的串的集.lex中用到的正則表達式的一些規則如下：

轉義字元（也稱操作符）：

" \ [ ] ^ - ? . * + | ( ) $ / { } % < >

這些符號有特殊含義，不能用來匹配自身。如果需要匹配的話，可以通過引號(")或者轉義符號(\)來指示。比如

C"++" C\+\+

都可以匹配C++。

非轉義字元：所有除了轉義字元之外的字元都是非轉義字元。一個非轉義字元可以匹配自身。比如

integer

匹配文本中出現的integer。

通配符：通配符就是.（dot），可以匹配任何一個字元。

字符集：用一對[]指定的字元構成一個字符集。比如[abc]表示一個字符集，可以匹配a、b、c中的任意一個字元。使用 – 可以指定範圍。比如[a-z]表示可以匹配所有小寫字母的字符集。

重複：

* 任意次重複+ 至少一次的重複，相當於xx*? 零次或者一次

選擇和分組：|符號表示選擇，二者則一；括弧表示分組，括弧內的組合被看作是一個原子。比如(ab|cd)匹配ab或者cd。

一般的Lex源代碼格式為

{definitions}

%%

{rules}

%%

{user subroutines}

而definitions和user subroutines經常被忽略。第二個%%是可選擇的，但是第一個必須存在以標記rules的開始。因此最簡單的Lex程序是

%%

（沒有definitions和rules），這個程序輸入將不加修改地複製到輸出。

由上面的Lex程序輪廓可知，規則（rules）反映了用戶的控制；它是一個表格，左側是正則 表達式（regular expressions）（參見第3節），而右側是 動作（actions），當表達式被識別出以後，動作的程序片斷被執行。所以，一個單獨的規則可能是

它用於在輸入流中尋找字元串中的 integer，找到后輸出“found keyword INT”。在這個例子中，主程序為C語言並且用C庫函數 printf列印字元串。用第一個出現的空白符或者製表符作為表達式的結束標記。如果action僅僅是一條簡單的C表達式，那麼它可以直接寫在這一行的右側；如果是複合表達式或者包含了很多行，則必須用大括弧括起來。作為一個更有用的例子——用來將一些英式拼寫轉換為美式拼寫——其詞法分析器應該以如下規則開始：

這些規則是不夠強大的，比如pertroleum應該變為gaseum；一種處理它的方法將在下文中予以介紹。

有一些病態的表達式會使由表格轉化的確定的自動機成指數增長；幸運的是，這樣的情況很少見。

REJECT沒有重複掃描輸入；而是記住先前掃描的結果。這意味著如果一條規則需要回退發現的上下文，並且REJECT被執行了，用戶將不能使用 unput來改變輸入流中的後續字元。這是對用戶操作後續輸入的唯一限制。