プログラミング言語論第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 0 式数字 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記法で簡潔に記述できる。ただ、プログラミング言語の構文を文脈自由文法のみで完全に規定するのは困難。 • 名前の定義と参照の関係の整合性 • データ型の整合性は文脈自由文法では記述できないか、あるいは、記述すると非常に複雑になる。 --- コンパイラでは、構文解析フェーズとは別のフェーズにおいて、これらの整合性の検査（意味解析（静的意味の解析））を行う。先週までの内容の復習、補足構文の定義通常、構文の定義は、字句の定義（正規表現で定義）と構文の定義（文脈自由文法（のサブクラス）で定義）に分ける。コンパイラにおける構文解析も、これに対応して、字句解析と構文解析に分ける。分けない場合文法定義における終端記号はアルファベット分ける場合文法定義における終端記号は字句