<   2006年 03月 ( 19 )   > この月の画像一覧

抽象的プログラミング

Racc を使ってみて一番面白かったのは、Raccが構文解析のみを行うプログラムを作れることだ。何かのプログラム言語や設定ファイルを解析するプログラムを作る際に、語句や文の具体的な内容を考えないで、あいまいにしたまま、構文解析のみをきっちりやることが出来るということだ。

使ったことは無いが、Ruby on Rails も同じような物ではないだろうか。たった一行で、ブックマークをデータベースに登録するウェブ・プログラムが書けるようになるらしいが。これも、個々の機能の詳細を気にせずその外枠だけを作ってしまうということなのだろう。

大まかな枠組みや構造をプログラムして動作確認も出来て、詳細はあとで詰めることが出来るような抽象的なプログラムのやり方ができれば生産性がかなりあがるのではないだろうか。

例えば、HTMLのレンダリングをするプログラムを作る際に、ウェブにアクセスする、HTMLの分析をする、表示をするというように大まかに決めた枠組みが実行可能なプロクラムでできて、その後で技術的な細かいことはプログラムでき、それも部分的にできていても実行確認できるというようなプログラムの手段があれば便利だと思う。

そのために必要な要件は何かというと、様々な動作を求められる多くのプログラムに共通する抽象的な構造はどういうものかを研究することだ。そうして、その構造のみを実行可能なプログラムを作成できることだ。Word や Excel が部分的にはそういう要求を満たしているかもしれないが、やれることの制限が多い。誰かRuby on Rails を一発でインストールしてすぐに使えるような本を書いてくれないだろうかと思う。
[PR]
by tnomura9 | 2006-03-28 08:06 | Ruby | Comments(0)

Racc の使い方 その7

スキャナとパーサの分離

Racc で作成される言語処理プログラムは大きく分けて字句解析部(scanner)と構文解析部(parser)の二つの部分で構成されている。スキャナで字句解析が行われ、それがパーサに渡されるが、この二つのプログラムは分離して管理することが可能だ。

はじめに、Racc 添付の calc.y のコピーを2つ calcrule.y と calcscan.rb という名前で作成する。次に calcrule.y は、calc.y の文法規則を記述した部分のみを残して、後は消去する。また、アクションもトップレベル以外は消してしまう。calcrule.y は次のようになる。

class Calcp
prechigh
nonassoc UMINUS
left '*' '/'
left '+' '-'
preclow
rule
target: exp { puts 'syntax OK' }
| /* none */

exp: exp '+' exp
| exp '-' exp
| exp '*' exp
| exp '/' exp
| '(' exp ')'
| '-' NUMBER =UMINUS
| NUMBER
end

calcscan.rb のほうは、calcrule.y とは逆に、文法定義の部分を消去してしまう。また、calc.y で inner として記述されていた部分は、Calcp クラスの中に記述される部分なので、class Calcp ~ end の間に記述するようにする。calcscan.rb は次のようになる。

# calc scanner

require 'calcrule.tab.rb'

class Calcp

def parse(str)
@q = []
until str.empty?
case str
when /\A\s+/
when /\A\d+/
@q.push [:NUMBER, $&.to_i]
when /\A.|\n/o
s = $&
@q.push [s, s]
end
str = $'
end
@q.push [false, '$end']
do_parse
end

def next_token
@q.shift
end

end

parser = Calcp.new
puts
puts 'type "Q" to quit.'
puts
while true
puts
print '? '
str = gets.chop!
break if /q/i =~ str
begin
parser.parse(str)
rescue ParseError
puts $!
end
end

これで準備が整ったので、実験開始だ。まず、calcrule.y を Racc でコンパイルする。

> Racc calcrule.y

calcrule.y にはアクションも何もない抽象的な文法だけしか記述していないのにコンパイルは成功する。コンパイルして作成されたファイルは calcrule.tab.rb である。そこで、ruby calcscan.rb として calcscan.rb を起動すると、次のように入力した式の文法チェックをしてくれる。

? 1 + 2
syntax OK

統語論的なプログラムを作成する Racc

この実験で驚くのは、calcrule.y には抽象的な文法規則のみしか記述していないのにコンパイルされたプログラムがきちんと動作してしまうことだ。Raccが構文規則のみをうまくコンパイルしてくれることが分かる。個々の式や演算に意味を与える前に、syntax のみを処理することができるのだ。意味論的(semantic)なメカニズムは後で自由に構築できるのである。

