システムソフトウェア: 2007年10月10日

q
q
システムソフトウェア
第2回:2007年10月10日(水)
q
q
本日学ぶこと

計算機のための言語
q
q
q
プログラミング言語,自然言語,形式言語
正規表現,パターンマッチ,Emacsなどでの利用
BNF記法
2
ことば(言語)の分類



人同士でコミュニケーションをとるのは,日本語,英語,フラ
ンス語,ドイツ語,エスペラント語…自然言語
人から計算機にまとまった指示を出すのは,C,FORTLAN,
COBOL,Java…プログラミング言語(計算機言語)
「計算とは?」を理論的・フォーマルに記述するのは,数式,
集合,関係,論理,…形式言語
3
自然言語とは


人間が日常的に使っている言語のこと.
計算機言語や形式言語よりも,多様性に富んでいる.
q
q
誤用であっても,聞き手(読み手)が正しく解釈する.
新語が社会で使われていき,いくつかは辞書に載る.
4
プログラミング言語とは

ソフトウェアの設計図に当たるソースコードを記述するため
の人工言語.「計算機言語」ともいう.
q

人間が計算機に命令を指示するという目的がある.
q
q

インタプリタ型を除き,計算機はソースコードを直接実行できな
いので,コンパイラやアセンブラによって実行ファイルを生成し,
そのファイルで実行する.
自然言語に比べて,曖昧さが非常に少ない.
言語仕様は,言語設計者が決める.
関連語
q
アルゴリズムは,計算機が処理する手順を定めたもので,通常,
自然言語または擬似言語で書かれる.
5
形式言語とは

数学的かつ厳密に議論するために使用される人工言語.
q
q

「形式」は,「形だけの」ではなく「フォーマルな」の意味.
有限個の情報をもとに,規則を有限回適用して得られる情報は
何か(一般に無限集合)を考える.
次のような問題に対して,理論的な観点で検討できる.
q
q
q
sinθ+cosθ=2のとき,sinθcosθの値は?
人間同士でうまくコミュニケーションが取れるのはなぜか?
プログラムが停止する(無限ループに陥らない)ことを事前に知
るようなプログラムは作れる?
6
正規表現:はじめに

ニーズ
q
q

レポートに書いている文書で「和大」をすべて「和歌山大学」に
変更しないといけない.見落とさずに,すべて書き換えられるか
な?
2006年1月だったか2007年1月だったか,作ったファイル,どこ
だ….
正規表現を学び,活用することで
q
q
膨大な文書からでも,関心のある箇所を見つけることができる.
日本語で表すと煩雑になる「条件」を,「パターン」で簡潔に記述
できる.
7
パターンマッチとは

パターン "やまだ" は
q
q
q
q

「"や" "ま" "だ" が連続して並ぶ」を意味する.
"わかやまだいがく" にマッチする.
"やまだたろう" にマッチする.
"むらかわたけひこ" にはマッチしない.
パターン "和.*大" は
q
q
q
q
q
「"和"のあと0個以上の文字を挟んで"大"がある」を意味する.
"和歌山大学" にマッチする.
"和大" にマッチする.
"和歌山県にある和歌山大学" にマッチする.
"大和" にはマッチしない.
8
正規表現のメタ文字

メタ文字は,特別な意味を持つ文字のこと
q

a など,特別な意味を持たず,文字がそのままの意味になるも
のを「リテラル」という.
メタ文字の例
q
q
q
q
q
q
q
q
. …任意の1文字
+ …1回以上の繰り返し
* …0回以上の繰り返し
? …1回または0回(あってもなくてもよい)
[ ] …中の一つ
^ …先頭
$ …末尾
「\メタ文字」で,メタ文字自身を表す.
9
メタ文字を利用した正規表現の例






"200[67]-01" は,"2006-01" または "2007-01" を含む文
字列にマッチする.
"200[5-7]-01" は,"2005-01","2006-01" または "200701" を含む文字列にマッチする.
"^Hello" も "World$" も,"Hello World" にマッチする.
"Wi*" は,"W","Wii","Wiiiiiiiiiiiiiiiiiiii" など(を含む文字列)
にマッチする.
"Wii+" は,"W" と "Wi" にはマッチしないが, "Wii",
"Wiiiiiiiiiiiiiiiiiiii" など(を含む文字列)にマッチする.
"(Wi)+" は,"Wi","WiWi","WiWiWi",…など(を含む文字
列)にマッチする.
10
正規表現が利用可能なソフトウェア



