21–30 of 50 posts
Parser combinators are less powerful than what parser generators can do, in terms of expressiveness and efficiency. And we've known parser generators since the 70s. So I'm not sure what the point is of the title of the article.
The rest of the paper elaborates on the title.
Parser combinators are less powerful than what parser generators can do, in terms of expressiveness and efficiency. And we've known parser generators since the 70s. So I'm not sure what the point is of the title of the article.
It may be true that parser generators are superior from a technical point of view (I can't comment), but parser combinators sure can be nice to use. I very recently used nom to implement a parser for a structured text format, it feels wonderfully expressive and you can knock together a reasonably sophisticated parser in a matter of hours. Performance-wise, it is zero-copy and chomps through a 100MB file in less than…
Earlier quoted context omitted.
I thought most real world compilers tend to be hand written rather than using a generator? By no means an expert but that's something I've heard and know to be true for many real world compilers.
References: https://stackoverflow.com/questions/6319086/are-gcc-and-clan...
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 m…
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.
Parser combinators are less powerful than what parser generators can do, in terms of expressiveness and efficiency. And we've known parser generators since the 70s. So I'm not sure what the point is of the title of the article.
Earlier quoted context omitted.
(one of the authors here): parser generators are generally good for one thing: parsing programming languages. For more complex formats, where you have to carry state around, or binary formats, they're extremely cumbersome to use. I often meet people that tell me they want the parser generator to end all parsers. But for most real world formats, you'll have to hack around the generator's limitations. Theoretically, pa…
I thought most real world compilers tend to be hand written rather than using a generator? By no means an expert but that's something I've heard and know to be true for many real world compilers.
Using a combinator or generator makes sense when you really care just about getting trees out as fast as possible; e.g. what a command line batch compiler or interpreter does.
Earlier quoted context omitted.
I thought most real world compilers tend to be hand written rather than using a generator? By no means an expert but that's something I've heard and know to be true for many real world compilers.
I suppose that's because they take the standpoint that they have so much testing code available, that any conflicts with the grammar are easily found. However, in general, you can easily shoot yourself in the foot with a handwritten parser, because you can't see the conflicts by looking at the code locally.
Conflicts is generally one of the least interesting problems in writing a parser unless you're designing a new language, and especially when hand writing recursive descent parsers, potential conflicts/ambiguities tend to become obvious quickly.
For prototyping a new language, sure, use a parser generator to test the grammar.
I too fall in the category of loving the idea of parser generator (and having written a few) but always falling back on hand-written parsers because the generators I've seen have all been inadequate. I hope that chances some day.
Earlier quoted context omitted.
(one of the authors here): parser generators are generally good for one thing: parsing programming languages. For more complex formats, where you have to carry state around, or binary formats, they're extremely cumbersome to use. I often meet people that tell me they want the parser generator to end all parsers. But for most real world formats, you'll have to hack around the generator's limitations. Theoretically, pa…
> For more complex formats, where you have to carry state around, or binary formats, they're extremely cumbersome to use. That's not a theoretical issue, but more a practical issue. > you'll have to hack around the generator's limitations You're probably thinking of LALR(1) class generators. But we have GLR parser generators for a long time now, and they are very flexible and have little limitations. See e.g. [1]. [1…
Parser combinators are less powerful than what parser generators can do, in terms of expressiveness and efficiency. And we've known parser generators since the 70s. So I'm not sure what the point is of the title of the article.
That alone pretty much wipes out any remaining advantages of parser generators, in which the "cow" of your rules has been turned into a "hamburger" state machine that is very difficult to follow, usually having very poor debug support compared to the maturity of the rest of the tooling. ("How come if I add a variant to ths rule, I get a reduce/reduce conflict in these five other rules elsewhere? Waaaah ...")
Lest there be any doubt: GCC uses a hand-written recursive descent parser for C++. (Meg and a half of code and increasing.)
That's virtually a proof that just parsing with functional decomposition is good enough for anything.
Another thing is that with functional parsing, you can use the exception handling (or other non-local, dynamic control transfers) of the programming language for recovery and speculative parsing. This parse didn't work? Chuck the whole damn branch of the parse with a dynamic return, and try going down another rabbit hole.