前回、どちゃっと乗せたPEG電卓のコードなんですが、これはPappyやFrisbyのようにメモ化をまったくやっていないPEGパーサーです。ちょっと思いついて、いったいどれくらいの勢いでバックトラッキングが起きているのかを調べてみました。 バックトラッキング…

前回のポストから日数がたってしまいましたが、たまにはちゃんと最後まで書こうということで、出来上がったPEG電卓のコードを乗せておきます。パーサーの定義が前回までのポストとは微妙に変わっていますが、大筋は同じです。こっちのほうがコンパイルして動…

前回、シグネチャだけで終わっていたパーサーを実装してみました。 seqP :: Parser i o -> Parser i o -> Parser i o seqP p q = do v ([o] -> Parser i o) -> Parser i o -> Parser i o ifP p ps pf = Parser $ \i -> case (runParser p i) of Nothing -> r…

PEGで文法を表現してみて、ルールのそれぞれの使い方動きにもなじみが出てきました。ここで、PEGパーサーをちょっと書いてみたいと思います。PappyやFrisbyのようにO(N)というわけに行くかどうかはわかりませんが…方針としては、Parsecのまねということで、…

前回PEGで整数をパースするパターンをやってみました： NUMBER = (ZERO/NONZERO) NONZERO = (DIGIT, DIGIT0*) ZERO = 0!(DIGIT0) DIGIT = (1/2/3/4/5/6/7/8/9) DIGIT0 = (0/DIGIT) これに加減乗除を追加して四則演算をパースするPEGを書いてみます。まずは整…

えー、あけましておめでとうございます。昨年中は色々な方にコメントをいただき、大変ありがとうございました。更新のペースが鈍ってきてはいるのですが、Haskellを通して学んでいることに対する興味は尽きる様子はありません。今年もよろしくどうぞ。

パーサーにかかわることについて勉強していて引っかかったのがPEG（解析表現文法）という文法です。CFG（文脈自由文法）やCSG(文脈依存文法）は生成文法、つまり文章を生成するときに使いやすい表記であるのに対し、PEGは解析、つまりパース時に使いやすい表…