-
lex
（計算機領域的詞法分析器）
鎖定
- 中文名
- 詞法分析器生成器
- 外文名
- Lexical analyzer generator
- 縮 寫
- Lex
- 運行環境
- Unix環境
- 主要功能
- 生成一個詞法分析器的C源碼
lex生成工具
圖1
它被設計用來對輸入字符流進行詞法處理。它接受一種高級的、面向問題的説明書，並用它匹配字符串中的字符、生成能夠識別正則表達式的程序。正則表達式通過用户輸入的代碼説明書給入。Lex識別這些表達式，並且將輸入流分成一些匹配這些表達式的字符串。在這些字符串的分界處，用户提供的程序片段被執行。Lex代碼文件將正則表達式和程序片斷關聯。對每一條輸入到由Lex生成程序的表達式，相應的代碼片段被執行。
為了完成任務，除了需要提供匹配的表達式以外，用户還需要提供其它代碼，甚至是由其他生成器產生的代碼。用户提供一般程序設計語言的代碼片斷完成程序識別表達式。因此，用户自由編寫動作時，並不影響其編寫高層的表達式語言來匹配字符串表達式。這就避免迫使用户使用字符串語言來進行輸入分析時，也必須使用同樣的方法來編寫字符處理程序，而這樣做有時是不合適的。Lex不是完整的語言，但是是一個新語言的生成器，它可以插入到各種不同的被叫做“宿主語言”的程序設計語言中。就像大多數目的語言可以生成在不同計算機硬件上運行的代碼，Lex可以生成不同的宿主語言。宿主語言用於Lex生成輸出代碼，也用於用户插入程序片斷。這使得Lex適用於不同的環境和不同的使用者。每一個應用程序可以是硬件、適用於該任務的宿主語言、用户背景和局部接口屬性的直接結合。現在，Lex支持的宿主語言是C，儘管Fortran（形式為Ratfor[2]）在過去也被支持。Lex自身存在於UNIX、GCOS和OS/370上；但是Lex生成的代碼可以在任何適當的編譯器上使用。
Lex將用户輸入的表達式和動作actions（在這篇文章中被稱作源代碼）轉換為宿主語言；生成的程序叫做yylex。yylex識別字符流中的表達式（本文稱作輸入流），並且當每一個表達式被檢測出來後，輸出相應的動作。
過程如圖 。
declarations %% translation rules %% auxiliary procedures
分別是聲明，轉換規則和其它函數。
%{
#include <stdio.h>
#include "y.tab.h"
typedef char * YYSTYPE;
char * yylval;
%}
正則表達式聲明如下
/* regular definitions */ delim [ \t\n]ws +letter [A-Za-z]digit [0-9]id ()*number +(\.+)?(E[+\-]?+}?
規則段是由正則表達式和相應的動作組成的。
p1 p2 …… pn
值得注意的是，lex 依次嘗試每一個規則，儘可能地匹配最長的輸入流。如果有一些內容根本不匹配任何規則，那麼 lex 將只是把它拷貝到標準輸出。比如
%%A {printf("you");}AA {printf("love ");}AAAA {printf("I ");}%%
編譯後運行一下，
$ ./sample3AAAAAAAI love you
可以看出lex的確按照最長的規則匹配。
" \ [ ] ^ - ? . * + | ( ) $ / { } % < >
這些符號有特殊含義，不能用來匹配自身。如果需要匹配的話，可以通過引號(")或者轉義符號(\)來指示。比如
C"++" C\+\+
都可以匹配C++。
非轉義字符：所有除了轉義字符之外的字符都是非轉義字符。一個非轉義字符可以匹配自身。比如
integer
匹配文本中出現的integer。
通配符：通配符就是.（dot），可以匹配任何一個字符。
重複：
* 任意次重複+ 至少一次的重複，相當於xx*? 零次或者一次
選擇和分組：|符號表示選擇，二者則一；括號表示分組，括號內的組合被看作是一個原子。比如(ab|cd)匹配ab或者cd。
lexLex源代碼
一般的Lex源代碼格式為
{definitions}
%%
{rules}
%%
{user subroutines}
而definitions和user subroutines經常被忽略。第二個%%是可選擇的，但是第一個必須存在以標記rules的開始。因此最簡單的Lex程序是
%%
（沒有definitions和rules），這個程序輸入將不加修改地複製到輸出。
由上面的Lex程序輪廓可知，規則（rules）反映了用户的控制；它是一個表格，左側是正則表達式（regular expressions）（參見第3節），而右側是動作（actions），當表達式被識別出以後，動作的程序片斷被執行。所以，一個單獨的規則可能是
integer | printf("found keyword INT"); |
它用於在輸入流中尋找字符串中的integer，找到後輸出“found keyword INT”。在這個例子中，主程序為C語言並且用C庫函數printf打印字符串。用第一個出現的空白符或者製表符作為表達式的結束標記。如果action僅僅是一條簡單的C表達式，那麼它可以直接寫在這一行的右側；如果是複合表達式或者包含了很多行，則必須用大括號括起來。作為一個更有用的例子——用來將一些英式拼寫轉換為美式拼寫——其詞法分析器應該以如下規則開始：
colour | printf("color"); |
mechanise | printf("mechanize"); |
petrol | printf("gas"); |
這些規則是不夠強大的，比如pertroleum應該變為gaseum；一種處理它的方法將在下文中予以介紹。
lex警告和缺陷
有一些病態的表達式會使由表格轉化的確定的自動機成指數增長；幸運的是，這樣的情況很少見。
REJECT沒有重複掃描輸入；而是記住先前掃描的結果。這意味着如果一條規則需要回退發現的上下文，並且REJECT被執行了，用户將不能使用unput來改變輸入流中的後續字符。這是對用户操作後續輸入的限制。
