「形式文法」の版間の差分
削除された内容 追加された内容
形式言語にリンクしておく。 |
|||
(5人の利用者による、間の14版が非表示) | |||
1行目:
{{seealso|形式言語}}
形式文法にはふたつの捉えかたがある。それは「生成」と「分析」である。[[#チョムスキー階層]]の節および単独記事に詳細があるが、両者は対応するので、ある意味では同じものをそれぞれ逆の側から見たものにすぎない。
以下で「文法の規則(構文規則)の集まり」と呼んでいるのは、具体的には、[[句構造規則#基本モデル]]にあるようなものである。また[[終端記号と非終端記号]]の記事も参照のこと。
* [[生成文法]](''Generative grammar'')は、
* '''分析的文法'''(''Analytic grammar'')は、文法の規則(構文規則)の集まりを「任意の終端記号列に対し、パターンが一致すれば右辺から左辺に書き換え規則が適用できる規則の集まりであり、最終的にトップレベルの非終端記号(たとえば <文>)が得られれば'''受理された'''として、入力の列がその言語に含まれるか否かを判定できるもの」と見るものである。
生成文法は、ある言語に含まれる文字列を生成する[[アルゴリズム]]を定式化するもの、分析的文法は、ある言語に含まれる文字列を[[構文解析]]し受理するアルゴリズムを定式化するもの、とも言える(この2者への分類は、構文解析の手法の分類の、[[トップダウン構文解析]]と[[ボトムアップ構文解析]]といくぶんかまぎらわしい。実際に、トップダウン構文解析は流れとして左辺から右辺への書換えとなっている点は生成的であるのに対し、一方のボトムアップ構文解析は右辺から左辺への「還元」(reduce)を主要な動作とする点で分析的である。しかし、どちらも構文解析を目的とするという点では、分析的文法にあたる)。
{{Main|生成文法}}
▲== 生成文法 ==
生成文法は文字列変換規則の集まりである。ある言語の文字列を生成するには、まずひとつの「開始」文字だけから成る文字列から始めて、規則を適当な回数適用して文字列を書き換えていく。逆に言えば、その言語はその規則群によって生成される全文字列を含む。ある規則の組み合わせで生成された文字列について、別の規則の適用の仕方でも同じ文字列が生成できる場合、その文法は[[曖昧な文法|曖昧]]であると言う。
26 ⟶ 28行目:
:: <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|形式言語の階層}}
==== 文脈自由文法 ====
93 ⟶ 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>。
119 ⟶ 123行目:
* [http://www.formalgrammar.tk/ Yearly Formal Grammar conference]
{{Normdaten}}
[[Category:形式言語|けいしきふんほう]]
[[Category:数学に関する記事|けいしきふんほう]]
|