2009-11-03

Parse::RecDescent (3)

Perl

左結合な減法，つまり「1-2-3」は「(1-2)-3」であって「1-(2-3)」ではない，ということを解決する方策をHigher-order Perlの8.4節からもらってきます．

左結合を実現するのに，単純に

expression : expression "-" atom

としてしまうと，expressionを処理するためにどんどん再帰が深くなり，その上，与えられた文字列は一切消費されないのでその再帰は無限ループになってしまいます（左再帰，left-recursive）．Parse::RecDescentはそれを検出してエラーを出すのです．これを解決する方法は，当たり前ですが

文字列をきちんと消費する（再帰が終わるようにする）
左から計算させる細工を入れる

ことにつきます．しかし左から計算させるために，上のように左側にexpressionをおいてはいけません．となると，左におけるのは今の場合，atomしかありません．そうすると右におくものは「式の残り」になります．

簡単な例で考えます．「1-2」を「1」と「-2」とし，この「-2」を関数だと思います．つまり，f(x)=x-2という関数を「-2」と表現しているとみなします（Haskellとかの関数型言語の考え方ですね）．この考え方だと「1-2=f(1)」ということになります．「-2」を一個の関数とみなすことが重要です．Parse::RecDescentの文法のルールの形で表すと

expression : atom expression_tail
expression_tail : "-" atom

となります．expression_tailは上でのf(x)=x-2に相当する関数を返すことになるので，アクションもつけると

expression : atom expression_tail
expression_tail : "-" atom
    {$result = sub {$_[0] - $item[2]; }; }

となります．$resultには無名サブルーチンが入ります．$item[2]が「1-2」の「2」に，関数fがこの無名サブルーチンに，fの引数xが$_[0]に対応します．このように返ってきた無名サブルーチンを最初のルールのexpression_tailが受け取り，atomを引数として処理すればいいので，最初のルールとそのアクションは次のようになります．

expression : atom expression_tail
    { $result = $item[2]->($item[1]); }
expression_tail : "-" atom
    { $result = sub {$_[0] - $item[2]; }; }

これで単純な「1-2」のような引き算は処理できます．なお，expression_tailのアクションでは，引き算が順番に依存することを考慮して$_[0]-$item[2]としていることにも注意してください．

さらに左結合性を考えるために「1-2-3」を考えてみます．「1-2」を先に計算したいので，先ほどのf(x)=x-2を用いると「f(1)-3」となります．そこで今度はg(x)=x-3とすると，まったく同じく「f(1)」「-3」という構造になるので，g(f(1))と表現できることになります，左側の演算であるfが，右側の演算であるgの中に入り込んでいるので，fから計算されること，つまり「左結合」が関数の合成で表現できています．「1-2-3」から「g(f(1))」まで変換する文法が必要になります．f(1)を作るために文字列「1-2-3」から「1-2」を消費すれば左再帰の問題もおきません．

上の文法では不足なのは明らかですが，文字列は明らかに消費されますので左再帰はおきません．まず最初に，expressionルールでatom="1"とexpression_tail="-2-3"になるのは問題ないとは思いますが，expression_tailルールでは「-2-3」を受け入れてくれません．そこで新しいルールが必要になります．今度は「1-2」から「3を引く」ということになるので，「3を引く関数g」を意識して，上の単純な引き算のexpression_tailを利用することも考えて，次のようなルールを作ります．

expression_tail : "-" atom expression_tail

こうすることで新たなatomは"2"，新たなexpression_tailは"-3"です．この"-3"が「3を引く関数g」となります．atomである"2"と"-"と組み合わせて，「2を引く関数f」をつくり，このfにもとのexpressionのatomである"1"を引数として与えてf(1)を作って，このf(1)をgの引数としてg(f(1))をつくれればよいのです．このgをつくるアクションはすでに，単純な引き算「1-2」の考察で作られていることに注意してください．また，expression_tailは「関数を返す」ということにも注意です．ルール中のexpression_tailは$item[3]で，atomは$item[2]です．そして，もとのexpressionのatomである"1"はexpression側でexpression_tailの引数として与えられるので$_[0]となります．つまりf(x)=x-2は$_[0]-$item[2]になり，これがgつまり$item[3]の引数になります．これをParse::RecDescentの文法で書けば

