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

構文の記述 プログラミング言語の構文はどのように定式化できるか？ このような構造は、文脈自由文法で表す。 プログラミング言語の特徴: 入れ子構造(nesting) 例１: forループの中にforループが書ける。 for (i=0; i<= 10; i++) { for (j=0; j<=20; j++) { … 例2: 算術式の中で、(…) の中で、(…)を書ける。 1 + (2 * (3+ 4) ) このような構造は、文脈自由文法で表す。 （正規表現では表すことができない。） 文脈自由文法を表記するためのメタ言語である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） 非終端記号または終端記号からなる列に展開される。<>で囲む。 終端記号（terminal symbol） 文字列、数値、= など それ以上他の要素の組み合わせで置き換えることができないもの ’ ’等で囲んで表すこともある。

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

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

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

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

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

拡張BNF記法(2) A | B は、AまたはB。 {A}は、Aの0回以上の繰り返しを表す。 （A）は、Aをひとまとめにする。 （例） {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問 ビット列をBNF記法を利用して定義せよ. また拡張BNF記法で書くとどうなるか. 以下の非終端記号を利用せよ ビット列用の非終端記号 --- ＜ビット列＞ ビット用の非終端記号 --- ＜ビット＞ （ビット列の例） 10010111001011100010100 など。

解答1 ちなみに、空文字列（ε）を含む場合は、 BNF記法 <ビット列> ::= <ビット> | <ビット><ビット列> <ビット> ::= 0 | 1 拡張BNF記法 (例) <ビット列> ::= (0 | 1)+ ちなみに、空文字列（ε）を含む場合は、 <ビット列> ::= ε | <ビット><ビット列> <ビット列> ::= (0 | 1)*

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

解答2 BNF記法 <evena> ::= aa | <evena> aa 拡張BNF記法 ちなみに、空文字列を含む場合は、 <evena> ::= ε | <evena> aa <evena> ::= (aa)*

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

解答3 BNF記法 <natList> ::= ( ) | ( <nat> . <natList> )

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

解答４ BNF記法 <paren> ::= ( ) | ( <paren> ) 空文字列εを含む場合は、 <paren> ::= ε | ( <paren> ) | <paren><paren>

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

解答５ BNF記法 <paren> ::= <paren1> | ( <paren1> ) 空文字列εを許す場合は、 <paren> ::= ε | <paren1> | ( <paren1> ) | <paren> <paren>

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

解答６ できる。 { ( {( )}* ) } + 空文字列を含む場合 { ( {( )}* ) } * （注） ここでは、{ }を、正規表現における括弧として 用いた。

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

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

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

第７問 次の構成図が与えられたとき，この構成図で表現できる文字列として正しいものを①～⑤から全て選べ．ただし，英字は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)*の有限部分集合。生成規則(production)あるいは書き換え規則(rewriting rule)と呼ぶ。 SはNの要素で、開始記号(start symbol)と呼ぶ。

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