Lex

Lexは、1975年にエリック・シュミットとマイク・レスクによって開発された、レキシカルアナライザを生成するプログラムである。unixにおける標準のレキシカルアナライザとなっており、POSIX標準ともなっている。コンパイラの作成のためにパーサジェネレータのyaccとともに使用されることも多い。

1. 概要
-----

1.1. 名称
-------

Lexはレキシカルアナライザジェネレータである。すなわちレキシカルアナライザの生成ツールであり、Lexの名称も英語のLexical analysisからきている。

1.2. 用途
-------

字句解析はテキスト中の文字列の変換、カウント、抽出などさまざまな目的に使われ、その応用領域は、コンパイラやコンバータの作成を筆頭に、自然言語処理や簡単な整形まで幅広い。

このうち、コンパイラにおけるレキシカルアナライザの位置づけを、以下に説明する。プログラムを中間言語あるいは機械語に変換するコンパイラは、一般的にソースを入力し構文木を出力する構文解析部と、その構文木を入力し中間言語コードまたは機械語を出力するコード生成部からなる。

コンパイラ 　├構文解析部 　│　├字句解析器　←〔ソース〕 　│　│呼出し↑↓ 　│　│　　　↑〔トークン列〕 　│　│　　　↑↓ 　│　└構文解析器 　│　　　　　↓ 　│　　〔構文木〕 　│　　　　　↓ 　└コード生成部　　　→〔中間言語コードまたは機械語〕

このうちの前半は、ソースを入力しトークン列を出力する字句解析器である。 後半は、そのトークン列を入力し、構文規則にしたがって構文解析をし、構文木を出力する構文解析器である。 のレキシカルアナライザを生成するのが、レキシカルアナライザジェネレータである。

1.3. 機能概要
---------

構文解析器に解析を数字や英字や空白などの1文字単位で行わせると、複雜になりすぎる。しかし、人間が英文から英単語や数字などの記号列を、区切り文字やその列を目印に抽出して、意味を判断しているのと、同様の発想ができる。すなわち、区切り記号列でソースを切っていくと、「print」のような語、「1999」のような10進数、「"Hello, world"」といった文字リテラル、「++」といった演算子、「}」や「;」など意味のある区切り文字など、各種の文字列が取り出せる。これをトークンという。ここまでの下位の文法処理を上記字句解析器に行わせ、一方、構文解析器はトークンから出発して句、文、ブロック、プログラムなどを認識する上位の文法処理に専念させる。この分業化により、それぞれの定義と処理を簡潔にできる。

この字句解析器の合理的な開発を目的とし、機械可読にした規則定義を与えれば字句解析器を自動生成してくれる便利なツールがレキシカルアナライザジェネレータであり、LexやFlexなどがそれに属する。

〔規則定義〕 　　↓ レキシカルアナライザジェネレータ 　　↓ 〔字句解析器〕

同様に、構文解析器の合理的な開発を目的とし、構文規則定義を与えれば構文解析器を自動生成してくれる便利なツールとして、Yaccなどのパーサジェネレータがある。

1.4. 構文解析器ジェネレータとの関係
--------------------

Yaccなどの構文解析器生成ツールを利用するなら、Lexに字句文法定義を与えて生成させたC言語ソースである字句解析器がyylex関数を含んでいるので、CコンパイラでYacc出力と一緒にこれをリンクして組み込む。これにより、ソーステキストの字句解析と構文解析を両方行って、規則のアクション部に書かれた計算の結果や、コンパイルの生成に使われる抽象構文木の構造体データ、あるいは各種表示が出力される変換プログラムが完成する。

YaccとLexはよく似た文法定義をもち、セットで使われ、セットで解説されることが多い。LexとYaccの機能はIEEE POSIX 1003.1-2008で標準化されている。

1.5. 配布と派生、改良
-------------

YaccはほとんどのUNIXシステムで、デフォルトのレキスカルアナライザジェネレータとして利用可能だった。 Lexは多くのシステム、多くのプログラミング言語に移植されている。たとえばJava言語による字句解析器を生成するLex系ツールに、[1]、それを書き直した[2]がある。このJFlexとJava言語用構文解析器[3]と組みあわせて用いることも行われている。

Lexと同等の機能を有し性能が改善されているFlexというものもあるが、開発者がLexの開発者とは別人の:en:Vern Paxsonであり、ライセンスもLexが Plan 9: MIT Licenseなのに対しFlexのほうはBSDライセンスであり、つまりは全く別のソフトウェアであり、しっかり区別したほうがよい。

Flexについては別記事　{Flex }　を立ち上げ、そちらで説明すること。

2. Lex のファイル構造
--------------

Lexのファイル構造は意識的にyaccのそれに似せて定義されている。 ファイルは3つの部分に分割されており、それぞれ定義領域、規則領域、Cコード領域である。各領域はパーセント記号2つのみを含んだ行で区切られる。

定義領域は正規表現を用いてマクロを定義するところであり、かつCのヘッダーファイルを取り込む場所でもある。

規則領域は最も重要な領域でありCの命令との関連付けを行う。Lexの規則と一致するパターンがあるとそれに関連付けされたCコードを実行する。

Cコード領域には生成したソースにそのままコピーされるCの命令や関数が含まれている。 これらの命令は規則領域での規則により呼ばれたコードを含む場合もある。大規模なプログラムではここに分割しておきコンパイル時にリンクするほうが便利である。

3. Lexの正規表現
-----------

通常の正規表現の特殊文字にくわえ、「"」 「/」 「%」 「」 「+」 「/」 「<」 「>」 「?」 「{」 「|」 「}」 も特殊文字である
行頭の「%」は、上述のように領域を区切ったり、Lex特有の指示をあたえるために使う
文字クラス、否定文字クラスの内側で「\」が特殊文字になる
陽に指定したときを除いて、否定文字クラスは、改行にも照合する
「"」で引用できる。引用の終了も「"」
「パターン{最少,最多}」や「パターン{回数}」でパターンの繰返し回数を指定できる 
「+」は「{1,}」の、「?」は「{,1}」の、それぞれの省略形である 
「|」で択一できる。「」で範囲を広げて指定できる 
「\b」「\f」「」「\r」「\t」「\v」「\8進数」は、Cの文字定数の定義と同じ

「<WtXmlEndTag /><<WtXmlEndTag />開始条件>正規表現」で、指定の名前の開始条件にあるときの正規表現だけに照合できる。開始条件は、コンマで区切って複数指定できる
「r/s」は、正規表現「s」の後続する正規表現「r」を表わす。アクションで参照できるのが「r」のみになるところが、重要である
「{名前}」で、定義領域で定義した名前のマクロに展開される

4. 脚注・出典
--------

5. 関連項目
-------

字句解析器
Yacc

6. 外部リンク
--------

[4] - Oracle Documentation プログラミングユーティリティ 第2章、特に[5]

[6] - 作者 M. E. Lesk and E. Schmidt
[7] - Tom Niemann epaperpress.com
[8]G・フリードマン著、矢吹道郎ら訳、竹本 浩OCR復刻
[9]- 原著 G. T. Nicol、特に[10]

[11]
[12]