expression_tail : "-" atom expression_tail
    { $return = sub { $item[3] -> ( $_[0] - $item[2]); }; }

となります．以上をまとめると

expression : atom expression_tail
    { $return = $item[2] -> ($item[1]) ;}

expression_tail : "-" atom expression_tail
    { $return = sub { $item[3] -> ($_[0] - $item[2]) ;} ;}

expression_tail : "-" atom 
    { $return = sub { $_[0] - $item[2] ;} ;}

また，加法は可換な演算なので，引き算同様にこのexpression_tailの形で統一できます．そうすることで同じインターフェースにできて加法・減法を統一的，つまり，組合せや再帰が可能になります．実行可能なコードをあげます．

use strict;
use warnings;

use Parse::RecDescent;
use Data::Dumper;

my $grammar=q(
expression : atom expression_tail
    { $return = $item[2] -> ($item[1]) ;}

expression : atom
    { $return = $item[1] ;}

expression_tail : "+" atom expression_tail
    { $return = sub { $item[3] -> ($_[0] + $item[2]) ;} ;}

expression_tail : "+" atom 
    { $return = sub { $_[0] + $item[2] ;} ;}

expression_tail : "-" atom expression_tail
    { $return = sub { $item[3] -> ($_[0] - $item[2]) ;} ;}

expression_tail : "-" atom 
    { $return = sub { $_[0] - $item[2] ;} ;}

atom : /\d+/
    { $return = $item[1] ;}

);

my $parser = new Parse::RecDescent ($grammar) or die "Bad grammar!\n";

my $text = "1-3-4+7";
my $result = $parser->expression($text);
print "$text = $result\n";

これで足し算も引き算もできます．ここで，一つルールを追加しています．

expression : atom
    { $return = $item[1] ;}

がそれです．これは「1」のようなただの数を与えたときも，式とみなすための細工です．expression_tailが空になるときに対応します．このルールは

expression : atom expression_tail
    { $return = $item[2] -> ($item[1]) ;}

のあとにあることがトリックです．順番を変えると正しく動作しません．さらに，まだ演算順序を制御する「括弧」が扱えませんし，したがって「1-(-2)」のような計算もできませんし，「-2+1」のような負の数の計算もできません．

追記

えーっと，まだ途中なので，Parse::RecDescentの他の機能を使った整理とかは考えてないです．以下に「シンプルな部分」だけで頑張れるかです．サブルールを「選言」で書くとかもまだ考えてないです．

2009-11-01

Parse::RecDescent (2)

Perl

単純な足し算だけに続いて，引き算もしたいということで，単純に拡張します．

use strict;
use warnings;

use Parse::RecDescent;

my $grammar=q(
expression : atom "+" expression
    { $return = $item[1] + $item[3] ;}

#引き算を追加
expression : atom "-" expression
    { $return = $item[1] - $item[3] ;}
####

expression : atom
    { $return = $item[1] ;}

atom : /\d+/
    { $return = $item[1] ;  }

);

my $parser = new Parse::RecDescent ($grammar) or die "Bad grammar!\n";

my $text = "8 - 2";
my $result = $parser->expression($text) or die "Bad text!\n";
print "$text = $result\n";

今回は「8-2」を与えてみます．もちろん結果は「6」となります．めでたい．しかし，これはすぐに破綻してしまいます．

$text="8-4-2";

としたらどうなるでしょう．これは

8-4-2 = 6

となってしまいます．「8-4-2」は「(8-4)-2」でなければいけないのに，「8-(4-2)」となってしまっています．足し算の場合は順序は関係ないので問題はおきません．しかし，引き算は順序が関係あり，いわゆる「左結合」の演算なので，そもそもexpressionの段階で間違っています．

expression : atom "-" expression

というのは，「右結合」であり，今の例では，「8-4-2」はatomに「8」，次に「-」，そして次のexpressionが「4-2」ということを意味しています．つまり「8-4-2」が「8-(4-2)」となるのはまさにルール通りです．したがってルールが誤っているのです．

そこで，単純な変更を試みます．atom "-" expressionが「右結合」なら，順番を変えてみる，つまり

expression : expression "-" atom

