- Authors
- Name
- Youngju Kim
- @fjvbn20031
字句解析 - トークン、パターン、正規表現
字句解析（Lexical Analysis）はコンパイルの最初の段階です。ソースコードの文字ストリームを読み取り、意味のある単位であるトークンに分割する過程を見ていきましょう。
1. 字句解析器の役割
字句解析器（Lexer、Scanner）は以下のことを行います。
ソースプログラム（文字ストリーム）
|
v
+------------------+
| 字句解析器 | <---> シンボルテーブル
+------------------+
|
v
トークンストリーム（パーサへ渡す）
主な機能
- トークン認識: 文字をトークン単位にまとめます。
- 空白/コメント除去: パーサに不要な文字をフィルタリングします。
- ソース位置追跡: エラーメッセージのための行番号と列番号を記録します。
- シンボルテーブル管理: 識別子をシンボルテーブルに登録します。
字句解析器を別途分離する理由
- 設計の簡素化: パーサが空白やコメントを気にする必要がありません。
- 移植性の向上: 入力デバイス依存の処理を字句解析器に隔離します。
- 効率性: トークン認識に特化した技法（有限オートマトン）を適用できます。
2. トークン、パターン、レキシム
この3つの概念は字句解析の核心です。
トークン（Token）
トークンはプログラミング言語の語彙単位を表す抽象的な名前です。
パターン（Pattern）
パターンはトークンを構成できる文字列の形態を記述します。
レキシム（Lexeme）
レキシムはソースコード内でパターンにマッチする実際の文字列です。
例
Cソースコード: printf("Total = %d\n", score);
+----------+--------------------------+---------------------+
| トークン | パターン | レキシムの例 |
+----------+--------------------------+---------------------+
| id | 文字で始まり、文字/数字の組合 | printf, score |
| num | 1つ以上の数字 | 42, 3, 100 |
| literal | " の間の文字列 | "Total = %d\n" |
| lparen | ( | ( |
| rparen | ) | ) |
| comma | , | , |
| semi | ; | ; |
+----------+--------------------------+---------------------+
トークンの種類
1. キーワード（Keyword）: if, else, while, return, ...
2. 識別子（Identifier）: ユーザー定義名
3. 定数（Constant）: 整数、実数、文字列リテラル
4. 演算子（Operator）: +, -, *, /, =, ==, !=, ...
5. 区切り子（Delimiter）: (, ), {, }, ;, ,, ...
3. トークンの属性（Attribute）
一つのトークン名に複数のレキシムがマッチする可能性があるため、追加情報が必要です。
ソースコード: position = initial + rate * 60
トークンストリーム:
<id, "position">
<assign_op, >
<id, "initial">
<add_op, >
<id, "rate">
<mul_op, >
<num, 60>
ここで2番目の要素が属性です。
識別子の属性は通常シンボルテーブルエントリへのポインタです。数値の属性は実際の値になります。
4. 正規表現（Regular Expression）
トークンのパターンを定義するために**正規表現（regex）**を使用します。
基本演算
アルファベットSigma上で定義される正規表現の基本演算は次の3つです。
1. 和集合（Union）: r | s
- rまたはsにマッチする文字列
2. 連接（Concatenation）: rs
- rにマッチする文字列の後にsにマッチする文字列
3. 閉包（Closure）: r*
- rにマッチする文字列の0回以上の繰り返し
基本正規表現
式 説明 マッチ例
-------------------------------------------------
a 文字'a'そのもの "a"
epsilon 空文字列 ""
r | s rまたはs rが"a"、sが"b"なら"a"または"b"
rs rの後にs "ab"
r* rの0回以上の繰り返し "", "a", "aa", "aaa", ...
拡張記法
便宜のための略記法です。
r+ = r r* (1回以上の繰り返し)
r? = r | epsilon (0回または1回)
[a-z] = a | b | ... | z (文字クラス)
[^a-z] = a-z以外の文字 (否定文字クラス)
. = 任意の1文字
正規表現の例
// 整数リテラル
digit = [0-9]
digits = digit+
integer = digits
// 浮動小数点リテラル
fraction = . digits | epsilon
exponent = (E | e)(+ | - | epsilon) digits | epsilon
float_num = digits fraction exponent
// 識別子
letter = [a-zA-Z_]
identifier = letter (letter | digit)*
// 文字列リテラル（二重引用符内のそれ以外の文字）
string_lit = " [^"]* "
5. 正規定義（Regular Definition）
複雑な正規表現を簡潔に表現するために、正規表現に名前を付けて使用します。
// C言語の識別子の正規定義
letter_ -> [a-zA-Z_]
digit -> [0-9]
id -> letter_ (letter_ | digit)*
// C言語の整数定数の正規定義
digit -> [0-9]
nonzero -> [1-9]
decimal -> nonzero digit*
octal_dig -> [0-7]
octal -> 0 octal_dig*
hex_dig -> [0-9a-fA-F]
hex -> 0 (x|X) hex_dig+
integer -> decimal | octal | hex
注意: 正規定義では循環参照は許可されません。各名前はそれ以前に定義された名前のみを参照できます。
6. 入力バッファリング（Input Buffering）
字句解析器はソースコードを1文字ずつ読む必要がありますが、I/Oコストを削減するためにバッファリング技法を使用します。
ダブルバッファリング（Double Buffering）
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| E | = | M | * | C | * | * | 2 |eof| . | . | . | . | . | . | . |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
^ ^
| |
lexemeBegin forward
Buffer 1 Buffer 2
- 2つのバッファを交互に使用して連続的な読み取りを保証します。
lexemeBegin: 現在のレキシムの開始位置forward: 現在検査中の文字位置- 各バッファの終わりに**センチネル（sentinel）**文字
eofを置いて境界検査を簡素化します。
センチネルを使用したforwardポインタの移動
// センチネルなしのコード（毎回2回の検査）
forward++;
if (forward >= bufferEnd) {
// 次のバッファをロード
reloadBuffer();
}
if (*forward == EOF) {
// 入力終了処理
terminate();
}
// センチネルありのコード（通常1回の検査）
forward++;
if (*forward == EOF) {
if (forward == bufferEnd) {
reloadBuffer(); // バッファ末尾のセンチネル
forward = bufferStart;
} else {
terminate(); // 実際の入力終了
}
}
7. トークン認識の例
簡単な言語のトークン認識過程を見てみましょう。
関係演算子の認識
relop -> < | <= | <> | > | >= | =
この認識過程を**遷移図（Transition Diagram）**で表現します。
開始 --'<'--> s1 --'='--> [return LE]
|
+--'>'--> [return NE]
|
+--other--> [return LT] (retract)
開始 --'='--> [return EQ]
開始 --'>'--> s2 --'='--> [return GE]
|
+--other--> [return GT] (retract)
retract は forward ポインタを1つ戻すことを意味します。例えば、< の次に = でも > でもない文字が来た場合、その文字を次のトークンの一部として処理する必要があります。
識別子とキーワードの認識
開始 --letter--> s1 --letter|digit--> s1
|
+--other--> [キーワードテーブル確認後 return]
識別子を認識した後、キーワードテーブルを検索してキーワードかどうか確認します。if、else、while のような予約語は識別子と形態が同じなので、別途処理が必要です。
// キーワードテーブルの初期化
Map<String, TokenType> keywords = new HashMap<>();
keywords.put("if", TokenType.IF);
keywords.put("else", TokenType.ELSE);
keywords.put("while", TokenType.WHILE);
keywords.put("return", TokenType.RETURN);
// 識別子認識後
String lexeme = getLexeme();
if (keywords.containsKey(lexeme)) {
return new Token(keywords.get(lexeme), lexeme);
} else {
return new Token(TokenType.ID, lexeme);
}
8. 簡単な字句解析器の実装
Javaで簡単な字句解析器を実装してみましょう。
public class SimpleLexer {
private String input;
private int pos;
public SimpleLexer(String input) {
this.input = input;
this.pos = 0;
}
public Token nextToken() {
skipWhitespace();
if (pos >= input.length()) {
return new Token(TokenType.EOF, "");
}
char ch = input.charAt(pos);
// 数字: 整数リテラル認識
if (Character.isDigit(ch)) {
return readNumber();
}
// 文字: 識別子またはキーワード認識
if (Character.isLetter(ch) || ch == '_') {
return readIdentifier();
}
// 演算子と区切り子
switch (ch) {
case '+': pos++; return new Token(TokenType.PLUS, "+");
case '-': pos++; return new Token(TokenType.MINUS, "-");
case '*': pos++; return new Token(TokenType.STAR, "*");
case '/': pos++; return new Token(TokenType.SLASH, "/");
case '=':
if (peek() == '=') {
pos += 2;
return new Token(TokenType.EQ, "==");
}
pos++;
return new Token(TokenType.ASSIGN, "=");
case '(': pos++; return new Token(TokenType.LPAREN, "(");
case ')': pos++; return new Token(TokenType.RPAREN, ")");
case ';': pos++; return new Token(TokenType.SEMI, ";");
default:
throw new RuntimeException(
"Unexpected character: " + ch + " at position " + pos
);
}
}
private Token readNumber() {
int start = pos;
while (pos < input.length() && Character.isDigit(input.charAt(pos))) {
pos++;
}
return new Token(TokenType.NUM, input.substring(start, pos));
}
private Token readIdentifier() {
int start = pos;
while (pos < input.length() &&
(Character.isLetterOrDigit(input.charAt(pos)) ||
input.charAt(pos) == '_')) {
pos++;
}
String lexeme = input.substring(start, pos);
TokenType type = Keywords.lookup(lexeme);
return new Token(type != null ? type : TokenType.ID, lexeme);
}
private void skipWhitespace() {
while (pos < input.length() && Character.isWhitespace(input.charAt(pos))) {
pos++;
}
}
private char peek() {
return (pos + 1 < input.length()) ? input.charAt(pos + 1) : '\0';
}
}
実行例
入力: "x = 10 + y;"
トークンストリーム:
<ID, "x">
<ASSIGN, "=">
<NUM, "10">
<PLUS, "+">
<ID, "y">
<SEMI, ";">
<EOF, "">
9. エラー処理
字句解析器がどのパターンにもマッチしない文字に遭遇した場合のエラー処理戦略です。
- パニックモード（Panic Mode）: マッチするパターンが見つかるまで文字をスキップします。
- 文字削除: 不正な文字を削除して続行します。
- 文字挿入: 足りない文字を挿入します（例: 引用符のペアを合わせる）。
- 文字置換: 不正な文字を正しい文字に置き換えます。
実際のコンパイラでは、できるだけ多くのエラーを一度に報告するために、回復後も分析を続行します。
まとめ
| 概念 | 核心内容 |
|---|---|
| トークン | 語彙単位の抽象的な名前（id、num、relopなど） |
| パターン | トークンを構成する文字列の形態（正規表現） |
| レキシム | パターンにマッチする実際の文字列 |
| 正規表現 | 和集合、連接、閉包の3つの基本演算 |
| 正規定義 | 正規表現に名前を付けて再利用 |
| 入力バッファリング | ダブルバッファとセンチネルで効率的I/O |
| 遷移図 | トークン認識過程を状態遷移で表現 |
字句解析はコンパイルの最も基礎的な段階ですが、全コンパイル時間のかなりの部分を占めるため効率的な実装が重要です。次の記事では、正規表現に基づいて字句解析器を自動生成する有限オートマトンを扱います。