もうひとつは、スキャナとパーサが独立しているので、汎用的なスキャナーを作っておけば、どんな文法規則にも同じスキャナで対応することができるということだ。プログラム言語で使用する記号の種類は高が知れているので、事実上どんな言語にも対応するスキャナを作っておくことができる。

構文解析プログラムを作成するということは複雑なようでいて、Raccを利用するとほとんど同じような定型的な操作で作成できることが分かる。ブログで説明できるのはこの程度だが、Raccについて解説した唯一の参考書である『Rubyを256倍活用するための本 無道編』青木峰郎著を読むともっと突っ込んだ形で、このことが体験できる。
[PR]
by tnomura9 | 2006-03-27 18:15 | Ruby | Comments(0)

Racc の使い方 その6

calc.rb で変数を使えるようにする

待ちに待った『Rubyを256倍使うための本 無道編』、青木峰郎著が届いたので、calc.rb に変数への代入を出来るようになった。文法規則のところを次のように変更する。斜体の部分が改造したところだ。ただし、Racc 添付の calc.y からの変更ではなくて文字列を認識できるように改造したその5のソースからの改造になる。

rule
target: exp
| IDENT '=' exp { result = do_assign( val[0], val[2] ) }
| /* none */ { result = 0 }

exp: exp '+' exp { result += val[2] }
| exp '-' exp { result -= val[2] }
| exp '*' exp { result *= val[2] }
| exp '/' exp { result /= val[2] }
| exp '^' exp { result **= val[2] }
| '(' exp ')' { result = val[1] }
| '-' NUMBER =UMINUS { result = -val[1] }
| NUMBER
| IDENT { result = do_refval( val[0] ) }
end

うえの規則のアクションのうち、do_assign と do_refval は自分で定義しなくてはならないが、calc.y の inner の部分に書き込むと良い。inner というのはパーサのクラス Calcp の中で定義するということだ。calc.y の変更は次のようになる。

---- inner
def initialize
@vtab = {}
end

def do_assign(vname, vval)
@vtab[vname] = vval
end

def do_refval(vname)
@vtab[vname]
end


def parse(str)
@q = []

改造した calc.y を racc -o calc.rb calc.y でコンパイルして、ruby calc.rb を走らせると、

? a = 1
= 1

? b = 2
= 2

? a + b
= 3

のように変数を使った計算が出来るようになった。Racc を使ったプログラムも calc.y をいろいろと変更しながら使ってみると意外に難しくないかもしれない。
[PR]
by tnomura9 | 2006-03-26 12:08 | Ruby | Comments(0)

連想を妨げる要因

いろいろ試してみたが、記憶力を強化するコツは連想をどう上手に使うかという事のようだ。

連想の使い方が下手な理由の第一の原因は、思い出そうとしないことだ。本を読みながら、うんうんと納得していてもその直後に何が書いてあったか思い出そうとしても思い出せないのに気がつくことがある。それは、理解したことでも思い出そうと意図しないと忘れてしまうということを意味している。

エピソード記憶に見られるように、本来、一度経験したことは記憶があまり消滅しないのではないだろうか。それを思い出せないのは想起するための連想がうまく働かないせいなのではないか。こまめに本を読み止めて、今読んだことを思い出すのは、わずらわしい労力だが、必要なことなのかもしれない。

連想を妨害するもうひとつの要因は干渉だ。連想はもともと、ひとつの項目ともうひとつの項目が結びつく一対一の関係でできているのではないかと思う。ひとつの項目に複数の項目を関連付けるとお互いが干渉しあって想起できなくなってしまうのではないだろうか。意識して連想を作り上げるときは、できるだけ一対一の関係を壊さないような連想の鎖にする必要があるだろう。

他にも、たとえば連想にストーリ性を持ち込むとか、論理的な推論を利用するとか、連想を強化するための方策はいろいろありそうだが、用は、意識的に思い出そうとする練習をつむことである。スポーツと一緒でひたすら練習することも大切なのだ。
[PR]
by tnomura9 | 2006-03-25 07:15 | 考えるということ | Comments(0)

Racc の使い方 その5

字句解析部と構文解析部

その4で述べたように、数式処理のばあい、数字と記号の列で与えられる数式を処理するプログラムはまず字句解析部でトークンと呼ばれる単位に切り分け、それを構文解析部が処理して文法のチェックを行うという手順になる。実は Racc はこの構文解析部の面倒しか見てくれないのだ。字句解析部のプログラムは自分で用意しなくてはならない。

