Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ohm: Parsing Made Easy

nextjournal.com

Post reply on HN
Print view View original

21–30 of 100 posts

Re: Ohm: Parsing Made Easy

#21

Post by pdubroy »

jwiley wrote: post #9
pdubroy wrote: post #6

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…

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?

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.

Re: Ohm: Parsing Made Easy

#22

Post by zzzcpan »

tomp wrote: post #7

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

It's not hard to point out ambiguities, it's hard to fix them. That's why PEGs are nice, they don't make humans work as much, since fixing ambiguities is just a matter of precedence.

But I don't think the world of context-free grammars even matters that much.

Re: Ohm: Parsing Made Easy

#23

Post by pdubroy »

marknadal wrote: post #13
pdubroy wrote: post #6

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…

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

Re: Ohm: Parsing Made Easy

#24

Post by panic »

zzzcpan wrote: post #22
tomp wrote: post #7

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

It's not hard to point out ambiguities, it's hard to fix them. That's why PEGs are nice, they don't make humans work as much, since fixing ambiguities is just a matter of precedence. But I don't think the world of context-free grammars even matters that much.

Pointing out ambiguities in a context-free grammar is an undecidable problem (http://www.cis.upenn.edu/~jean/gbooks/PCPh04.pdf).

Re: Ohm: Parsing Made Easy

#25

Post by yxhuvud »

shalabhc wrote: post #17
tomp wrote: post #10

Earlier quoted context omitted.

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…

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…

Regarding your regexp question, it depends on what implementation of regexp you use. If you go by the formal definition and the state machine parsers optimized for that, then multiple matches is not problematic for finding the longest match. It can be if using some common extensions though, that change the running time to exponential. See https://blog.codinghorror.com/regex-performance/ for example.

Re: Ohm: Parsing Made Easy

#26

Post by chrisseaton »

tomp wrote: post #10
shalabhc wrote: post #8

Earlier quoted context omitted.

Is this a limitation of the PEG syntax itself? IOW, is it possible to identify ambiguities in grammars defined as PEGs?

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…

> They try to sell this as a "solution" to ambiguous grammars

But it is a solution... the grammar is no longer ambiguous if you define choice as giving priority to one side or the other. There's no need for scare quotes! It is a solution that removes ambiguity. There is no longer any ambiguity, and there's nothing 'vague' at all about a rule as simple and clear as this.

> but they're just ... wrong

You'll have to give a more convincing argument than that if you want to persuade people!

> 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

But if you had this rule, then the code isn't ambiguous any more is it? It has a well-defined way to decide which method to use, which everyone can understand and implement.

Re: Ohm: Parsing Made Easy

#28

Post by pdubroy »

dman wrote: post #12

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.

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

Re: Ohm: Parsing Made Easy

#29

Post by zzzcpan »

panic wrote: post #24
zzzcpan wrote: post #22

Earlier quoted context omitted.

It's not hard to point out ambiguities, it's hard to fix them. That's why PEGs are nice, they don't make humans work as much, since fixing ambiguities is just a matter of precedence. But I don't think the world of context-free grammars even matters that much.

Pointing out ambiguities in a context-free grammar is an undecidable problem ( http://www.cis.upenn.edu/~jean/gbooks/PCPh04.pdf ).

No, that's not what your link proves and not what we are talking about.

Re: Ohm: Parsing Made Easy

#30

Post by shalabhc »

yxhuvud wrote: post #25
shalabhc wrote: post #17

Earlier quoted context omitted.

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…

Regarding your regexp question, it depends on what implementation of regexp you use. If you go by the formal definition and the state machine parsers optimized for that, then multiple matches is not problematic for finding the longest match. It can be if using some common extensions though, that change the running time to exponential. See https://blog.codinghorror.com/regex-performance/ for example.

I'm not talking about performance though. I'm talking about the fact that when given an ambiguous regexp, most engines match it happily and return the longest match, instead of erroring out saying 'ambiguous input provided'. This is not considered problematic in practice (or I don't hear criticisms about this at least).

Contrast with the the criticism of PEGs - that they don't report 'ambiguous input' but just go ahead and match using ordered choice.

Post reply on HN