プログラム言語の記述

1. 構文記述法
   • BNF(Backus Naur Form)
     バッカス・ナウアー記法 (ALGOL60)
   • CFG(Context-free grammar)
     文脈自由文法 (Noam Chomsky, 1956)

   • 正規表現 (regular expression)
     名標 identifier 定数語 constant の表現
   • 素語 lexical unit 基要語 keyword (鍵語)
2. 文脈自由文法 CFG

   CFG 実際のプログラム言語では Context-free では ないが、文法規定の中核として重要。

   慣用的な数式の構成がCFGに適合する。

   構文単位の構成の際に内部構造が外部構造と無関係。

   CFG についての処理系による認識など理論・技法が得られている。

   CFGとは、次の４つ組

   G = < V, Σ, P, S >

   である。ここで
   1. V はGの語彙(vocabulary)と呼ぶ有限集合。
      その要素はGの記号(symbol)。
   2. Σ はV の部分集合で、G の文字集(alphabet)。

      Σの要素

      G の文字 終端記号(terminal symbol)

      V - Σの要素

      構文単位(syntactic unit) 構文変数(syntactic variable) 非終端記号(nonterminal symbol)という。

   3. P はG の生成規則集(set of poduction rules)
      Gの構文単位A に V 上の記号列α を 対応させる順序対 <A,α>を

      A → α

      の形に書いたもの。
   4. S は構文単位の一つで、G の開始記号(start symbol)

   連接

   αβ は α と β の連接

   導出

   σ ⇒ σ′ A の出現に着目し、 αで置き換える操作

   生成

   σ₀ = S からの導出で得られるものの全体 L(G)

   文法G で生成された言語

   例 2進数字`0'と`1'を並べた2進数で、3の倍数になるものを生成するCFG

   Σ = {0,1};

   V_N = V - Σ

   = {M, M₀, M₁, M₂ };

   P = {M → 0,

   M → M₀, M₁ → 1,

   M₀ → M₁1, M₀ → M₀0,

   M₁ → M₀1, M₁ → M₂0,

   M₂ → M₁0, M₂ → M₂1 };

   S = M

3. BNF
   1. 非終端記号は < > で囲んで表す。
   2. 終端記号はプログラムに使われる文字を書く。
   3. 生成規則は `::=' を使って書く。同じ左辺の構文単位に生成規則が ２つ以上ある場合は `|' (たてぼう) で区切って並べる。
   3の倍数である2進数を生成する BNF

   <3の倍数> ::= 0 | <正の3の倍数>

   <正の3の倍数> ::= <正の3の倍数>0 |

   <3の倍数たす1>1

   <3の倍数たす1> ::= <正の3の倍数>1|

   <3の倍数たす2>0

   <3の倍数たす2> ::= <3の倍数たす1>0 |

   <3の倍数たす2>1

4. 構文図 構文を流れ図風に描いたもの。

   例：3の倍数である2進数の構文図
   

実際の構文記述の例：

• メールなどのメッセージヘッダRFC822
• インターネットドメインネームRFC1035(Page 7)

---

シラバスへ戻る