W.Deeの2007年3月の日記

kikyou.info»日記
最新月 : 2008年10月
2003年 [             3    4    5    6    7    8    9   10   11   12  ] 月
2004年 [   1    2    3    4    5    6    7    8    9   10   11   12  ] 月
2005年 [   1    2    3    4    5    6    7    8    9   10   11   12  ] 月
2006年 [   1    2    3    4    5    6    7    8    9   10   11   12  ] 月
2007年 [   1    2    3    4    5    6    7    8    9   10   11   12  ] 月
2008年 [   1    2    3    4    5    6    7    8    9   10   11   12  ] 月
2009年 [   1    2    3    4    5    6    7    8    9   10   11       ] 月
前月の日記  次月の日記

2007年3月26日

悪質なダウンロード

kikyou.infoからダウンロードできるファイルはfiles.kikyou.infoとdownload.kikyou.infoでホストされています。通常はfiles.kikyou.infoでホストして、こっちの帯域が危なくなってくるとdownload.kikyou.infoにリダイレクトするようになっています。最近はそれほどアクセスのあるファイルもないので、ほとんどがfiles.kikyou.infoからダウンロードされています。

で、数週間前から、中国に割り当てられているIPアドレスをもつ複数のホストから同時多発的に、同時20~100分割など、ほとんどサーバへの攻撃に近い形での悪質な分割ダウンロードが行われています。これを受け、悪質なダウンロード方法を採るホストに対してはパケットごと遮断するようにしました。遮断する時間は、悪質さの程度にもよりますが、最長24時間です。

スクリプトで監視してますし、ホストの国別の判断もしてないので、国内からのアクセスでも異常なアクセスの仕方をすると自動的に遮断される可能性があります。といっても1週間ほど この遮断システムを運用して、ひっかかるのはすべて中国からのアクセスという罠。

ちなみに過去に開発した分割ダウンロードを効率よく禁止できるhttpdは、今のところ使っておりません。現状、kikyou.infoではメインのApache httpdがポート80で動いているため他のhttpdは8080などで動かすしかなく、そうするとダウンロードできないという報告がセキュリティポリシーがきつめのところからいくつかあったためです。

中国からのこれらの悪質なアクセスで困るのは、回線が細くてダウンロードに時間がかかるのに大量のコネクションを張られてしまうことです。いまのところただのApache httpdでデータを提供していますから、それだけサーバのプロセス数とメモリを喰うことになります。文句の言い先もわからんですしね。

まぁほんと、分割ダウンロードしたって大して速くなりませんからやめて欲しい物です。

  • 2007-03-31 10:33 エフシイエス : 中国では分割ダウンロードは常識として行われています、あまり言い争うのも良くないと思います。私ははじめてここに辿り着いちゃったですか、 中国の人の代わりに謝罪を・・・大変ご迷惑を掛けました、まことにすみませんでした
  • 2007-03-31 23:55 Miliardo : こちらは吉里吉里/KAGの推進を行いますから、中国のサーバで吉里吉里(中国語化したカスタマイズバージョンなんだけと)のダウンロードを提供しています。中国からの負担を軽減できるなら嬉しいです。 中国のネット回線はかなり不良ですから、分割ダウンロードを行わないとスピードが落ちます、或いは中断されるかも知れない。だからみんなも既に分割ダウンロードを慣れました。その件について、私も中国の同胞の代わりに謝罪します。誠に申し訳ありません。
  • 2007-04-01 21:51 W.Dee : 国外からのアクセスに対しては分割ダウンロード禁止httpdにリダイレクトするようにしました(異常な同時接続数と判断されるホストからのアクセスは相変わらず遮断しています)。あ、毎度ありがとうございます > Miliardoさん

2007年3月17日

Risse進捗(16)

引き続きの引き続きの話です。

今回はコンテキストとクロージャの話です。

TJS2と同じく(嘘です、TJS2にはこれはないです)、Risseでは、メソッドやプロパティのローカル変数をメソッドやプロパティに束縛する機能があります。クロージャと呼んでいます。

これはたとえば

function f() {
  var local_var = 0
  return function () { return ++local_var }
}

