終端記号と非終端記号

形式言語では、終端記号と非終端記号は、形式文法を構成する生成規則を指定する際に使用される語彙要素です。 終端記号は、形式文法の一部として定義された言語の基本記号です。非終端記号(または構文変数) は、生成規則に従って終端記号のグループに置き換えられます。

特定の文法の終端記号と非終端記号は、完全に別の 2 つのセットに存在します。

終端記号

終端記号は、形式文法の生成規則の出力に現れる可能性があり、文法の規則を使用して変更できない記号です。記号のソース文字列に規則を再帰的に適用すると、通常、終端記号のみで構成される最終出力文字列で終了します。

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

シンボルΨはБΨ
シンボルΨはБ

ここではБ、を他の何かに変更する規則が存在しないため、は終端記号です。一方、にはΨ変更できる規則が 2 つあるため、非終端記号です。特定の文法によって定義または生成される形式言語は、その文法によって生成でき、終端記号のみで構成される文字列の集合です。図 1 は、この文法で生成できる文字列を示しています。

非終端記号

非終端記号は、置き換え可能な記号です。単に構文変数と呼ばれることもあります。形式文法には、開始記号が含まれます。これは、生成規則を連続的に適用することで言語内のすべての文字列を導出できる非終端記号の集合の指定されたメンバーです。実際、文法で定義される言語は、まさにそのように導出できる 終端文字列の集合です。

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

制作ルール

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

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

非終端記号の有限集合 $N$ 。
$N$ と交わらない終端記号の有限集合 $Σ$ 。
生成規則の有限集合 $P$ 、各規則は次の形式をとる

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

ここで、はクリーネのスター演算子であり、

\cup は

集合の和集合を表すので、は0 個以上の記号を表し、

N は1 つの

非終端記号を意味します。つまり、各生成規則は、最初の文字列に少なくとも 1 つの非終端記号が含まれる、1 つの記号文字列を別の文字列にマッピングします。本体が空の文字列のみで構成される場合^{[注 1]} 、混乱を避けるために、特別な表記法 (多くの場合、

Λ

、

e

、または

ε

)で表されます。

{}^{*}

(\Sigma \cup N)^{*}

開始記号である識別記号。 $S\in N$

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

例

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

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

この例では、記号（-,0,1,2,3,4,5,6,7,8,9）は終端記号であり、<digit>およびは<integer>非終端記号です。 ^{[注 2]}

別の例は次のとおりです。

{\ce {S -> cAd}}

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

この例では、記号 $a、b、c、d$ は終端記号であり、 $S、A$ は非終端記号です。

参照

注記

^ 記号は一切含まれていません。
^ この例では、「0056」や「0000」のような先頭にゼロが付いた文字列と、「-0」や「-00000」のような負のゼロが付いた文字列がサポートされています。

参考文献

^ Rosen, KH (2012). 離散数学とその応用. McGraw-Hill. 847-851ページ
^ チョムスキー、ノーム (1956)。「言語記述のための3つのモデル」。IRE Transactions on Information Theory。2 ( 3): 113–123。doi : 10.1109 /TIT.1956.1056813。S2CID 19519474 。
^ チョムスキー、ノーム（1957）。統語構造。ハーグ：ムートン。
^ ギンズバーグ、シーモア(1975)。形式言語の代数的およびオートマトン理論的性質。ノースホランド。pp. 8–9。ISBN 0-7204-2506-9。
^ ハリソン、マイケル A. (1978)。形式言語理論入門。マサチューセッツ州レディング：アディソン・ウェズリー出版社。pp. 13。ISBN 0-201-02955-3。

[4] 記号は一切含まれていません。

[7] この例では、「0056」や「0000」のような先頭にゼロが付いた文字列と、「-0」や「-00000」のような負のゼロが付いた文字列がサポートされています。

[1] Rosen, KH (2012). 離散数学とその応用. McGraw-Hill. 847-851ページ

[Chomsky1956-2] チョムスキー、ノーム (1956)。「言語記述のための3つのモデル」。IRE Transactions on Information Theory。2 ( 3): 113–123。doi : 10.1109 /TIT.1956.1056813。S2CID 19519474 。

[Chomsky1957-3] チョムスキー、ノーム（1957）。統語構造。ハーグ：ムートン。

[5] ギンズバーグ、シーモア(1975)。形式言語の代数的およびオートマトン理論的性質。ノースホランド。pp. 8–9。ISBN 0-7204-2506-9。

[6] ハリソン、マイケル A. (1978)。形式言語理論入門。マサチューセッツ州レディング：アディソン・ウェズリー出版社。pp. 13。ISBN 0-201-02955-3。

終端記号

非終端記号

制作ルール

例

参照

注記

参考文献

関連するトピック

形式言語

形式文法

生成規則

語彙要素