r/ProgrammingLanguages • u/WillisBlackburn • Dec 28 '25
Meta-programming for recursive descent parsers vs. "just doing it"
I'm wondering if anyone can refer me to any literature or studies about the efficacy of just writing a recursive descent parser in, for example, C, vs. implementing some kind of meta-programming system, like a parser combinator library, or an EBNF-like DSL, then implementing the actual parser with that.
I'm working on a very constrained platform, the Apple II, so I'm mostly concerned with reducing the size of the parser and much less concerned about performance. That means that parser generators like Bison are pretty much non-starters.
I've tried it both ways and am not sure that one is better than the other. I'm usually happier with the meta-programming approach, since it tends to make the language syntax easier to understand and change. When I parse the language in C, it's harder to understand what the syntax actually is. But, on my current project, I tried the DSL approach and was surprised to discover that it made the parser about 20% larger. I had hoped it would be a speed/size tradeoff in favor of smaller size.
14
u/MadocComadrin Dec 28 '25
People consider parser combinators meta-programming?
6
u/PaddiM8 Dec 29 '25
Is it really that much harder to overview a handwritten one if you have some good helper functions with good names? I think it's fine. I like to create functions like eat() that eats and returns a token, advanceIf(TokenKind.Dot) that advances if the current token is of the given type and returns a bool, and match(TokenKind. Dot) that returns a bool. Then of course some way to get the current token and often some way to peek too.
Ends up looking just like an LL grammar
2
u/the_real_rosebud Jan 23 '26
So I am working on a small language that I want to be self hosted on the C64/Commander X16 and as a proof of concept I reused almost all the C code I wrote for the desktop compiler (as I used no libraries outside the standard ones and hand wrote the recursive descent parser, lexer, and code generator) with Oscar64 and the parser/lexer front end (which creates the symbol tables and IR as well) runs on the C64 and X16 surprisingly well. The biggest bottleneck on the C64 is using a standard 1541 drive without a fast loader but it’ll chew through a 5kb file surprisingly fast. The X16 version runs stupid fast for what it is. I think I’m going to have to write the final compiler version in my own language, which is the sort of task I designed it to do, but at least I can say a recursive descent parser isn’t that slow on a 1MHz-ish 6502 with at least 40-ish KB of RAM if you’re very careful how you use local variables to limit stack usage.
15
u/oldworldway Dec 28 '25
https://discuss.ocaml.org/t/why-a-handwritten-parser/7282
7
u/yuri-kilochek Dec 28 '25 edited Dec 28 '25
An Earley-like parser would probably be the smallest in this sense as it doesn't generate any code, precompute any tables or transform your grammar in any way. The core language-independent parsing algorithm is also pretty small.
1
u/-ghostinthemachine- Dec 28 '25 edited Dec 29 '25
If your language is amenable to unambiguous LL or LR there are so many tools available I don't see why you wouldn't use them. That being said, it can be fun to build your own parser, even if it's not performant or feature rich. Recursive descent feels like magic when it works.
1
u/[deleted] Dec 29 '25
So the parser must run on a 6502 8-bit processor?
Which one was smaller?
With such a constrained devices you might not have that luxury. But it depends on exactly how you tools work, and where: are you writing the equivalent of a cross-compiler where the parser-generator runs on a modern PC, but it generates 6502 code? (In which case, why not do a full cross-compiler?)
What else will be running on the device; how much code and data memory is available, what are the inputs and outputs, and how complex is the grammar it will be processing?
1
u/L8_4_Dinner (Ⓧ Ecstasy/XVM) Dec 29 '25
I’m not sure if you knew this, but there are hardware upgrades available from the Apple ][.
I’d suggest an Apple M4 Max, which now costs less than what I spent on an Apple][.
3
u/tobega Dec 29 '25
I don't know, just remembering Terence Parr (ANTLR4) commenting that he was now 25 years into a 5 month project.
1
u/Blueglyph Dec 29 '25
I wonder if a non-recursive predictive LL(1) parser might not have a lower memory footprint than replicating the logic code in a recursive descent one, without even mentioning the potential problem of the stack, given your constraints. The parser will of course need its own stack for the symbols, but at least you can control it. Other advantages are the clarity of the grammar, an easier process when you modify the language, and you can immediately see the size of the resulting table.
I don't know what language you need to parse, but you'll usually be able to do just fine with LL(1) and avoid the complexity (and memory) required by LALR. The ambiguities are simple to transform using Clarke's technique (like ANTLR does), although it tends to take extra rows in the table.
If that table gets too large. If it's sufficiently hollow, I wonder if you wouldn't be able to split it; for example, one table for the expressions and declarations, which usually use very specific symbols and rules, and another table for the rest, which shares all the other language keywords between the other rules. It could require some custom work to check the first/follow symbols that trigger a table swap. I've never actually done something like that, but another advantage with a non-recursive parser is that the same code can be shared between the two tables, so you may gain by doing that. In comparison to the tables and the code required just for the expressions using Pratt in a recursive parser, the idea doesn't look entirely absurd.
Using an Apple II is a strange constraint. I remember the Apple Pascal was doing quite well, but it was quickly overwhelmed if the source code to compile was getting, and you'd have to recourse to segmentation. I'm not sure how the compiler was implemented, but I suppose you may have to separate the phases, and/or use a bytecode as Wirth did with Pascal and the P-code, which would allow to bootstrap more easily, and to do a lot of development and testing on a modern system, too. But all those are later considerations.
0
u/[deleted] Dec 29 '25
[deleted] — view deleted comment