Q q システムソフトウェア 第２回：２００７年１０月１０日（水） q q.

Presentation on theme: "Q q システムソフトウェア 第２回：２００７年１０月１０日（水） q q."— Presentation transcript:

1 q q システムソフトウェア 第２回：２００７年１０月１０日（水） q q

2 本日学ぶこと 計算機のための言語 プログラミング言語，自然言語，形式言語 正規表現，パターンマッチ，Emacsなどでの利用 BNF記法

3 ことば（言語）の分類 人同士でコミュニケーションをとるのは，日本語，英語，フランス語，ドイツ語，エスペラント語…自然言語
人から計算機にまとまった指示を出すのは，C，FORTLAN，COBOL，Java…プログラミング言語（計算機言語） 「計算とは？」を理論的・フォーマルに記述するのは，数式，集合，関係，論理，…形式言語

4 自然言語とは 人間が日常的に使っている言語のこと． 計算機言語や形式言語よりも，多様性に富んでいる．
誤用であっても，聞き手（読み手）が正しく解釈する． 新語が社会で使われていき，いくつかは辞書に載る． 自然言語: 日本語の誤用:

5 プログラミング言語とは ソフトウェアの設計図に当たるソースコードを記述するための人工言語．「計算機言語」ともいう．
インタプリタ型を除き，計算機はソースコードを直接実行できないので，コンパイラやアセンブラによって実行ファイルを生成し，そのファイルで実行する． 人間が計算機に命令を指示するという目的がある． 自然言語に比べて，曖昧さが非常に少ない． 言語仕様は，言語設計者が決める． 関連語 アルゴリズムは，計算機が処理する手順を定めたもので，通常，自然言語または擬似言語で書かれる． プログラミング言語:

6 形式言語とは 数学的かつ厳密に議論するために使用される人工言語． 次のような問題に対して，理論的な観点で検討できる．
「形式」は，「形だけの」ではなく「フォーマルな」の意味． 有限個の情報をもとに，規則を有限回適用して得られる情報は何か（一般に無限集合）を考える． 次のような問題に対して，理論的な観点で検討できる． sinθ+cosθ=2のとき，sinθcosθの値は？ 人間同士でうまくコミュニケーションが取れるのはなぜか？ プログラムが停止する（無限ループに陥らない）ことを事前に知るようなプログラムは作れる？ 形式言語:

7 正規表現：はじめに ニーズ 正規表現を学び，活用することで
レポートに書いている文書で「和大」をすべて「和歌山大学」に変更しないといけない．見落とさずに，すべて書き換えられるかな？ 2006年1月だったか2007年1月だったか，作ったファイル，どこだ…． 正規表現を学び，活用することで 膨大な文書からでも，関心のある箇所を見つけることができる． 日本語で表すと煩雑になる「条件」を，「パターン」で簡潔に記述できる．

8 パターンマッチとは パターン "やまだ" は パターン "和.*大" は 「"や" "ま" "だ" が連続して並ぶ」を意味する．
"わかやまだいがく" にマッチする． "やまだたろう" にマッチする． "むらかわたけひこ" にはマッチしない． パターン "和.*大" は 「"和"のあと0個以上の文字を挟んで"大"がある」を意味する． "和歌山大学" にマッチする． "和大" にマッチする． "和歌山県にある和歌山大学" にマッチする． "大和" にはマッチしない． マッチするしないだけでなく，パターンが，文字列のどこにマッチするかという観点で考えると， パターン "和.*大" と文字列 "和歌山県にある和歌山大学" に関しては，多くのソフトウェアで， 「和歌山県にある和歌山大」にマッチし，「和歌山大」ではない． このようなパターンマッチのしかたを，最左最長マッチという．

9 正規表現のメタ文字 メタ文字は，特別な意味を持つ文字のこと メタ文字の例
a など，特別な意味を持たず，文字がそのままの意味になるものを「リテラル」という． メタ文字の例 . …任意の１文字 + …１回以上の繰り返し * …0回以上の繰り返し ? …1回または0回（あってもなくてもよい） [ ] …中の一つ ^ …先頭 $ …末尾 「\メタ文字」で，メタ文字自身を表す． 「\」もメタ文字である．しばしば，エスケープ文字と呼ばれる．

10 メタ文字を利用した正規表現の例 "200[67]-01" は，"2006-01" または "2007-01" を含む文字列にマッチする．
"200[5-7]-01" は，" "，" " または " " を含む文字列にマッチする． "^Hello" も "World$" も，"Hello World" にマッチする． "Wi*" は，"W"，"Wii"，"Wiiiiiiiiiiiiiiiiiiii" など（を含む文字列）にマッチする． "Wii+" は，"W" と "Wi" にはマッチしないが， "Wii"，"Wiiiiiiiiiiiiiiiiiiii" など（を含む文字列）にマッチする． "(Wi)+" は，"Wi"，"WiWi"，"WiWiWi"，…など（を含む文字列）にマッチする． あるバージョンのgrepや，sedでは，最後の例は \(Wi\)+ としなければならない．