grep,sedなどのテキスト処理ツール
AWK, Perl, Python, Rubyなどのプログラミング言語
ed,vi,Emacsなどのテキストエディタ
q

Emacsの例: M-x replace-regexp [Enter] \?$ [Enter] ! [Enter]
で,行末の ? をすべて ! に変換する.
Linuxのシェルなどで使用可能な「ワイルドカード」とは異なる.
11
理論と実用とで異なる正規表現

計算機上では
q
q

パターン01* は,"0", "01", "011", "0111", …のほか,それらを
含む文字列("10101" など)にもマッチする.
 多くのプログラミング言語で,パターンは /01*/ のように表
記される.
^01*$ と書けば, "0", "01", "011", "0111", … に限定される.
理論では
q
正規表現01* は,0, 01, 011, 0111, …からなる言語(語の集
合)に対応づけられる.10101 はこの集合に属さない.
12
構文図式

パターン "Wi"
W

i
パターン "Wi*"
W
i

パターン "(Wi)*"
"Wi"
13
BNF記法とは


バッカス・ナウア記法(Backus-Naur Form)とも書かれる.
(計算機向けの)文法を定義する記法の一つ
q
q
q

ALGOL 60というプログラミング言語の定義で用いられた
XMLの構文定義にも使用されている
理論的には,文脈自由文法(第3回授業で解説予定)と関連
変種
q
q
EBNF (Extended Backus-Naur Form)では,正規表現と同様
に,反復などが使用可能
ABNF (Augmented BNF)というのもある
14
BNF記法による表記の例(1)

数字
q
q

コロン,コロン,イコール
縦棒(パイプともいう)
<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
「数字とは,"0", "1", …, "9" のいずれかである.」
数字列
q
q
q
q
<digit-sequence> ::= <digit> | <digit> <digit-sequence>
「数字列とは,一つの数字であるか,一つの数字と一つの数字
列を連結したものである.」
<digit-sequence>を定義する際に,<digit-sequence>自身を
使用している…「再帰的な定義」という
"12345" や "00321" などが該当する
15
BNF記法による表記の例(2)

非ゼロ数字
q

符号なし整数
q

<unsigned-integer> ::= <digit> | <digit-nonzero> <digitsequence>
符号
q

<digit-nonzero> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" |
"9"
<sign> ::= "+" | "-"
整数
q
<integer> ::= <sign> <unsigned-integer> | <unsignedinteger>
16
BNF記法,EBNF記法と構文図式

<digit-sequence> ::= <digit> | <digit> <digit-sequence>
digit
digit-sequence

<digit-sequence> ::= <digit> {<digit>}
{…} は
0回以上の反復
再帰が不要!
digit
digit
digit
17
BNF記法による表記の例(3)

自然言語への適用
q
q
q
q
q
<主語> ::= "私" | "あなた" | "彼" | "彼女" | "それ"
<主格助詞> ::= "は" | "が" | "も"
<動詞> ::= "勉強する" | "食事する" | "遊ぶ"
<文> ::= <主語> <主格助詞> <動詞>
"私は勉強する","それも食事する" など,5×3×3 = 45通りの
文例が作れる.
18
BNF記法をどう使う?

文法が適切に定義されているか,想定していない文字列が
含まれていないかを,設計者らが検証する.
q

先ほどの例では,"0777" は数字列ではあるが,符号なし整数
ではないし,整数でもない.
構文解析により,入力文字列を計算機内部で処理しやすい
形に変換する.
q
q
ソフトウェアはBison/Flexが有名
詳細は,第4回以降の講義や,「データ構造とプログラミング技
法」の授業などで学んで欲しい
19
まとめ



プログラミング言語,正規表現,BNF記法などは,人の思考
(自然言語,あやふやなアイデア)と計算機(指示通りに厳格
に処理する)を仲介する人工言語である.
正規表現は,すでにあるテキスト情報から該当箇所を探す
のに使う.
BNF記法は,「情報の形(構文)」を計算機向けに定義するの
に有用である.
20