calc.y の字句解析部は次のようになる。

def parse(str)
@q = []
until str.empty?
case str
when /\A\s+/
when /\A\d+/
@q.push [:NUMBER, $&.to_i]
when /\A.|\n/o
s = $&
@q.push [s, s]
end
str = $'
end
@q.push [false, '$end']
do_parse
end

def next_token
@q.shift
end

このプログラムで@q がトークンを収めておくキューだ。字句解析部が数式をトークンに切り分けるとき一つ一つのトークンをこのキューに収めておく。構文解析プログラムは next_token メソッドを使ってキューに収められたトークンを取り出して解析していく。

トークンは二つの要素からなっている。ひとつはトークンの種類。もうひとつはトークンの値だ。23 のような数値の場合、トークンの種類は :NUMBER で値はその整数値になる。また記号の場合は種類も値もその記号そのものになる。

上のプログラムの when /\A\s+/ の部分が先頭部分の余分な空白を取り除く処置を行う部分だ。正規表現の\Aは先頭から比較するという意味を表している。when /\A\d+/ は数値をトークンとして取り出す処理、/\A./|\n/は一文字の記号をトークンとして取り出す処理を行っている。数式処理の部分で @q.push([:NUMBER, $&.to_i]) がトークンをキューに収める処理である。

そこでこの字句処理部がアルファベットの単語を認識するように変更してみよう。変更部分は次のようになる。

when /\A\s+/
when /\A\d+/
@q.push [:NUMBER, $&.to_i]
when /\A\w+/
@q.push [:IDENT, $&]
when /\A.|\n/o

文法規則に文字列トークンの処理を書いておかないとコンパイルエラーになるので rule のところに文字列トークンの処理を追加する。

target: exp
| IDENT { puts "identifier exists" }
| /* none */ { result = 0 }

コンパイルして calc.rb を起動したとき、次のようになっていれば成功だ。

? racc
idenifier exists
= racc

管理人がRaccを試してみて出来たのはここまでだ。演算子の優先順位の操作、新しい文法の定義、字句解析部分の改造である。

しかし、ここまでの操作でなんとなくRaccに何をさせればよいのかが分かってきたような気がする。calc.y はシンプルとはいえ一通りの数式処理が出来る。すべてのプログラム言語は数式処理の機能を内包しているから、自分のプログラム言語を作るときもこの calc.y を土台に改造していけば何とかなりそうだという気がする。

とにかく、言語処理や数式処理の自前のプログラムが作れるかもしれないと思っただけでうれしくなってしまうのは管理人だけではないはずだ。『Rubyを256倍使うための本(無道編)』の届くのが待ち遠しい。
[PR]
by tnomura9 | 2006-03-21 20:21 | Ruby | Comments(0)

Racc の使い方 その4

アクション

英文を読むとき、英文自身はアルファベットが連続して並んだものだが、それを、単語や熟語、文といった単位に分割して解読していく。

数式の場合も同じで、12 + (345 / 5) のような数式も一連の数と記号の列だがこれを、12 や + や、(、345、/、5、) といったトークンに切り分け、さらにそれらのトークンの配列が文法に沿っているかどうかを構文解析プログラムで解析するという手順になる。

数式の記号列をトークンに切り分けるプログラムが字句解析プログラム。切り分けられたトークンが文法通りに配列されているかを調べるのが構文解析プログラムである。構文解析プログラムはそれ以外に正しい文法の文であれば、その文が指示する作業を行うという役割もある。文に関連させて行う処理をアクションといい、rule ~ end 文のなかの定義の横に書いてある { と } で囲まれた部分が実行される。calc.y の rule の部分を再掲しよう。

rule
target: exp
| /* none */ { result = 0 }

exp: exp '+' exp { result += val[2] }
| exp '-' exp { result -= val[2] }
| exp '*' exp { result *= val[2] }
| exp '/' exp { result /= val[2] }
| '(' exp ')' { result = val[1] }
| '-' NUMBER =UMINUS { result = -val[1] }
| NUMBER
end

exp: exp '+' exp の隣にある、{ result += val[2] } がアクションだ。構文解析プログラムが exp '+' exp というパターンを認識したとき、第3項目の exp の値を result の値に加算する処理を行う。result も val[] も Racc で決められた変数で、大まかに、result は式の値、val[0]は定義の第1項の値、val[1]は第2項の値、val[3]は第3項の値と考えておけばプログラムの改造もできる。

