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

Owl: Parser generator for visibly pushdown languages

github.com

Post reply on HN
Print view View original

21–30 of 34 posts

Re: Owl: Parser generator for visibly pushdown languages

#21

Post by davidkellis »

bd82 wrote: post #14
davidkellis wrote: post #3

Earlier quoted context omitted.

I'm in the same boat. I've found https://github.com/harc/ohm to be a pretty pleasant grammar and parser to use. Ohm also has a nice interactive editor: https://ohmlang.github.io/editor/

Ohm has several impressive features, such as separation of grammar and semantics and incremental parsing capabilities. The base performance however very low, as in two orders of magnitude lower than most other parsing libraries in JavaScript. See benchmark at: https://sap.github.io/chevrotain/performance/ that I have created.

chevrotain's playground tool - https://sap.github.io/chevrotain/playground/?example=JSON%20... - is sure nice!

What parsing algorithm does chevrotain use under the hood? Does it allow left-recursive and right-recursive productions/rules?

Re: Owl: Parser generator for visibly pushdown languages

#22

Post by jhpriestley »

chrisseaton wrote: post #18
jhpriestley wrote: post #17

Earlier quoted context omitted.

Could you explain in more detail what you mean about LALR error messages? I haven't used the parser generators you mention but I've implemented LALR parsing before, the error reporting situation doesn't seem drastically different from recursive descent to me. You can report the location where the parse failed, what was recognized before that point, what tokens would have been allowed to follow. Is the problem that th…

> You can report the location where the parse failed, what was recognized before that point, what tokens would have been allowed to follow. This is a garbage 'computer says no' kind of error message. It doesn't tell you why those tokens would have been allowed to follow, why it is that those are the only tokens allowed to follow, why the token you used is not one of the allowed one, or what you could have more likely…

What context or data would constitute a helpful error message in your opinion? Do you have an example of a recursive-descent parser that generates particularly good error messages?

Re: Owl: Parser generator for visibly pushdown languages

#23

Post by chrisseaton »

jhpriestley wrote: post #22
chrisseaton wrote: post #18

Earlier quoted context omitted.

> You can report the location where the parse failed, what was recognized before that point, what tokens would have been allowed to follow. This is a garbage 'computer says no' kind of error message. It doesn't tell you why those tokens would have been allowed to follow, why it is that those are the only tokens allowed to follow, why the token you used is not one of the allowed one, or what you could have more likely…

What context or data would constitute a helpful error message in your opinion? Do you have an example of a recursive-descent parser that generates particularly good error messages?

A great example is if you forget to put 'end' at the end of a function at the end of a file in languages that have that.

Your idea of a good parser error message is being told that the end of file was unexpected and being given a list of a hundred possible tokens that could start another statement, including 'end' buried somewhere in the list, because that's what's valid there.

My idea of a good parser error message would be in a recursive descent parser looking for the 'end' token, not seeing it, seeing that it's end of file instead and saying 'missing 'end' or a new statement at end of file'.

Re: Owl: Parser generator for visibly pushdown languages

#24

Post by lihaoyi »

nickpsecurity wrote: post #19
jhpriestley wrote: post #17

Earlier quoted context omitted.

Could you explain in more detail what you mean about LALR error messages? I haven't used the parser generators you mention but I've implemented LALR parsing before, the error reporting situation doesn't seem drastically different from recursive descent to me. You can report the location where the parse failed, what was recognized before that point, what tokens would have been allowed to follow. Is the problem that th…

I'll also add you can use two parsers: one that's super fast on code that's correctly written; if that fails, one that makes error messages easy to handle. sklogic said he used that strategy in his tools for program analysis. The extra code is negligible. I don't know how much extra time or maintenance burden but I figured marginal versus cost of handling errors in first place.

