終端記号と非終端記号のソースを表示

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

== 終端記号 ==
終端記号は、生成規則の右辺のみに現れ、左辺には現れない。よって、生成規則によってそれ以上は変換されない（これが“終端”と呼ばれる理由である）。
<!--
例として、次の2つの規則で定義される文法を考えよう：
#''x'' can become ''xa'' 
#''x'' can become ''ax''
ここで ''a'' に対する変換規則はないので、これは終端記号である。（一方、''x'' に対する変換規則は2つあるので、これは非終端記号である。）ある文法によって定義（あるいは生成）される[[形式言語]]とは、その文法によって生成される文字列の集合であり、''終端記号のみからなる''。
--><!--蛇足、ないし説明として足りていない。-->

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

[[文脈自由文法]]とは、すべての生成規則において左側がただ1つの非終端記号からなるような文法のことである。この制限は非自明であり、すべての言語が文脈自由文法によって生成できるわけではない。文脈自由文法によって生成される言語を文脈自由言語と呼ぶ。
文脈自由言語は、非決定的[[プッシュダウン・オートマトン]]によって認識される言語であり、多くの[[プログラミング言語]]の構文の理論的基礎になっている。
--><!--蛇足、ないし句構造文法の記事などここじゃない場所に書くべき内容-->
==句構造文法==
{{main|句構造文法}}
以下、単に「集合」とあるものは全て有限集合である。この理論では文法は一般に、記号列を別の記号列に置換できるものとして定義する生成規則の集合によって定義される。これらの生成規則は、文字列の生成やパースに使われる。それぞれの生成規則は、置換される記号列からなる ''ヘッド'' （左辺）と、置換する記号列からなる ''ボディ'' （右辺）を持つ。規則は、''ヘッド'' → ''ボディ'' のような形に書く。例えば、規則 z0 → z1 は、z0 を z1 で置き換えることを表す。

1950年代に [[ノーム・チョムスキー]] <ref name="Chomsky1956">{{Cite journal
 | author = Chomsky, Noam
 | title = Three Models for the Description of Language
 | journal = [[IRE Transactions on Information Theory]]
 | volume = 2 
 | issue = 2
 | pages = 113&ndash;123
 | year = 1956
 | doi = 10.1109/TIT.1956.1056813
}}</ref><ref name="Chomsky1957">{{Cite book
 | author = Chomsky, Noam
 | title = Syntactic Structures
 | publisher = [[Mouton]]
 | location = The Hague
 | year = 1957
}}</ref> によって提案された生成文法の古典的な形式では、文法 ''G'' は次のように構成される：
* ''非終端記号'' の集合 <math>N</math>
* ''終端記号''([[アルファベット (計算機科学)|アルファベット]]) の集合 <math>\Sigma</math>
* ''生成規則'' の集合 <math>P</math>。<math>P</math> の要素であるそれぞれの規則は次のような形をしている：
:: <math>(\Sigma \cup N)^{*} n (\Sigma \cup N)^{*} \rightarrow (\Sigma \cup N)^{*} </math> ここで <math>n \in N</math>
:ここで <math>{}^{*}</math> は [[クリーネ閉包|クリーネのスター]]（つまり、0個以上の並びを意味する）、<math>\cup</math> は和集合を表し、よって <math>(\Sigma \cup N)^{*}</math> は0個以上の記号の並びを表す。つまり、左辺は少なくとも1つの非終端記号を含む。右辺が空列の場合は、誤解を避けるために <math>\Lambda</math>, <math>e</math>, <math>\epsilon</math> のような記号を使うことがある。
* ''開始記号'' <math>s \in N</math>

以上からなる4つ組 <math><N, \Sigma, P, s></math> として、言語が形式的に定義される。<ref>{{cite book|first=Seymour|last=Ginsburg|authorlink=Seymour Ginsburg|title=Algebraic and automata theoretic properties of formal languages|publisher=North-Holland|pages=8–9|year=1975|isbn=0-7204-2506-9}}</ref><ref>{{cite book|last=Harrison|first=Michael A.|authorlink=Michael A. Harrison|title=Introduction to Formal Language Theory|year=1978|pages=13|isbn=0-201-02955-3|location=Reading, Mass.|publisher=Addison-Wesley Publishing Company}}</ref>
<!--
==例==
例えば、符号付きの整数を表現する場合、[[バッカス・ナウア記法]]的に表すと以下のようになる。

 <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.
{{reflist}}

{{Computer-stub}}

{{DEFAULTSORT:しゆうたんきこうとひしゆうたんきこう}}
[[Category:形式言語]]
[[Category:数学に関する記事]]