# Which library to write a parser **URL:** \ **Category:** ruby-talk\ **Created:** [16 January 2012 07:48 UTC](https://rubytalk.org/t/which-library-to-write-a-parser/64605 "2012-01-16T07:48:59Z")\ **Posts on this page:** 16\ **Page:** 1
**Author:** ![thomas\_carlier](https://avatars.discourse-cdn.com/v4/letter/t/ecc23a/32.png) [@thomas\_carlier](https://rubytalk.org/u/thomas_carlier)\ **Post date:** [16 January 2012 07:48 UTC](https://rubytalk.org/t/which-library-to-write-a-parser/64605/1 "2012-01-16T07:48:59Z")
Hi, I need to write an easy parser and i don't know if i can use an existing library. Thanks > **···** > > -- > Posted via [http://www.ruby-forum.com/](http://www.ruby-forum.com/). ---
**Author:** ![Peter\_Zotov](https://avatars.discourse-cdn.com/v4/letter/p/bbce88/32.png) [@Peter\_Zotov](https://rubytalk.org/u/Peter_Zotov)\ **Post date:** [16 January 2012 08:07 UTC](https://rubytalk.org/t/which-library-to-write-a-parser/64605/2 "2012-01-16T08:07:16Z")
thomas carlier писал 16.01.2012 11:48: > Hi, > > I need to write an easy parser and i don't know if i can use an existing > library. > > Thanks Try Treetop: [http://treetop.rubyforge.org/](http://treetop.rubyforge.org/) You may find one of my blog posts useful: [http://whitequark.org/blog/2011/09/08/treetop-typical-errors/](http://whitequark.org/blog/2011/09/08/treetop-typical-errors/) > **···** > > -- >    WBR, Peter Zotov. ---
**Author:** ![Benedikt\_Huber](https://avatars.discourse-cdn.com/v4/letter/b/ea666f/32.png) [@Benedikt\_Huber](https://rubytalk.org/u/Benedikt_Huber)\ **Post date:** [31 January 2012 12:05 UTC](https://rubytalk.org/t/which-library-to-write-a-parser/64605/3 "2012-01-31T12:05:04Z")
Hello again, I found one combinator-based parser library which seems to provide quite decent performance:   rsec-ext ([http://rsec.heroku.com/](http://rsec.heroku.com/)) Here is the code implementing parslet's MiniP parser:   require 'rubygems'   require "rsec"   include Rsec::Helpers   id = /[a-z]+/.r.fail 'id'   int = /[0-9]+/.r.fail 'int'   op = one\_of\_('+')   comma = /\s\*,\s\*/.r   sum = seq(int, op, lazy{expr})   arglist= '('.r \>\> lazy{expr}.join(comma).even \<\< ')'   funcall= seq\_(id, arglist)   expr = funcall | sum | int   parser = expr.eof   File.readlines(ARGV.first).each { |line| parser.parse!(line) } I do not claim that the parsers are equivalent (different datastructures for the result), and so the comparison is a little bit unfair and only shows a trend. I'd like to share it anyway: Parsing 10000 lines, each containing   puts(3 + 2 + 61235 + 24 + 51, 252 + 235 + 23532 + 11, 2, 3, 5, 7, 11, 19) the parsers need:   parslet / ruby 1.8: 162.8s   parslet / ruby 1.9: 49.5s   rsec-ext / ruby 1.9: 0.7s Kind Regards, Benedikt > **···** > > -- > Posted via [http://www.ruby-forum.com/](http://www.ruby-forum.com/). ---
**Author:** ![GD1](https://avatars.discourse-cdn.com/v4/letter/g/6f9a4e/32.png) [@GD1](https://rubytalk.org/u/GD1)\ **Post date:** [31 January 2012 23:47 UTC](https://rubytalk.org/t/which-library-to-write-a-parser/64605/4 "2012-01-31T23:47:57Z")
Hi Thomas, I use ANTLR to generate C++ code which I subsequently extend into Ruby. It'd be absolute overkill if you're not already extending/embedding for your project though! I believe ANTLR is LL(\*). It also does lexers. There is apparently a Ruby target for ANTLR as well. I've never tried it myself. You'll need Java to build, but not to run- that's the case in my current project but I'm not using the latest ANTLR. Some links: [http://www.antlr.org/](http://www.antlr.org/) > **[ANTLR](https://en.wikipedia.org/wiki/ANTLR)** > > In computer-based language recognition, ANTLR (pronounced antler), or ANother Tool for Language Recognition, is a parser generator that uses a LL(\*) algorithm for parsing. ANTLR is the successor to the Purdue Compiler Construction Tool Set (PCCTS), first developed in 1989, and is under active development. Its maintainer is Professor Terence Parr of the University of San Francisco.\[citation needed\] > PCCTS 1.00 was announced April 10, 1992. > ANTLR takes as input a grammar that specifies a language ... [http://www.antlr.org/wiki/display/ANTLR3/Antlr3RubyTarget](http://www.antlr.org/wiki/display/ANTLR3/Antlr3RubyTarget) Another thing to explore, maybe. 🙂 Good luck! Garth PS. If someone has already suggested ANTLR, my apologies. I skimmed the replied but it was hardly a detailed search. > **···** > > On 16/01/12 18:18, thomas carlier wrote: > > > Hi, > > > > I need to write an easy parser and i don't know if i can use an existing > > library. > > > > Thanks ---
**Author:** ![Kaspar\_Schiess](https://avatars.discourse-cdn.com/v4/letter/k/d78d45/32.png) [@Kaspar\_Schiess](https://rubytalk.org/u/Kaspar_Schiess)\ **Post date:** [16 January 2012 08:33 UTC](https://rubytalk.org/t/which-library-to-write-a-parser/64605/5 "2012-01-16T08:33:54Z")
> Try Treetop: > [http://treetop.rubyforge.org/](http://treetop.rubyforge.org/) And then try parslet: [http://kschiess.github.com/parslet/](http://kschiess.github.com/parslet/) k ---
**Author:** ![thomas\_carlier](https://avatars.discourse-cdn.com/v4/letter/t/ecc23a/32.png) [@thomas\_carlier](https://rubytalk.org/u/thomas_carlier)\ **Post date:** [16 January 2012 09:40 UTC](https://rubytalk.org/t/which-library-to-write-a-parser/64605/6 "2012-01-16T09:40:46Z")
Peter Zotov wrote in post #1041059: > thomas carlier писал 16.01.2012 11:48: > > > Hi, > > > > I need to write an easy parser and i don't know if i can use an > > existing > > library. > > > > Thanks > > Try Treetop: > [http://treetop.rubyforge.org/](http://treetop.rubyforge.org/) > > You may find one of my blog posts useful: > [http://whitequark.org/blog/2011/09/08/treetop-typical-errors/](http://whitequark.org/blog/2011/09/08/treetop-typical-errors/) Thanks and nice blog, very useful informations. I'll try treetop > **···** > > -- > Posted via [http://www.ruby-forum.com/\](http://www.ruby-forum.com/%5C). ---
**Author:** ![11142](https://avatars.discourse-cdn.com/v4/letter/1/e0b2c6/32.png) [@11142](https://rubytalk.org/u/11142)\ **Post date:** [31 January 2012 17:30 UTC](https://rubytalk.org/t/which-library-to-write-a-parser/64605/7 "2012-01-31T17:30:16Z")
For heavy lifting, there's always Racc. ruby\_parser uses it, and it's pretty fast. [http://i.loveruby.net/en/projects/racc/](http://i.loveruby.net/en/projects/racc/) [http://rubygems.org/gems/racc](http://rubygems.org/gems/racc) [http://rubydoc.info/gems/racc/1.4.7/frames](http://rubydoc.info/gems/racc/1.4.7/frames) (Didn't do benchmarks.) -- Matma Rex ---
**Author:** ![Tony\_Arcieri3](https://avatars.discourse-cdn.com/v4/letter/t/8baadc/32.png) [@Tony\_Arcieri3](https://rubytalk.org/u/Tony_Arcieri3)\ **Post date:** [16 January 2012 08:47 UTC](https://rubytalk.org/t/which-library-to-write-a-parser/64605/8 "2012-01-16T08:47:40Z")
Gotta give a nod to kpeg: > **[GitHub - evanphx/kpeg: A simple PEG library for ruby](https://github.com/evanphx/kpeg)** > > A simple PEG library for ruby. Contribute to evanphx/kpeg development by creating an account on GitHub. > **···** > > On Mon, Jan 16, 2012 at 12:33 AM, Kaspar Schiess \ wrote: > > > Try Treetop: > > > > > [http://treetop.rubyforge.org/](http://treetop.rubyforge.org/) > > > > And then try parslet: > > [http://kschiess.github.com/\*\*parslet/<http://kschiess.github.com/parslet/>](http://kschiess.github.com/**parslet/<http://kschiess.github.com/parslet/>); > > > > k > > -- > Tony Arcieri ---
**Author:** ![Ryan\_Davis1](https://yyz1.discourse-cdn.com/flex029/user_avatar/rubytalk.org/ryan_davis1/32/1848_2.png) [@Ryan\_Davis1](https://rubytalk.org/u/Ryan_Davis1)\ **Post date:** [31 January 2012 22:20 UTC](https://rubytalk.org/t/which-library-to-write-a-parser/64605/9 "2012-01-31T22:20:27Z")
I did, but with all the complexity of ruby\_parser, not the grammar in this thread. I did both the 10k testcase above as well as 10k lines of puts(2 + 3) on both ruby 1.8 and 1.9: 1.8: 116.05s: 86.17 l/s: 6.23 Kb/s: 722 Kb:10000 loc:../dev/blah1\_10k.rb   8.68s: 1152.15 l/s: 13.50 Kb/s: 117 Kb:10000 loc:../dev/blah2\_10k.rb 1.9: 84.80s: 117.92 l/s: 8.52 Kb/s: 722 Kb:10000 loc:../dev/blah1\_10k.rb   5.48s: 1825.23 l/s: 21.39 Kb/s: 117 Kb:10000 loc:../dev/blah2\_10k.rb Not an entirely fair comparison by using ruby\_parser instead of an incredibly restrained grammar... but there you have it. That said, I will say that I only barely tolerate LR based parser generators. I would love to have a fully conformant LL-based parser for ruby. I'm not convinced it is possible as ruby's grammar is seriously fucked up. > **···** > > On Jan 31, 2012, at 09:30 , Bartosz Dziewoński wrote: > > > For heavy lifting, there's always Racc. ruby\_parser uses it, and it's > > pretty fast. > > > > [http://i.loveruby.net/en/projects/racc/](http://i.loveruby.net/en/projects/racc/) > > [http://rubygems.org/gems/racc](http://rubygems.org/gems/racc) > > [File: README — Documentation for racc (1.4.7)](http://rubydoc.info/gems/racc/1.4.7/frames) ---
**Author:** ![Peter\_Zotov](https://avatars.discourse-cdn.com/v4/letter/p/bbce88/32.png) [@Peter\_Zotov](https://rubytalk.org/u/Peter_Zotov)\ **Post date:** [16 January 2012 10:31 UTC](https://rubytalk.org/t/which-library-to-write-a-parser/64605/10 "2012-01-16T10:31:23Z")
Tony Arcieri писал 16.01.2012 12:47: > Gotta give a nod to kpeg: > > [GitHub - evanphx/kpeg: A simple PEG library for ruby](https://github.com/evanphx/kpeg) > > > Try Treetop: > > > > > [http://treetop.rubyforge.org/](http://treetop.rubyforge.org/) > > > > And then try parslet: > > > > [http://kschiess.github.com/\*\*parslet/<http://kschiess.github.com/parslet/>](http://kschiess.github.com/**parslet/<http://kschiess.github.com/parslet/>); > > > > k Is there a PEG parser around here which does not keep all the symbols each in its own node? Or, maybe, any one which is faster than a dying snail? Just wondering. > **···** > > > On Mon, Jan 16, 2012 at 12:33 AM, Kaspar Schiess \ \> wrote: > > -- >    WBR, Peter Zotov. ---
**Author:** ![Benedikt\_Huber](https://avatars.discourse-cdn.com/v4/letter/b/ea666f/32.png) [@Benedikt\_Huber](https://rubytalk.org/u/Benedikt_Huber)\ **Post date:** [1 February 2012 00:57 UTC](https://rubytalk.org/t/which-library-to-write-a-parser/64605/11 "2012-02-01T00:57:03Z")
Ryan Davis wrote in post #1043324: > > For heavy lifting, there's always Racc. ruby\_parser uses it, and it's > > pretty fast. > > > > [Racc](http://i.loveruby.net/en/projects/racc/) > > [racc | RubyGems.org | your community gem host](http://rubygems.org/gems/racc) > > [http://rubydoc.info/gems/racc/1.4.7/frames](http://rubydoc.info/gems/racc/1.4.7/frames) > > I did, but with all the complexity of ruby\_parser, not the grammar in > this thread. Thanks for the numbers. I wrote a small grammar for the MiniP language in racc, and repeated the experiments (on a different machine, ruby 1.9.3). racc's speed is ok, but it seems to be slower than rsec-ext. parslet 53.10s racc 2.05s rsec-ext 0.72s > That said, I will say that I only barely tolerate LR based parser > generators. I would love to have a fully conformant LL-based parser for > ruby. I believe both racc and ANTLR won't be faster than rsec-ext, as they generate ruby code. For many less-convoluted grammars (ruby is not a good example ;)), a PEG-style parser library is a good and pleasant to use alternative to a parser generator. For my prototype, I rewrote a constraint file parser to rsec-ext, which works great. I can't use it at the moment, because it is 1.9 only, but that's a different story. Kind Regards, Benedikt > **···** > > > On Jan 31, 2012, at 09:30 , Bartosz Dziewoński wrote: > > -- > Posted via [http://www.ruby-forum.com/\](http://www.ruby-forum.com/%5C). ---
**Author:** ![Kaspar\_Schiess](https://avatars.discourse-cdn.com/v4/letter/k/d78d45/32.png) [@Kaspar\_Schiess](https://rubytalk.org/u/Kaspar_Schiess)\ **Post date:** [16 January 2012 15:58 UTC](https://rubytalk.org/t/which-library-to-write-a-parser/64605/12 "2012-01-16T15:58:42Z")
> Is there a PEG parser around here which does not keep all the symbols > each in > its own node? Or, maybe, any one which is faster than a dying snail? Just > wondering. As one of the authors of one of these libraries which are slow as a dying snail, I am wondering: How do you measure? Would you like to contribute your benchmark, so that our (quite extensive) optimization efforts can go your way? And finally, what is the ground speed of a dying snail? My measurements (to contribute to the thread as well) are here: [press play on tape – Parslet and its friends](http://blog.absurd.li/2011/02/02/parslet_and_its_friends.html) k ---
**Author:** ![thomas\_carlier](https://avatars.discourse-cdn.com/v4/letter/t/ecc23a/32.png) [@thomas\_carlier](https://rubytalk.org/u/thomas_carlier)\ **Post date:** [18 January 2012 03:18 UTC](https://rubytalk.org/t/which-library-to-write-a-parser/64605/13 "2012-01-18T03:18:41Z")
Kaspar Schiess wrote in post #1041114: > > Is there a PEG parser around here which does not keep all the symbols > > each in > > its own node? Or, maybe, any one which is faster than a dying snail? Just > > wondering. > > As one of the authors of one of these libraries which are slow as a > dying snail, I am wondering: How do you measure? Would you like to > contribute your benchmark, so that our (quite extensive) optimization > efforts can go your way? And finally, what is the ground speed of a > dying snail? > > My measurements (to contribute to the thread as well) are here: > [press play on tape – Parslet and its friends](http://blog.absurd.li/2011/02/02/parslet_and_its_friends.html) > > k Hi, Which one will you recommend for a simple grammar like expressions : expression+ ; expression : [{]content+[}] ; content : token               \> TOKEN[|]content               \>TOKEN[|]expression ; TOKEN : .\* ; The grammar is not correct, but you'll understand the main idea Example : some text {text {text|text}} some text {text|text|text} input size [100 - 5000] chars > **···** > > -- > Posted via [http://www.ruby-forum.com/\](http://www.ruby-forum.com/%5C). ---
**Author:** ![Ryan\_Davis1](https://yyz1.discourse-cdn.com/flex029/user_avatar/rubytalk.org/ryan_davis1/32/1848_2.png) [@Ryan\_Davis1](https://rubytalk.org/u/Ryan_Davis1)\ **Post date:** [18 January 2012 04:07 UTC](https://rubytalk.org/t/which-library-to-write-a-parser/64605/14 "2012-01-18T04:07:02Z")
Write your own by hand. It'll be faster and smaller than anything mentioned above. [http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf](http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf) > **···** > > On Jan 17, 2012, at 19:18 , thomas carlier wrote: > > > Which one will you recommend for a simple grammar like > > > > expressions : expression+ > > ; > > expression : [{]content+[}] > > ; > > content : token > >              \> TOKEN[|]content > >              \>TOKEN[|]expression > > ; > > TOKEN : .\* > > ; > > > > The grammar is not correct, but you'll understand the main idea > > > > Example : some text {text {text|text}} some text {text|text|text} > > > > input size [100 - 5000] chars ---
**Author:** ![Kaspar\_Schiess](https://avatars.discourse-cdn.com/v4/letter/k/d78d45/32.png) [@Kaspar\_Schiess](https://rubytalk.org/u/Kaspar_Schiess)\ **Post date:** [25 January 2012 08:20 UTC](https://rubytalk.org/t/which-library-to-write-a-parser/64605/15 "2012-01-25T08:20:47Z")
And for another definition of faster (faster to code): parslet. greetings, k > **···** > > On 18.01.12 05:07, Ryan Davis wrote: > > > Write your own by hand. It'll be faster ---
**Author:** ![Benedikt\_Huber](https://avatars.discourse-cdn.com/v4/letter/b/ea666f/32.png) [@Benedikt\_Huber](https://rubytalk.org/u/Benedikt_Huber)\ **Post date:** [30 January 2012 22:58 UTC](https://rubytalk.org/t/which-library-to-write-a-parser/64605/16 "2012-01-30T22:58:28Z")
Kaspar Schiess wrote in post #1042425: > > Write your own by hand. It'll be faster > > And for another definition of faster (faster to code): parslet. > > greetings, > k Hello, I tried out parslet today, and I really appreciate its design (i.e., what parsers look like) as well as the beautiful webpage you built. I could not use it for my current project, however, as it was way to slow. I need to be able to parse millions of constraint specifications, each based on a fairly simple grammar (20 rules or so). I found my original implementation (regular expression matching and scanning) to be ugly, inefficient (scanning a string a few times) and rather slow (~15K constraints per second). The goal was to get both more beautiful and faster by using a parser framework. It got more beautiful, but too slow to be useful to me. If I had benchmarked the MiniP parser posted on the homepage of parslet, it would have been obvious that parslet is too slow for my purposes: On my machine, it parses 180 lines / second, given the test string   "puts(3 + 2 + 61235 + 24 + 51, 252 + 235 + 11, 2, 3, 5, 7, 11,19)" So while I appreciate the neat interface of those fancy new parsers, people should know that they are slow. But, I think it would be awesome to have a beautiful parser lib that is fast, and given that the performance of the regular expression engine is quite decent, it should be feasible to build such a parser. a) Do you think there is any chance to get a faster (say, factor 100) implementation for parslet with the same (or a similar) interface? b) If not, is there any maintained ruby parsing library or parser generator (no need to be in pure ruby) which is fast enough? How fast is antlr for ruby? Kind Regards, Benedikt > **···** > > > On 18.01.12 05:07, Ryan Davis wrote: > > -- > Posted via [http://www.ruby-forum.com/\](http://www.ruby-forum.com/%5C).