プログラミング言語論 第10回（演習） 情報工学科　木村昌臣 　 篠埜　功

[参考] Chomskyの言語階層 Noam Chomskｙの言語階層について Type 0 Type 1 Type 2 Type 3 (１年後期 形式言語とオートマトン)

先週の補足: 文法とは 文法とは、 (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) によって生成される言語。

Type 3 右線形文法 (Right-linear grammar) すべての生成規則が X  xY または X  x の形をしている。ただし、 X, Y  N x  T * Type3は正規表現と同等。

Type 2 文脈自由文法 (Context free grammar) すべての生成規則が X   の形をしている。ただし、 X  N   (T  N)* Type 2はBNF記法と同等

Type 1 文脈依存文法 (Context sensitive grammar) すべての生成規則が X     の形をしている。ただし、 X  N ,   (T  N)*   (T  N)+

Type 0 制限なし 生成規則は    の形であれば何でもよい。 ,  は、 ,   ( T  N )*

先週の補足: BNF記法 Backus Normal Form (Backus Naur Form) 文脈自由文法を簡潔に表現する記法 左辺が同じ非終端記号の規則を、縦棒 | を使って、まとめて表す。 （例） 文脈自由文法 G = (T, N, S, P) N = { S } T = { ( , ) } P = { S  ( ), S  (S), S  SS } は、BNF記法では、 <paren> ::= ( ) | (<paren>) | <paren> <paren> と表せる。

先週の復習: 拡張BNF記法 * + （） { } [ ] などを使えるようにしたのが拡張BNF記法。

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

第２問 aが偶数個(０個は除く)並んだ文字列をBNF記法、拡張BNF記法で定義せよ。 aa, aaaa, aaaaaa, aaaaaaaa, aaaaaaaaaa, ……

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

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

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

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

構文図式 文脈自由文法の構文規則を表す際に用いられる（graphicalな）言語 = <数字> ::= ’0’ | ’1’ <式> ::= <数字> （’and’ | ’or’） <数字> ’=’ <数字> 数字 1 式 数字 and 数字 = 数字 or

第７問 次の構成図が与えられたとき，この構成図で表現できる文字列として正しいものを①～⑤から全て選べ．ただし，英字は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 数字 英字 英字

先週までの内容の復習、補足 デジタルコンピュータ --- 機械語で書かれたプログラムを実行する機械。 デジタルコンピュータ --- 機械語で書かれたプログラムを実行する機械。 コンピュータによる問題解決は、必要な情報をビット列で表現（コード化）し、それを機械語プログラムで処理することにより行われる。 大規模なプログラムでも原理的には機械語プログラムを書けるが、事実上不可能。

先週までの内容の復習、補足 プログラミング言語が持つべき性質 高水準の記述能力 プログラムの論理構造を簡潔に記述 厳密な意味の定義 その言語で記述可能なすべてのプログラムの意味（動作）を完全に規定 効率的実装 その言語で記述可能なすべてのプログラムを、効率のよい機械語に変換

先週までの内容の復習、補足 プログラミング言語の定義 構文の定義 Chomskyの文法の理論を基礎とする 曖昧さを許さない 文法構造がコンピュータで解析可能 意味の定義 その言語で記述可能なすべてのプログラムの意味（動作）を完全に規定 表示的意味論（denotational semantics） 公理的意味論（axiomatic semantics） 操作的意味論（operational semantics）

先週までの内容の復習、補足 構文の定義 文脈自由文法（の部分クラス）で定義。BNF記法で簡潔に記述できる。 ただ、プログラミング言語の構文を文脈自由文法のみで完全に規定するのは困難。 名前の定義と参照の関係の整合性 データ型の整合性 は文脈自由文法では記述できないか、あるいは、記述すると非常に複雑になる。 --- コンパイラでは、構文解析フェーズとは別のフェーズにおいて、これらの整合性の検査（意味解析（静的意味の解析））を行う。

先週までの内容の復習、補足 構文の定義 通常、構文の定義は、字句の定義（正規表現で定義）と構文の定義（文脈自由文法（のサブクラス）で定義）に分ける。コンパイラにおける構文解析も、これに対応して、字句解析と構文解析に分ける。 分けない場合 文法定義における終端記号はアルファベット 分ける場合 文法定義における終端記号は字句