と、関数が関数を返すようなときに出てくる話です。この例では f() 内のローカル変数local_varを、入れ子の関数内で参照しています。その入れ子の関数が返されています。入れ子の関数が返される頃にはf()のスコープは抜けているのでlocal_varは消滅しているのかというとそうではなくて、ちゃんと入れ子の中の方の関数が参照しているローカル変数はそのまま生きています。この場合では、この入れ子の中の関数を呼び出すごとにインクリメントされた値が返ることになります。

それとは別に、メソッドやプロパティが動作すべき「this」をメソッドやプロパティそのものに束縛する機能があります。これをなんと呼ぶべきかはまだ調べてないのでよく分かりませんが、コンテキストと今のところ呼んでいます。また、これは上述のクロージャとはまた別の機能です。

TJS2にもある演算子ですが、incontextofという演算子があって、コンテキストを任意の物に変えることができます。

var func = function () { print(this) }
func = func incontextof "AA"
func() //=> "AA"
func = func incontextof 123
func() //=> 123

インスタンスやクラスからメソッドを取り出すと、コンテキストが束縛された状態の物が返ってきます。

var s1 = "ABC".charAt
print(s1(0)) //=> "A"
var s2 = "DEF".charAt
print(s2(0)) //=> "D"

正確には、 . (直接メンバ選択) 演算子が、メソッドやプロパティを返す場合、この演算子の左側にある物をコンテキストとして束縛した状態の値を返してきます。. 演算子がコンテキストとして演算子の左側にある物を束縛する条件はもう一つあって、"dynamic" コンテキストが指定されているものに限られます。function で定義されたメソッドは、static 指定が無ければかならず dynamicコンテキストが指定されている物とみなされます。static 指定があれば、前のエントリでも述べたとおり、そのメソッドが宣言された位置におけるthisがコンテキストとして束縛されます。dynamicコンテキストを明示的に指定するためにincontextof dynamicという構文が用意されています。

var obj.m = function() { print(this) } incontextof dynamic
obj.m() //=> メソッドは obj のコンテキストで実行される
         //   ( . 演算子の左側のコンテキストで実行される)
var obj.m = function() { print(this) } incontextof A
obj.m() //=> メソッドは A のコンテキストで実行される

これに対して :: 演算子は、たとえメソッドがdynamicコンテキストであると指定されていても、このコンテキストの束縛の動作を行いません。メソッドがdynamicコンテキストの場合は、メソッドを呼び出した時点のthisが、呼び出し先メソッドのコンテキストになります。

var obj.m = function() { print(this) } incontextof dynamic
obj::m() //=> メソッドは this のコンテキストで実行される

これがsuperと :: 演算子を組み合わせて使わなければならない理由です。super.m() としてしまうと、m()のコンテキストはsuper、つまりスーパークラスそのものになってしまいます。しかしsuperを呼び出す場合は、呼び出し元のthisが呼び出し先に伝わってくれないと困るため、:: 演算子を使うことになります。

コールバックブロックは、それを評価した位置のthisをコンテキストとし、またその位置にあるローカル変数を引きずったクロージャとして呼び出し先に渡ります。

function Integer.times() b {
  // this回、bを呼び出す
  var x = this
  while(x--) b() // コールバックブロックを呼び出す
}

var this.inst_var = 0
var local_var = 20
10 .times() { inst_var += local_var }

これにより、簡単にコールバックを記述することができます。

function による入れ子の関数を返す用途では、そのままではthisが束縛されません。束縛するには以下のようにstatic指定をする必要があります。

function C.m(x) {
  return static function () {
    return this.n(x)
  }
}

2007年3月16日

Risse進捗(15)

引き続きの話です。

Risseのコンストラクタはinitializeという名前のメソッドです。TJS2の場合はクラス名と同じ名前のメソッドでした。Risseでは名前が固定されているので、TJS2のようにクラス名を変えたのにコンストラクタ名を変え忘れて変な動作になるという間抜けなことが起きなくなります。

それとは異なる、constructという名前のメソッドがあります。これもインスタンスの初期化の際に呼ばれます。

インスタンスの初期化は、クラスのnewメソッドが司っています。いまのところ、Risseのnewの動作は以下の通りです。

