形式言語と処理機械（オートマトン）の関係

１．チョムスキーの分類

形式言語とオートマトンの関係を詳しく述べるために、チョムスキーの分類を再掲しておく。

２．正規文法

識別子（変数名、関数名など）の構文規則は次のように正規文法により定義できる[1]。

  ＜識別子＞　::＝　＜英字＞ ｛ ＜英数字＞ ｝
  ＜英数字＞　::＝　＜英字＞ | ＜数字＞
  ＜英字＞　  ::＝　a | b | … | z | A | B | … | Z
  ＜数字＞　  ::＝　0 | 1 | 2 | … | 9

ここで ｛ ＜英数字＞ ｝ は ＜英数字＞ が０個以上並んだものを表す。 第２回の授業での記法を使えば、( ＜英数字＞ )* となる。

正規文法により定義された構文は有限オートマトン(finite automaton)によって認識することができる。 有限オートマトンは、有限個の状態と状態間の遷移を基本概念とする認識機械である。 初期状態から出発し、入力語中の記号を１つずつ読み込み、状態遷移を次々に繰り返し、 入力語が認識されるかどうかを調べる。上の構文規則で定義される識別子を認識する 有限オートマトンを図１．に示す。図中、○は状態を表し、矢印は状態遷移を表す。

初期状態s0で英字を読み込むと、状態s1に遷移する。 s1では、英字または数字の読み込みによって自分自身へ遷移する。 状態s1が◎になっているのは、それが識別子を認識した状態になっていることを表している。

図１．識別子を認識する有限オートマトン

この有限オートマトンの数学モデルは <Σ, S, s₀, δ, F> の5要素から構成される。

• Σ は入力文字セット（有限だが空ではないシンボルの集合）
• S は有限であって空でない状態の集合
• s₀ は Sの要素でもある初期状態
• δ は状態遷移関数: δ: S x Σ → S
• F は終了状態の集合であり、 Sの部分集合（空もありうる）

プログラミング言語の構成要素は識別子のほか、 予約語（C言語で言えば、int, if, for, structなど）、演算子、記号、数値などが存在するが、 いずれも、正規文法で定義することができる。 したがって、コンパイラやインタプリタの字句解析フェーズでは、 このような有限オートマトンに対応する処理メカニズムを何らかの形で実現すればよい。

参考文献