Hacker News Reader

Comment by Analemma_ | Hacker News Reader

Is it possible to have "parser generators" (not necessarily in the formal sense of the term) that produce recursive descent parsers? Even if mathematically they can't be perfect, could we have "good enough" ones? Nobody uses parser generators because even though P.G.s "work" on the barest level of ingesting source code and spitting an AST, they don't do anything beyond that. For example, trying to get helpful error messages (think: from old GCC to Clang) from a P.G.s output is close So instead everyone writes custom parsers, and that introduces these problems.

Can't we have smarter parser generators that do make debugging nice, but are still formally verified?

View on HN

> trying to get helpful error messages

Menhir is a parser generator that tries to do that: http://gallium.inria.fr/~fpottier/slides/fpottier-2015-11-ou... (Don't get scared by the first slide; the title is in French, the rest is in English.)

> formally verified

Menhir has been used for a formally verified parser for C: http://gallium.inria.fr/~xleroy/publi/validated-parser.pdf

The result is in CompCert: https://github.com/AbsInt/CompCert/tree/master/cparser

http://github.com/meric/leftry

It generates recursive descent parsers, it even allows left-recursive grammars - it will rewrite the grammar on its own and wrangle it back into left-recursive form for your convenience, no need to shuffle a right-recursive AST back into left-recursive form by yourself.

It's a side project so it could use a lot of improvement, especially in the debugging messages side.

But it does prove left-recursive descent grammars can be generated automatically without getting into infinite loop and without hassle of manually reversing right-recursive AST's.

> Is it possible to have "parser generators" (not necessarily in the formal sense of the term) that produce recursive descent parsers?

Isn't that basically what PEG parser generators are?

For my parsing pet project(s), the following structure seems to serve me best:

- Recursive descent parser for statements

- "Canned" configurable expression parser for expressions: https://github.com/stefanhaustein/expressionparser

- Both use a simple regex based generic tokenizer

- In more complex cases, parse the expressions to an unresolved syntax tree first (constructed from the bottom), then resolve the tree in a secondary top-down step (potentially to a linear representation).

Are you just talking about making parser generators for LL(k) grammars?

It's fairly straightforward to make one. One exercise in Wirth's short book Compiler Construction is to make an LL(1) parser generator. You even make it check for ambiguities. (I've even found it useful on a couple occasions.)

I would claim ANTLR is such a tool.

Reply on news.ycombinator.com