クラスオブジェクトの new メソッドが呼ばれる
  newメソッド内(コンテキスト=クラスオブジェクト)
  | 空のオブジェクトを作る
  | new メソッドは自分のクラスのfertilizeメソッドを呼ぶ
  |   fertilize メソッド内(コンテキスト=クラスオブジェクト)
  |   |  親クラスのfertilize メソッドを呼ぶ(再帰)
  |   |  自分のクラスのmodules[]に登録されているモジュールのconstructメソッドを順番に呼ぶ
  |   |  自分のクラスのconstructメソッドを呼ぶ
  | new メソッドは新しいインスタンスのinitializeメソッドを呼ぶ(普通再帰する)
  | 新しいインスタンスを返す

ええと、ややこしいですが、要するにconstructメソッドはスーパークラス→サブクラスの順に順番に呼ばれます。これに対して、initializeはサブクラス→スーパークラスの順に通常は呼ばれます。initializeメソッドへの引数は、newメソッドへの引数がそのまま渡されます。

通常はというのは、initializeメソッドがスーパークラスのinitializeメソッドを呼び出すのはinitializeメソッドの責任なので、呼び忘れるとスーパークラスのinitializeメソッドが呼ばれない可能性があります。

なので、constructではインスタンスに必須な初期化を行い、initializeではそれ以外の追加的な初期化を行うようにするといった使い方になるかと思います。

そこにmodules[]と書いてあるのは、mix-inを実現するための仕組みです。ここら辺の仕組みはRubyによく似ていて、moduleでモジュールを宣言し、それをクラスにincludeメソッドでインクルードすると、そのmoduleで定義したメソッドがそのクラスで使えるようになります。

Risseのpropertyの宣言方法はTJS2と一緒です。

property f {
  getter    { return v }
  setter(x) { v = x }
}

このメンバを読み出すと getter が、書き込むと setter が呼ばれます。内部の実装はだいぶTJS2と変わっています。

TJS2ではメンバに対するアクセスの際、それがプロパティかどうかを常に確認し、プロパティであればプロパティとして振る舞い、そうでなければ普通のメンバとして振る舞います。Risseの場合は、メンバの属性として「それがプロパティである」というものがあり、それに従って動作しています。

ここで「メンバ」と書きましたが、プロパティは何らかのインスタンスのメンバとして登録されないと使用することができません。ローカル変数としてプロパティを宣言することはできません。ローカル変数にはそういった属性を管理する機構がないためです。

TJS2では . 演算子に代入しようとするとメンバを作成する動作も伴っていました。JavaScriptもそうでした。

object.member = 0;

という文では、objectにmemberというメンバがもし存在しない場合はmemberが作成されていました。

Risseではメンバが存在しない場合はエラーになります。. 演算子はもはやメンバを自動的に作成することはありません。

なぜそういう事になったかはいずれ話すかもしれませんが、決定の過程が長すぎてなんでだったか覚えてません。

メンバを作成するにはvarを使います。上記の例は

var object.member = 0;

と書けば、メンバを作成し、かつ値を代入することができます。

Risseの例外クラスの階層はJavaっぽいです。今のところ以下のようになってます

Throwable
  Error
    AssertionError
  (BlockExitException)
  Exception
    IOException
      CharConversionException
    RuntimeException
      CompileException
      ClassDefinitionException
      InstantiationException
      BadContextException
      UnsupportedOperation
      ArgumentException
        IllegalArgumentException
          NullObjectException
        BadArgumentCountException
      MemberAccessException
        NoSuchMemberException
        IllegalMemberAccessException

例外クラス名長いッスね。例外にこういった名前を付けるのはいいのですが、この階層でいいかどうかは永遠の謎のような気がします。

Throwableの下にはErrorとExceptionがあります。catchする際に条件を省略するとExceptionのサブクラスしかcatchできません。たとえばErrorクラスの例外をcatchしたい場合は、

try
 ...
catch(e if e instanceof Error)
 ...

と明示的に書かなくてはなりません。ただし、Errorのサブクラスはたいていcatchしてもしようがないものですのでcatchしようと思わない方がいいと思います。

BlockExitExceptionというのは、ユーザからはアクセスできない例外です。コールバックブロック中で、たとえば

function loop() block {
  try {
    block(); // コールバックブロックを呼び出す
  }
  catch(e) {
    // block() 内で発生した例外をcatchしたい場合
  }
}

...

loop(x) {
  // コールバックブロックの中身
  ...
  if(x<0) break x;
}
// breakするとloop()の実行を中断してここに制御が遷る

