Ohm: Parsing Made Easy

Hi HN, I&#x27;m a researcher at HARC (<a href="https:&#x2F;&#x2F;harc.ycr.org&#x2F;" rel="nofollow">https:&#x2F;&#x2F;harc.ycr.org&#x2F;</a>) and one of the authors of Ohm. We&#x27;ve used it to power several of our programming language investigations, such as Seymour (which was on HN yesterday: <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=15471954" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=15471954</a>) and Chorus (<a href="http:&#x2F;&#x2F;www.chorus-home.org&#x2F;" rel="nofollow">http:&#x2F;&#x2F;www.chorus-home.org&#x2F;</a>).<p>If you&#x27;re interested, here&#x27;s the grammar for the language used in the Seymour demo: <a href="https:&#x2F;&#x2F;github.com&#x2F;harc&#x2F;seymour&#x2F;blob&#x2F;6f55361ad3410f42f67f183da7b7549418884e50&#x2F;lang&#x2F;grammar.js" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;harc&#x2F;seymour&#x2F;blob&#x2F;6f55361ad3410f42f67f183...</a><p>Happy to answer any questions that you have!

Ohm is very impressive.<p>Specifically:<p><pre><code> 1. The separation of Grammar and Semantics. 2. Handling left recursion in a top down (peg) parser. 3. Incremental parsing. </code></pre> I think that the one feature missing to make it applicable for more than rapid prototyping and teaching purposes is <i>performance</i>.<p>In this benchmark I&#x27;ve authored: <a href="http:&#x2F;&#x2F;sap.github.io&#x2F;chevrotain&#x2F;performance&#x2F;" rel="nofollow">http:&#x2F;&#x2F;sap.github.io&#x2F;chevrotain&#x2F;performance&#x2F;</a> Which uses the simple JSON grammar it is about <i>two orders of magnitudes</i> slower than most other parsing libraries in JavaScript.<p>So I am sure there is a great deal of room for optimizations.

I&#x27;ve really tried to get on with parser generators, but I&#x27;ve found they are hard to use, hard to debug and the languages&#x2F;DSLs are clunky and weird. Except for cleanroom academic implementations, or for language designers who can afford the time and resources to learn and get good at a parser generator, I&#x27;ve found its better to simply use regular expressions to do matching and a functional language that can build up a data structure recursively.<p>Another problem is a lot of them resort to clunky code generation from the grammar file, and when something goes wrong you&#x27;re not debugging the grammar per se, you are stepping through a bunch of machine generated code that you didn&#x27;t write yourself. So your debug process looks like make change to grammar, regenerate parser, try parsing again, loop. etc. It replaces the entire file too, so its not like you can isolate areas of the code and work on them like you would regular code. And the time to generate the parser is often times slow.<p>Also when runtime parsing errors do happen, often the incorrect line&#x2F;column numbers are reported, and getting good descriptive parser errors is a project in and of itself after you have your grammar written and working.

Hey, I’m one of the founders of Nextjournal, the coding, writing and publishing platform this article was written in.<p>This probably isn’t obvious: you can get a copy of the article and play with it if you click remix and sign in&#x2F;up.<p>There’s some more context about what we’re trying to build and why in our launch post <a href="https:&#x2F;&#x2F;medium.com&#x2F;nextjournal&#x2F;launch-nextjournal-public-beta-for-open-research-a55d15bfa95f" rel="nofollow">https:&#x2F;&#x2F;medium.com&#x2F;nextjournal&#x2F;launch-nextjournal-public-bet...</a>

I’ve used Ohm for a few small parsers. What’s great about the editor is that you can take it and share it with somebody else and they’re given insights into _how_ the parser works.

Any thoughts on how to handle parsing for the IDE use case where a document is being edited that might have errors in it. I would usually expect an area around the cursor that is an area that receives edita and hence contains errors. I would also expect a header and footer surrounding the edited area that would be okay structurally since its unchanged from a previously sound definition of the file.

I&#x27;ve had great experience using PEG.js, another PEG-based parser generator. How does Ohm compare?

I really liked what was done in STEPS project. I learned a lot from their repors. For example, this Ian Piumarta&#x27;s paper is absolutely beautiful [1]. I also spent a lot of time learning oMeta [3] system by Alessandro Warth.<p>And, honestly, now I see nothing really new in Ohm. Basically, it&#x27;s just some tweaking of the same tech. Moreover, Ohm was made for isolated parsing task. For me it&#x27;s a step back. My point is that the parsing alone is not very interesting thing, for making DSLs you need to have other tools too. In the Ian Piumarta&#x27;s paper we had a minimalistic program transformation system [2]. Remember original META II [4]? It was a compiler-compiler (metacompiler), not just a parser generator. I&#x27;m really curious to know why the authors decided this time to limit themselves by only parsing.<p>[1] <a href="http:&#x2F;&#x2F;www.vpri.org&#x2F;pdf&#x2F;tr2010003_PEG.pdf" rel="nofollow">http:&#x2F;&#x2F;www.vpri.org&#x2F;pdf&#x2F;tr2010003_PEG.pdf</a><p>[2] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;List_of_program_transformation_systems" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;List_of_program_transformation...</a><p>[3] <a href="http:&#x2F;&#x2F;www.vpri.org&#x2F;pdf&#x2F;tr2008003_experimenting.pdf" rel="nofollow">http:&#x2F;&#x2F;www.vpri.org&#x2F;pdf&#x2F;tr2008003_experimenting.pdf</a><p>[4] <a href="http:&#x2F;&#x2F;www.ibm-1401.info&#x2F;Meta-II-schorre.pdf" rel="nofollow">http:&#x2F;&#x2F;www.ibm-1401.info&#x2F;Meta-II-schorre.pdf</a>

