字句解析 (Lexical Analysis)

1. 字句解析の役割とトークン分割

字句解析を行うプログラム（レキサー/スキャナー）は、ソースコードの文字列を左から右へ1文字ずつスキャンし、空白や改行を取り除きながら、意味のまとまりごとに分割します。この分割された部分文字列と、その種類をセットにしたデータをトークン（Token）と呼びます。

例えば、ソースコード上に次のような1行があったとします。

total = count * 10;

字句解析器は、これをスキャンして次のようなトークン列に切り分けます。

部分文字列	トークンの種類（Type）	意味
total	IDENTIFIER	識別子（変数名）
=	ASSIGN_OP	代入演算子
count	IDENTIFIER	識別子（変数名）
*	MULT_OP	乗算演算子
10	NUMBER_LITERAL	数値リテラル
;	SEMICOLON	文の終端記号

このように、文字列を「文法上意味のある記号」に分類することで、後段の構文解析が扱いやすい構造にします。

2. トークン検出の基礎理論：正規表現

各トークンがどのようなパターンの文字列であるかは、通常、形式言語理論における正規表現（Regular Expression）で定義されます。

• 数値（整数）のパターン： [0-9]+ （0から9の文字が1回以上繰り返す）
• 識別子（変数名など）のパターン： [a-zA-Z_][a-zA-Z0-9_]* （アルファベットまたは下線で始まり、2文字目以降は数字も許容）
• 予約語（if, while等）： 固有の文字列に完全一致するパターン

3. 実行モデル：決定性有限オートマトン (DFA)

正規表現で定義されたパターンを、コンピュータプログラムで高速に識別するために使われる数学的モデルが、有限状態オートマトン（Finite State Automaton）です。

オートマトンは、「現在の状態」と「入力された文字」によって次の状態へ遷移する仕組みです。プログラムがあるトークンパターンを検出するとき、状態遷移を繰り返して最終的に「受理状態（Accept State）」と呼ばれる合格状態に到達すれば、そのトークンとして正しいと認識します。

例えば、数値リテラル（[0-9]+）を検出するための極めて単純なオートマトンは以下のようになります。

このオートマトンでは、開始の「状態S」において数字（0〜9）が与えられると「状態A（受理状態）」に遷移します。それ以降、数字が続く限り「状態A」のループに残り、数字以外の文字が入力された時点でその手前までの文字列を「数値リテラル（NUMBER_LITERAL）」として確定します。

このような遷移ルールを「決定性有限オートマトン（DFA）」と呼びます。DFAは、どの状態にあっても入力文字に対して次の遷移先が一意に決定されるため、プログラムのループ処理として非常に効率よく実装できます。

文字列をトークン列に無事分解したのち、コンパイラはそれをプログラミング言語の構造的な文法ルールに照らし合わせる「構文解析」のフェーズに進みます。次節では、この構文解析のメカニズムを解説します。