My FastParse (https://www.lihaoyi.com/fastparse/) parser combinator library does this; by default it runs without error logging, just giving you an error position, but if something fails you can ask it to re-do the parse keeping track of additional metadata to give you a nice error message with what tokens could have succeeded and a stack trace telling you why wants those tokens.

Tracing errors slows things down about 2x, which is why it isnt on by default, on the assumption that most parses are successful

Re: Owl: Parser generator for visibly pushdown languages

#25

Post by [deleted] »

ccmcarey wrote: post #2

I've been looking at parser generators recently in an effort to begin writing my own simple interpreted language. My end goal is a self hosted language. My first attempt was writing a recursive descent parser by hand: https://gist.github.com/cmcarey/eee1571721141c356d4f61b453a6... This didn't work so well (badly structured as well as finding out my grammar was ambiguous after I'd written 600 lines of parser code). Lo…

[deleted]

Re: Owl: Parser generator for visibly pushdown languages

#26

Post by dbcurtis »

jhpriestley wrote: post #17
dbcurtis wrote: post #13

Earlier quoted context omitted.

The problem with yacc/bison-style LALR parser generators is that you end up with an LALR parser. Which works great on syntactically correct code, but trying to get a reasonable error message out of one is about as much fun as repeatedly poking yourself in the eye with a sharp stick. Also, by the time you add the empty productions that you want to help with code generation, the grammar gets delicate and brittle. OTOH,…

Could you explain in more detail what you mean about LALR error messages? I haven't used the parser generators you mention but I've implemented LALR parsing before, the error reporting situation doesn't seem drastically different from recursive descent to me. You can report the location where the parse failed, what was recognized before that point, what tokens would have been allowed to follow. Is the problem that th…

A bottom up parser such as LALR knows what it has built successfully, and knows that the next token makes no sense in the current state. So you have stuff in the parse stack that is headed somewhere but you don't know where, and you know you are at the earliest point you can detect a syntax error. Unless you rummage around in the parse stack for clues, there really isn't much you can do to make a good message, and the rummaging is often ad-hoc.

When parsing top-down as in recursive descent, you know what higher level syntactic structure you are in the middle of constructing, and anything successfully parsed so far is probably slotted into the AST in a meaningful way, so you simply have a lot more context to go on when constructing a message, and that context is an intuitive AST walk away.

Re: Owl: Parser generator for visibly pushdown languages

#27

Post by bd82 »

davidkellis wrote: post #21
bd82 wrote: post #14

Earlier quoted context omitted.

Ohm has several impressive features, such as separation of grammar and semantics and incremental parsing capabilities. The base performance however very low, as in two orders of magnitude lower than most other parsing libraries in JavaScript. See benchmark at: https://sap.github.io/chevrotain/performance/ that I have created.

chevrotain's playground tool - https://sap.github.io/chevrotain/playground/?example=JSON%20... - is sure nice! What parsing algorithm does chevrotain use under the hood? Does it allow left-recursive and right-recursive productions/rules?

Thanks.

Chevrotain is an LL(K) Parser library, or more precisely SLL(K), It looks up-to K fixed token ahead to choose the next alternative.

Because it is just a library to assist in hand crafting recursive decent parsers, the same limitations apply, left recursion would lead to an infinite loop...,however left recursion is detected during initialization and an descriptive error is thrown instead.

Right recursion is allowed.

It is possible to resolve more complex ambiguities using back tracking: http://sap.github.io/chevrotain/docs/features/backtracking.h... or other types of custom logic.

However in general, the library does not try to be able to parse all the possible grammars in the world, instead the focus is more on performance, features and ease of development.

Re: Owl: Parser generator for visibly pushdown languages

#28

Post by rstuart4133 »

ccmcarey wrote: post #2

I've been looking at parser generators recently in an effort to begin writing my own simple interpreted language. My end goal is a self hosted language. My first attempt was writing a recursive descent parser by hand: https://gist.github.com/cmcarey/eee1571721141c356d4f61b453a6... This didn't work so well (badly structured as well as finding out my grammar was ambiguous after I'd written 600 lines of parser code). Lo…

If you happy to work with Pycon, the easiest LR(1) generator to use and that generates the fastest Python parsers by far is: http://lrparsing.sourceforge.net/ The documentation is very good and the error messages are (by the standards of for the parsing world) clear.

The point the others have made here about error recover being hard for LR parsers still stands, unfortunately. But that's only an issue if you are doing error recovery. Most scripting languages don't.

Re: Owl: Parser generator for visibly pushdown languages

#29

Post by lemming »

dbcurtis wrote: post #13
ccmcarey wrote: post #2

I've been looking at parser generators recently in an effort to begin writing my own simple interpreted language. My end goal is a self hosted language. My first attempt was writing a recursive descent parser by hand: https://gist.github.com/cmcarey/eee1571721141c356d4f61b453a6... This didn't work so well (badly structured as well as finding out my grammar was ambiguous after I'd written 600 lines of parser code). Lo…

The problem with yacc/bison-style LALR parser generators is that you end up with an LALR parser. Which works great on syntactically correct code, but trying to get a reasonable error message out of one is about as much fun as repeatedly poking yourself in the eye with a sharp stick. Also, by the time you add the empty productions that you want to help with code generation, the grammar gets delicate and brittle. OTOH,…

For a really nice solution to the error message problem, see this recent strangeloop talk: https://www.youtube.com/watch?v=Jes3bD6P0To

Basically it uses the parse tree disambiguation from the GLR parser to look for the most likely mistake the user made - it's very clever.

Re: Owl: Parser generator for visibly pushdown languages

#30

Post by goldfeld »

imoverclocked wrote: post #20

Unfortunate naming. This is not to be confused with OWL or OWL2: https://en.wikipedia.org/wiki/Web_Ontology_Language

Yes, I'm trying to find resources on this lib, which I guess aren't many since it's new and because all results on first page for my query are about the Ontology language, which is frustrating so I agree that the naming was a bit unfortunate.
Post reply on HN