Ohm: Parsing Made Easy • Hacker News Board

Re: Ohm: Parsing Made Easy

#81

Post by beagle3 » Tue, Oct 17, 2017, 7:40 PM UTC

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…

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

Re: Ohm: Parsing Made Easy

#82

Post by pdubroy » Tue, Oct 17, 2017, 7:51 PM UTC

richard_shelton wrote: post #79

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…

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

Re: Ohm: Parsing Made Easy

#83

Post by richard_shelton » Tue, Oct 17, 2017, 8:08 PM UTC

pdubroy wrote: post #82

richard_shelton wrote: post #79

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…

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

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!

Re: Ohm: Parsing Made Easy

#84

Post by cabaalis » Tue, Oct 17, 2017, 8:24 PM UTC

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…

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

Re: Ohm: Parsing Made Easy

#85

Post by pdubroy » Tue, Oct 17, 2017, 9:02 PM UTC

richard_shelton wrote: post #83

pdubroy wrote: post #82

Earlier quoted context omitted.

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

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…

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

Right, we don't support context-sensitive grammars yet. But we'd like to -- we're just trying to figure out how to do it in a way that fits Ohm's design principles. I'm optimistic that we'll be able to do that.

Re: Ohm: Parsing Made Easy

#86

Post by feelin_googley » Tue, Oct 17, 2017, 9:03 PM UTC

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.

Re: Ohm: Parsing Made Easy

#87

Post by tomp » Tue, Oct 17, 2017, 9:15 PM UTC

victorNicollet wrote: post #53

haberman wrote: post #43

Earlier quoted context omitted.

> But it is a solution... the grammar is no longer ambiguous if you define choice as giving priority to one side or the other. Sure it's no longer ambiguous to the computer. But the important question is: is it ambiguous to a human? Take the "dangling else" problem. What does this mean in C? if (a) if (b) f(); else g(); If you defined your grammar with a PEG, the answer is: whichever alternative you put first (if-wit…

Ambiguity of a grammar is rather unrelated to how surprising it can be to a human. Something like TypeScript: var a = { label: f() }; () => { label : f() }; These constructs look similar, but one is an object literal and the other is a block with a useless label. All of this can be implemented as an unambiguous context-free grammar. Relying on grammar ambiguity detection to find constructs surprising to humans is not…

> Relying on grammar ambiguity detection to find constructs surprising to humans is not very effective

Well yeah, obviously, that's like relying on unittests and type system to keep your program bug free... I mean, neither can guarantee your program is going to work, but either failing means that it almost certainly won't work (well).

Re: Ohm: Parsing Made Easy

#88

Post by cwp » Tue, Oct 17, 2017, 9:17 PM UTC

bd82 wrote: post #68

iamleppert wrote: post #66

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…

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.... . (no anchors for direct link).

Yacc/bison seems pretty common for stuff implemented in C.

Re: Ohm: Parsing Made Easy

#89

Post by pdubroy » Tue, Oct 17, 2017, 9:26 PM UTC

BoppreH wrote: post #44

jwiley wrote: post #9

Earlier quoted context omitted.

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

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

Re: Ohm: Parsing Made Easy

#90

Post by tomp » Tue, Oct 17, 2017, 9:27 PM UTC

chrisseaton wrote: post #60

haberman wrote: post #55

Earlier quoted context omitted.

It's very strange that you keep returning to this. "Dangling else" is a problem regardless of how you write down your grammar or implement your parser. It's like sweeping a mound of dirt under the rug and then saying "by definition, there is no dirt on the rug!"

I guess I just can't understand where you are coming from then. Someone said that PEGs don't solve ambiguous grammars. I said that's wrong - they do - they are no longer ambiguous. Now people are arguing about having to understand the grammar and how languages should be designed and things like that? Seems irrelevant to me. I thought there was one precise technical question - do PEGs make solve the problem of ambiguo…

> do PEGs make solve the problem of ambiguous grammars. Yes they do

That's a problem noone ever had.

By this definition, even grammars generated by yacc and Bison (LR parser generators) aren't ambiguous - even if there are conflicts a working parser will be produced. They even resolve conflicts in a "sensible" way - shift/reduce conflicts are resolve in favour of shift (i.e. longest match - like regexes) whereas reduce/reduce conflicts are resolved in favour of the earlier rule (like PEGs). Hell, I even left one shift/reduce conflict unresolved in a parser I wrote a few days ago (amply documented, of course), because I know precisely where the ambiguity, no, confusion stems from, and I decided that rewriting the grammar to resolve the conflict explicitly would be too much work and would make the grammar much less readable.

So I really see no point in PEGs (except possibly ease of use). LR parser generators apply more-or-less the same conflict resolution, except that they will proactively warn you about where your grammar is, or could be, confusing.