実は、これが分かるだけで calc.rb に累乗の計算を付け加えることができるのだ。

まず累乗の計算を示す演算子 '^' を calc.y に付け加えなければならない。'^' の優先順位は '*' より上なので prechigh に次のように登録する。ここで、left ディレクティブの代わりに、right ディレクティブが使われているのは累乗の場合 2^3^4 のような式は右から計算されるからだ。

prechigh
nonassoc UMINUS
right '^'
left '*' '/'
left '+' '-'
preclow

また、文法の rule にも累乗の規則を追加しなければならない。

rule
target: exp
| /* none */ { result = 0 }

exp: exp '+' exp { result += val[2] }
| exp '-' exp { result -= val[2] }
| exp '*' exp { result *= val[2] }
| exp '/' exp { result /= val[2] }
| exp '^' exp { result **= val[2] }
| '(' exp ')' { result = val[1] }
| '-' NUMBER =UMINUS { result = -val[1] }
| NUMBER
end

calc.rb に累乗の計算を追加するためにやることはたったこれだけだ。あとは racc -o calc.rb calc.y としてcalc.y をコンパイルしてみよう。コンパイルが成功したら ruby calc.rb として calc.rb を実行する。

? 2 ^ 3
= 9

のように表示されれば成功だ。
[PR]
by tnomura9 | 2006-03-21 19:29 | Ruby | Comments(0)

Racc の使い方 その3

演算の優先順位

数式の演算には優先順位がある。1 + 2 * 3 のような場合は、まず 2 * 3 が計算され、その結果の 6 が1 と加算され、答えは 7 になる。つまり、 + の演算より * の演算が優先されるのだ。

このような演算の優先順位は Racc では prechigh と prechlow の間に記述される。calc.y に定義されている演算子の優先順位は次のようになる。

prechigh
nonassoc UMINUS
left '*' '/'
left '+' '-'
preclow

上の記述のディレクティブのうち、left は * や + などの演算が左側から順次遂行されることを示している。nonassoc は単項演算のようにひとつの項にのみ演算が行われることを示す。UMINUS は数の正負を反転させることを示しているが、演算の '-' と区別するために使われ、さしあたってどんな演算子も表していない。使い方は後で述べる。各演算子は上の行に書かれているほど優先順位が高い。この場合、UMINUS > * > + のようになる。* と /、+ と - の優先順位は同じである。つまり、+ と - が混在しているような数式の場合計算は順次左から行われる。

数式の文法規則

calc.y では 3 のように単一の数や、1 + 2 のように数と数を演算子で結合させたものを数式 exp であると定義している。また 3 * (1 + 2) のように、数式 3 と数式 (1 + 2) を演算子(この場合は * )で結合させたものも数式である。このような数式についての文法規則は、Racc では、rule と end の間に記述される。calc.y の場合、次のようになる。

rule
target: exp
| /* none */ { result = 0 }

exp: exp '+' exp { result += val[2] }
| exp '-' exp { result -= val[2] }
| exp '*' exp { result *= val[2] }
| exp '/' exp { result /= val[2] }
| '(' exp ')' { result = val[1] }
| '-' NUMBER =UMINUS { result = -val[1] }
| NUMBER
end

上の例で | は「または」という意味で、exp + exp も、exp * exp も、( exp ) も、単独の数 NUMBER も皆 exp すなわち数式であると言っているわけだ。

注意しないといけないのは数式を表す exp が : の右にも左にもあるということだ、これは再帰的定義といって、プログラムで階乗を定義するときにも使われる。このような再帰的定義の利点は、1 + (2 - (3 * 4)) といったように何層にも入れ子になっている式でも規則的に計算することができることだ。

'-' NUMBER =UMINUS の = の記号が気になるかもしれない。これは -2 などのように数の直前につけられたマイナス記号は単項演算で * よりも優先順位が上になるが、'-' NUMBER という定義ではそれが指示できないため、この定義が UMINUS とおなじ優先順位を持つことを = 記号で宣言しているのだ。

target ディレクティブは構文解析がそこで終了する構造を指示している。字句解析プログラムから構文解析プログラムに渡されたデータの解析が終了したときそれが exp であるか、なにもなしであれば文法は正常だと判断される。それ以外の場合はエラーとなる。
[PR]
by tnomura9 | 2006-03-21 18:37 | Ruby | Comments(0)

