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

91–100 of 100 posts

Re: Ohm: Parsing Made Easy

#91

Post by vidarh »

yazaddaruvala wrote: post #80
pdubroy wrote: post #33

Earlier quoted context omitted.

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…

Any thoughts on https://github.com/nikomatsakis/lalrpop , and it's first priority being "Nice error messages"? Sidenote: I created this issue a while ago, but never got a response: https://github.com/nikomatsakis/lalrpop/issues/180

'Nice error messages' is an important goal - it is one of a few things that tends to stop people from using parser generators for 'production' compilers. Parsing itself is the easy bit, and while things like left recursion can make some things a bit easier, the workarounds are so well understood it is not what stops people.

But error handling does.

Re: Ohm: Parsing Made Easy

#92

Post by groovy2shoes »

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…

While PEGs necessarily impose a notion of "precedence" due to their construction, LL parsers don't necessarily impose any such notion. Any precedence that an LL parser might have is a consequence of its implementation. It's also possible to check an LL(1) grammar for ambiguities by computing an LL(1) parsing table and checking that any given (state, input) pair has at most one entry in the table. The process for other sorts of LL parsers is similar.

Re: Ohm: Parsing Made Easy

#93

Post by Sophistifunk »

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…

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.

Re: Ohm: Parsing Made Easy

#94

Post by abecedarius »

danbruc wrote: post #52
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…

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…

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.

Re: Ohm: Parsing Made Easy

#95

Post by Sophistifunk »

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…

It struck me as mostly the point of Ohm. Bring the ideas behind the various OMetas into an environment we can actually use it.

Re: Ohm: Parsing Made Easy

#96

Post by parrt »

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

The unwritten corollary of course is that "almost nobody writes commercial compilers." :) Almost all of us do, however, write parsers for data, config files, languages etc... all the time. I'd personally used ANTLR of course for all my parsing needs beyond the trivial.

Re: Ohm: Parsing Made Easy

#97

Post by kasbah »

I have been using Nearley.js [1] and have had a lot of fun using it. I actually quite liked being able to mix in the JS post-processing with the grammar definition in Nearley but could be convinced of the advantages of keeping the separate (checking out your paper on DSLs now).

How would you compare it to Nearley? Can Ohm handle ambiguous grammars?

[1]: http://nearley.js.org

Re: Ohm: Parsing Made Easy

#98

Post by grandinj »

derriz wrote: post #56

Sorry to be negative and this comment probably doesn't belong in a discussion about a specific parsing toolkit but I've become unconvinced that parser generators are useful. My experience is limited to Yacc/lex back in the old days (quickly jumped to Bison/flex), more recently Antlr and a couple of functional parser combinator libraries. In nearly all case it was to deal with "real world" (i.e. not toy) programming l…

For many of the same reasons H2 (h2database.com) use a recursive descent parser to parse SQL

Re: Ohm: Parsing Made Easy

#99

Post by victorNicollet »

nerdponx wrote: post #71
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…

Is ordered a choice a necessary property for PEG parsing? Maybe PEG parser generators should have an "unordered mode".

In practice, they should distinguish between / (I meant this alternative to be ordered, because I care about something) versus | (no ordering required, because I know only one choice will ever be picked), and come up with a way to determine that a | generates an ambiguity.

Re: Ohm: Parsing Made Easy

#100

Post by beojan »

bd82 wrote: post #75
nerdponx wrote: post #73

Earlier quoted context omitted.

Does Pandoc count? IIRC it implements CommonMark in a PEG.

I don't understand the question. I am not familiar with Haskell but from what I understand Pandoc is a group of hand crafted parsers (readers) for markup formats. How does this relate to a discussion on the relevance of parser generators / libraries? https://github.com/jgm/pandoc/tree/master/src/Text/Pandoc

If you check the Parser.hs file there, Pandoc uses Parsec.
Post reply on HN