このようにbreakやreturnでブロックを抜けなければならない場合に内部的に発生する例外です。これはcatchされても困るのでcatchできないようになっています。上記の catch(e) { } の部分でもcatchできません。なにがおこってもどうしても実行したいものがある場合はfinallyをつかってください。

throwできるのはThrowableクラスのサブクラスに限ります。

throw "eeeee!!!"

throw 文は、与えられた式のtoExceptionメソッドを呼び出してその結果をthrowします。上記の場合は文字列が与えられているのでString.toException()が呼ばれますが、String.toException()は、RuntimeException.new(this)を返すように実装されているため、結局この場合はRuntimeExceptionがthrowされることになります。

throw RuntimeException.new("a --!!")

の場合もRuntimeException.new("a --!!").toException()が呼ばれますが、ThrowableクラスとそのサブクラスのtoException()は、thisがクラスでなければ自身がthisを返すだけの実装になってるので、結局はRuntimeException.new("a --!!")がthrowされます。

また、ThrowableクラスとそのサブクラスのtoException()は、thisがクラスの場合はインスタンスを作ってから返す実装になってます。なので

throw RuntimeException

とだけした場合はRuntimeException.toException()が呼ばれますが、結局はRunetimeException.new()がthrowされます。

先ほどのコールバックブロックの例ですが、

loop(x)
{
  // コールバックブロックの中身
}

と書いてしまうとloop(x)の次の改行で一文が終わってしまい、その次の { } はただのブロックになってしまいます。"{" の手前で改行を入れる癖のある人(僕もそうです)はうっかりはまる罠だとおもいます。

一応、Risseはこういう書き方をすると

warning: ambiguous block after function call

という警告を出してきます。関数呼び出しのあとのブロックの意味が曖昧であるという警告です。この警告を出さないようにするには、コールバックブロックとして書きたいならば

loop(x) {
  // コールバックブロックの中身
}

とし、ただのブロックとして書きたいならば

loop(x)
// なんかここに空行を入れたり行コメントを入れたりする
{
  // コールバックブロックの中身
}

のようにしてください。

それと、前のエントリではまりそうな罠として挙げた

return
 a()+b();

r = 1 + 4
     + 5;

ですが、最新のRisseではこれも警告してくるようになりました。この場合は

warning: mixing semicolon style and newline style

と言ってきます。セミコロンを使うスタイルと改行を使うスタイルが混在してるという警告なのですが、普段セミコロンで文を終わらせる癖が付いている人が、うっかり変なところに改行を入れて意図しない動作をしてしまう罠をかなり救済できるはずです。

2007年3月15日

Risse進捗(14)

いろいろな話の続きです。

Risseでは

function f() { ... }

と記述すると

var f = function () { ... }

とほぼ同じ意味になります。これは、function をローカルで定義すると、その名前はローカルなスコープに制限されると言うことです。これは class でも property でも一緒です (propertyをローカルで定義すると動作しませんが、なぜかというのはまた後日)。

Risseではクラスの定義の仕方がかなり変わります。

まず、class { } の中身はクラスが定義された時点で評価されます。TJS2 の場合は new の呼び出し時に評価されていました。

つまり

class C {
  var v = 0
  f()
  function m() { } 
}

の中にある f() は、このクラスの定義を評価した時点で実行されます。

じゃあ class C { } の中で、上記のように変数 v などを宣言するとどうなるの、というと、これはクラス変数になります。クラス変数というのはクラス固有の変数で、全インスタンスから同じように見えます。

functino m() { } がどう解釈されるかというのは、最初に述べた「function は var とほぼ同じ意味になる」という話の通りで、これは var m = function { } として扱われ、つまりクラス変数になります。つまり全インスタンスから同じように見えるわけです。

Risse のコンストラクタは initialize という名前のメソッドになります。

class C {
  function initialize() {
    // これがコンストラクタ
  }
}

それとは別に construct というメソッドがあるのですが、それも後日に。

さて、インスタンス固有のインスタンス変数を書く場合ですが、TJS2の場合は class { } の中に書いた var 宣言がそのままインスタンス変数になりました。Risse の場合はコンストラクタ内で宣言して貰うことになります。

class C {
  function initialize() {
    var this.instvar = 0 // これがインスタンス変数
  }
}

