SMLの関数適用を構文解析する時の問題

まだ構文解析器で苦労している。今回も詰まっているのは構文のconflict。

問題

これが関数適用

app : exp exp

infixapp : exp vid exp

この時に入力を

x y z

とすると２つの解釈ができてしまうことになる。

((x y) z)

とするネストした関数適用なのか

x y z

とする二項演算子の適用なのかParserが判断つけられない。

前者ならreduceするが後者ならshiftする。なのでこれはshift/reduce conflictが起きていると言える。 happyはデフォルトでshiftするので二項演算子として解釈される。

これを解消したい。

sml-njやmltonのgrmファイルの定義を覗いたところ

FlatAppExp : exp list

のようなデータコンストラクタを使ってとりあえずシンボルのリストとしていったん読み込んでしまうらしい。なぜ関数適用と二項演算子適用は全然違う構造にも関わらず峻別せずに扱うのだろうと疑問に思った。

SMLではfixityを自分で定義して二項演算子を作れる。

左結合か右結合かをどこかのテーブルに保存しておくことになる。(おそらくEnv的なもの？まだそのあたり解らない) こういう動的にassociativityが定義される二項演算子はパーサジェネレータでは扱えないっぽい。

なので一度解析しきってから、後でsanityチェックして弾くっぽい。

解析の途中でこのfixityのテーブルを更新しながら進めば別に解析の完了を待たなくてもいいじゃんとも思った。けれど、それだとfixityの定義が必ず演算子の使用よりも前に定義済みである必要がある。それは不便だろう。

ということでFlatなんたらという構造を導入してなんとか解決はできた。

追記

ここを見るとinfix operatorを動的に定義していく方法が提示されているが、やはりparsecだな。ghcはどうやっているのか見てみる必要ありかな。。。

悪手かなと思うのは、こうした構文解析上の問題のために抽象的なデータ構造にコンストラクタを追加しなければならないという点。せっかくきれいにsyntax objectを定義できたのにノイズが入ってしまうみたいでイマイチだなと思う。

これだと

1 + 2 + 3

みたいな入力は

["1", "+", "2", "+", "3"]

のようにreduceされる。

parsecならこれをexpression builder的なAPIでうまく木構造に変換できるのだが。。。まあ、部分的にparsec使うのはありかもしれない。

あとはモジュール系の構文解析が作れればとりあえず構文解析のステージは終わりだろう。と、言いたいところだがshift/reduceやreduce/reduceのconflictがわんさか残っている。

どうしよう。。。問題ないならこのまま進めてしまいたい。正直conflictの解消法は未だにわかってない。

あとまだわかってないこと。

やりながら良かったと思うこと。

詳解Linux カーネル読んでる。メモリアドレッシングからいきなりハードル高い。

特にページングテーブルの初期化のところとか全然解らない。

Scala勉強しなきゃ、からマッハで脱線してClojureの情報ばかり漁っている。

どっかの記事で「Clojureは大規模プロジェクトになるとメンテナンスが難しくなってきてスケールしない」みたいなこと言ってた。そうだろうなと思う。リファクタリングはそれほど気軽にできないだろう。

specが出てきてチェック機構は揃ってきているけれど、それでもやはり「実行しないと結果が解らない」という制約は残る。

REPLで探索しながら直すべきところは見つけられるよ、という意見もあるかもしれないけれどリファクタリングの過程で影響のあるところ全部を検査する仕組みはやっぱり無いではなかろうか。というかリファクタリングして壊れたところを機械的に見つける手段が無い、と言うべきか。

Clojureもそうだけど、RubyやPythonやJS使っている人たちどうしているのだろう。素朴に疑問。

とかぐだぐだ言いながらもなんかClojure好きなので勉強を続けてしまう。