[解決済み] 文脈自由文法とは？

質問

文脈自由文法とは何か、誰か説明してください。Wikipediaの項目を見た後、Wikipediaの形式文法の項目を見て、私は全く、困惑したままです。どなたか、これらが何であるかを説明してくださる親切な方はいらっしゃいませんか？

私は構文解析を調査したいので、これを疑問に思っており、また、副次的に正規表現エンジンの限界もあります。

これらの用語が直接プログラミングに関連しているのか、それとも一般的な言語学に関連しているのか、よくわかりません。もしそうであれば、申し訳ありませんが、おそらくこれは移動することができますか？

どのように解決するのですか？

文脈自由文法とは、ある性質を満たす文法のことです。コンピュータサイエンスでは、文法は言語を記述し、特に、形式言語を記述します。

形式言語とは、文字列の集合（数学用語でオブジェクトの集まりのこと）です。形式言語の簡単な例としては、長さ 3 のすべての 2 進文字列の集合 {000, 001, 010, 011, 100, 101, 110, 111} が挙げられます。

文法は、文法で記述された言語で文字列を構成するために行える変換を定義することで機能します。文法は、開始記号（通常はS）をある記号の文字列に変換する方法を述べます。先にあげた言語のための文法は

S -> BBB
B -> 0
B -> 1

これを解釈する方法としては S で置き換えることができます。 BBB で、そして B は0に置き換えることができ B は 1 で置き換えることができます。したがって、010 という文字列を作るには S -> BBB -> 0BB -> 01B -> 010 .

文脈自由文法とは、置き換えられるもの（矢印の左）が単一の "非終端記号" である文法のことを指します。非終端記号とは、文法で使用する記号のうち、最終的な文字列には現れないものを指します。上の文法では、"S" と "B" が非終端記号で、"0" と "1" が "terminal" 記号にあたります。文法は

S -> AB
AB -> 1
A -> AA
B -> 0

のような規則を含むので、文脈自由ではありません。 AB -> 1 のように、左側に複数の非終端記号を持つルールが含まれるため、文脈自由ではありません。