9 ms·

Ohm: Parsing Made Easy

248 points by pdubroy 9y ago

chrislloyd 9y ago
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.
disconnected 9y ago
"Further reading" links at the bottom just link back to the same page.
- pdubroy 9y ago
  Thanks. Fixed!
deleted 9y ago
[deleted]
pdubroy 9y ago
Hi HN, I'm a researcher at HARC (https://harc.ycr.org/ https://harc.ycr.org/) and one of the authors of Ohm. We've used it to power several of our programming language investigations, such as Seymour (which was on HN yesterday: https://news.ycombinator.com/item?id=15471954 https://news.ycombinator.com/item?id=15471954) and Chorus (http://www.chorus-home.org/ http://www.chorus-home.org/). If you're interested, here's the grammar for the language used in the Seymour demo: https://github.com/harc/seymour/blob/6f55361ad3410f42f67f183da7b7549418884e50/lang/grammar.js https://github.com/harc/seymour/blob/6f55361ad3410f42f67f183... Happy to answer any questions that you have!
- jwiley 9y ago
  Nice project, thanks for sharing. One interesting application that comes to mind is creating a "safe" subset of Javascript, that could be run in an end-users browser without requiring a sandbox. One definition of safe might be: not allowing access to the DOM or global variables. Is this a reasonable use case? Is Ohm's executing environment appropriate for this usecase?
  - pdubroy 9y ago
    Yes, if I understand correctly, you're describing something like ADsafe (http://www.adsafe.org/ http://www.adsafe.org/). I'm pretty sure you could implement that in Ohm, by extending our ES5 grammar (https://github.com/harc/ohm/blob/master/examples/ecmascript/es5.ohm https://github.com/harc/ohm/blob/master/examples/ecmascript/...). However, Ohm doesn't really have an "executing environment". It's up to Ohm users to define how their language is interpreted or compiled, by writing semantic actions for the grammar rules. See the second half of the article for an example.
  - BoppreH 9y ago
    Javascript is too dynamic to have a safe subset. For example, using only the six characters ()+ []! you can write arbitrary code. The main culprits are the weak typing, permissive attribute access, and large runtime environment with lots of surface area. This is unlikely to be fixable by changing the language grammar. See http://www.jsfuck.com/ http://www.jsfuck.com/ JSFuck is an esoteric and educational programming style based on the atomic parts of JavaScript. It uses only six different characters to write and execute code. It does not depend on a browser, so you can even run it on Node.js.
    - pdubroy 9y ago
      Depending on your definition of "safe", it is indeed possible. See the paper "Preventing Capability Leaks in Secure JavaScript Subsets" for a good analysis: http://www.adambarth.com/papers/2010/finifter-weinberger-barth.pdf http://www.adambarth.com/papers/2010/finifter-weinberger-bar...
    - Sophistifunk 9y ago
      If you simply hand your subset off to the standard runtime yes, but you needn't do that. Once you've parsed it, you could certainly close those doors with a few simple rewrite rules.
  - hackcasual 9y ago
    asm.js/WebAssembly fit that bill.
- marknadal 9y ago
  @pdubroy , wow! This is some really exciting work. I had just looked at JISON but this walk through article really takes the cake at making Ohm look like the better approach. Thank you. Just want to say, this article is probably in the Top 5 coolest things I've seen on HackerNews in the last 7ish years. Can't wait to see/read more about Ohm!
  - pdubroy 9y ago
    Thank you! Be sure to check out the Ohm Editor (https://ohmlang.github.io/editor/ https://ohmlang.github.io/editor/), and if you have any trouble getting started with Ohm, you can ask for help on the mailing list: https://groups.google.com/a/ycr.org/forum/#!forum/ohm https://groups.google.com/a/ycr.org/forum/#!forum/ohm.
- scroot 9y ago
  Are you guys working on (or have you considered) WASM text format as a target language?
  - pdubroy 9y ago
    Not yet, but I would love to see someone do that.
- danbruc 9y ago
  Many PEG-based parser generators do not support left recursion — requiring grammar authors to use repetition or right recursion instead. But left recursion is the most straightforward way to express left associative operators, which is why left recursion is supported by Ohm. Does Ohm have any limitation with regard to left recursion? The last time I checked there was a paper by Warth et al. [1] extending PEG Packrat Parsers to handle left recursion but later a paper by Tratt [2] pointed out a flaw in that algorithm and only managed to fix the problem for a limited subset of grammars. [1] http://www.vpri.org/pdf/tr2007002_packrat.pdf http://www.vpri.org/pdf/tr2007002_packrat.pdf [2] http://tratt.net/laurie/research/pubs/papers/tratt__direct_left_recursive_parsing_expression_grammars.pdf http://tratt.net/laurie/research/pubs/papers/tratt__direct_l...
  - pdubroy 9y ago
    Ohm implements the same algorithm described in [1] -- Alex Warth (the author of that paper) created Ohm. We're understand the complaint in [2], but we strongly disagree with Laurie's claim that these are "incorrect" parses. He proposes a different way of handling left recursion, which is just that -- different. You can find a more thorough discussion here: https://github.com/harc/ohm/issues/55 https://github.com/harc/ohm/issues/55
  - abecedarius 9y ago
    I believe left recursion is a frill, because you don't really miss it when you write a recursive-descent parser. You just write the actions a little bit differently for a left-associative operator than a right-associative one, with a loop instead of recursion. Since PEGs are supposed to be the theory abstracting recursive-descent parsers, I would want semantic actions to be added to the theory in a way that can handle both kinds of operators, instead of complicating the parsing algorithm with left recursion. Here's an example of how that can work: https://github.com/darius/parson/blob/master/eg_calc.py https://github.com/darius/parson/blob/master/eg_calc.py -- the '-' operator associates left, while the '^' op associates to the right. (Like Ohm, my system separated the semantic actions from the grammar: .bind(operator) on line 24. It's older than Ohm, actually, but unfinished and undocumented -- just something I've been using in my own projects.) Of course, another reason to support left recursion is to let you use a grammar someone else has already written with left-recursion baked in, without having to mess with it.
- beagle3 9y ago
  Thanks! As the grammar and the semantic actions are separate, is there any support for languages in which the actual parsing rules depend on earlier "semantics" of the language? This kind of thing is needed IIRC to decide whether the C expression (hello)(world) Is a function call (e.g. following "int hello(int x)") or a conversion, (e.g. following "typedef float hello"); Many languages have these constructs that make a parse ambiguous unless you can look at previous semantics. Also, if I remember correctly, Ometa had a problem with the proof and implementation of left recursive PEG grammars - was this fixed in Ohm? (Or am I misremembering?)
- cabaalis 9y ago
  Can the generated parser be saved somehow externally so that I don't have to ship the grammar with a project?
tomp 9y ago
> 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 Uh-oh. I've voiced my concerns about PEGs (and LL parsers) before, but IMO any grammar "interpreter" that doesn't point out the ambiguities in grammar and instead relies on some vague, and ultimately arbitrary, notion of "precedence" (e.g. that rules declared first in the grammar file have priority), isn't a good foundation for a serious language (good for throwaway parsers and language experiments, though).
- shalabhc 9y ago
  Is this a limitation of the PEG syntax itself? IOW, is it possible to identify ambiguities in grammars defined as PEGs?
  - tomp 9y ago
    Possible? Maybe. But the problem is more that, (according to Wikipedia), the choice operator in PEGs (i.e. e1 | e2) is in fact defined as ordered choice, i.e. it prefers the first alternative. They try to sell this as a "solution" to ambiguous grammars, as an advantage, but they're just ... wrong. It's as if Java, when resolving method overloading, arbitrarily prefered the method that's declared first in the source file, instead of refusing to compile ambiguous code, as it does now.
    - shalabhc 9y ago
      I'm aware of ordered choice in PEGs. I'm not entirely convinced that's a real problem in practice (or am missing some compelling example). E.g. regular expressions can be ambiguous too, but are still used very extensively and people tend to not complain about them. Is longest match - a common resolution to multiple matches in regexps - also problematic? I'm also wondering if this specific complaint wrt ambiguity can be easily addressed by just implementing an analyzer that identifies ambiguities in a PEG grammar by evaluating `|` as alternative choice.
      - 9y ago
jsierles 9y ago
Pretty cool for sharing as it can run in the browser. So click on the 'Remix' button and you can play around with and run the article's contents. Is there a way to play with this using Node.js as well?
dman 9y ago
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.
- pdubroy 9y ago
  You might be interested in Ohm's incremental parsing support. I'll be presenting a paper on this at SPLASH next week: https://ohmlang.github.io/pubs/sle2017/incremental-packrat-parsing.pdf https://ohmlang.github.io/pubs/sle2017/incremental-packrat-p.... In theory, what you're suggesting should be possible to implement with our incremental packrat parsing algorithm. But we haven't tried it yet, so I can't say for sure.
  - dman 9y ago
    Thanks!
- bd82 9y ago
  One option would be to use a Parser that supports fault tolerance and error recovery. In hand crafted parsers this error recovery may be added manually (but resulting in a-lot of work...) For example: search for the word "recovery" in the TypeScript parser which is used to provide Language Services for the VSCode IDE. https://github.com/Microsoft/TypeScript/blob/master/src/compiler/parser.ts https://github.com/Microsoft/TypeScript/blob/master/src/comp... Automatic Error Recovery using heuristics can also be implemented by parsing Libraries. In the world of JavaScript I'm familiar with two libraries that support Error Recovery: Antlr4 - https://github.com/antlr/antlr4 https://github.com/antlr/antlr4 Chevrotain - https://github.com/SAP/chevrotain https://github.com/SAP/chevrotain (disclaimer - I'm the author of Chevrotain)
ohm 9y ago
Nice
wybiral 9y ago
Those popup chats on articles like this gross me out... I'm just trying to read something, stop phishing for my email address.
- kvlr 9y ago
  Sorry about that. We didn't mean to show it to visitors and a bug prevented us from quickly disabling it. We've now removed it completely.
simplify 9y ago
I've had great experience using PEG.js, another PEG-based parser generator. How does Ohm compare?
- pdubroy 9y ago
  It's somewhat similar, but the main difference is that Ohm has a strict separation between syntax and semantics. We think this has several benefits, which we describe a bit here: https://github.com/harc/ohm/blob/master/doc/philosophy.md https://github.com/harc/ohm/blob/master/doc/philosophy.md Another difference is that Ohm grammars can contain left recursion -- both direct and indirect. IMHO this is a pretty big deal, but I know that some people don't agree, and think that avoiding left recursion is not a big problem.
  - yazaddaruvala 9y ago
    Any thoughts on https://github.com/nikomatsakis/lalrpop https://github.com/nikomatsakis/lalrpop, and it's first priority being "Nice error messages"? Sidenote: I created this issue a while ago, but never got a response: https://github.com/nikomatsakis/lalrpop/issues/180 https://github.com/nikomatsakis/lalrpop/issues/180
    - vidarh 9y ago
      'Nice error messages' is an important goal - it is one of a few things that tends to stop people from using parser generators for 'production' compilers. Parsing itself is the easy bit, and while things like left recursion can make some things a bit easier, the workarounds are so well understood it is not what stops people. But error handling does.
bd82 9y ago
Ohm is very impressive. Specifically: 1. The separation of Grammar and Semantics. 2. Handling left recursion in a top down (peg) parser. 3. Incremental parsing. I think that the one feature missing to make it applicable for more than rapid prototyping and teaching purposes is performance. In this benchmark I've authored: http://sap.github.io/chevrotain/performance/ http://sap.github.io/chevrotain/performance/ Which uses the simple JSON grammar it is about two orders of magnitudes slower than most other parsing libraries in JavaScript. So I am sure there is a great deal of room for optimizations.
- pdubroy 9y ago
  Thanks! Yes, we are aware that Ohm's batch parsing performance is not great. In practice, it has been fast enough for our uses -- especially since we implemented incremental parsing. With incremental parsing, Ohm's ES5 parser can be as fast as hand-optimized parsers like Acorn. But you're right, there is definitely room for improvement. So far, we have been much more concerned with making Ohm easy to learn and pleasant to use. I would certainly be happy to have contributors who are interested in improving our batch performance.
  - bd82 9y ago
    Incremental parsing is indeed amazing for IDE scenarios. But you still have to parse the entire file at least once. For example it takes 15 seconds to parse lodash.js with Ohm (on my machine) using the sample EcmaScript grammar. But what happens if my IDE has 200 files and 400KLOC of code? From my personal experience, if you want high performance you have to treat it as an ongoing feature, this could mean: * Inspect each new version for performance regressions. * Reinspect previous feature implementations for possible performance optimizations. * keep track of underlying performance characteristics of your runtime, for example V8 hidden class changes and other de-optimization causes. These characteristics may (and do!) change over time with newer releases of V8... It would be interesting to try and optimize Ohm.js I even contributed some optimizations to Nearley.js in the past. But I'm afraid I just don't know when I will get around to trying this with too many projects and ideas competing for my time. :(
CalChris 9y ago
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. Actually, the need for that 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. Much cleaner that way.
- bd82 9y ago
  It did not exactly went away. It is still possible to embed semantics inside an Antlr4 grammar. For example see the Antlr4 EcmaScript grammar sample: https://github.com/antlr/grammars-v4/tree/master/ecmascript https://github.com/antlr/grammars-v4/tree/master/ecmascript which uses embedded code to solve the RegExp vs division operator ambiguity. Another scenario when embedding code could be preferred is optimizing for maximum performance as abstractions normally come at a performance overhead. I do agree that the default approach should be to separate the semantics unless there is a very good reason why not to...
  - CalChris 9y ago
    I stand corrected. I rewrote my grammar with ANTLR4 and gutted all the embedded semantics. That was a good day. I'm going to hit reply now and then I'm going to take out my personal neuralyzer and forget that I ever found out that you can still embed.
derriz 9y ago
Sorry to be negative and this comment probably doesn't belong in a discussion about a specific parsing toolkit but I've become unconvinced that parser generators are useful. My experience is limited to Yacc/lex back in the old days (quickly jumped to Bison/flex), more recently Antlr and a couple of functional parser combinator libraries. In nearly all case it was to deal with "real world" (i.e. not toy) programming languages. The last time I needed a parser (in Java), I started studying the Antlr docs (it'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. So I quickly wrote a "hand crafted" 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. Advantages that pop into my head: - The code was clean, readable and very concise. For debugging, the stacktraces were helpful and I could use my regular debugger/IDE to step through the parsing process. The method names in my Parser class mostly matched the names of corresponding grammar rules. - You can code around the theoretical limitations of recursive descent parsing in a very intuitive manner (e.g. "if (tokens.peekAhead(1).getType() == Token.LEFT_BRACE) { parseX(); } else { parseY(); }"). In theory it might seem this would lead to a mess but it actually allows very flexible and natural abstractions. - 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. - It'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. - For parsing expressions, there is a relatively well-known way to deal with operators with different arities and associativity rules (by adding a numeric "context binding strength" parameter to your parseExpr() method) - a quick google provided the template. - The entire parser was self contained in a small number of reasonably compact classes: a Lexer/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. - 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're 99% of the way there only to realize that the tool you're using makes the last 1% impossible forcing you to rethink/rewrite already "banked" functionality. - Zero dependencies and trivial to integrate into the build and test process. edit: paragraphs
kvlr 9y ago
Hey, I’m one of the founders of Nextjournal, the coding, writing and publishing platform this article was written in. This probably isn’t obvious: you can get a copy of the article and play with it if you click remix and sign in/up. There’s some more context about what we’re trying to build and why in our launch post https://medium.com/nextjournal/launch-nextjournal-public-beta-for-open-research-a55d15bfa95f https://medium.com/nextjournal/launch-nextjournal-public-bet...
iamleppert 9y ago
I've really tried to get on with parser generators, but I've found they are hard to use, hard to debug and the languages/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've found its better to simply use regular expressions to do matching and a functional language that can build up a data structure recursively. Another problem is a lot of them resort to clunky code generation from the grammar file, and when something goes wrong you're not debugging the grammar per se, you are stepping through a bunch of machine generated code that you didn'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. Also when runtime parsing errors do happen, often the incorrect line/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.
- bd82 9y ago
  Even the creator of Antlr (Terence Parr) Said: "In my experience, almost no one uses parser generators to build commercial compilers." https://github.com/antlr/antlr4/blob/master/doc/faq/general... https://github.com/antlr/antlr4/blob/master/doc/faq/general..... (no anchors for direct link).
  - nerdponx 9y ago
    Does Pandoc count? IIRC it implements CommonMark in a PEG.
    - bd82 9y ago
      I don't understand the question. I am not familiar with Haskell but from what I understand Pandoc is a group of hand crafted parsers (readers) for markup formats. How does this relate to a discussion on the relevance of parser generators / libraries? https://github.com/jgm/pandoc/tree/master/src/Text/Pandoc https://github.com/jgm/pandoc/tree/master/src/Text/Pandoc
richard_shelton 9y ago
I really liked what was done in STEPS project. I learned a lot from their repors. For example, this Ian Piumarta's paper is absolutely beautiful [1]. I also spent a lot of time learning oMeta [3] system by Alessandro Warth. And, honestly, now I see nothing really new in Ohm. Basically, it's just some tweaking of the same tech. Moreover, Ohm was made for isolated parsing task. For me it'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'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'm really curious to know why the authors decided this time to limit themselves by only parsing. [1] http://www.vpri.org/pdf/tr2010003_PEG.pdf http://www.vpri.org/pdf/tr2010003_PEG.pdf [2] https://en.wikipedia.org/wiki/List_of_program_transformation_systems https://en.wikipedia.org/wiki/List_of_program_transformation... [3] http://www.vpri.org/pdf/tr2008003_experimenting.pdf http://www.vpri.org/pdf/tr2008003_experimenting.pdf [4] http://www.ibm-1401.info/Meta-II-schorre.pdf http://www.ibm-1401.info/Meta-II-schorre.pdf
- pdubroy 9y ago
  Ohm is not really "just" a parser generator -- but that's the easiest way to describe it. The big idea in Ohm is its modular semantic actions. You can read more about the design -- and why we think it's interesting -- in our DLS paper: https://ohmlang.github.io/pubs/dls2016/modular-semantic-actions.pdf https://ohmlang.github.io/pubs/dls2016/modular-semantic-acti...
  - richard_shelton 9y ago
    Thank you for the answer! I understand that separation of the grammar and semantics has its benefits. You can use the same grammar description with different semantic rules sets etc. It's, indeed, a clean and interesting approach. But, as I understand, Ohm still has no support for context-sensitive grammars, which is more important to have in many cases, than proper left recursion handling. And oMeta had another nice feature: meta-rules (higher-order rules) which is absent in Ohm, if I understand correctly. Ohm tries to be very user-friendly, but at the price of droping the functionality. So in this case Ohm is not a modern replacement for oMeta (which had the AST transforming features -- very important for making compilers!). I'm not trying to be negative and I really wish a big success to your team!
feelin_googley 9y ago
IMHO, nothing makes parsing as easy as snobol/spitbol. It is almost as old as lisp, and older than C. The question I have as a mere mortal user, who is not interested very much in theory and debates thereon, is what has the fastest performance? If the proponents of post-snobol PEG/packrat were to publish a "parsing challenge" and let us replicate/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.
kasbah 9y ago
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). How would you compare it to Nearley? Can Ohm handle ambiguous grammars? [1]: http://nearley.js.org http://nearley.js.org

248 points by pdubroy 9y ago

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.

disconnected 9y ago

"Further reading" links at the bottom just link back to the same page.

pdubroy 9y ago
Thanks. Fixed!

deleted 9y ago

[deleted]

pdubroy 9y ago

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

jwiley 9y ago
Nice project, thanks for sharing. One interesting application that comes to mind is creating a "safe" subset of Javascript, that could be run in an end-users browser without requiring a sandbox. One definition of safe might be: not allowing access to the DOM or global variables. Is this a reasonable use case? Is Ohm's executing environment appropriate for this usecase?
- pdubroy 9y ago
  Yes, if I understand correctly, you're describing something like ADsafe (http://www.adsafe.org/ http://www.adsafe.org/). I'm pretty sure you could implement that in Ohm, by extending our ES5 grammar (https://github.com/harc/ohm/blob/master/examples/ecmascript/es5.ohm https://github.com/harc/ohm/blob/master/examples/ecmascript/...). However, Ohm doesn't really have an "executing environment". It's up to Ohm users to define how their language is interpreted or compiled, by writing semantic actions for the grammar rules. See the second half of the article for an example.
- BoppreH 9y ago
  Javascript is too dynamic to have a safe subset. For example, using only the six characters ()+ []! you can write arbitrary code. The main culprits are the weak typing, permissive attribute access, and large runtime environment with lots of surface area. This is unlikely to be fixable by changing the language grammar. See http://www.jsfuck.com/ http://www.jsfuck.com/ JSFuck is an esoteric and educational programming style based on the atomic parts of JavaScript. It uses only six different characters to write and execute code. It does not depend on a browser, so you can even run it on Node.js.
  - pdubroy 9y ago
    Depending on your definition of "safe", it is indeed possible. See the paper "Preventing Capability Leaks in Secure JavaScript Subsets" for a good analysis: http://www.adambarth.com/papers/2010/finifter-weinberger-barth.pdf http://www.adambarth.com/papers/2010/finifter-weinberger-bar...
  - Sophistifunk 9y ago
    If you simply hand your subset off to the standard runtime yes, but you needn't do that. Once you've parsed it, you could certainly close those doors with a few simple rewrite rules.
- hackcasual 9y ago
  asm.js/WebAssembly fit that bill.
marknadal 9y ago
@pdubroy , wow! This is some really exciting work. I had just looked at JISON but this walk through article really takes the cake at making Ohm look like the better approach. Thank you. Just want to say, this article is probably in the Top 5 coolest things I've seen on HackerNews in the last 7ish years. Can't wait to see/read more about Ohm!
- pdubroy 9y ago
  Thank you! Be sure to check out the Ohm Editor (https://ohmlang.github.io/editor/ https://ohmlang.github.io/editor/), and if you have any trouble getting started with Ohm, you can ask for help on the mailing list: https://groups.google.com/a/ycr.org/forum/#!forum/ohm https://groups.google.com/a/ycr.org/forum/#!forum/ohm.
scroot 9y ago
Are you guys working on (or have you considered) WASM text format as a target language?
- pdubroy 9y ago
  Not yet, but I would love to see someone do that.
danbruc 9y ago
Many PEG-based parser generators do not support left recursion — requiring grammar authors to use repetition or right recursion instead. But left recursion is the most straightforward way to express left associative operators, which is why left recursion is supported by Ohm. Does Ohm have any limitation with regard to left recursion? The last time I checked there was a paper by Warth et al. [1] extending PEG Packrat Parsers to handle left recursion but later a paper by Tratt [2] pointed out a flaw in that algorithm and only managed to fix the problem for a limited subset of grammars. [1] http://www.vpri.org/pdf/tr2007002_packrat.pdf http://www.vpri.org/pdf/tr2007002_packrat.pdf [2] http://tratt.net/laurie/research/pubs/papers/tratt__direct_left_recursive_parsing_expression_grammars.pdf http://tratt.net/laurie/research/pubs/papers/tratt__direct_l...
- pdubroy 9y ago
  Ohm implements the same algorithm described in [1] -- Alex Warth (the author of that paper) created Ohm. We're understand the complaint in [2], but we strongly disagree with Laurie's claim that these are "incorrect" parses. He proposes a different way of handling left recursion, which is just that -- different. You can find a more thorough discussion here: https://github.com/harc/ohm/issues/55 https://github.com/harc/ohm/issues/55
- abecedarius 9y ago
  I believe left recursion is a frill, because you don't really miss it when you write a recursive-descent parser. You just write the actions a little bit differently for a left-associative operator than a right-associative one, with a loop instead of recursion. Since PEGs are supposed to be the theory abstracting recursive-descent parsers, I would want semantic actions to be added to the theory in a way that can handle both kinds of operators, instead of complicating the parsing algorithm with left recursion. Here's an example of how that can work: https://github.com/darius/parson/blob/master/eg_calc.py https://github.com/darius/parson/blob/master/eg_calc.py -- the '-' operator associates left, while the '^' op associates to the right. (Like Ohm, my system separated the semantic actions from the grammar: .bind(operator) on line 24. It's older than Ohm, actually, but unfinished and undocumented -- just something I've been using in my own projects.) Of course, another reason to support left recursion is to let you use a grammar someone else has already written with left-recursion baked in, without having to mess with it.
beagle3 9y ago
Thanks! As the grammar and the semantic actions are separate, is there any support for languages in which the actual parsing rules depend on earlier "semantics" of the language? This kind of thing is needed IIRC to decide whether the C expression (hello)(world) Is a function call (e.g. following "int hello(int x)") or a conversion, (e.g. following "typedef float hello"); Many languages have these constructs that make a parse ambiguous unless you can look at previous semantics. Also, if I remember correctly, Ometa had a problem with the proof and implementation of left recursive PEG grammars - was this fixed in Ohm? (Or am I misremembering?)
cabaalis 9y ago
Can the generated parser be saved somehow externally so that I don't have to ship the grammar with a project?

tomp 9y ago

> 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 Uh-oh. I've voiced my concerns about PEGs (and LL parsers) before, but IMO any grammar "interpreter" that doesn't point out the ambiguities in grammar and instead relies on some vague, and ultimately arbitrary, notion of "precedence" (e.g. that rules declared first in the grammar file have priority), isn't a good foundation for a serious language (good for throwaway parsers and language experiments, though).

shalabhc 9y ago
Is this a limitation of the PEG syntax itself? IOW, is it possible to identify ambiguities in grammars defined as PEGs?
- tomp 9y ago
  Possible? Maybe. But the problem is more that, (according to Wikipedia), the choice operator in PEGs (i.e. e1 | e2) is in fact defined as ordered choice, i.e. it prefers the first alternative. They try to sell this as a "solution" to ambiguous grammars, as an advantage, but they're just ... wrong. It's as if Java, when resolving method overloading, arbitrarily prefered the method that's declared first in the source file, instead of refusing to compile ambiguous code, as it does now.
  - shalabhc 9y ago
    I'm aware of ordered choice in PEGs. I'm not entirely convinced that's a real problem in practice (or am missing some compelling example). E.g. regular expressions can be ambiguous too, but are still used very extensively and people tend to not complain about them. Is longest match - a common resolution to multiple matches in regexps - also problematic? I'm also wondering if this specific complaint wrt ambiguity can be easily addressed by just implementing an analyzer that identifies ambiguities in a PEG grammar by evaluating `|` as alternative choice.
    - 9y ago

jsierles 9y ago

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

dman 9y ago

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.

pdubroy 9y ago
You might be interested in Ohm's incremental parsing support. I'll be presenting a paper on this at SPLASH next week: https://ohmlang.github.io/pubs/sle2017/incremental-packrat-parsing.pdf https://ohmlang.github.io/pubs/sle2017/incremental-packrat-p.... In theory, what you're suggesting should be possible to implement with our incremental packrat parsing algorithm. But we haven't tried it yet, so I can't say for sure.
- dman 9y ago
  Thanks!
bd82 9y ago
One option would be to use a Parser that supports fault tolerance and error recovery. In hand crafted parsers this error recovery may be added manually (but resulting in a-lot of work...) For example: search for the word "recovery" in the TypeScript parser which is used to provide Language Services for the VSCode IDE. https://github.com/Microsoft/TypeScript/blob/master/src/compiler/parser.ts https://github.com/Microsoft/TypeScript/blob/master/src/comp... Automatic Error Recovery using heuristics can also be implemented by parsing Libraries. In the world of JavaScript I'm familiar with two libraries that support Error Recovery: Antlr4 - https://github.com/antlr/antlr4 https://github.com/antlr/antlr4 Chevrotain - https://github.com/SAP/chevrotain https://github.com/SAP/chevrotain (disclaimer - I'm the author of Chevrotain)

ohm 9y ago

Nice

wybiral 9y ago

Those popup chats on articles like this gross me out... I'm just trying to read something, stop phishing for my email address.

kvlr 9y ago
Sorry about that. We didn't mean to show it to visitors and a bug prevented us from quickly disabling it. We've now removed it completely.

simplify 9y ago

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

pdubroy 9y ago
It's somewhat similar, but the main difference is that Ohm has a strict separation between syntax and semantics. We think this has several benefits, which we describe a bit here: https://github.com/harc/ohm/blob/master/doc/philosophy.md https://github.com/harc/ohm/blob/master/doc/philosophy.md Another difference is that Ohm grammars can contain left recursion -- both direct and indirect. IMHO this is a pretty big deal, but I know that some people don't agree, and think that avoiding left recursion is not a big problem.
- yazaddaruvala 9y ago
  Any thoughts on https://github.com/nikomatsakis/lalrpop https://github.com/nikomatsakis/lalrpop, and it's first priority being "Nice error messages"? Sidenote: I created this issue a while ago, but never got a response: https://github.com/nikomatsakis/lalrpop/issues/180 https://github.com/nikomatsakis/lalrpop/issues/180
  - vidarh 9y ago
    'Nice error messages' is an important goal - it is one of a few things that tends to stop people from using parser generators for 'production' compilers. Parsing itself is the easy bit, and while things like left recursion can make some things a bit easier, the workarounds are so well understood it is not what stops people. But error handling does.

bd82 9y ago

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

pdubroy 9y ago
Thanks! Yes, we are aware that Ohm's batch parsing performance is not great. In practice, it has been fast enough for our uses -- especially since we implemented incremental parsing. With incremental parsing, Ohm's ES5 parser can be as fast as hand-optimized parsers like Acorn. But you're right, there is definitely room for improvement. So far, we have been much more concerned with making Ohm easy to learn and pleasant to use. I would certainly be happy to have contributors who are interested in improving our batch performance.
- bd82 9y ago
  Incremental parsing is indeed amazing for IDE scenarios. But you still have to parse the entire file at least once. For example it takes 15 seconds to parse lodash.js with Ohm (on my machine) using the sample EcmaScript grammar. But what happens if my IDE has 200 files and 400KLOC of code? From my personal experience, if you want high performance you have to treat it as an ongoing feature, this could mean: * Inspect each new version for performance regressions. * Reinspect previous feature implementations for possible performance optimizations. * keep track of underlying performance characteristics of your runtime, for example V8 hidden class changes and other de-optimization causes. These characteristics may (and do!) change over time with newer releases of V8... It would be interesting to try and optimize Ohm.js I even contributed some optimizations to Nearley.js in the past. But I'm afraid I just don't know when I will get around to trying this with too many projects and ideas competing for my time. :(

CalChris 9y ago

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. Actually, the need for that 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. Much cleaner that way.

bd82 9y ago
It did not exactly went away. It is still possible to embed semantics inside an Antlr4 grammar. For example see the Antlr4 EcmaScript grammar sample: https://github.com/antlr/grammars-v4/tree/master/ecmascript https://github.com/antlr/grammars-v4/tree/master/ecmascript which uses embedded code to solve the RegExp vs division operator ambiguity. Another scenario when embedding code could be preferred is optimizing for maximum performance as abstractions normally come at a performance overhead. I do agree that the default approach should be to separate the semantics unless there is a very good reason why not to...
- CalChris 9y ago
  I stand corrected. I rewrote my grammar with ANTLR4 and gutted all the embedded semantics. That was a good day. I'm going to hit reply now and then I'm going to take out my personal neuralyzer and forget that I ever found out that you can still embed.

derriz 9y ago

Sorry to be negative and this comment probably doesn't belong in a discussion about a specific parsing toolkit but I've become unconvinced that parser generators are useful. My experience is limited to Yacc/lex back in the old days (quickly jumped to Bison/flex), more recently Antlr and a couple of functional parser combinator libraries. In nearly all case it was to deal with "real world" (i.e. not toy) programming languages. The last time I needed a parser (in Java), I started studying the Antlr docs (it'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. So I quickly wrote a "hand crafted" 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. Advantages that pop into my head: - The code was clean, readable and very concise. For debugging, the stacktraces were helpful and I could use my regular debugger/IDE to step through the parsing process. The method names in my Parser class mostly matched the names of corresponding grammar rules. - You can code around the theoretical limitations of recursive descent parsing in a very intuitive manner (e.g. "if (tokens.peekAhead(1).getType() == Token.LEFT_BRACE) { parseX(); } else { parseY(); }"). In theory it might seem this would lead to a mess but it actually allows very flexible and natural abstractions. - 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. - It'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. - For parsing expressions, there is a relatively well-known way to deal with operators with different arities and associativity rules (by adding a numeric "context binding strength" parameter to your parseExpr() method) - a quick google provided the template. - The entire parser was self contained in a small number of reasonably compact classes: a Lexer/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. - 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're 99% of the way there only to realize that the tool you're using makes the last 1% impossible forcing you to rethink/rewrite already "banked" functionality. - Zero dependencies and trivial to integrate into the build and test process. edit: paragraphs

kvlr 9y ago

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

iamleppert 9y ago

I've really tried to get on with parser generators, but I've found they are hard to use, hard to debug and the languages/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've found its better to simply use regular expressions to do matching and a functional language that can build up a data structure recursively. Another problem is a lot of them resort to clunky code generation from the grammar file, and when something goes wrong you're not debugging the grammar per se, you are stepping through a bunch of machine generated code that you didn'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. Also when runtime parsing errors do happen, often the incorrect line/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.

bd82 9y ago
Even the creator of Antlr (Terence Parr) Said: "In my experience, almost no one uses parser generators to build commercial compilers." https://github.com/antlr/antlr4/blob/master/doc/faq/general... https://github.com/antlr/antlr4/blob/master/doc/faq/general..... (no anchors for direct link).
- nerdponx 9y ago
  Does Pandoc count? IIRC it implements CommonMark in a PEG.
  - bd82 9y ago
    I don't understand the question. I am not familiar with Haskell but from what I understand Pandoc is a group of hand crafted parsers (readers) for markup formats. How does this relate to a discussion on the relevance of parser generators / libraries? https://github.com/jgm/pandoc/tree/master/src/Text/Pandoc https://github.com/jgm/pandoc/tree/master/src/Text/Pandoc

richard_shelton 9y ago

I really liked what was done in STEPS project. I learned a lot from their repors. For example, this Ian Piumarta's paper is absolutely beautiful [1]. I also spent a lot of time learning oMeta [3] system by Alessandro Warth. And, honestly, now I see nothing really new in Ohm. Basically, it's just some tweaking of the same tech. Moreover, Ohm was made for isolated parsing task. For me it'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'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'm really curious to know why the authors decided this time to limit themselves by only parsing. [1] http://www.vpri.org/pdf/tr2010003_PEG.pdf http://www.vpri.org/pdf/tr2010003_PEG.pdf [2] https://en.wikipedia.org/wiki/List_of_program_transformation_systems https://en.wikipedia.org/wiki/List_of_program_transformation... [3] http://www.vpri.org/pdf/tr2008003_experimenting.pdf http://www.vpri.org/pdf/tr2008003_experimenting.pdf [4] http://www.ibm-1401.info/Meta-II-schorre.pdf http://www.ibm-1401.info/Meta-II-schorre.pdf

pdubroy 9y ago
Ohm is not really "just" a parser generator -- but that's the easiest way to describe it. The big idea in Ohm is its modular semantic actions. You can read more about the design -- and why we think it's interesting -- in our DLS paper: https://ohmlang.github.io/pubs/dls2016/modular-semantic-actions.pdf https://ohmlang.github.io/pubs/dls2016/modular-semantic-acti...
- richard_shelton 9y ago
  Thank you for the answer! I understand that separation of the grammar and semantics has its benefits. You can use the same grammar description with different semantic rules sets etc. It's, indeed, a clean and interesting approach. But, as I understand, Ohm still has no support for context-sensitive grammars, which is more important to have in many cases, than proper left recursion handling. And oMeta had another nice feature: meta-rules (higher-order rules) which is absent in Ohm, if I understand correctly. Ohm tries to be very user-friendly, but at the price of droping the functionality. So in this case Ohm is not a modern replacement for oMeta (which had the AST transforming features -- very important for making compilers!). I'm not trying to be negative and I really wish a big success to your team!

feelin_googley 9y ago

IMHO, nothing makes parsing as easy as snobol/spitbol. It is almost as old as lisp, and older than C. The question I have as a mere mortal user, who is not interested very much in theory and debates thereon, is what has the fastest performance? If the proponents of post-snobol PEG/packrat were to publish a "parsing challenge" and let us replicate/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.

kasbah 9y ago

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). How would you compare it to Nearley? Can Ohm handle ambiguous grammars? [1]: http://nearley.js.org http://nearley.js.org