終端記号と非終端記号

終端記号（しゅうたんきごう、英: Terminal symbol）と非終端記号（ひしゅうたんきごう、英: Nonterminal symbol）は、形式文法における生成規則の記述に使われる記号である。終端記号は、その文法で生成される文字列の一部を構成する要素である。非終端記号は文法の生成規則内で使われる一種の変数名であり、他の非終端記号や終端記号（あるいはそれらの組み合わせ）に置換されて文字列を生成する（生成文法的観点からは）。

終端記号

終端記号は、形式文法における生成規則の入力や出力に現れ、その生成規則によってそれ以上は変換されない（これが”終端”と呼ばれる理由である）。

例として、次の２つの規則で定義される文法を考えよう：

1. x can become xa
2. x can become ax

ここで a に対する変換規則はないので、これは終端記号である。（一方、 x に対する変換規則は２つあるので、これは非終端記号である。）ある文法によって定義（あるいは生成）される形式言語とは、その文法によって生成される文字列の集合であり、 終端記号のみからなる 。

非終端記号

非終端記号とは、置換されうる記号のことであり、 構文変数 と呼ばれることもある。非終端記号の1つである 開始記号 から生成規則を適用していくことにより、言語のすべての文字列を得ることができる。実際、ある文法によって定義される言語とは、そのようにして得られる 終端 文字列の集合のことである。

文脈自由文法とは、すべての生成規則において左側がただ1つの非終端記号からなるような文法のことである。この制限は非自明であり、すべての言語が文脈自由文法によって生成できるわけではない。文脈自由文法によって生成される言語を文脈自由言語と呼ぶ。 文脈自由言語は、非決定的プッシュダウン・オートマトンによって認識される言語であり、多くのプログラミング言語の構文の理論的基礎になっている。

生成規則

文法は、記号を別の記号に置換する生成規則の集合によって定義される。これらの生成規則は、文字列の生成 やパースに使われる。それぞれの生成規則は、置換される文字列からなる ヘッド （左辺）と、置換する文字列からなる ボディ （右辺）を持つ。規則はしばしば ヘッド → ボディ のような形に書かれる。例えば、規則 z0 → z1 は、z0 を z1 で置き換えることを表す。

1950年代に ノーム・チョムスキー によって提案された生成文法の古典的な形式では、文法 G は次のように構成される：

• 非終端記号 の有限集合 $N$
• $N$ と 素 な 終端記号 の有限集合 $\Sigma$
• 生成規則 の有限集合 $P$ 。それぞれの規則は次のような形式である：

$(\Sigma \cup N)^{*} N (\Sigma \cup N)^{*} \rightarrow (\Sigma \cup N)^{*}$

ここで ${}^{*}$ は クリーネ・スター演算子、 $\cup$ は和集合を表し、よって $(\Sigma \cup N)^{*}$ は0個以上の演算子を表す。つまり、左辺は少なくとも1つの非終端記号を含む。右辺が空文字列の場合は、誤解を避けるために $\Lambda$, $e$, $\epsilon$ のような記号を使うことがある。

• 開始記号 $S \in N$

文法は、順序付けられた4つ組 $<N, \Sigma, P, S>$ として形式的に定義される。 このような形式的な文法は 項書き換え系 あるいは 句構造文法 と呼ばれることもある 。

例

例えば、符号付きの整数を表現する場合、バッカス・ナウア記法的に表すと以下のようになる。

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

ここで、記号 (-,0,1,2,3,4,5,6,7,8,9) は終端記号であり、<digit> や <integer> は非終端記号である。構文木の分岐点にあたるのが非終端記号で、葉（すなわち終端）にあたるのが終端記号である。

参考文献

• Aho, Sethi, & Ullman, Compilers: Principles, Techniques, and Tools, Addison-Wesley, 1986.