News for hackers. Stuff that matters.
Re:Writing Parsers Like it is 2017 [pdf] by Analemma_ on Wednesday June 28, 2017 @03:52PM (#14657639)
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?

Re:Writing Parsers Like it is 2017 [pdf] by tom_mellior on Thursday June 29, 2017 @04:09AM (#14661576)
> 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

Re:Writing Parsers Like it is 2017 [pdf] by meric on Wednesday June 28, 2017 @09:52PM (#14660169)
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.

Re:Writing Parsers Like it is 2017 [pdf] by wtetzner on Wednesday June 28, 2017 @04:39PM (#14658140)
> 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?

Re:Writing Parsers Like it is 2017 [pdf] by dukoid on Wednesday June 28, 2017 @05:03PM (#14658372)
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).

Re:Writing Parsers Like it is 2017 [pdf] by kmill on Wednesday June 28, 2017 @05:16PM (#14658512)
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.)

Re:Writing Parsers Like it is 2017 [pdf] by zoren on Wednesday June 28, 2017 @03:57PM (#14657692)
I would claim ANTLR is such a tool.