bd82

6 years agodiscuss

Even the Antlr FAQ mentions that "almost no one uses parser generators to build commercial compilers."

* https://github.com/antlr/antlr4/blob/master/doc/faq/general....

* See: "What do you think are the problems people will try to solve with ANTLR4?" question

I've used several different parser generators in the past. But I've also transitioned to hand-rolled recursive decent parsers, being Lazy I've created a library to assist in hand-rolling a recursive decent parser: https://github.com/SAP/chevrotain

bd82

7 years agodiscuss

Some of the top of my Head:

  - Antlr (https://github.com/antlr/antlr4/blob/master/doc/javascript-target.md)

  - PegJS (https://github.com/pegjs/pegjs)

  - Nearley (https://github.com/kach/nearley)

bd82

7 years agodiscuss

Luckily there are many Parsing Libraries in the JavaScript eco-system, So we won't have to find out if this convoluted approach is worthwhile :)

- https://tomassetti.me/parsing-in-javascript/

bd82

7 years agodiscuss

I develop a parsing library for fun and I don't think that would be an easy or useful interview question.

Maybe it makes sense if you assume the input has already been tokenized so you are not expected to deal with the minutiae of string literal escape sequences and such and can focus on the high level design/flow...

bd82

7 years agodiscuss

You can find it At: https://github.com/SAP/chevrotain

bd82

7 years agodiscuss

I've created a Parsing Toolkit (for JavaScript) which I believe fulfills 7/10 of the requirements described.

Chevrotain - https://github.com/SAP/chevrotain

The list of features can be found here: - https://sap.github.io/chevrotain/docs/features/blazing_fast....

What is interesting imho is that Chevrotain is not a Parser Generator nor a Parser Combinator. It is a tool that makes it easier to craft hand built recursive decent parsers rather than a whole new level of abstraction.

bd82

7 years agodiscuss

I kept putting of switching from Travis to Circle-CI in one of my open source projects, But when I did get around to it the whole thing went pretty smoothly and easily and I regret not doing it earlier.

1.The builds are much faster now. 2. The configuration has virtually no hacks anymore as I'm using Circle-CI own docker images (including browsers). 3. And the UI/UX is superior as well.

bd82

8 years agodiscuss

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.

bd82

8 years agodiscuss

If you are looking for an alternative to standard parser generators you may wish to have a peek at Chevrotain. * https://github.com/SAP/chevrotain

Instead of using an abstraction of a declarative grammar definition and code generation to provide an alternative to writing a parser by hand, Chevrotain simplifies the process of hand crafting a parser.

Meaning no code generation and you can still directly debug the code you have written (unlike most parser combinators).

bd82

8 years agodiscuss

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.

bd82

8 years agodiscuss

Have a look at this: https://tomassetti.me/parsing-in-javascript/#chevrotain

This is Not exactly a parser generator but an internal JavaScript DSL for writing parsers, but it does meet the criteria for a more verbose syntax.

bd82

8 years agodiscuss

Maybe this example will help? https://github.com/SAP/chevrotain/blob/master/examples/gramm...

It is implemented using a parsing library so the lookaheads are automatically performed by the library, but the general pattern is still relevant.

Basically each binary precedence level gets a rule (weakest first) and each of these rules will consume as many operators of the current precedence level as it can.

bd82

9 years agodiscuss

Perhaps Antlr?

bd82

9 years agodiscuss

Incremental parsing is indeed amazing for IDE scenarios. But you still have to parse the entire file at least once.

For example it takes 15 seconds to parse lodash.js with Ohm (on my machine) using the sample EcmaScript grammar. But what happens if my IDE has 200 files and 400KLOC of code?

From my personal experience, if you want high performance you have to treat it as an ongoing feature, this could mean:

  * Inspect each new version for performance regressions.

  * Reinspect previous feature implementations for possible 
    performance optimizations.

  * keep track of underlying performance characteristics of your 
    runtime, for example V8 hidden class changes and other 
    de-optimization causes. These characteristics may (and do!) 
    change over time with newer releases of V8...

It would be interesting to try and optimize Ohm.js I even contributed some optimizations to Nearley.js in the past. But I'm afraid I just don't know when I will get around to trying this with too many projects and ideas competing for my time. :(

bd82

9 years agodiscuss

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

bd82

9 years agodiscuss

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

bd82

9 years agodiscuss

It did not exactly went away.

It is still possible to embed semantics inside an Antlr4 grammar.

For example see the Antlr4 EcmaScript grammar sample: https://github.com/antlr/grammars-v4/tree/master/ecmascript which uses embedded code to solve the RegExp vs division operator ambiguity.

Another scenario when embedding code could be preferred is optimizing for maximum performance as abstractions normally come at a performance overhead.

I do agree that the default approach should be to separate the semantics unless there is a very good reason why not to...

bd82

9 years agodiscuss

One option would be to use a Parser that supports fault tolerance and error recovery.

In hand crafted parsers this error recovery may be added manually (but resulting in a-lot of work...) For example: search for the word "recovery" in the TypeScript parser which is used to provide Language Services for the VSCode IDE. https://github.com/Microsoft/TypeScript/blob/master/src/comp...

Automatic Error Recovery using heuristics can also be implemented by parsing Libraries. In the world of JavaScript I'm familiar with two libraries that support Error Recovery:

Antlr4 - https://github.com/antlr/antlr4

Chevrotain - https://github.com/SAP/chevrotain (disclaimer - I'm the author of Chevrotain)

bd82

9 years agodiscuss

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.

bd82

9 years agodiscuss

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?

Submissions

Show HN: Chevrotain – Parser Building Toolkit for JavaScript

Show HN: Chevrotain – Parser Building Toolkit for JavaScript

Chevrotain – Fault-Tolerant Parser Building Toolkit for JavaScript

Chevrotain – Parser Building Toolkit for JavaScript

Show HN: JavaScript Parsing Libraries Benchmark

Show HN: JavaScript Parsing Libraries Benchmark

Theia – One IDE for Desktop and Cloud

Chrome 59 stable released

Show HN: JavaScript Parsing Libraries Benchmark

Show HN: Chevrotain – Fault-Tolerant JavaScript Parsing DSL

comments