「形式文法」の版間の差分
削除された内容 追加された内容
Louperibot (会話 | 投稿記録) m robot Adding: ko:형식 문법 |
形式言語にリンクしておく。 |
||
(21人の利用者による、間の43版が非表示) | |||
1行目:
{{seealso|形式言語}}
形式文法にはふたつの捉えかたがある。それは「生成」と「分析」である。[[#チョムスキー階層]]の節および単独記事に詳細があるが、両者は対応するので、ある意味では同じものをそれぞれ逆の側から見たものにすぎない。
以下で「文法の規則(構文規則)の集まり」と呼んでいるのは、具体的には、[[句構造規則#基本モデル]]にあるようなものである。また[[終端記号と非終端記号]]の記事も参照のこと。
* [[生成文法]](''Generative grammar'')は、
* '''分析的文法'''(''Analytic grammar'')は、文法の規則(構文規則)の集まりを「任意の終端記号列に対し、パターンが一致すれば右辺から左辺に書き換え規則が適用できる規則の集まりであり、最終的にトップレベルの非終端記号(たとえば <文>)が得られれば'''受理された'''として、入力の列がその言語に含まれるか否かを判定できるもの」と見るものである。
生成文法は、ある言語に含まれる文字列を生成する[[アルゴリズム]]を定式化するもの、分析的文法は、ある言語に含まれる文字列を[[構文解析]]し受理するアルゴリズムを定式化するもの、とも言える(この2者への分類は、構文解析の手法の分類の、[[トップダウン構文解析]]と[[ボトムアップ構文解析]]といくぶんかまぎらわしい。実際に、トップダウン構文解析は流れとして左辺から右辺への書換えとなっている点は生成的であるのに対し、一方のボトムアップ構文解析は右辺から左辺への「還元」(reduce)を主要な動作とする点で分析的である。しかし、どちらも構文解析を目的とするという点では、分析的文法にあたる)。
{{Main|生成文法}}
▲== 生成文法 ==
生成文法は文字列変換規則の集まりである。ある言語の文字列を生成するには、まずひとつの「開始」文字だけから成る文字列から始めて、規則を適当な回数適用して文字列を書き換えていく。逆に言えば、その言語はその規則群によって生成される全文字列を含む。ある規則の組み合わせで生成された文字列について、別の規則の適用の仕方でも同じ文字列が生成できる場合、その文法は[[曖昧な文法|曖昧]]であると言う。
20 ⟶ 22行目:
=== 形式的定義 ===
生成文法の定式化は[[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> が以下の規則から構成される。
55 ⟶ 57行目:
=== チョムスキー階層 ===
{{Main|チョムスキー階層}}
[[1950年代]]に[[ノーム・チョムスキー]]が初めて生成文法を定式化したとき、彼はそれを4つのタイプに分類した。これを[[チョムスキー階層]]と言う。これらのタイプの差異は、生成規則の制限の強さであり、表現できる形式言語の多様さである。重要なふたつのタイプとして「[[文脈自由文法]]」と「[[正規文法]]」がある。これらの文法で生成される言語はそれぞれ「[[文脈自由言語]]」と「[[正規言語]]」と呼ばれる。制限のない文法よりも非力ではあるが、これらの言語は[[チューリングマシン]]で受容(認識)することができ、[[構文解析]]が簡単であるために、これらの文法はよく使われる。たとえば文脈自由文法については効率的な[[LL法]]や[[LR法]]の構文解析器を生成するアルゴリズムが知られている。▼
{{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>。さらに、文脈自由言語の重要なサブセットは他のアルゴリズムを使って線形時間で認識可能である。
==== 正規文法 ====
68 ⟶ 76行目:
<math>\left \{ a^{n}b^{m} | m,n > 0 \right \}</math> で表される言語(ひとつ以上の 'a' の後にひとつ以上の 'b' が続く)を定義する文法 <math>G3</math> を例として考える。<math>G3</math> は <math>N=\left \{S, A,B\right \}</math>, <math>\Sigma=\left \{a,b\right \}</math> から成り、開始記号 <math>S</math> と以下の生成規則で定義される。
: 1. <math>S \
: 2. <math>A \
: 3. <math>A \
: 4. <math>B \
: 5. <math>B \
: 6. <math>S \rightarrow \epsilon</math>
正規文法で生成される言語は、全て[[有限オートマトン]]で線形時間内で認識される。実際には正規文法は[[正規表現]]
==== 正規言語と文脈自由言語 ====
84 ⟶ 93行目:
形式文法についてのチョムスキーの本来の階層に対して言語学者や情報工学者が独自の拡張や派生を試みてきた。その目的は表現力を強化するか[[構文解析]]をやりやすくするためである。もちろん、これら二つの目的は方向性が異なる。表現力が強化された形式文法は自動化されたツールによる構文解析は困難となる。最近開発された文法には以下のようなものがある。
* [[木接合文法]]は、文字列だけでなく[[構文木]]も操作することによって規則を書き換えて、従来の文法で生成されるよりも表現力豊かな言語を生成する<ref name="JoshiEtAl1975">Joshi, Aravind K., ''et al.'', "Tree Adjunct Grammars," ''Journal of Computer Systems Science'', Vol. 10 No. 1, pp. 136-163, 1975.</ref>。
* [[接辞文法]]<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>。
==関連項目==
* [[抽象構文木]]
* [[バッカス・ナウア記法]]
* [[曖昧な文法]]
* [[文脈自由言語の反復補題]]
* [[構文木]]
* [[句構造規則]]
* [[L-system]]
* [[ロジバン]]
== 脚注 ==
{{Reflist}}
== 外部リンク ==
* [http://www.formalgrammar.tk/ Yearly Formal Grammar conference]
{{Normdaten}}
[[Category:形式言語|けいしきふんほう]]
[[Category:数学に関する記事|けいしきふんほう]]
|