3 ms·

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

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?

zoren 9y ago
I would claim ANTLR is such a tool.
wtetzner 9y ago
> 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?
dukoid 9y ago
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 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).
kmill 9y ago
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.)
meric 9y ago
http://github.com/meric/leftry 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.
tom_mellior 9y ago
> 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-oups.pdf 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 http://gallium.inria.fr/~xleroy/publi/validated-parser.pdf The result is in CompCert: https://github.com/AbsInt/CompCert/tree/master/cparser https://github.com/AbsInt/CompCert/tree/master/cparser

zoren 9y ago

I would claim ANTLR is such a tool.

wtetzner 9y ago

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

dukoid 9y ago

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

kmill 9y ago

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

meric 9y ago

http://github.com/meric/leftry 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.

tom_mellior 9y ago

> 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-oups.pdf 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 http://gallium.inria.fr/~xleroy/publi/validated-parser.pdf The result is in CompCert: https://github.com/AbsInt/CompCert/tree/master/cparser https://github.com/AbsInt/CompCert/tree/master/cparser