PEG意見交換会

event
  • 濃すぎ。完全に消化不良
  • SICPの4章が終わってないのに参加は無謀でした。今後、何をすればいいかの指標にはなった
  • どんな議論があったかはLingrのログでだいたいわかる
  • 「A ← a A a / a」がなぜ「aaaaa」にマッチしないかでいきなり蹴躓いて最後まで悩む
    • kinabaさんに説明してもらって、懇親会でみなさんに説明してもらって、それでもきちんと理解できなかった
    • PEGのマッチが貪欲（greedy）なことが、他のパーサーとの挙動の差を生むらしい
    • 最後にa A aがマッチして/を越えられないと、バックトラックの過程で空文字列が出てきて失敗してしまう、らしい
    • Lingrに、naoya_tさんがほぼ同様の問題を検証してるとこのリンクが張ってあった
    • 水島さんによるとPEGパーサーは関数型でも書けるそうなので、関数型での検証が今後の自分への宿題
  • ちなみに翌日のLingrから引用

naoya_t
dragon bookの問題はA <- a A a / a ではなく A <- a A a / aa だから、拾える文字列が長さ2^n-1ではなく2^n
ずいぶん悩まされたけれど答えは出てるのでそのうちノートからブログかwikiに写す。a A a の方が取れちゃうと a (もしくはaa) を調べないのがポイントですね。A <- a A aがとれてもその２番目のaが文字列の最後だったらその上の a A a の２番目のaがなくて失敗する、にもかかわらずさっき取れたa A aの代替のA <- a (aa)を試してくれない。
とかいうのを適当な長さのnを設定して辿っていくと帰納的に答えが出る

ということらしい

  • 待ち合わせのときに、某氏と某氏が某調査機関に就職したと聞いてびっくり
  • Erlangにはバイト列にパターンマッチングを行う機能がある（リンク）
  • C++では、hoge < 1 > a; は文脈によって二通りに解釈される
  • 西尾さんがDNAの回文（パリンドローム）構造の話をちょっとしてた。彼も生物系なのか
  • 懇親会では隣でSPARCのレジスタウィンドウの話とかしてた
  • 関数型言語はパーサーを書きやすいというのはウソ（by 水島さん）
    • ここのことかな？
    • Parsecのイメージに引きずられているということらしい
    • 書きやすいのはコンパイラ。ML＝Meta Languageだし
  • peg.scmはdefine-syntaxとか使いまくりで読んでもよくわかんないらしい