終端記号と非終端記号

形式言語では、終端記号と非終端記号は形式文法における語彙の一部です。語彙は有限で空でない記号の集合です。終端記号は、語彙内の他の記号で置き換えることができない記号です。非終端記号は、同じ形式文法における生成規則によって、語彙内の他の記号で置き換えることができる記号です。 ^{[ 2 ]}

形式文法は、その文法の語彙に基づいて形式言語を定義する。

形式言語の文脈では、語彙という用語は一般的にアルファベットとして知られています。非終端記号は構文変数とも呼ばれます。

終端記号とは、形式文法によって定義された形式言語に現れることができる記号のことです。開始記号に生成規則を順次適用する処理は必ずしも終了するとは限りませんが、適用できる生成規則がなくなった時点で処理が終了すると、出力文字列は終端記号のみで構成されます。

例えば、2つの規則で定義される文法を考えてみましょう。この文法では、記号はБ終端記号であり、Ψ非終端記号と開始記号の両方です。文字列を作成するための生成規則は次のとおりです。

1. シンボルΨはБΨ
2. シンボルΨはБ

これБは終端記号です。なぜなら、これを他の記号に置き換える規則が存在しないからです。一方、 にはそれを変更する2つの規則があるため、これは非終端記号です。これらの規則は、最初の規則を任意の回数だけ適用できるという事実によって、可算無限個の有限長のΨ単語を含む形式言語を定義します。図1は、この文法で生成できる文字列を示しています。

非終端記号とは、形式文法によって定義される形式言語には出現できない記号のことです。形式文法には開始記号が含まれており、これは非終端記号の集合の指定された要素です。生成規則を順次適用することで、終端記号のみからなる文字列の集合を導出できます。生成された集合は、終端記号の集合上の形式言語です。

文脈自由文法とは、各生成規則の左辺が単一の非終端記号のみで構成される文法のことです。この制約は自明ではなく、すべての言語が文脈自由文法で生成できるわけではありません。生成できる言語は文脈自由言語と呼ばれます。これらはまさに、非決定性プッシュダウンオートマトンによって認識できる言語です。文脈自由言語は、ほとんどのプログラミング言語の構文の理論的基盤となっています。

文法は、どの記号が他のどの記号を置き換えることができるかを指定する生成規則（または単に「生成規則」）によって定義されます。これらの規則は、文字列を生成したり、文字列を解析したりするために使用できます。このような規則には、置き換えられる文字列で構成されるヘッド（左辺）と、置き換えられる文字列で構成されるボディ（右辺）があります。規則は多くの場合、ヘッド→ボディの形式で記述されます。たとえば、規則a → bは、 a をbに置き換えることができることを指定します。

1950年代にノーム・チョムスキーによって最初に提案された生成文法の古典的な形式化では、 ^{[ 3 ] [ 4 ]}文法Gは次の要素から構成されます。

• 非終端記号の有限集合N。
• Nと互いに素な、終端記号の有限集合Σ。
• 生成規則の有限集合Pで、各規則は次の形式である。

${\displaystyle V^{*}NV^{*}\rightarrow V^{*}}$

どこ$\displaystyle V^{*}}$は、語彙全体にわたるすべての可能な有限長文字列の集合を表します。${\displaystyle V=\Sigma \cup N}$クリーネスターを使用する。つまり、各生成規則は、少なくとも 1 つの非終端記号を含む記号列を別の記号列に置き換える。本体が空文字列のみで構成されている場合^{[注 1 ]}、混乱を避けるために特別な表記 (多くの場合Λ、eまたはε ) で表すことができる。

• 際立ったシンボル${\displaystyle S\in N}$それは開始記号です。

文法は、順序付き四つ組として正式に定義される。${\displaystyle \langle N,\シグマ ,P,S\rangle }$このような形式文法は、文献では書き換えシステムまたは句構造文法と呼ばれることが多い。 ^{[ 5 ] [ 6 ]}

バッカス・ナウア記法は、特定の文法を表現するための記法です。例えば、バッカス・ナウア記法では、符号付き整数を表すために以下の生成規則が使用されます。

<数字> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' <整数> ::= ['-'] <数字> { <数字> } 

この例では、終端記号は${\displaystyle \{-,0,1,2,3,4,5,6,7,8,9\}}$非終端記号は${\displaystyle \{}$<digit>、<integer>${\displaystyle \}}$[ ^{注2 ]}

別の例としては、次のものがあります。

${\displaystyle {\ce {S -> cAd}}}$

${\displaystyle {\ce {A -> a |アブ}}}$

この例では、終端記号は${\displaystyle \{\mathrm {a,b,c,d} \}}$非終端記号は${\displaystyle \{\mathrm {S,A} \}}$。

• アルファベット（正式な言語）
• チョムスキー階層
• 再帰文法