bd82

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

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)

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/

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

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

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.

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.

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.

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

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.

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.

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.

Perhaps Antlr?

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

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

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

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

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)

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.

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.

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?

Acorn has a plugin system: https://github.com/ternjs/acorn#plugins

But as far as I know Esprima does not: https://github.com/jquery/esprima/issues/1168

I have no idea about Cherow...

beating Acorn & Esprima in raw performance is very very impressive.

But please consider that performance is not the only factor when building parsers.

Extensibility is a major concern. Afaik Babylon (used in babel) is a fork of Acorn partly driven by the need for greater extensibility. https://github.com/babel/babylon

Another example is espree used in ESLint https://github.com/eslint/espree According to their readme.md espree was based on Esprima and is now using Acorn. Specifically for extensibility reasons. https://github.com/eslint/espree/issues/200

I'm less familiar with ometa.

Chevrotain shares two main ideas/concepts with Ohm.

1. Separation of grammar and semantics, but in a less opinionated manner as it does not enforce the separation as Ohm does (it is still possible to embed actions directly in the grammar).

2. Grammar Inheritance.

Although while those ideas are not common they are also not that rare (For example the same concepts exist in Antlr). I think there are three big conceptual differences.

1. In Chevrotain Performance is considered as a major feature. Which results in it being two orders of magnitude faster (in the benchmark linked above)

2. Chevrotain attempts to provides capabilities relevant for writing IDEs, for example automatic error recovery/tolerance and syntactic content assist.

3. Internal vs External DSL -

From an implementation perspective there is a vast difference as Ohm is an external DSL while Chevrotain is an internal DSL. In practical(user) terms this means that you can place a breakpoint directly in a Chevrotain grammar, but you cannot do so in Ohm. Or that you will need a separate editor to edit an Ohm grammar while you can use any JavaScript editor to create a Chevrotain grammar.

It also means that Ohm could be ported to different target runtimes (Like Antlr actually is) while Chevrotain can only run in an ECMAScript engine.

I'm not familiar with Smug, but I would guess that the combinator is implemented using LISP macros which are than expanded into "real" source code (lisp lists) which is evaluated directly and can halt on break points.

In programing languages which do not have true macros The combinator API normally creates a data structure representing the grammar which is than interpreted Which usually makes debugging harder and the parsing slower.

This is a really great way to customize error messages and ensure all error messages have been customized (or at least handled).

I think I'm going to try and implement this in a parsing library I develop. :)

Is this what you are referring to? https://github.com/alexwarth/ometa-js

Is it still relevant if it has not been updated for several years?

Perhaps Ometa's younger's brother (Ohm) should have been referenced instead: https://github.com/harc/ohm Unfortunately while it seems to have some very nice features, particularly the separation of grammar and semantics.

Its performance is underwhelming. See a benchmark I've created of JSON parsers implemented using many parsing libraries.

http://sap.github.io/chevrotain/performance/

On V8 (Chrome 60) It is the slowest by far, in most cases by two orders of magnitude...

I also slightly dislike parser combinators. Mainly because usually you cannot easily debug them by placing a breakpoint.

In the best case scenario the specific parser combinator has good tracing support to enable debugging. However, imho this is still inferior to simple breakpoints and debugging "directly" in one's favorite IDE.

The article mentioned using Parser Combinators as the sweet spot between Hand Written Parsers and Parser Generators.

Another possible sweet spot would using something I call a "Parsing DSL" which is a sort of a cross between a parser combinator and a parser generator.

TLDR: See the JavaScript Parsing DSL library (Chevrotain) I've authored: https://github.com/SAP/chevrotain

Details: A Parsing DSL means using API similar to hand building a parser but without a-lot of the cruft associated with hand building while enjoying higher level abstractions from the Parsing DSL library such as: 1. automatic ambiguity detection. 2. lookahead calculation. 3. Grammar diagrams 4. auto-complete. 5. automatic error recovery 6. and more...

Under V8 (Chrome/Node) this is much faster than any other library tested and even substantially faster than a naive hand built parser. http://sap.github.io/chevrotain/performance/

(Benchmarked using a simple grammar [JSON])

Some more information in this interview: https://jaxenter.com/theia-ide-efftinge-interview-134467.htm...

Makes it much easier to use in continuous integration scenarios.

For example running tests in a browser in your pull request voter.