字句解析
計算機科学における字句解析 (じくかいせき、テンプレート:Lang-en-short) とは、ソースコードを構成する文字の並びを、トークン (token) の並びに変換することをいう[1]。ここでいう「トークン」とは、意味を持つコードの最小単位のこと。字句解析を行うプログラムは、字句解析器 (lexical analyzer, 略称：lexer) と呼ばれる。字句解析器はスキャナ (scanner) とトークナイザ (tokenizer) から構成される。
字句解析によって得られたトークンの並びについて、トークン間の関係を解析することは、構文解析という。字句解析は、構文解析の前段階として広く行われている。しかし、高速な動作が必要でない場合は1文字を1トークンとみなすことで字句解析を無くし、構文解析のみで文字列の解析を行うシンプルな手法が使われる場合もある。
どんな文字の並びがトークンとして成立するのかということに関しては、ふつうはプログラミング言語の仕様として決められている。具体的には、それを指定する規則が構文記法に含まれている。ちなみに空白文字は、字句解析では無視されることが多い。
トークン
ここでいうトークンとは、ソースコードを構成する最小単位のことをいう。 自然言語の場合の語彙素に相当する。字句解析器は、ソースコードの「語彙素」を、機能に基づいて分類し、それらに意味を与える。このような意味の付与をトークン化（tokenization）と呼ぶ。トークンの形態は様々である。自然言語的な場合もあるし、一見わけのわからない記号の場合もあるが、それらは皆、構造化テキストの一部として有用である。
C言語での文 sum=3+2; を考えてみよう。これは、次の表のようにトークン化される。
| 語彙素 | トークン型 |
| sum | IDENT |
| = | ASSIGN_OP |
| 3 | NUMBER |
| + | ADD_OP |
| 2 | NUMBER |
| ; | SEMICOLON |
トークンは正規表現で定義されることが多い。例えば字句解析器 lex では正規表現が使われている。字句解析器は語彙素の並びを読み込み、それらをトークンとして分類する。字句解析器が不正なトークンを見つけた場合、エラーが報告される。
字句解析の次には構文解析が行われる。その後、解釈済みのデータがデータ構造に取り込まれ、インタプリタやコンパイラといった各種用途に使われる。
例えば、"46 - number_of(cows); " という計算式を表すテキストを考えてみよう。ここでの語彙素は "46"、"-"、"number_of"、"("、"cows"、")"、";" となる。字句解析器は語彙素 "46" を「数値」トークン、"-" を「文字」トークン、"number_of" を独立したトークンとする。C言語のような言語では、語彙素 ";" も特別な意味を持つ。
トークンはトークンとして認識されるだけの段階では妥当性は考慮されない。例えば、上記の例で "cows" や "number_of" は（おそらく）その言語にとっては意味がないが、トークンとしては問題ない。
スキャナ
字句解析の第一段階であるスキャナは、通常有限状態機械に基づいている。その有限状態機械は、それが処理する任意のトークンにでも含まれる文字の考えられる並びに関する情報を符号化したものである。そして、このときの個々の文字の並びを語彙素と呼ぶ。例えば、「整数」トークンは任意個の数字の並びを含むかもしれない。一般に空白でない先頭の文字の種類によってそこから始まるトークンの種類が類推できるよう設計され、その後の文字の並びはそのトークンとして受理できない文字が出てくるまでひとまとめとして処理される（最長一致の規則）。言語によっては、語彙素生成規則がもっと複雑で、複数個の文字を戻すようなバックトラッキングが必要になることもある。
トークナイザ
トークン化（tokenization）とは、境界を設定し、場合によっては入力文字列の一部を分類する過程である。結果として得られたトークンの並びは、構文解析などの入力とされる。
例として次の文字列を考える。人間とは異なり、コンピュータは直観的に9個の単語があるとは認識できない。コンピュータにとっては、これは単なる43文字の文字の並びでしかない。
The quick brown fox jumps over the lazy dog
トークン化では、この文を単語トークンに分割する。以下はそれを XML で表現したものだが、トークン化された入力を格納する形式は様々である。
<sentence>
<word>The</word>
<word>quick</word>
<word>brown</word>
<word>fox</word>
<word>jumps</word>
<word>over</word>
<word>the</word>
<word>lazy</word>
<word>dog</word>
</sentence>しかし、語彙素は単なる特定の文字の並び（文字列リテラル）でしかない。トークンを構築するには、字句解析器には第二段階の評価器が必要であり、評価器は語彙素の文字列に対して「値」を付与する。値と語彙素の型を結びつけたものが適切にトークンを表し、構文解析器に入力できるものとなる。括弧などの一部のトークンは「値」を持たないので、評価器（関数）はそれらについては何も返さない。整数、識別子、文字列などを扱う評価器は非常に複雑になる。評価器は語彙素を完全に抑制して、構文解析器に見せないこともある（空白やコメントなど）。
例えば、プログラミング言語のソースコードの中の次の文字列は、
net_worth_future = (assets - liabilities);
以下のような字句のならびに変換できる。 （空白は無視している）
NAME "net_worth_future" EQUALS OPEN_PARENTHESIS NAME "assets" MINUS NAME "liabilities" CLOSE_PARENTHESIS SEMICOLON
構文解析器は人間が一から書くこともできるし、それが必要な場合もあるが、一般に自動化ツールによって生成される。そのようなツールは、正規表現で表されたトークンの定義を使って、入力文字列を字句解析するプログラムを生成する。つまり、正規表現は特定のプログラミング言語の語彙的文法を表しており、それによって生成されるプログラムはその文法を有限状態機械（あるいはその状態表）にしたものと言える（一般に、生成された字句解析プログラムはコンパイラやインタプリタで使える形式になっている）。
正規表現は、語彙素を構成する文字が従うパターンを簡潔に表現する。例えば、英語をベースとした言語では、NAME トークンは英語のアルファベット文字とアンダースコアで始まり、その後に任意の ASCII の英数字やアンダースコアが続くと定義される場合もある。これを正規表現で表すと、[a-zA-Z_][a-zA-Z_0-9]* となる。これはつまり、「a-z、A-Z、_ のいずれかの文字に、a-z、A-Z、_、0-9 のいずれかが（0個も含めて）任意個続く」ということを表している。
正規表現とそれによって生成される有限状態機械は、括弧の入れ子のような再帰的なパターンを処理できるほど強力ではない。つまり、何かを数えて、個数を比較するといったことはできない（個数に制限があれば不可能ではない）。これは構文解析器が一般に処理する事柄である。
lex は、語彙的文法の記述に基づいて高速な字句解析器のコードを生成する。しかし、複雑な語彙規則の場合や、性能要求が厳しい場合には対応できない。実際、GNUコンパイラコレクションでは、独自の字句解析器を使っている。
字句解析器生成器
字句解析は、一度に一文字ずつ読み込むならワンパスで実行できる。ワンパスの字句解析器は lex や flex のような古くからあるツールで生成可能である。
lex/flex 系の生成器は表駆動型の手法を採用しており、直接符号化手法よりも効率は劣る。re2c や queχ といったツールは flex よりも2倍から3倍高速な字句解析器を生成するとされている（article about re2c）。これらのツールよりも高性能な字句解析器を人間が一から書くのは非常に難しい。
言語の開発途中段階などでは、仕様が頻繁に変わるため、スキャナ生成器などの単純なツールの方が有用な場合もある。正規表現として語彙構成要素を表現する能力により、字句解析器の記述が容易になる。一部のツールは、人間が書くのが難しい事前条件や事後条件を記述できる。このような場合、字句解析器生成器によって開発時間が大幅に節約できる。
脚注
関連項目
参考文献
- CS 164: Programming Languages and Compilers (Class Notes #2: Lexical)
- Compiling with C# and Java, Pat Terry, 2005, ISBN 0-321-26360-X 624
- 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. (2006). Concepts of programming languages (Seventh edition) pp.177. Boston: Pearson/Addison-Wesley.
外部リンク
- U-Tokenizer - 日中韓自然言語に対応している字句解析API
- Flex lexical analyser - lex の GNU 版
- JLex - Java 向け字句解析器生成器
- Quex ('Queχ') - C++ 向け字句解析器生成器
- OOLEX - オブジェクト指向字句解析器生成器
