5 ms·

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 l

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?

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?