[B! packrat_parsing] InoHiroのブックマーク

Packrat Parsing and Parsing Expression Grammars

Introduction Parsing expression grammars (PEGs) are an alternative to context free grammars for formally specifying syntax, and packrat parsers are parsers for PEGs that operate in guaranteed linear time through the use of memoization. For a brief technical summary see the Wikipedia entry on PEGs. For more in-depth descriptions see the original PEG paper and packrat parsing paper, and related pape

InoHiro 2012/01/17

リンク

Packrat Parserについて - Yet Another Ranha

この記事は、私が全くPackrat Parserが分からなかったにも関わらず、 Packrat Parser generatorを書こうとするうちに、何故かPackrat Parserの事が分かってしまった様な気がしたので書くエントリ。参考ページは http://pdos.csail.mit.edu/~baford/packrat/icfp02/ 上記ページでは非常に簡潔にしかし十分にPackrat Parserについて書かれている。しかも分かりやすく、私の様な馬鹿にさえ理解されてしまう。そもそもPackrat Parserとは何なのか Packrat Parserはその名の通りparsingの技法である。具体的にどういう事をしているのか、という事はFord先生のpaperでも触れられているが、再帰下降パーザ(Recursive Descent Parsing)+Tabular

InoHiro 2010/12/13

packrat_parsing

リンク

Scalaで作るPackrat Parserコンビネータ - kmizuの日記

【急募】PEGパーサのメモ化の実装 http://twitter.com/anatoo/status/1253132392 とかあったんで、せっかくなのでサクっと実装してみた。ポイントは、PEGパーサコンビネータでは、ParserがString => Option[(A, String)]を継承していたのを、Int => Option[(A, Int)]を継承するようにしたことと、Parserの外側のクラスに入力文字列を表すメンバinputを追加したこと。Stringを引数に取る形でも良いのだけど、そうすると、テーブルのルックアップコストが高くなってしまうので、メモ化する意味がほとんど無くなってしまう。 trait PackratParser[+A] { val input: String abstract class Parser[+A] extends (Int => Option[

InoHiro 2010/08/02

packrat_parsing

リンク

Scalaで作るPEGパーザコンビネータ - kmizuの日記

といっても、昨日Javaで作ったPEGパーザコンビネータライブラリをScalaで書き直しただけのものだけど。Java版に比べて、1/3くらいの行数になっている。 object PEGParserCombinator { abstract class Parser[+A] extends (String => Option[(A, String)]) { def /[B >: A](that: => Parser[B]): Parser[B] = parserOf((in) => { this(in) orElse that(in) }) def ~[B](that: => Parser[B]): Parser[(A, B)] = parserOf((in) => { for((r1, rest1) <- this(in); (r2, rest2) <- that(rest1)) yield

InoHiro 2010/08/02

packrat_parsing

リンク

Packrat Parsing を調べてみる - ronSpace

InoHiro 2010/06/04

packrat_parsing

リンク

Rolling with Ruby on Rails

Now, next, and beyond: Tracking need-to-know trends at the intersection of business and techno logy AI/ML Few techno logies have the potential to change the nature of work and how we live as artificial intelligence (AI) and machine learning (ML). Future of the Firm Everything from new organizational structures and payment schemes to new expectations, skills, and tools will shape the future of the fi

InoHiro 2010/06/04

packrat_parsing

リンク

Ruby で packrat parser - まめめも

packrat parsing というパーサの実装方法があります。特徴は、再帰下降パーサ + 無限先読み可能 + memoize*1 という感じです。僕が下手な説明をするより、英語わからなくても Haskell わかればわかる素晴らしいスライドやPappy (reference implementation) を参照してもらったほうがいいです。で、練習として Ruby で packrat parser を使って足し算と掛け算だけの電卓を作ってみました。 $ ruby arith.rb 1 + 2 + 3 => 6 1 + 2 * 3 => 7 1 + 2 * (3 + 4) => 15文法はこんな感じ。式　　　　　 = 空白加算式文字列終端加算式　　　 = 乗算式 ("+" 乗算式)* 乗算式　　　 = プリミティブ ("*" プリミティブ)* プリミティブ = 数値 / "("

InoHiro 2010/05/26

リンク

関数型言語マニアのための論文紹介２：Packrat Parsing - sumiiのブログ

Packrat Parsing: Simple, Powerful, Lazy, Linear Time. Bryan Ford. ICFP 2002. http://pdos.csail.mit.edu/~baford/packrat/icfp02/ 「設定ファイルや専用言語のparserをYACCで書こうと思ったけど、conflictだらけになってわけがわからない」という経験はないでしょうか。それはLALR(1)という構文解析アルゴリズムがややこしいからいけないのです。packrat parsingは、すごく単純で効率のよい構文解析アルゴリズムです。大ざっぱに言うと「再帰＋バックトラッキング＋dynamic programming」だけ。YACCみたいな自動生成器もあるようですが、関数型言語なら手書きしてもno probl emなぐらい楽みたいです。（Y研の卒論でC++パーザを手書きした