Sorry to be negative and this comment probably doesn&#x27;t belong in a discussion about a specific parsing toolkit but I&#x27;ve become unconvinced that parser generators are useful. My experience is limited to Yacc&#x2F;lex back in the old days (quickly jumped to Bison&#x2F;flex), more recently Antlr and a couple of functional parser combinator libraries. In nearly all case it was to deal with &quot;real world&quot; (i.e. not toy) programming languages.<p>The last time I needed a parser (in Java), I started studying the Antlr docs (it&#x27;s changed quite a bit since I used it last) but became disillusioned quickly with the amount of reading and studying I would have to do to get something working.<p>So I quickly wrote a &quot;hand crafted&quot; tokenizer and recursive descent parser. I found this so satisfying that it made me wonder why I had bothered learning relatively complex tools in the past particularly since I had been exposed to recursive descent parsing as an undergrad.<p>Advantages that pop into my head:<p>- The code was clean, readable and very concise. For debugging, the stacktraces were helpful and I could use my regular debugger&#x2F;IDE to step through the parsing process. The method names in my Parser class mostly matched the names of corresponding grammar rules.<p>- You can code around the theoretical limitations of recursive descent parsing in a very intuitive manner (e.g. &quot;if (tokens.peekAhead(1).getType() == Token.LEFT_BRACE) { parseX(); } else { parseY(); }&quot;). In theory it might seem this would lead to a mess but it actually allows very flexible and natural abstractions.<p>- You have complete control over the building of the AST - the parseX(...) methods can take arguments or the calling parse method can manipulate the returned AST - doing stuff like flattening (normalising) node trees or re-ordering child nodes, etc. The shape of the AST can be independent of the structure of the grammar rules.<p>- It&#x27;s easy to provide helpful error messages and even error recovery without fighting with the toolkit. Better still, you can start with a fairly lazy generic error handler and later, in a natural style, add special cases to make the messages more and more helpful for specific common user mistakes. I sneakily logged all parse failures by users to constantly improve error reporting. After a while the parser seemed almost like an AI when reporting errors.<p>- For parsing expressions, there is a relatively well-known way to deal with operators with different arities and associativity rules (by adding a numeric &quot;context binding strength&quot; parameter to your parseExpr() method) - a quick google provided the template.<p>- The entire parser was self contained in a small number of reasonably compact classes: a Lexer&#x2F;Tokenizer class, a Parser class and a SymbolTable class (and of course a TokenType enum and an ASTNode class). Other developers could grok the code because it was compact and self contained without having to learn a parsing toolkit.<p>- You feel in control; i.e. you can add features to the language and the parser incrementally without fearing that sinking feeling you get when you think you&#x27;re 99% of the way there only to realize that the tool you&#x27;re using makes the last 1% impossible forcing you to rethink&#x2F;rewrite already &quot;banked&quot; functionality.<p>- Zero dependencies and trivial to integrate into the build and test process.<p>edit: paragraphs

<i>In many parser generators (e.g. Yacc and ANTLR), a grammar author can specify the language semantics by including semantic actions inside the grammar. A semantic action is a snippet of code — typically written in a different language —that produces a desired value or effect each time a particular rule is matched.</i><p>Actually, <i>the need for that</i> went away with ANTLR4. The grammar is now all grammar (and lexer) and the semantic actions are listeners or walkers written separately calling or overriding methods and classes generated from the grammar.<p>Much cleaner that way.

IMHO, nothing makes parsing as easy as snobol&#x2F;spitbol. It is almost as old as lisp, and older than C.<p>The question I have as a mere mortal user, who is not interested very much in theory and debates thereon, is <i>what has the fastest performance</i>?<p>If the proponents of post-snobol PEG&#x2F;packrat were to publish a &quot;parsing challenge&quot; and let us replicate&#x2F;create benchmarks of different parsers, including some written in snobol, I would find that very useful in determining whether these other parsers are worth a more serious look.

I have been using Nearley.js [1] and have had a lot of fun using it. I actually quite liked being able to mix in the JS post-processing with the grammar definition in Nearley but could be convinced of the advantages of keeping the separate (checking out your paper on DSLs now).<p>How would you compare it to Nearley? Can Ohm handle ambiguous grammars?<p>[1]: <a href="http:&#x2F;&#x2F;nearley.js.org" rel="nofollow">http:&#x2F;&#x2F;nearley.js.org</a>

Pretty cool for sharing as it can run in the browser.<p>So click on the &#x27;Remix&#x27; button and you can play around with and run the article&#x27;s contents.<p>Is there a way to play with this using Node.js as well?

&quot;Further reading&quot; links at the bottom just link back to the same page.

&gt; The Ohm language is based on parsing expression grammars (PEGs), which are a formal way of describing syntax, similar to regular expressions and context-free grammars<p>Uh-oh. I&#x27;ve voiced my concerns about PEGs (and LL parsers) before, but IMO any grammar &quot;interpreter&quot; that doesn&#x27;t point out the ambiguities in grammar and instead relies on some vague, and ultimately arbitrary, notion of &quot;precedence&quot; (e.g. that rules declared first in the grammar file have priority), isn&#x27;t a good foundation for a serious language (good for throwaway parsers and language experiments, though).

Those popup chats on articles like this gross me out...<p>I&#x27;m just trying to read something, stop phishing for my email address.

Nice