と書き換えます．これを実行すると，

               ERROR: Rule "expression" is left-recursive.
               (Hint: Set $::RD_HINT (or -RD_HINT if you're using "perl -s")
              for hints on fixing these problems.)

悲しいかな，エラーです．-s -RD_HINTで実行するとヒントがあるというのでやってみます．

perl -s  cal.pl -RD_HINT

                ERROR: Rule "expression" is left-recursive.
                (Hint: Redesign the grammar so it's not left-recursive. That
               will probably mean you need to re-implement repetitions
               using the '(s)' notation. For example:
               "expression(s)".)

「左再帰になってるから文法を見直せ，繰り返しの(s)を使ってる部分を実装しなおせ」といわれますが，そもそも「(s)」なんてものは使ってません．ですので，キーワードは「左再帰」ということです．

今，"8-2"をexpressionルールにマッチさせるとどうなるでしょうか．8-2はatomではないですので，expression "-" atomにマッチしようとします．そこで，さらに最初にexpressionがでてきます．これはatomか「expression "-" atom」ですが，同様の理由で，「expression "-" atom」が対応します．これを延々繰り返してしまうので，左側の項が再帰的にループしてしまうことになり，それがあらかじめ検出されてエラーになっているのです．

これを文法そのものから排除して，なおかつ「左結合」を実現する方策を考えなければいけません．Higher-order Perlの8.4節に助けてもらうことにします．

2009-10-25

Parse::RecDescent (0)

Perl

仕事でどうにもparserを書かないといけなくなるような気がしてます．なんかXMLへの変換とかさせられそうな雰囲気をびしびし．LaTEX2HTMLもそのための伏線．

ということで，Parse::RecDescentも考えよう．HaskellのParsecだとマニアックすぎてだめかもしれないし，メンテナンスできる人間がいなくなるのは確実．Perlなら最悪別部所に読める人がいるからなんとかなる可能性がある．

しっかし，あまりに資料が少ない・・というか「分かってる人向け」がほとんどで，初等的なチュートリアルが少ない．そこで，Higher-Order Perlに助けてもらうことに．8.2節「PARSING IN GENERAL」という節があるのでそこの例を使わせてもらうことに．簡単な計算機，小学校くらいの算数ができるのを作ることを目標としよう．2+3*4とか(2+3)/(1+2)とかを入力すると答えを出してくれるのが目標．

予備知識は，Perlの基本的な事項（「続初めてのPerl」くらいまでの知識）くらいで考えることにする．

2009-10-25

Vistaにインストールした．

LaTeX2HTML

LaTeX2HTMLをVistaにインストールしました．インストールは
http://www.phys.asa.hokkyodai.ac.jp/osamu/l2h2002-2/l2h.html
にあるとおりで一切問題ありません．

さて・・・どうカスタマイズするかを考えねば．

2009-10-25

とりあえず復活

日記

それだけ

2009-10-25

Parse::RecDescent (1)

Perl

Higher-Order Perl（以下HOP）の8.2節の文法をさらにシンプルにして「足し算のみ」を考えます．足し算の文法として以下のものを考えます．

expression -> atom + expression | atom
atom       -> /\d+/

なんか，いろいろなものをチャンポンにした表記ですが，表記にはそれほどこだわらずに，分かればいいくらいで進めます．別に本格的な仕様書を書くわけではありません．

expressionとは

atom + expression，または
atom

であり，atomとは

0から9までの文字が一個以上並んだもの

であると定義しています．これをParse::RecDescentで書いてみると

use strict;
use warnings;

use Parse::RecDescent;

my $grammar=q(
expression : atom "+" expression
    { $return = $item[1] + $item[3] ;}

expression : atom
    { $return = $item[1] ;}

atom : /\d+/
    { $return = $item[1] ;  }

);

my $parser = new Parse::RecDescent ($grammar) or die "Bad grammar!\n";

my $text = "1+2";
my $result = $parser->expression($text) or die "Bad text!\n";
print "$text = $result\n";

これを実行すると

1+2=3

となります．めでたし．

もちろん，問題山積みですが，ひとまず「文字列として数式を与え」て，それを「計算させる」ことができました．もちろんevalを使わずに．

ちょびっとだけ，説明．$grammerに文法を記述します．q( )はシングルクォ−トで囲むのと同じ．expression : とすることで「expression」というルールがどのように定義されるかを指定して，{ }の中に，そのルールに当てはまるときの動作（アクション）を記述します．アクションでは，$returnに代入されたものがその「ルール」の結果得られたものとして返されます．アクション内の配列@itemはルールにマッチしたものが入ってきます．

これではわけが分からないので，シンプルな「1+2」を考えます．

my $parser = new Parse::RecDescent ($grammar) or die "Bad grammar!\n";

によって，$grammerで定義された文法にそったパーサ（の集合体というべきか）$parserが定義されます．$grammerで定義されたルールがこのパーサ（オブジェクトになっている）のメソッドになっています．このメソッドが実際にはパーサであり，

my $result = $parser->expression($text) or die "Bad text!\n";

は$textをexpressionパーサに与えます．

いま，$textは「1+2」であり，これがexpressionパーサに渡されると，expressionパーサのルールにしたがって，パースされます．最初のルール（とアクション）は

expression : atom "+" expression
    { $return = $item[1] + $item[3] ;}

であり，atomが「1」に，"+"は「+」に，そして，残りの「2」がexpressionにマッチします．

atomルールは

atom : /\d+/
    { $return = $item[1] ;  }

であるので，「1」はatomになって，そのマッチした部分「1」が$item[1]として返されます．これがexpressionルールでのatomに戻って，expressionの$item[1]が「1」となります．$item[2]は「+」です．

残された「2」の部分は，もうひとつの

expression : atom
    { $return = $item[1] ;}

でexpressionにマッチします．expressionはatomであり，atomは数字であるので，二段階降りて，atomの$item[1]がexpressionの$item[1]となり，それがさらにもう一つ上のexpressionの$item[1]となり，結果として，文字列"1+2"が数式「1+2」となり，それが計算されて「3」となり，最上位のexpressionの値$resultとして「3」が返ってくるのです．

したがって，「数式」を構成する各要素を慎重に吟味して，それぞれの要素を宣言（マッチするルールとそのときのアクションを定義）しさえすれば，あとは再帰的にどんどん降りていくことで自動的に処理してくれるという仕組みです．

この動きのパーサを「再帰降下」というらしいですが，「再帰降下」のほかにどういう仕組みがあるのかは知りません（苦笑）．HaskellのParsecもこの動きですね．

2009-02-01

初期設定の覚書

PowerShell on Vista

Vista化にともない，PowerShellも入れなおしました．いくつかはまる割には情報の少ない（というか，PowerShell自体の情報がそろえほど多くない）ことを書いておきます．初心者の備忘録でも枯れ木も山の賑わい，ないよりはましでしょう．

スクリプトの実行許可

デフォルトではPowerShellのスクリプト（拡張子ps1）は実行できません．これは，PowerShellのデフォルトがセキュリティの関係でスクリプトの実行を禁止しているからです．まずは，現在の設定を確認しましょう．

Get-ExecutionPolicy

とすると，次の四つのうちのどれかがでてきます．これは制限がきつい順番です．

Restricted
AllSigned
RemoteSigned
Unrestricted

デフォルトはRestrictedで，これだとスクリプトは実行できません．これをRemoteSignedに変更するには，PowerShellを管理者権限で実行させた上で

Set-ExecutionPolicy RemoteSigned

とします．管理者権限での実行は，たとえばPowerShellのアイコンを右クリックして，「管理者として実行」を選んでください．

もっと細かいことは，PowerShellで

Get-Help about_signing

とすると出てきます．この手のヘルプには珍しく，比較的読みやすい日本語です．

入手したスクリプトの実行

ネットから入手したスクリプトは，RemoteSignedポリシーのもとでは実行できません．実行させようとすると

ファイル ***.ps1 を読み込めません。ファイル ***.ps1 はデジタル署名されていません。このスクリプトはシステムで実行されません。詳細については、get-help about_signing」と入力してヘルプを参照してください。。

といわれてしまいます．これは署名がないから実行できないのですが，署名を作る（いわゆる「オレオレ署名）のも大げさな場合があります．そのときは，当該スクリプトファイルを右クリックして，[プロパティ]を開き，一番下の方にある[ブロックを解除]を押して，解除してください．これで次からは実行できます．