パーサが必要な部分だけを書き換えている様子を可視化

hoge1e32007-09-30


Eclipseっぽいインクリメンタルなコンパイルを行うための試作品.

http://www2.eplang.jp/tonyu/adaptive/ (JavaAppletが起動します.ソースあり)

  • 左にソースファイル,右に構文木が出る.
  • プログラム(というかS式)を書き換えると,その周辺だけが消去・再生成される.

文法

S := '(' values ')'
values := empty | value values
value := [a-zA-Z0-9]+ | S

書き換えの方法

  • 変化した部分を覆う最小の構文木を抽出する.アプレットでいうとカーソルを動かしたときに赤くなっている部分が相当
  • その部分を再解析する.
  • 再解析した結果,ソースコード上の開始位置,終了位置が同じだったら再解析成功
  • 再解析失敗なら,その構文木の親について同様に再解析
  • 最後までだめだったらソースファイル全体解析しなおし.

いろいろ問題点

  • 「(a b)」を「(a bc)」としただけでもリスト全体を再解析してしまう.

b というトークンは b までで終わっているので,その後ろに c を追加しても別のトークンだと思われる.一方,たとえば「10」を「120」にする(間に挿入する)場合はトークン内だけが再解析される.

  • 「 ...(a b)...」を 「...(a (b c) d)... 」にするとソース全体を解析してしまう.

ひらき括弧を書いた瞬間に再解析が走ってしまうから.大規模な変更が起きそうなときはすこし待ったほうがよいのかな