終端記号（しゅうたんきごう、英: Terminal symbol）と非終端記号（ひしゅうたんきごう、英: Nonterminal symbol）は、句構造規則の生成規則中にあらわれる記号類の分類である。規則群のうちの、どれかの規則の左辺にあらわれている記号、すなわち、他の記号列と置換できるものとして定義されている記号が非終端記号で、ある種の変数名のようなものとも言える。それに対し、右辺の記号列中のみにあらわれる、いわゆる「アルファベット」の1文字から成る記号が終端記号である。実用上は（プログラミング言語などでは）終端記号は文字そのものではなく、英語などにおける「単語」に相当する「トークン」と呼ばれるもの（「字句」の記事、および字句解析#トークンなどを参照）であることも多い。
終端記号[編集]
終端記号は、生成規則の右辺のみに現れ、左辺には現れない。よって、生成規則によってそれ以上は変換されない（これが“終端”と呼ばれる理由である）。
非終端記号[編集]
非終端記号とは、置換されうる記号のことであり、構文変数 と呼ばれることもある。
終端記号は、正式な文法の生成物の出力に現れる可能性がある記号であり、文法の規則を使用して変更することはできません。シンボルのソース文字列にルールを再帰的に適用すると、通常、最終的な出力文字列は終端シンボルのみで構成されます。 2 つのルールによって定義された文法を考えてみましょう。この文法では、記号 Б は終端記号であり、Ψ は非終端記号と開始記号の両方です。文字列を作成するための生成ルールは次のとおりです。 記号 Ψ は БΨ である可能性があります 記号 Ψ は Б になる場合があります。ここで、Б は終端記号です。他のものに変更するというルールがないからです。一方、Ψ は非終端です。これは、Ψ を変更できるルールが 2 つあるためです。特定の文法によって定義または生成される形式言語は、その文法によって生成され、終端記号のみで構成される文字列のセットです。図 1 は、この文法で生成できる文字列を示しています。
非終端記号は、置換可能な記号です。単に構文変数と呼ばれることもあります。正式な文法には開始記号が含まれます。開始記号は、言語内のすべての文字列が生成ルールの連続適用によって導出される非終端記号のセットの指定されたメンバーです。実際、文法によって定義される言語は、そのようにして導出できる終端文字列のセットにすぎません。 文脈自由文法は、各生成規則の左側が 1 つの非終端記号のみで構成される文法です。この制限は自明ではありません。すべての言語が文脈自由文法で生成できるわけではありません。これを可能にする言語はコンテキストフリー言語と呼ばれます。 これらは、非決定性プッシュダウン オートマトンによって認識できる言語にすぎません。コンテキストフリー言語は、ほとんどのプログラミング言語構文の理論的基盤です。
※コメント投稿者のブログIDはブログ作成者のみに通知されます