11 正規表現が利用可能なソフトウェア grep，sedなどのテキスト処理ツール
AWK, Perl, Python, Rubyなどのプログラミング言語 ed，vi，Emacsなどのテキストエディタ Emacsの例： M-x replace-regexp [Enter] \?$ [Enter] ! [Enter] で，行末の ? をすべて ! に変換する． Linuxのシェルなどで使用可能な「ワイルドカード」とは異なる． 正規表現メモ:

12 理論と実用とで異なる正規表現 計算機上では 理論では
パターン01* は，"0", "01", "011", "0111", …のほか，それらを含む文字列（"10101" など）にもマッチする． 多くのプログラミング言語で，パターンは /01*/ のように表記される． ^01*$ と書けば， "0", "01", "011", "0111", … に限定される． 理論では 正規表現01* は，0, 01, 011, 0111, …からなる言語（語の集合）に対応づけられる．10101 はこの集合に属さない．

13 構文図式 パターン "Wi" パターン "Wi*" パターン "(Wi)*" W i W i "Wi"
この図式は，Wirth, N.: "Algorithms + Data Structures = Programs", Prentice-Hall (1976)で使われ， 広まった（ただし村川はこの本を持っていない）． "Wi"

14 BNF記法とは バッカス・ナウア記法（Backus-Naur Form）とも書かれる． （計算機向けの）文法を定義する記法の一つ 変種
ALGOL 60というプログラミング言語の定義で用いられた XMLの構文定義にも使用されている 理論的には，文脈自由文法（第３回授業で解説予定）と関連 変種 EBNF (Extended Backus-Naur Form)では，正規表現と同様に，反復などが使用可能 ABNF (Augmented BNF)というのもある バッカス・ナウア記法: E8%A8%98%E6%B3%95 ABNF（日本語訳つき）:

15 BNF記法による表記の例（１） 縦棒（パイプともいう） コロン，コロン，イコール 数字 <digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" 「数字とは，"0", "1", …, "9" のいずれかである．」 数字列 <digit-sequence> ::= <digit> | <digit> <digit-sequence> 「数字列とは，一つの数字であるか，一つの数字と一つの数字列を連結したものである．」 <digit-sequence>を定義する際に，<digit-sequence>自身を使用している…「再帰的な定義」という "12345" や "00321" などが該当する EBNFでは， <digit-sequence> ::= <digit>* 再帰的な定義では通常，a_{n+2} = a_{n} + a_{n+1}のように，小さいものを用いてより大きいものを定義する（逆に解くときには，より小さい要素に置き換えながら求める）． BNFでは，そのような大小関係がない点に注意．これでも構文として成立しているのは， 「有限回のルールの適用で導出されるものに限る」からである．

16 BNF記法による表記の例（２） 非ゼロ数字 符号なし整数 符号 整数
<digit-nonzero> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" 符号なし整数 <unsigned-integer> ::= <digit> | <digit-nonzero> <digit-sequence> 符号 <sign> ::= "+" | "-" 整数 <integer> ::= <sign> <unsigned-integer> | <unsigned-integer> EBNFでは <unsigned-integer> ::= <digit> <digit-nonzero>* <integer> ::= <sign>? <unsigned-integer>

17 BNF記法，EBNF記法と構文図式 <digit-sequence> ::= <digit> | <digit> <digit-sequence> <digit-sequence> ::= <digit> {<digit>} digit digit-sequence {…} は 0回以上の反復 再帰が不要！ digit digit digit

18 BNF記法による表記の例（３） 自然言語への適用
<主語> ::= "私" | "あなた" | "彼" | "彼女" | "それ" <主格助詞> ::= "は" | "が" | "も" <動詞> ::= "勉強する" | "食事する" | "遊ぶ" <文> ::= <主語> <主格助詞> <動詞> "私は勉強する"，"それも食事する" など，5×3×3 = 45通りの文例が作れる． この例のように，日本語として正しい文の“一部”をBNF記法で定義するのは容易だが， 日本語として正しい文の“全て”をBNF記法（文脈自由文法）で定義するのは困難であり， 制限を緩めた文法定義のための枠組（文脈依存文法など）が必要とされる．

19 BNF記法をどう使う？ 文法が適切に定義されているか，想定していない文字列が含まれていないかを，設計者らが検証する．
先ほどの例では，"0777" は数字列ではあるが，符号なし整数ではないし，整数でもない． 構文解析により，入力文字列を計算機内部で処理しやすい形に変換する． ソフトウェアはBison/Flexが有名 詳細は，第４回以降の講義や，「データ構造とプログラミング技法」の授業などで学んで欲しい Cなどのプログラミング言語では「0777」を整数値として認めている． ただしその値の意味は「777」とは異なる．

20 まとめ プログラミング言語，正規表現，BNF記法などは，人の思考（自然言語，あやふやなアイデア）と計算機（指示通りに厳格に処理する）を仲介する人工言語である． 正規表現は，すでにあるテキスト情報から該当箇所を探すのに使う． BNF記法は，「情報の形（構文）」を計算機向けに定義するのに有用である．