プログラミング言語論 第３回 BNF 記法について（演習付き） 篠埜 功

構文の記述 プログラミング言語の構文はどのように定式化できるか？ 例１ : for ループの中に for ループが書ける。 for (i=0; i<= 10; i++) { for (j=0; j<=20; j++) { … 例 2: 算術式の中で、 (…) の中で、 (…) を書ける。 1 + (2 * (3+ 4) ) プログラミング言語の特徴 : 入れ子構造 (nesting) このような構造は、文脈自由文法で表す。 （正規表現では表すことができない。） 文脈自由文法を表記するためのメタ言語である BNF 記 法を紹介する。

BNF 記法 Backus Normal Form (Backus Naur Form) 集合を定義する際の記述法（言語）。集 合を帰納的に定義する。（帰納的定義 inductive definition ）（再帰的定義 recursive definition ともいう） 規則を「非終端記号（ non-terminal symbol ）」と「終端記号（ terminal symbol ）」で表す。 文脈自由文法（ context free grammar ）の構 文規則を記述する際に用いられる。 – 構文規則＝文を構成するための規則

非終端記号と終端記号 非終端記号（ non-terminal symbol ） – 非終端記号または終端記号からなる列に展開 される。 <> で囲む。 終端記号（ terminal symbol ） – 文字列、数値、 = など それ以上他の要素の組 み合わせで置き換えることができないもの – ’ ’ 等で囲んで表すこともある。

BNF 記法による規則の書き方（ BNF 記法の定義） ::= ::= ’>’ | ’<’ （ BNF 記法の例および意味） can beor が一つの規則であり、それを並べて書く。 非終端記号 （１つ）のあとに ::= を書き、その後に非終端 記号または終端記号からなる列を縦棒 | で区切って並べた もの（縦棒はなくてもよいし、２つ以上あってもよい）

BNF 記法の意味 非終端記号は集合に対応 – 非終端記号は、それに対応する集合の任意の要素を 表していると見てもよい。 – この見方では、複数回表れる同じ名前の非終端記号 は一般に別の要素を表す。 同じ名前の終端記号は同じものを表す ::= ::= ’>’ | ’<’ は、式の集合に対応する。 （式の集合中の任意の要素を表すと見てもよい）

BNF 記法の意味 複数の選択候補がある場合は「｜」を使って表 現 再帰的定義 recursive definition （帰納的定義 inductive definition ） ::= ’>’ | ’<’ ::= | 「文章は文あるいは、文と文章が並んだものある」 「不等号記号は ’>’ または ’<’ である」 can beor

構文木 ::= ::= ‘0’ | ‘1’ ::= ‘and’ | ‘or’ ::= ‘=’ <式><式> ‘1’ ‘or’ ‘0’ ‘1’ ‘=’ 終端記号 非終端記号 （例） 1or0=1 の構文木

拡張 BNF 記法（ extended BNF ） (1) BNF 記法を読みやすいように拡張 – 次の式は「文章は一つ以上の文で構成され る」ということを再帰的に表現 – これをもっと簡潔に書きたい ::= | ::= + + は１つ以上の繰り返しを表す

拡張 BNF 記法 (2) A | B は、 A または B 。 {A} は、 A の 0 回以上の繰り返しを表す。 – （例） {ab} は、 ε, ab, abab, ababab, abababab, … を表す。 （ A ）は、 A をひとまとめにする。 – （例） （ a|b ） c は、 ac または bc を表す。 [A] は、 A または空を表す。 （例） [a] は、 ε または a を 表す。 (A) + は、 A の１回以上の繰り返しを表す。 (A) * は、 A の 0 回以上の繰り返しを表す。（ {A} と同 じ） – （例） a + は、 a, aa, aaa, aaaa, …. を表す。 aa * と同じ。

【参考】 Chomsky の言語階層 Noam Chomsky の言語階層 Type 0 制限なし Type 1 文脈依存文法 (context sensitive grammar) Type 2 文脈自由文法 (context free grammar) Type 3 正規文法 (regular grammar) ( １年後期 形式言語とオートマトン )

第1問第1問 ビット列を BNF 記法を利用して定義せよ. また拡張 BNF 記法で書くとどうなるか. – 以下の非終端記号を利用せよ ビット列用の非終端記号 --- ＜ビット列＞ ビット用の非終端記号 --- ＜ビット＞ （ビット列の例） など。

第２問 a が偶数個 ( ０個は除く ) 並んだ文字列を BNF 記法、拡張 BNF 記法で定義せよ。 （例） aa や aaaaaaaa など。

第３問 自然数リストは、 ( ) であるか、ある いは自然数リストと自然数を ( 自然数. 自然数リスト ) のようにしてペアにした ものであるとする。これを BNF 記法で表 せ。ただし自然数は で既に定義さ れているものとする。 （例） (2. (30. (5. ( ) ) ) ) など。

第４問 対応のとれた括弧からなる文字列を BNF 記法で定義せよ。 （例） () や ()(()) など。

第５問 対応のとれた括弧で、３段階以上のネ ストは許さないような文字列を BNF 記法 で記述せよ。 (), (()), ()(), ()(()), …… ()((())) など、ネストが３段階以上のもの は除く。

第６問 問５の文字列は正規表現で記述できる か。

構文図式 （ syntax graph あるいは syntax diagram ） （さきほどの例） ::= ’0’ | ’1’ ::= （ ’and’ | ’or’ ） ’=’ 数字 1 0 式 and or 数字 = 文脈自由文法の構文規則を表す際に用いられ る graphical な言語

構文図式 終端記号 x x 非終端記号 A 繰り返し {α} α の図式

構文図式 並び α 1 α 2 … α n α 1 の図式 α 2 の図式 … α n の図式 選択 α 1 | α 2 | … | α n α 2 の図式 α 1 の図式 α n の図式 …

第７問 次の構成図が与えられたとき，この構成図で表現で きる文字列として正しいものを ① ～ ⑤ から全て選べ． ただし，英字は a, b, ・・・， z, A, B, ・・・， Z のい ずれか，数字は 0 ， 1 ，・・・， 9 のいずれかである とする． 英字 数字 ‘#’ ① A3 ② BB ③ A# ④ #9 ⑤ 99

第８問 あるプログラミング言語で使える変数名は，次の構 文図で規定されているものとする。このとき，変数 名として使えないものを選べ。ただし，英字は a, b, ･･･, z ， A, B, ･･･, Z のどれか，数字は 0, 1, ･･･, 9 のどれかである。 ① A ② name ③ B740 ④ C6H6 ⑤ 11PM 英字 数字 英字

補足 : 文法とは（１） 文法とは、 (N, T, P, S) N は記号の有限集合。非終端記号 (nonterminal symbol) と呼ぶ。 T は N とは重なりのない記号の有限集合。終端記 号 (terminal symbol) と呼ぶ。 P は、 (N  T)* N (N  T)*  (N  T)* の有限部分集 合。 P の要素を生成規則 (production) あるいは書 き換え規則 (rewriting rule) と呼ぶ。 (u,v)  P は文 字列 u を文字列 v に書き換えてもよいことを表す ルールであり、通常 u  v と書く。 S は N の要素で、開始記号 (start symbol) と呼ぶ。

補足 : 文法とは（２） u  v が生成規則で、 u が文字列  の部分文字列で あるとき（  =  u  となる ,   (N  T)* が存 在）、 文字列  の中の u を v に書き換えてよい （  ’ =  v  が得られる）。 これを    ’ と書く。 { x  T* | S  * x } が、 (N, T, P, S) によって生成され る言語。