Presentation is loading. Please wait.

Presentation is loading. Please wait.

プログラミング言語論 第3回 BNF記法について(演習付き)

Similar presentations


Presentation on theme: "プログラミング言語論 第3回 BNF記法について(演習付き)"— Presentation transcript:

1 プログラミング言語論 第3回 BNF記法について(演習付き)
篠埜 功

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

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

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

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

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

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

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

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

10 拡張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の1回以上の繰り返しを表す。 (A)* は、Aの0回以上の繰り返しを表す。({A}と同じ) (例) a+ は、a, aa, aaa, aaaa, ….を表す。 aa*と同じ。

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

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

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

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

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

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

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

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

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

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

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

22 第6問 問5の文字列は正規表現で記述できるか。

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

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

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

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

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

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

29 補足: 文法とは(1) 文法とは、 (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)と呼ぶ。

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


Download ppt "プログラミング言語論 第3回 BNF記法について(演習付き)"

Similar presentations


Ads by Google