Glush: A robust parser compiler built using non-deterministic automatons

In my experience, shift/reduce conflicts typically reflect real ambiguities, at least in your initial draft of a grammar. Reporting them at that stage is a good thing; you should be addressing them instead of glossing over them.

There are legitimate reasons to need more power than LALR(1) provides, but careless thinking is more common.

Skipping to "Glush, the algorithm" can be helpful if you already know the history of parsing.

TL;DR: Glush grammars consist of "rules" that are regexes + recursion of rule calls. Compiles to NFAs.

I'm not sure I see the point in declaring precedence levels inside rules -- maybe it's just a preference thing, but I like having operator precedences in a separate section of the grammar. Yacc does this. Megaparsec for Haskell does this.

This reminds me of two things:

1. How syntax highlighting is implemented in Vim and GEdit (which is to say GtkSourceView). See for example how "contexts" can be nested here: https://github.com/rubencaro/gedit_hacks/blob/master/.local/...

2. Kleenex: https://kleenexlang.org - https://github.com/diku-kmc/kleenexlang - a silly example: https://github.com/athas/EggsML/blob/master/concieggs/compil...

I am tempted to classify this as "regex extended with recursion" rather than "an alternative to CFGs", since I cannot decipher from the article the exact expressive power.

Fascinating journey through various parsing techniques, aside from describing glush itelf. bookmarked!

> By "not really sandboxable", what powerful features of jq do you mean?

On close inspection I can't find things as bad as I imagined, but there are still some unexpected barely-documented features like reading files from anywhere on disk[1] as long as they have the right extension, with much wider implications than one might expect at a glance. (Note the while the module path is relative and checked for path traversal, you can just set the search path. Undocumented is that the text needn't even parse as JSON because you can just set the raw flag.) In general, many language features are implemented by exposing a more powerful primitive than necessary to the language and documenting a less powerful wrapper but not the primitive itself; the security implications go more or less unexamined.

There seems to be no particular provision for executing any less than enough to generate the next output, so if you want to set limits on execution you'll have to do that at the process level. This is something you can probably do better in a separate implementation, though.

> I'm not sure what's meant by "expose as a user interface". It's a pretty abstract DSL, so I would certainly only expose it to programmers.

Only trusted users should have access to jq. I would assume that anyone who has access to executing jq code can execute arbitrary code in the interpreter's context. I'm less sure that it's true right now than I was when I made the post above, but it still seems pretty likely.

[1]: https://stedolan.github.io/jq/manual/#importRelativePathStri...;

Error recovery and reporting are for sure the biggest challenge of a production parser. If you work out of band, you can play a lot of tricks in your parser to make it much more effective in handling errors. For example, braces can be matched in many languages without parsing any other constructs in the language, meaning these errors can all be reported and recovered from independent of the rest of the language. Then again, the overloading of as operators and braces in many languages defeats that a bit :)

Hand coding a parser is usually worth it for a moderately popular production language. Parser generators really shine for smaller language efforts that can’t afford the overhead and don’t really care about the niceties of decent error reporting.