クラスにからむ変数の種類にはあともう一つあります。僕もこれを「プライベート変数」だとか「@つき変数」だとか読んで呼び方が一定していないのですが、「クラスごとにもインスタンスごとにも異なる変数」です。これは @ を変数前につけることでアクセスできます。

class C {
  function initialize() {
    var @priv_var = 0 // これがプライベート変数
  }
}

class D extends C {
  function initialize() {
    var @priv_var = 0 // これもプライベート変数
  }
}

この例では C とそのサブクラスの D で同じ名前のプライベート変数を定義していますが、この変数には、それぞれそれのクラスに属するメソッドやプロパティからしかアクセスすることができません。アクセスすることができませんというのは実はちょっと嘘です。というのも @ つき変数は、実のところ、「クラス名_変数名」という変数名に対する糖衣構文です。たとえば、クラス C の中での @priv_var という変数は、実際は C_priv_var という名前のインスタンス変数としてアクセスされていることになります。なので、この命名規則が分かればクラス外からもアクセスすることができますが、そんなのはめんどくさいので、実質的なプライベート変数ですね。関数やプロパティ名としても @ 付きのものを使用することができます。

メンバの宣言には final や const といった属性を指定することができます。final を指定されたメンバは、サブクラスやインスタンスで同名のメンバを宣言したり作成したりすることができません。const を指定されたメンバは、その値を変更することができません。

Java と違って、final 指定されたクラスはサブクラスを作れなくなるわけではありません。一番始めに書いたとおり、 final class C { } と書くと final var C = class { } と同じ意味になるだけで、C というメンバがサブクラスで隠蔽できなくなるだけです。

いまのところ、サブクラスの作成を禁止するには、initialize メソッドを final 指定します。クラスを定義するとかならずそのクラスの initialize メソッドが定義されるので、initialize メソッドを final 指定することは、実質的にサブクラスの作成を禁止することになります。

直接メンバアクセス演算子には TJS2 からある . の他に :: というのがあります。これまたややこしいのですが、ひとまずは :: は super キーワードとともに使うと覚えておけば良いと思います。

class D extends C {
  function initialize() {
    super::initialize() // スーパークラスの initialize メソッドを呼ぶ
  }
}

のようにして使います。これをもし super.initialize() と書くと、スーパークラスのコンテキストで initialize メソッドが呼ばれてしまいます。つまりこの場合は、呼び出し先の initialize メソッドにおける this が C になってしまうということです。super::initialize() ならば 呼び出し先の initialize メソッドにおける this は、呼び出しもとの initialize メソッドにおける this、つまりインスタンスオブジェクトということになります。. (ドット) 演算子が、名前空間とそれが動作するコンテキストを指定するのに対し、:: 演算子は名前空間のみを指定するという意味になります。ここは PHP における -> と :: の違いに似ているかもしれません。

static 宣言されたメソッドや property は、それが宣言された位置の this にコンテキストが束縛されます。

class C {
  static function s() {
    // このメソッドの動作コンテキストは常に C
  }
}

class { ... } 内での this はそのクラス自身ですので、クラス宣言内で static 宣言したメソッドは、常にクラスをコンテキストとして動作することになります。同様に global 位置で static 宣言されたメソッドは、常に global をコンテキストとして動作するようになります。global 位置における this は global そのものだからです。

TJS2 では . 演算子が直接メンバ選択演算子、 [ ] 演算子が間接メンバ選択演算子となっており、間接か直接かの違いはあるものの機能は全く同一でしたが、Risse では名前はそのままですが機能が全然異なります。. 演算子と [ ] 演算子の間に関連性は無くなりました。

一番の違いは [ ] 演算子はクラスごとに再定義できるが、 . 演算子は再定義できないという所です。

class A {
  function [] (idx)    { /* 間接メンバ選択演算子の読み出しの際に呼ばれる */ }
  function []=(e, idx) { /* 間接メンバ選択演算子の書き込みの際に呼ばれる */ }
}

ちなみに . 演算子は直接メンバ選択肢で、A . B と書いた場合は A の中から B という名前のメンバを選択するという意味になります。 B の部分を任意の式にして TJS2 における間接メンバ選択演算子にしたいなー、というときは . の右側に ( ) を書いて、 A . ("B") のように ( ) の中に式を書くことができます。これによりメンバを間接的に指定することが可能になります。