Racc を使う その2

calc.y の書き方

Racc についてコード例を示しながら書いていくのは諦めたが、考え方とかアイディアなら書いていけると考え直した。そこで、calc.y を Racc でコンパイルした calc.rb の動作について調べてみることにする。

> ruby calc.rb

で calc.rb を起動するとプロンプトが現れ、1 + 1[Ret] のように入力するとその答えが次のように表示される。

> 1 + 1
= 2

何と言うことはない単純な動作だが、1 + 1 以外にも、1 + 1 + 1 や、1 + 1 + 1 + 1 など、考えられる限りの組み合わせにも対応することができるのだ。数式の文法が文脈自由文法で記述できるので、文法に従うどんな組み合わせの数式にも対応できる。

このような複雑な動作を一からプログラムするのは大変だが、上の動作も calc.y の中で、

prechigh
left '+'
preclow



rule
exp: exp '+' exp { result += val[2] }
end

と二箇所に記述するだけで実現することができるからすごい。上の例で、left '+' というのは、1 + 2 + 3 のような計算を左側から計算していく、つまり、1 + 2 を最初に計算して、その結果の 3 に 3 を足すということを指示しているし、exp : exp '+' exp というのは、式と式をプラス記号でつないだものも式であるというのを指示している。プログラムする側がやるのはたったこれだけで、後は全部 Racc がやってくれる。

数式の中には 1 * (2 + 3) のように括弧を使って入れ子になっているものも在る。そのようなものも calc.y の中で

  exp: '(' exp ')' { result = val[1] }

とルールを定義するだけで良い。
[PR]
by tnomura9 | 2006-03-21 08:48 | Ruby | Comments(0)

究極の単語帳

読むだけで単語が頭に入ってくる究極の単語帳を見つけた。光文社ペーパーバックスシリーズがそれ。

『起業バカ』、渡辺 仁著を読むと、reality = 「お客様は神様です」ということが良く分かる。

人間、辛抱だ。
[PR]
by tnomura9 | 2006-03-21 00:18 | 考えるということ | Comments(0)

Racc を使う その1

calc.y をコンパイルする

Ruby のアプリケーションで使ってみたいが、使い方が全く分からないのが Racc だ。Racc は、コンパイラーのコンパイラーだ。プログラム言語の文法規則から、それを解読するパーサーを作成するためのプログラムだ。

趣味でプログラムをやっていても、コンピュータに簡単なプログラム言語のようなもので指示ができたらうれしいだろうと思うことがあるが、たいていは挫折する。プログラム言語を解釈するパーサーの部分は知識がないと作れないからだ。本屋に行ってコンパイラ関係の解説書を買ってきても、よく分からないで放置している。

しかし、Raccなら、プログラム言語の文法規則を記述するだけで、パーサーを自動的に作成することができる。しかし、使い方が全く分からない。ネット検索にも全く引っかかってこない。Rubyを256倍活用するための本(無道編)、青木峰郎著を読めば使えるようになるらしいが、注文したばかりで手元にない。待ちきれないので、ちょっといじってみようと思う。

Raccのダウンロードやインストールの仕方はネットで検索できるから省略する。Windowsの場合、RaccはActiveScriptRubyの中に含まれているから、これをインストールするだけでいい。ただ、サンプルなどはRaccのホームページからダウンロードしなくてはならない。zipで圧縮してあるので、LHacaデラックス版で解凍する。解凍した文書ファイルはUnixの形式になっているので WardPad でないと行末が改行されない。

ダウンロードしたサンプルの中に calc.y がある。これを racc でコンパイルしてみよう。コンソールやコマンドプロンプトから

racc -o calc.rb calc.y

とすると calc.rb という Ruby のファイルが作成されている。そこで、

ruby calc.rb

とタイプすると、シンプルな整数の四則演算計算機が起動する。演算子の優先順位や、括弧もきちんと動作するので感動する。

この後、mycalc.y の改行コードを Unix 形式から、Windows 形式に変換する Ruby スクリプトの紹介、mycalc.y に累乗を導入する、mycalc.y に文字列を認識させる、mycalc を実数の計算機にする、mycalc に sin() 関数を導入する、mycalc に変数への代入を導入するという順番に書いていこうと思ったが、ブログではプログラムリストが書けない場合があるのに出くわして断念した。残念。
[PR]
by tnomura9 | 2006-03-20 07:12 | Ruby | Comments(0)