字句解析

計算機科学における字句解析  とは、ある言語で書かれた文について、その文字の並びを解析し、言語的に意味のある最小の単位に分解する処理のこと。

1. 概要
-----

字句解析は、コンピュータを用いた自然言語処理でも、プログラミング言語のコンパイルでも行われる。

自然言語の文であれ、プログラムのソースコードであれ、文というのは結局、文字や記号や約物類が多数並んだものであるが、字句解析はそれを、言語的に意味のある最小単位トークンに分解する処理である。

文を解析してトークンに分解する作業を自動的に行うプログラムを字句解析器という。

1.1. 具体例
--------

コンパイラの中の字句解析の例を挙げる。

たとえばソースコード中に、あらかじめ現在値や初期値を入れるためのpresentやinitialという変数が宣言された後に、次の1行があるとする。

present := initial + 15 これを字句解析すると次のようになる。

つまり「present」や「initial」という変数名、「:=」という変数への値の代入を示す演算子、「15」という数字列は、意味を持つ最小単位である。

文字と文字の間の空白は、通常、字句解析の途中で除去する。上の例では present と := の間やその後ろなどにある空白文字が除去されている。空白文字はトークンとトークンを分離する役割くらいしかないものなのでトークンには含めない。

また、コンパイラの字句解析では、コメント文つまり「/* 現在値を計算するためのプログラム。 */」といったような文は、処理の最初の段階でひとつのカタマリとして扱い、まるごと除去してしまうこともある。

もうひとつ、C言語での文の例を挙げる。

sum = 35 + 21;これは、次の表のようにトークン化される。

トークンは字句解析する段階では、プログラムの要素としての妥当性は必ずしも考慮されない。例えば上記の例で sum は、もしこの文の前にsumが宣言されていなければ意味がないが、字句解析器は通常トークンとしては問題ないとして扱う。

一方、数リテラルの値が、そのプログラミング言語で扱えるいかなる型がサポートする範囲よりも大きい値が書かれている場合は、最初からエラーにすることもある。

2. 字句解析器
--------

2.1. スキャナ
---------

一般に、文字列をなめるような処理をするものをスキャナという。字句解析の場合、文字列から、1個のトークンになるような部分文字列を切り出す部分をスキャナとして分けて考える場合がある。

スキャナはある種の有限状態機械にモデル化できる。その有限状態機械は、それが処理する任意のトークンに含まれる文字の考えられる並びに関するルールを元に生成される。ここでいうルールとは例えば、「整数」トークンは任意個の数字の並びである、といったようなものである。プログラミング言語では、一般に、空白でない先頭の文字の種類によって、そこから始まるトークンの種類が類推できるよう設計され、その後の文字の並びはそのトークンとして受理できない文字が出てくるまでひとまとめとして処理される。言語によっては、規則がもっと複雑で、複数個の文字について戻るようなバックトラッキングが必要になることもある。

狭義の正規表現による表現が面倒な字句規則の代表例に、C言語の「/* コメント */」のようなコメントがある。ルールを直感的に言明すると「コメントには任意の文字が使えるが、"*/" という並びが現れたらそこで終わる」というものであるが、これを何も考えずにそのまま正規表現にしてしまうと、正規表現の * が最長一致であるために、「ソースコード中に現れる最初のコメントの開始から、ソースコード中に現れる最後のコメントの終了」にマッチしてしまう。正規表現に非欲張り量指定子か先読みがあればこれに対し正しい規則を書くのは簡単だが、無い場合は不可能ではないものの、その規則は読みやすいものではない。

コメントの例の場合は、手書きの解析器であればそこだけアドホックにちょっと先読みすれば簡単に済むが、こういったパターンが意外とあることも、手書きが選ばれる理由のひとつである。また、JavaのGenericsやC++のテンプレートなどの字句解析で「>>」という並びが現れうることも、悩ましい点のひとつである。本格的な処理系では往々にして、こういった場合への対処のために後段からの情報を必要とし、実装がややこしいものになりやすい。

2.2. トークナイザ
-----------

トークン化は、スキャナによって得られた部分文字列に、トークンの種別の情報を付け、その種類によっては、たとえば整数ならその整数値といったような意味値を与える処理である。部分文字列の列からトークンを構築するには、字句解析器には第二段階の評価器が必要であり、評価器は文字列に対して「値」を付与する。文字列と型を結びつけたものが適切にトークンを表し、構文解析器に入力できるものとなる。括弧などの一部のトークンは「値」を持たないので、評価器はそれらについては何も返さない。整数、識別子、文字列などを扱う評価器は非常に複雑になる。空白やコメントなどはそのまま捨ててしまうこともある。最終的に、#トークンの節に挙げた表のような形の情報を持った、トークン列が得られる。

3. 字句解析器生成器
-----------

字句解析器を自動的に作成するソフトウェアを字句解析器生成器という。

1975年にマイク・レスクとエリック・シュミットにより字句解析器生成器Lex が開発され、POSIXにも採用された。Lexは、トークンの規則を正規表現で記述した文書をもとに、自動的に字句解析器を作る。入力がどの規則にもマッチしないようであればエラーとする。

1987年ころには、Lexを :en:Vern Paxson が改良したFlexがリリースされ、広く利用されるようになった。Linuxのディストリビューションの多くがFlexを標準採用している。

なおLex 系の生成器は表駆動型の手法を採用している。

1994年にはPeter Bumbulisが開発したre2cがリリースされた。 re2cはFlexの2倍から3倍の速度で処理を行う字句解析器を生成すると言われている

2017年にはFrank-Rene Schaeferが開発したquexがリリースされた。 これも高速な字句解析器を生成する。

4. 脚注
-----

5. 参考文献
-------

[1]
//Compiling with C# and Java//, Pat Terry, 2005, ISBN 0-321-26360-X
//Algorithms + Data Structures = Programs//, Niklaus Wirth, 1975, ISBN 0-13-022418-9
//Compiler Construction//, Niklaus Wirth, 1996, ISBN 0-201-40353-6
Sebesta, R. W. . Concepts of programming languages  pp.177. Boston: Pearson/Addison-Wesley.

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

[2] - 日中韓自然言語に対応している字句解析API
[3] - lex の GNU 版
[4] - Java 向け字句解析器生成器
[5]  - C++ 向け字句解析器生成器
[6] - オブジェクト指向字句解析器生成器