クラスからインスタンスを作成するには new 演算子を使います。ただし、new 演算子は、クラスの new メソッドを呼び出してその結果を返すだけです。なので、

var instance = C.new();

という書き方ができます。すると、new() したあとに . で式をつなげることができて便利です。たとえば いままで (new Date()).getYear() としていたのが、Date.new().getYear() と書けるようになるということです。将来的には .new のところさえ省略できるようにしてもよいかとおもってます。つまり Date().getYear() と書けるようになるかもしれません。

2007年3月14日

Risse進捗(13)

いろいろな話です。

パーザの話にもからみますが、一文を改行で終わることができるようにしました。

「トレンドっぽいから」「セミコロン書くのが面倒だから」というちょっと弱めの理由からですが、実際最近は Risse のテストスクリプトを書いていてもセミコロンを省略する癖がつきつつあります。面倒だからでしょうか。

これには落とし穴があります。行末のセミコロンを省略できる Ruby や JavaScript にも似たような落とし穴が存在します。

それは、たとえば

r = 1 + 4
     + 5

と書かれていた場合で、この場合は r = 1 + 4 + 5 ではなくて r = 1 + 4 と + 5 という二つの式として扱われてしまいます。

これを r = 1+ 4+ 5 として認識させるためには

r = 1 + 4 +
     5

のように + を行末に書いて、次の行に続くことにしなければなりません。

あとありがちなのが

return
  a()+b();

という書き方。これは return の次に改行があるのでそこで return 文が終わってしまっています。このため void が返ります。でもこれは(まだ実装してないけど)「実行されない文がある」という警告を出すことはできそう。a() + b() の部分は return の直後にあるため永遠に実行されないからです。

Risse はこの解釈については Ruby と同じ解釈の仕方をしていて、JavaScript とは微妙に違う解釈の仕方をします。

たとえばさっきの

r = 1 + 4
     + 5

は Risse や Ruby では r=1+4 と 5 という二つの式として解釈されますが、JavaScript の場合は r=1+4+5 という一つの式として解釈されます。Risse や Ruby が単純に「次の行に文が続いているのが明かな場合を除いて、改行をセミコロンとして見なす」のに対して、JavaScriptが「文法エラーが起こった場合に、改行位置でセミコロンをいれることによりその文法エラーが解消されるならば、セミコロンを入れる」という規則だからです。JavaScript的には、 r=1+4+5 は文法エラーを起こしておらず、 4 の後にセミコロンを挿入する必要はない、という判断です。

でもなぜかJavaScriptって

return
  1 + 4

は、return 1+4 が文法エラーを起していないにも関わらず、return と 1+4 という二つの文に分かれるのね (結局 undefined しか返されず、1+4は実行されない)。なぜかしら。

Risseには、このセミコロンの省略の機能を、いいんかなこれとか思いつつ実装。これは結構異論がありそうな感じ。必要ならば通常通りの解釈のモードもつけるかなぁ。

あと、Risseでは TJS2と違い、ブロックの終わりの直前のセミコロンは省略できます。

たとえば

function f() { return r }

と書くことができます。

2007年3月13日

Risse進捗(12)

まずパーザがらみの話です。

あまりに話が長いので少しずつ書いていこうかと思います。

parser generatorとして、RisseではTJS2と同じくBisonをつかってます。

ECMAScriptでは { } で辞書配列を宣言できます。TJS2だとこれが %[ ] になってますが、なぜかというと僕のアタマではこう書くしかありませんでした。{ } は、それが辞書配列なのか、ブロックなのかが曖昧です。

たとえば

{ r: 4 }.dump()

とあった場合、人間ならこれを一目見て辞書配列だ、と分かるわけですが、トークンをアタマから一個一個読んでいくタイプのパーザはそうは行きません。

"{" のトークンを読み込んだ状態ではまだどっちつかずの状態です。"r" を読んでもまだ分かりません。":" を読んでも分かりません。r: がラベルに見えるからです。"4" を読んでもまだ分かりません。 "}" を読んでもまだ分かりません。この状態では、r : 4 という要素を持った辞書配列なのか、r: というラベルと 4 という式を含んだブロックなのかが分からないからです。

これがやっと辞書配列だと決定できるのは、"." を読み込んだ時です。ブロックの後に "." はつきませんから、これでやっとこれが辞書配列であると決定できます。

