字句解析

字句解析とは

字句解析（lexical analysis）は、計算機科学における重要なプロセスであり、プログラミング[[言語]]や自然言語処理において、テキストを意味のある最小単位である「トークン」に分解する処理を指します。この処理は、コンパイラやインタプリタなどの言語処理系において、最初の段階で行われることが一般的です。

概要

字句解析は、人間が書いたプログラムコードや自然言語のテキストを、コンピュータが理解できる形に変換するための最初のステップです。具体的には、文字列として与えられた入力（ソースコードやテキスト）を、単語、記号、数値などの意味を持つ最小単位であるトークンに分解します。このトークンは、その後の構文解析や意味解析などの処理で利用されます。

字句解析を行うプログラムは「字句解析器（lexical analyzer）」または「スキャナ（scanner）」と呼ばれます。字句解析器は、入力文字列を読み込みながら、定義された規則に従ってトークンを切り出します。例えば、プログラミング[[言語]]では、変数名、演算子、キーワード、数値などがトークンとして認識されます。

具体例

プログラムコードの字句解析

以下は、簡単なプログラムコードの例です。


present := initial + 15


このコードを字句解析すると、次のようなトークン列が得られます。

• - `present` (変数名)
• - `:=` (代入演算子)
• - `initial` (変数名)
• - `+` (加算演算子)
• - `15` (数値)

このように、字句解析では、プログラムコードを構成する要素が、意味のある最小単位であるトークンに分割されます。また、空白文字やコメントなどは、トークンを区切る役割を果たすため、通常は削除されます。

C[[言語]]の例

c
sum = 35 + 21;


このC[[言語]]のコードを字句解析すると、以下のトークンに分解されます。


字句解析の段階では、トークンがプログラムとして意味を成すかどうかの妥当性は考慮されません。例えば、`sum` が宣言されていなくても、字句解析器は通常エラーとはしません。しかし、数値リテラルがそのプログラミング[[言語]]で扱える範囲を超える場合は、エラーとして検出されることがあります。

字句解析器

スキャナ

字句解析器は、一般にスキャナとトークナイザの2つの部分から構成されます。スキャナは、入力文字列を先頭から読み進めながら、トークンの候補となる部分文字列を切り出す役割を担います。スキャナは、有限状態機械としてモデル化でき、トークンとして認識可能な文字の並びに関するルールに基づいて動作します。

例えば、「整数」トークンは、数字の連続として認識されます。プログラミング[[言語]]では、トークンの種類は通常、空白以外の先頭文字の種類によって推測可能であり、その後の文字の並びは、トークンとして受理できない文字が現れるまでまとめられます（最長一致の規則）。

トークナイザ

スキャナによって抽出された部分文字列には、トークンの種別の情報が付与されます。さらに、必要に応じてトークンの意味値が付与されます。例えば、整数であればその数値が、識別子であれば識別子の名前が、意味値として付与されます。この処理を行うのがトークナイザです。トークナイザによって生成されたトークンは、構文解析器へと引き渡されます。

字句解析器生成器

字句解析器を自動的に生成するツールを字句解析器生成器（lexical analyzer generator）といいます。代表的な字句解析器生成器として、以下のようなものがあります。

• - Lex: 1975年に開発された、最も初期の字句解析器生成器です。正規表現を用いてトークンの規則を記述し、C[[言語]]で記述された字句解析器を生成します。
• - Flex: Lexを改良したもので、より高速に動作します。多くのLinuxディストリビューションで標準採用されています。
• - re2c: Flexよりも高速に動作する字句解析器を生成します。
• - quex: 高速な字句解析器を生成する比較的新しいツールです。

これらのツールを用いることで、字句解析器を手作業で作成する手間を大幅に削減できます。生成された字句解析器は、コンパイラやインタプリタなどの言語処理系のフロントエンドとして活用されています。

まとめ

字句解析は、プログラミング[[言語]]や自然言語処理において、テキストデータをコンピュータが理解できる形に変換するための重要なステップです。字句解析器は、スキャナとトークナイザの2つの部分から構成され、字句解析器生成器を用いることで、効率的に字句解析器を開発できます。

もう一度検索