文法入門
用語の文学的意味では、文法は自然言語での会話の構文規則を示します。言語学は、英語、サンスクリット語、マンダリンなどの自然言語の開始以来、文法を定義しようと試みてきました。
形式言語の理論は、コンピュータサイエンスの分野で広く適用可能です。 Noam Chomsky 1956年にコンピュータ言語を書くのに効果的な文法の数学的モデルを与えました。
文法
文法 G 正式には4タプル（N、T、S、P）として記述できます。ここで-
N または VN 変数または非終端記号のセットです。
T または ∑ 終端記号のセットです。
S は開始記号と呼ばれる特別な変数、S∈Nです。
Pは、終端記号と非終端記号の生成規則です。プロダクションルールは、αおよびβは、V上の文字列である形態α→β有するN ∪Σ及びαの少なくとも一つのシンボルがVに属するNを。
例
文法G1−
（{S、A、B}、{a、b}、S、{S→AB、A→a、B→b}）
ここに、
S, A, そして B 非終端記号です。
a そして b 終端記号です
S は開始記号、S∈Nです
プロダクション、 P : S → AB, A → a, B → b
例
文法G2−
（（{S、A}、{a、b}、S、{S→aAb、aa→aaAb、A→ε}）
ここに、
S そして A 非終端記号です。
a そして b 終端記号です。
ε 空の文字列です。
S は開始記号、S∈Nです
製造 P : S → aAb, aA → aaAb, A → ε
文法からの派生
文字列は、文法のプロダクションを使用して他の文字列から派生させることができます。文法の場合G 生産があります α → β、私たちはそれを言うことができます x α y 派生 x β y に G。この導出は次のように記述されます-
x α y ⇒G x β y
例
文法を考えてみましょう-
G2 =（{S、A}、{a、b}、S、{S→aAb、aA→aaAb、A→ε}）
導出できる文字列のいくつかは次のとおりです。
S⇒を1aA B生産S→aAbをを使用して
⇒を1aA BB生産AAは使用→aAbを
⇒AAA A BBB使用して生産AAの→aAbを
⇒プロダクションAを使用したaaabbb →ε