終端記号と非終端記号

終端記号（しゅうたんきごう、英: Terminal symbol）と非終端記号（ひしゅうたんきごう、英: Nonterminal symbol）は、句構造規則の生成規則中にあらわれる記号類の分類である。規則群のうちの、どれかの規則の左辺にあらわれている記号、すなわち、他の記号列と置換できるものとして定義されている記号が非終端記号で、ある種の変数名のようなものとも言える。それに対し、右辺の記号列中のみにあらわれる、いわゆる「アルファベット」の1文字から成る記号が終端記号である。実用上は（プログラミング言語などでは）終端記号は文字そのものではなく、英語などにおける「単語」に相当する「トークン」と呼ばれるもの（「字句」の記事、および字句解析#トークンなどを参照）であることも多い。

終端記号

終端記号は、生成規則の右辺のみに現れ、左辺には現れない。よって、生成規則によってそれ以上は変換されない（これが“終端”と呼ばれる理由である）。

非終端記号

非終端記号とは、置換されうる記号のことであり、構文変数 と呼ばれることもある。

句構造文法

→詳細は「句構造文法」を参照

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

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

• 非終端記号 の集合 $N$
• 終端記号(アルファベット) の集合 $\Sigma$
• 生成規則 の集合 $P$。$P$ の要素であるそれぞれの規則は次のような形をしている：

$(\Sigma \cup N)^{*}n(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}$ ここで $n\in N$

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

• 開始記号 $s\in N$

以上からなる4つ組 $<N,\Sigma ,P,s>$ として、言語が形式的に定義される。

参考文献

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