"r" ":" はラベルに、"4" は式あるいは "r" も式として還元するような文法規則を書くわけですが、bison の LALR(1) パーザでは、こんなに長い間還元をしないまま、いくつものトークンの先読みを行うことができません。LALR(1) の (1) が示すように、たかだか一個先のトークンを先読みできるだけです。

なので、TJS2やRisseでは { } ではなくて %[ ] を辞書配列としてつかっています。

昔 yacc/bison でこの問題を解決できるのかと期待して JavaScript の実装系を手当たり次第に調べたことがありますが、すべて yacc/bison はつかっていませんでした (手書きの再帰下降パーザかそのほかの何か)。

Risseでもこれをやりたかったのですがいろいろ探していると、btyacc - BackTracking Yacc というものが目に付きました。これはこういった競合にぶつかると、「トライ」モードにはいって、パーズを進めます。パーズが失敗したら競合が見つかった場所に戻り、もう一方の競合文法をもとにパーズを進めます。最終的にパーズの成功した道筋だけを選択してアクションを実行します。たぶん、このいったん元に戻る動作から BackTracking と呼ばれているのでしょう。

で、一時期この btyacc に Risse を移植してみました。というかこの btyacc、まず bison と結構文法が違う。簡単な変換スクリプトを Ruby で書いてかましてなんとかそれはパス。次は出力されたファイルがまずコンパイルできないという問題orz。すごい単純な文法規則の出力でもコンパイルできない。しょうがないのでスケルトンを Risse 用に調整しました。

一応動くものができたのですが、そこまでして使うか?という脱力感。

なんか他にないのかなーとおもって探していると、なんと bison にいつのまにか GLR parser (Generalized LR parser)がついているではないですか。%glr-parser 指令を書くだけでこの GLR parser を出力できます。

bison の GLR parser は先ほどの BackTracking Yacc に似ていますが、BackTracking Yacc が一つの文法をたどってダメだったら元に戻って次の文法を、という動作をするのに対し、GLR parser は競合を見つけた時点でパーザが仮想的に分岐し、並列してすべての道筋をたどる動作をします。文法エラーを起こしたパーザはそのまま消滅し、最終的にエラーを起こさなかったパーザが残ります。

さすがにもともと bison 用に書いていただけあって GLR parser への移行はスムーズにすすみ、上記の { } で辞書配列を、の問題もあっさりと解決しました。

が、大きな落とし穴が。

正規表現リテラルを認識できなくなった orz

正規表現リテラルは / と / の間に囲まれた物ですが、この / は除算演算子でもあります。"4/ 5" となったときの "/" は除算演算子ですが、"a = /./" となったときの / は正規表現リテラルの開始です。/ のトークンを見つけたとき、それが 正規表現リテラルの開始なのか、除算演算子なのかはパーザが一番よく知っています。

なので、パーザが "/" のトークンを見つけたとき、それが正規表現ぽかったら、字句解析器にそれが正規表現であることをフィードバックして伝え、字句解析器が正規表現リテラルとして "/" に続く部分を解釈するという動作をします。

この「フィードバック」は bison 上ではアクションとして定義されていますが、bison の GLR parser の場合、このアクションが、文法が曖昧でなくなる点まで遅延されます。つまり、文法が曖昧な場合はアクションの実行はすべて遅延され、「これしかない」となった時点ですべての遅延されていたアクションが実行されます。その時点ではすてに字句解析器はずっと先を読んでいますから、字句解析器へのフィードバックは手遅れということです。

これは解決が難しいです。

あと曖昧な文法が出現するたびに GLR parser がパーザを分岐するためメモリを指数関数的に使うことになり、memory exhausted とかいって parser が異常終了することがあります orz これは文法が曖昧な状態のまま長い間パーズが進行するとよくであうもので、辞書配列の中に関数を入れ子にしてたりするとイチコロです。

それに、競合する文法がどちらも正しかった場合、文法に優先順位をつけないとならないのですが、意図しない場所で競合していたりしてどこで優先順位を指定すればいいのかがよくわからん!あとなんかすごい資料が少ない。

でも、まてよ、たかが辞書配列を { } で書きたいがためにそこまでするか?との疑問が浮かび、やっぱ %[ ] でいいんじゃね?ということで再び bison の LALR(1) パーザに戻ってきました。

でも GLR parser はまたどこかで使えそうだなーということで。