終端記号と非終端記号

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

終端記号[編集]

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

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

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

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

非終端記号[編集]

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

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

生成規則[編集]

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

1950年代に ノーム・チョムスキー [1][2] によって提案された生成文法の古典的な形式では、文法 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> として形式的に定義される。 このような形式的な文法は 項書き換え系 あるいは 句構造文法 と呼ばれることもある [3][4]

[編集]

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

<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.
  1. ^ Chomsky, Noam (1956). “Three Models for the Description of Language”. IRE Transactions on Information Theory 2 (2): 113–123. doi:10.1109/TIT.1956.1056813. 
  2. ^ Chomsky, Noam (1957). Syntactic Structures. The Hague: Mouton. 
  3. ^ Ginsburg, Seymour (1975). Algebraic and automata theoretic properties of formal languages. North-Holland. pp. 8–9. ISBN 0-7204-2506-9. 
  4. ^ Harrison, Michael A. (1978). Introduction to Formal Language Theory. Reading, Mass.: Addison-Wesley Publishing Company. pp. 13. ISBN 0-201-02955-3.