Hacker News Reader

Comment by pdubroy | Hacker News Reader

Hi HN, I'm a researcher at HARC (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) and Chorus (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/6f55361ad3410f42f67f183...

Happy to answer any questions that you have!

View on HN

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

[2] http://tratt.net/laurie/research/pubs/papers/tratt__direct_l...

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

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 -- 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.

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?)

@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!

Thank you! Be sure to check out the Ohm 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.

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?

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/

    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.

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-bar...

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.

Yes, if I understand correctly, you're describing something like ADsafe (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/...).

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.

asm.js/WebAssembly fit that bill.

Can the generated parser be saved somehow externally so that I don't have to ship the grammar with a project?

Are you guys working on (or have you considered) WASM text format as a target language?

Not yet, but I would love to see someone do that.

Reply on news.ycombinator.com