Skip to content

Latest commit

 

History

History
78 lines (46 loc) · 6.6 KB

README.md

File metadata and controls

78 lines (46 loc) · 6.6 KB

形式言語 (formal language)

1954年のジョージタウン大学-IBMの実験1以降、機械翻訳に対する関心が高まっていた。

1960年代は多くのOSがハードウェア固有で互換性が低かったため、OS開発者やコンピュータメーカーは、自社システムの競争力を高めるために、人気のプログラミング言語のコンパイラを自社システムに移植する必要があった。ところが、プログラミング言語の文法を厳密に定義する方法が無かったため、移植の担当者は細部で実装を参考にせざるを得なかった。その結果として、同じプログラミング言語でも互換性の無い実装が生まれてしまった。例えば、初期のALGOL 60においては、ネストしたIF文に続くELSEがどちらのIFに属するかの解釈の違いがあった。このような問題に対して、ALGOL 60では文法を定義するために文脈自由文法を用い、その定義にBNF記法を考案した。

形式言語における計算機及び認識する言語のモデルは、次の包含関係にある。

  • 有限オートマトン ⊂ プッシュダウンオートマトン ⊂ 線形拘束オートマトン ⊂ チューリングマシン
  • 正規言語 ⊂ 文脈自由言語 ⊂ 文脈依存言語 ⊂ 帰納的可算言語

正規言語

有限オートマトン (FA, finite automaton)

正式な定義は差し置いて、mermaidのstateDiagram-v2で示せるモデルが有限オートマトンである。特に、入力に対して遷移する状態が定まっているものを決定性有限オートマトンと呼ぶ。

[!NOTE] 有限オートマトンの正式な記述は実際に使われているの？ 実際に使われている。PythonのAutomataにおけるDFAクラスでは、まさに状態、アルファベット、遷移関数、開始状態、受理状態の集合の5つ組の引数を取る。2ただしアルファベットはinput_symbolとなっている。個人的にはその方が分かりやすいのでとても良いと思う。

ここで有限とは、(WIP)

非決定性有限オートマトン (NFA, nondeterministic finite automaton)

[!NOTE] NFAの動きを脳内でシミュレーションするのが難しい...NFAによるモデル化って、どんな時に役に立つの？

正規表現

[!NOTE] 「正規表現として記述された言語は正規である」といっても、あらゆる言語が.*で認識できるのであれば、あらゆる言語が正規なのでは？ 自作プログラミング言語のパーサーとして、.*という正規表現を用意することを考えると良いだろう。たしかに受理はするが、パースしたとは言えない。
言語の定義として文字列の集合であることは十分条件に過ぎず、生成規則も重要である、という理解をすると良さそうだ。それを踏まえると、「その言語の文字列のみを受理する正規表現を持つ言語は正規である」という表現の方がより正確かもしれない。

文脈自由言語 (CFL, context-free language)

正規言語ではJSONやXMLのパースができない。それは、開き括弧の数を記憶することができないためである。正規言語にスタックの概念を1つ導入し、JSONやXMLに加えて多くのプログラミング言語のパースを可能にしたのが文脈自由言語である。

文脈自由文法 (CFG, context-free grammar)

文脈自由言語を生成する文法を文脈自由文法という。例えば、次の通り定義される文脈自由文法$G_1$を考える。

A -> 0A1
A -> B
B -> #

$G_1$の各行を書き換え規則(substitution rule)という。書き換え規則は文字から文字への変換を定義する。文字は次の2種類に分けられる。

  1. 変数(variable)（または非終端記号）。書き換え規則の左辺に登場し、他の文字に変換できる文字をいう。通常大文字。$G_1$でいえばA,Bがあたる。
  2. 終端文字(terminal)。プログラミングでいうリテラルに相当すると思われる。$G_1$でいえば01#があたる。

バッカス・ナウア記法 (BNF)

プログラミング言語の文法を厳密に示すことは、コンパイラの環境差異に関わる現実的な問題であった。ALGOL 60において、文法の規則にはスタックを用いることができる文脈自由文法が採用され、その記述のためにバッカス・ナウア記法が考案された。2024年現在では、BNFを拡張したEBNFが標準的に用いられている。例えば、Pythonの文法はEBNFを用いて定義され、公開されている。3

BNFやその拡張仕様を用いることで、プログラミング言語の開発において、既存の構文解析器やドキュメント生成ツールを用いることができる。

  • PEG:WIP

プッシュダウン・オートマトン

有限オートマトンにスタックを加え、プッシュとポップが可能になったモデルをプッシュダウン・オートマトンと呼ぶ。4

非文脈自由文法

帰納的可算言語 / チューリングマシン

PDAでは、マシンが入力を左から右に読むだけだったが、入力に応じて左に戻ったり、入力を書き換えられたらどうなるか。そのような機能を持たせたマシンをチューリングマシンという。チューリングマシンは、無限の長さを持つテープとヘッドを使って、入力の任意の位置に自由にアクセスし、読み書きができるため、スタックよりも柔軟で強力な記憶装置を持つ。

文脈依存言語 (context-sensitive language) / 線形拘束オートマトン (LBA, linear bounded automation)

Footnotes

  1. Georgetown–IBM_experiment ↩

  2. Finite Automata Examples ↩

  3. Full Grammar Specification ↩

  4. Pushdown automatonによると、スタック最上段以外からの取り出しなど、操作を拡張したモデルをスタック・オートマトンと呼ぶようだ。 ↩