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

31–40 of 100 posts

Re: Ohm: Parsing Made Easy

#31

Post by e12e »

yxhuvud wrote: post #19
e12e wrote: post #14

Earlier quoted context omitted.

I'm not sure how this can be a critism - you inherently need to decide between left and right recursion - and you can, and it is explicit in the ohm grammar: > 4.1. Left Recursion > Another interesting thing to note about the new definition of "Exp" above is that it is recursive — i.e., its body contains an application of "Exp" itself. More specifically, it is left recursive, meaning that the recursive application is…

> you inherently need to decide between left and right recursion I assume that you mean that you have to do that to get a parser that can parse in linear time? Because it is certainly not true in the general case. But even if you mean that, it is wrong, as there are optimizations to the Earley parser that allows it to be linear on both grammars that contain both left- and right-recursive rules at the same time. (It c…

I meant that if you want your language to be unambiguous in what tree it produces, you have to choose (somehow not be ambiguous). You can be explicit in your grammar and semantics of your grammar, or you could throw away some set of "wrong" trees - or you can be implicit - allow your grammar (under certain semantic assumptions be ambiguous) - and assume left /right.

But if the grammar and semantics allow (force) you to be explicit - I'm not sure I see it as a problem. I certainly see how allowing ambiguity with a warning/error would also be good.

I'm on a cellphone now, and can't see if I can make useful/surprising grammar for the a/aa|a/aaa languages in ohm.

Maybe it's just too minimal an example for me (why not: a|aaa or aa+ - or whatever one is trying to express? Is it, say about the language of pairs or triplets of "a"s?).

Re: Ohm: Parsing Made Easy

#32

Post by bd82 »

pdubroy wrote: post #15
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…

I understand your concern, but can you tell me a bit more about how you think "serious" languages should be developed?

That is a very good question because afaik many(most?) commercial (meaning "serious"...) programing languages are developed using hand crafted recursive decent parsers which usually mean that the first alternative takes precedence and that there are no grammar validations to detect ambiguities at all.

I do agree that grammar validations and ambiguity detection is very important, but even if the semantics of a PEG grammar define that the first matching alternative should be taken, should it be possible to detect some cases such as unreachable alternatives as long as the grammar is structure is known in advance?

Re: Ohm: Parsing Made Easy

#33

Post by pdubroy »

simplify wrote: post #27

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

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

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.

Re: Ohm: Parsing Made Easy

#34

Post by dman »

pdubroy wrote: post #28
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.

Thanks!

Re: Ohm: Parsing Made Easy

#35

Post by yxhuvud »

e12e wrote: post #31
yxhuvud wrote: post #19

Earlier quoted context omitted.

> you inherently need to decide between left and right recursion I assume that you mean that you have to do that to get a parser that can parse in linear time? Because it is certainly not true in the general case. But even if you mean that, it is wrong, as there are optimizations to the Earley parser that allows it to be linear on both grammars that contain both left- and right-recursive rules at the same time. (It c…

I meant that if you want your language to be unambiguous in what tree it produces, you have to choose (somehow not be ambiguous). You can be explicit in your grammar and semantics of your grammar, or you could throw away some set of "wrong" trees - or you can be implicit - allow your grammar (under certain semantic assumptions be ambiguous) - and assume left /right. But if the grammar and semantics allow (force) you…

Well, most parsers have made a global choice of left and right. If the choice is on rule or symbol level, then that would allow a lot more flexibility - probably to the point that it would be powerful enough to parse most things without tedious rewriting of the grammar.

Re: Ohm: Parsing Made Easy

#36

Post by yxhuvud »

chrisseaton wrote: post #26
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…

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

It is a "solution" because it becomes unobvious what language it will parse, not because it doesn't resolve the ambiguity.

Re: Ohm: Parsing Made Easy

#37

Post by tomp »

e12e wrote: post #14
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…

I'm not sure how this can be a critism - you inherently need to decide between left and right recursion - and you can, and it is explicit in the ohm grammar: > 4.1. Left Recursion > Another interesting thing to note about the new definition of "Exp" above is that it is recursive — i.e., its body contains an application of "Exp" itself. More specifically, it is left recursive, meaning that the recursive application is…

A good example of the kind of ambiguitiy I mean is the "dangling else" problem.

Sure, for this example, the solution is easy - just declare whichever you want first! But in more complex grammars, conflicting rules can be declared very far away, and it can be highly non-obvious which should be prioritised, or that there even is a conflict! LR parser generators point out these conflicts (the infamous shift/reduce and reduce/reduce conflicts), which I find very useful.

Re: Ohm: Parsing Made Easy

#38

Post by chrisseaton »

yxhuvud wrote: post #36
chrisseaton wrote: post #26

Earlier quoted context omitted.

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

It is a "solution" because it becomes unobvious what language it will parse, not because it doesn't resolve the ambiguity.

I can't see why that would be the case. When I read the grammar I can see the choice operators and I know they have priority. What is unobvious about that?

Re: Ohm: Parsing Made Easy

#39

Post by bd82 »

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

Re: Ohm: Parsing Made Easy

#40

Post by yxhuvud »

shalabhc wrote: post #30
yxhuvud wrote: post #25

Earlier quoted context omitted.

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

Ah, that is what you mean.

Then the answer is that they are used for different things. PEGs are typically used to parse a string, while regexps are typically used to recognize a pattern.

Where regexps are used for parsing, then ambiguity is definitely a problem that very often will have to be resolved by rewriting the regexp to be less accepting.

Post reply on HN