プログラミング言語論1

プログラミング言語論
第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……
解答1
• BNF記法
<ビット列> ::= <ビット> | <ビット><ビット列>
<ビット> ::= 0 | 1
• 拡張BNF記法 (例)
<ビット列> ::= (0 | 1)+
ちなみに、空文字列（ε）を含む場合は、
• BNF記法
<ビット列> ::= ε | <ビット><ビット列>
<ビット> ::= 0 | 1
• 拡張BNF記法 (例)
<ビット列> ::= (0 | 1)*
第２問
• aが偶数個(０個は除く)並んだ文字列を
BNF記法、拡張BNF記法で定義せよ。
aa, aaaa, aaaaaa, aaaaaaaa, aaaaaaaaaa, ……
解答2
• BNF記法
<evena> ::= aa | <evena> aa
• 拡張BNF記法
<evena> ::= (aa)+
ちなみに、空文字列を含む場合は、
• BNF記法
<evena> ::= ε | <evena> aa
• 拡張BNF記法
<evena> ::= (aa)*
第３問
• リストは、( )であるか、あるいはリストと自
然数を(自然数 . リスト) のようにしてペア
にしたものであるとする。これをBNF記法
で表せ。ただし自然数は<nat>で既に定義
されているものとする。
解答3
• BNF記法
<list> ::= ( )
| ( <nat> . <list> )
第４問
• 対応のとれた括弧からなる文字列をBNF
記法で定義せよ。
(), (()), ()(), ()(()), ()((())) ……
解答４
• BNF記法
<paren> ::= ( )
| ( <paren> )
| <paren><paren>
空文字列εを含む場合は、
<paren> ::= ε
| ( <paren> )
| <paren><paren>
第５問
• 対応のとれた括弧で、３段階以上のネスト
は許さないような文字列をBNF記法で記
述せよ。
(), (()), ()(), ()(()), ……
()((())) など、ネストが３段階以上のものは
除く。
解答５
• BNF記法
<paren> ::= <paren1>
| ( <paren1> )
| <paren> <paren>
<paren1> ::= ( ) | <paren1> <paren1>
空文字列εを許す場合は、
<paren> ::= ε | <paren1>
| ( <paren1> ) | <paren> <paren>
第６問
• 問５の文字列は正規表現で記述できるか。
解答６
できる。
{ ( {( )}* ) } +
空文字列を含む場合
{ ( {( )}* ) } *
（注）ここでは、{ }を、正規表現における括弧として
用いた。
構文図式
文脈自由文法の構文規則を表す際に用いられる
（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記法で簡
潔に記述できる。
ただ、プログラミング言語の構文を文脈自由文法のみ
で完全に規定するのは困難。
• 名前の定義と参照の関係の整合性
• データ型の整合性
は文脈自由文法では記述できないか、あるいは、記述
すると非常に複雑になる。
--- コンパイラでは、構文解析フェーズとは別のフェー
ズにおいて、これらの整合性の検査（意味解析（静的
意味の解析））を行う。
先週までの内容の復習、補足
構文の定義
通常、構文の定義は、字句の定義（正規表現で定義）
と構文の定義（文脈自由文法（のサブクラス）で定義）
に分ける。コンパイラにおける構文解析も、これに対応
して、字句解析と構文解析に分ける。
分けない場合
文法定義における終端記号はアルファベット
分ける場合
文法定義における終端記号は字句

Download Report