前回、どちゃっと乗せた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を書いてみます。まずは整…

前回に引き続き、解析表現文法（PEG）を見ていきたいと思います。あいまい性が無かったり、再帰降下型パーサーと相性が良いなどの特徴があるPEGなんですが、どうゆう中身になっているのでしょうか。PEGは次のような要素で構成されます。各要素の英語名の後に…

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

id:kazu-yamamotoさんのとりとめのないパーサー談義に刺激されて パーサーのことを勉強しているところです。yamamotoさんは｢パーサーに詳しい人に答えていただけるととても嬉しい」といわれていますが、勉強がてら自分なりの答えを書いてみようと思います。 …