「形式文法」の版間の差分
削除された内容 追加された内容
英語版の最新版までの一部の更新を翻訳してマージ |
形式言語にリンクしておく。 |
||
| (19人の利用者による、間の36版が非表示) | |||
1行目:
{{seealso|形式言語}}
形式文法にはふたつの捉えかたがある。それは「生成」と「分析」である。[[#チョムスキー階層]]の節および単独記事に詳細があるが、両者は対応するので、ある意味では同じものをそれぞれ逆の側から見たものにすぎない。
以下で「文法の規則（構文規則）の集まり」と呼んでいるのは、具体的には、[[句構造規則#基本モデル]]にあるようなものである。また[[終端記号と非終端記号]]の記事も参照のこと。
* [[生成文法]]（''Generative grammar''）は、
* '''分析的文法'''（''Analytic grammar''）は、文法の規則（構文規則）の集まりを「任意の終端記号列に対し、パターンが一致すれば右辺から左辺に書き換え規則が適用できる規則の集まりであり、最終的にトップレベルの非終端記号（たとえば <文>）が得られれば'''受理された'''として、入力の列がその言語に含まれるか否かを判定できるもの」と見るものである。
生成文法は、ある言語に含まれる文字列を生成する[[アルゴリズム]]を定式化するもの、分析的文法は、ある言語に含まれる文字列を[[構文解析]]し受理するアルゴリズムを定式化するもの、とも言える（この2者への分類は、構文解析の手法の分類の、[[トップダウン構文解析]]と[[ボトムアップ構文解析]]といくぶんかまぎらわしい。実際に、トップダウン構文解析は流れとして左辺から右辺への書換えとなっている点は生成的であるのに対し、一方のボトムアップ構文解析は右辺から左辺への「還元」（reduce）を主要な動作とする点で分析的である。しかし、どちらも構文解析を目的とするという点では、分析的文法にあたる）。
{{Main|生成文法}}
▲== 生成文法 ==
生成文法は文字列変換規則の集まりである。ある言語の文字列を生成するには、まずひとつの「開始」文字だけから成る文字列から始めて、規則を適当な回数適用して文字列を書き換えていく。逆に言えば、その言語はその規則群によって生成される全文字列を含む。ある規則の組み合わせで生成された文字列について、別の規則の適用の仕方でも同じ文字列が生成できる場合、その文法は[[曖昧な文法|曖昧]]であると言う。
21 ⟶ 23行目:
=== 形式的定義 ===
生成文法の定式化は[[1950年代]]に[[ノーム・チョムスキー]]によって最初に提案された<ref name="Chomsky1956">Chomsky, Noam, "Three Models for the Description of Language," ''IRE Transactions on Information Theory'', Vol. 2 No. 2, pp. 113-123, 1956.</ref><ref name="Chomsky1957">Chomsky, Noam, ''Syntactic Structures'', Mouton, The Hague, 1957.</ref>。文法 ''G'' は以下の構成要素から成る。
* 「[[非終端記号]]」の[[有限集合]] <math>N</math>。
* 「[[終端記号]]」の有限集合 <math>\Sigma</math>。<math>N</math> とは共通の元を持たない。
* 「生成規則」の有限集合 <math>P</math>。各生成規則は以下のような形式である。
:: <math>(\Sigma \cup N)^{*}</math> 内の文字列 <math>\longrightarrow (\Sigma \cup N)^{*} </math> 内の文字列
:（ここで <math>{}^{*}</math> は[[クリーネスター]]であり、<math>\cup</math> は[[合併 (集合論)|和集合]]であり）<math>\longrightarrow</math> の左側には少なくともひとつ以上の非終端記号を含まなければならない。
* <math>N</math>内の記号<math>S</math>は「開始記号」である。
一般にこのような形式文法 <math>G</math> は 4要素 <math>(N, \Sigma, P, S)</math> で要約される。
33 ⟶ 35行目:
=== 例 ===
''以下の例では、[[形式言語]]を[[集合]]の内包的記法で記述している。''
<math>N = \left \{S, B\right \}</math>, <math>\Sigma = \left \{a, b, c\right \}</math> の文法 <math>G</math> について、生成規則 <math>P</math> が以下の規則から構成される。
56 ⟶ 58行目:
=== チョムスキー階層 ===
{{Main|チョムスキー階層}}
{{seealso|形式言語の階層}}
==== 文脈自由文法 ====
[[文脈自由文法]]では、生成規則の左側にはひとつの非終端記号だけが置かれる。
前述の例で定義された言語は文脈自由言語ではない。これは[[文脈自由言語の反復補題]]を使って厳密に証明可能である。<math>\left \{ a^{n}b^{n} | n > 0 \right \}</math> で表される言語（ひとつ以上の 'a' の後に同じ個数の 'b' が続く）を定義する文法 <math>G2</math> を例として考えよう。<math>G2</math> は <math>N=\left \{S\right \}</math>, <math>\Sigma=\left \{a,b\right \}</math> から成り、開始記号 <math>S</math> と以下の生成規則で定義される。
: 1. <math>S \longrightarrow aSb</math>▼
: 2. <math>S \longrightarrow ab</math>▼
文脈自由言語は[[アーリー法]]のようなアルゴリズムを使って <math>O(n^3)</math> の時間（[[ランダウの記号]]参照）で認識可能である。すなわち、全ての文脈自由言語について、任意の文字列を入力とし、それが特定の言語に含まれるかどうかを <math>O(n^3)</math> の時間内に決定する機械を構築できる。ここで、<math>n</math> は入力文字列長である<ref name="Earley1970">Earley, Jay, "An Efficient Context-Free Parsing Algorithm," ''Communications of the ACM'', Vol. 13 No. 2, pp. 94-102, February 1970.</ref>。さらに、文脈自由言語の重要なサブセットは他のアルゴリズムを使って線形時間で認識可能である。
==== 正規文法 ====
89 ⟶ 96行目:
* [[接辞文法]]<ref name="Koster1971">Koster , Cornelis H. A., "Affix Grammars," in ''ALGOL 68 Implementation'', North Holland Publishing Company, Amsterdam, p. 95-109, 1971.</ref>と[[属性文法]]<ref name="Knuth1968">Knuth, Donald E., "Semantics of Context-Free Languages," ''Mathematical Systems Theory'', Vol. 2 No. 2, pp. 127-145, 1968.</ref><ref name="Knuth1971">Knuth, Donald E., "Semantics of Context-Free Languages (correction)," ''Mathematical Systems Theory'', Vol. 5 No. 1, pp 95-96, 1971.</ref>は、意味属性と意味に関する操作を加えて生成規則を書き換えられるようにした。これにより表現力を増加させると共に、実用的な言語変換ツールを構築するのにも有効である。
<!--形式文法に関する学会が毎年開催されている。[http://www.formalgrammar.tk]--><!-- ← 一応存在していたようですが、2015年11月30日現在、かなりあやしげなリダイレクトで飛ばされるようですのでコメントアウトします-->
== 分析的文法 ==
[[
* [[Yacc]]
* [http://languagemachine.sourceforge.net The Language Machine] は制限のない分析的文法を直接実装したものである。置換規則は入力を変換して出力とふるまいを生成する。このシステムは、制限のない分析的文法の規則を適用したときに何が起きているかを図示することもできる<!-- the lm-diagram -->。
*
* [[
* [[リンク文法]]：言語学者によって設計された分析的文法の形式。単語間の所有関係を調べる文法構造を導く<ref name="Sleater&Temperly1991">Sleator, Daniel D. & Temperly, Davy, "Parsing English with a Link Grammar," Technical Report CMU-CS-91-196, Carnegie Mellon University Computer Science, 1991.</ref><ref name="Sleater&Temperly1993">Sleator, Daniel D. & Temperly, Davy, "Parsing English with a Link Grammar," ''Third International Workshop on Parsing Technologies'', 1993. (Revised version of above report.)</ref>。
105 ⟶ 113行目:
* [[文脈自由言語の反復補題]]
* [[構文木]]
* [[句構造規則]]
* [[L-system]]
* [[ロジバン]]
114 ⟶ 123行目:
* [http://www.formalgrammar.tk/ Yearly Formal Grammar conference]
{{Normdaten}}
[[Category:形式言語|けいしきふんほう]]
[[Category:数学に関する記事|けいしきふんほう]]
| |||