I use recursive descent parsers all the time for small DSL's and for a JIT compiled optimizing production quality compiler. It works great.
Why I write recursive descent parsers, despite their issues (2020)
81–89 of 89 posts
Re: Why I write recursive descent parsers, despite their issues (2020)
#82Earlier quoted context omitted.
Most people aren't writing something as complex as SQLite, but most people aren't writing parsers either. Those writing parsers are disproportionately writing things like programming languages and language servers that are quite complex. SQLite isn't some kind of universal template, I'm not saying people should copy it or that recursive descent is a bag choice. But empirically parser generators are used in real produ…
> Those writing parsers are disproportionately writing things like programming languages and language servers that are quite complex. Sure, but adding the complexity of a parser generator doesn't help with that complexity in most cases. [General purpose] programming languages are a quintessential example. Yes, a compiler or an interpreter is a very complex program. But unless your programming language needs to be par…
I'm not saying everyone or even anyone in particular needs a parser generator. I'm saying real, widely deployed projects - as far as you can get from academic - empirically find it useful.
Creating abstractions does decrease complexity if one (or more) of the following is true:
- The abstraction generates savings in excess of it's own complexity
- The abstraction is shared by enough projects to amortize the cost of writing/maintaining it to a tolerable level
- There are additional benefits like validating your grammars are unambiguous or generating flow charts of your syntax in your documentation, amortizing the cost across different features of the same project
It's up to you as the implementer to weigh the benefits and costs. If you choose to use recursive descent, more power to you. (For what it's worth, I personally use parser combinators to split the difference between writing grammars and hand-rolling parsers. But I've used parser generators before and found them helpful.)
Re: Why I write recursive descent parsers, despite their issues (2020)
#83I wonder who it is that likes other kinds of parser. Over the last ~10 years or so I've read several articles arguing that recursive descent parsers are in fact great on HN. And they seem to be both the easiest to get started with and what almost all production-grade systems use. I've seen very little in the way of anything arguing for any other approaches.
Recursive descent is fine if you trust that you won't write buggy code. If you implement a generator for it (easy enough), this may be a justifiable thing to trust (though this is not a given). I am assuming you're willing to put up with the insanity of grammar rewriting, one way or another. LR however is more powerful, though this mostly matters if you don't have access to automatic grammar rewriting for your LL. Mo…
> LALR(1) is probably fine; I have never encountered a useful language that must resort to LR(1)
An LR(1) parser can have many more states in it's DFA than LALR(1). That was important back in the 1970's when I was fighting for every byte of RAM, but now it's a total non-issue. I don't know why you would bother with LALR(1) now if you had a LR(1) parser generator.
Re: Why I write recursive descent parsers, despite their issues (2020)
#84Earlier quoted context omitted.
Recursive descent is fine if you trust that you won't write buggy code. If you implement a generator for it (easy enough), this may be a justifiable thing to trust (though this is not a given). I am assuming you're willing to put up with the insanity of grammar rewriting, one way or another. LR however is more powerful, though this mostly matters if you don't have access to automatic grammar rewriting for your LL. Mo…
> ambiguities It's important to note that ambiguities are something which exist in service of parser generators and the restricted formal grammars that drive them. They do not actually exist in the language to be parsed (unless that language is not well-specified, but then all bets are off and it is meaningless to speak of parsing), because they can be eliminated by side-conditions. For example, one famous ambiguity…
> It's important to note that ambiguities are something which exist in service of parser generators and the restricted formal grammars that drive them. They do not actually exist in the language to be parsed
Only partially true. How do you define the language to be parsed? It's with a grammar. If the grammar can yield two different parse trees for the same input, it's ambiguous. In LR parlance, if your grammar is ambiguous because of a shift-reduce conflict, it's because you stuffed up your grammar.
That's a real problem. It the difference between parsing "1 + 2 / 3" as "(1 + 2) / 3" and "1 + (2 / 3)". The two interpretations yield very different outcomes. The reason you see so many people here say "use a generated LL or LR parser" is the generator will find and report that mistake. It's a very easy mistake to make, and you won't realise you've made it.
Then there are what LR calls reduce-reduce conflicts. Yes, that may happen because the LR parser can't look far enough ahead. Or, it may again be because you've stuffed you grammar. Or it may be because the language you have in your head really isn't context free. Perl is in the last category. They claim to have got around it by saying its a "do what I mean" language. Fine, but it turns out in some cases what they think a string obviously means doesn't agree with what I thought it obviously meant.
Re: Why I write recursive descent parsers, despite their issues (2020)
#85Earlier quoted context omitted.
> Those writing parsers are disproportionately writing things like programming languages and language servers that are quite complex. Sure, but adding the complexity of a parser generator doesn't help with that complexity in most cases. [General purpose] programming languages are a quintessential example. Yes, a compiler or an interpreter is a very complex program. But unless your programming language needs to be par…
I'm not saying everyone or even anyone in particular needs a parser generator. I'm saying real, widely deployed projects - as far as you can get from academic - empirically find it useful. Creating abstractions does decrease complexity if one (or more) of the following is true: - The abstraction generates savings in excess of it's own complexity - The abstraction is shared by enough projects to amortize the cost of w…
I agree, I just don't understand why you seem to think this is a correction to anything I said.
If your goal is simply to reduce bugs--not something more complex like generating parsers in a bunch of languages--then hand rolling a parser generator and then using it to generate your parser [singular] is not a path to achieving your goals. That's what I said, and that's actually just true, which you probably know.
This is not an invitation to bring up irrelevant, exceptional cases, it's the rule of thumb you should operate on. Put another way, don't add layers when there isn't a reason to do so. If there is a reason to do so, have at it. Obviously.
In a meta sense, it's pretty socially inept to jump in with corrections like this. In a complex field like programming, of course there are exceptions, and it's disrespectful to the group of professionals in the room to assume that they don't know about the exceptions. I'm guilty of this myself: it's because I was brought up being praised for knowing things, so I want to demonstrate that I know things. But as an adult, I had to learn that I'm not the only knowledgeable person in the room, and it's rude to assume that I am.
Re: Why I write recursive descent parsers, despite their issues (2020)
#86Earlier quoted context omitted.
Yeah, let me know when you're writing the next SQLite. For your average parser, you're not writing the SQLite parser, you don't have the SQLite parser's problems, and you don't need SQLite's solutions.
There is a great Steve Yegge post on how useful ad-hoc transformation of source code is: http://steve-yegge.blogspot.com/2007/06/rich-programmer-food... The only time I have used this myself was an expat style transformer for terraform (HCL). We had a lot of terraform and they kept changing the language, so I would build a fixer to make code written for say 0.10 to work with 0.12 and then again for 0.14. It was very…
> The only time I have used this myself was an expat style transformer for terraform (HCL). We had a lot of terraform and they kept changing the language, so I would build a fixer to make code written for say 0.10 to work with 0.12 and then again for 0.14. It was very fun and let us keep updating to newer terraform versions. Pretty simple language except for distinguishing quoted blocks from non-quoted.
I hear stories like this and I just wonder how we got here. Like, did this work provide any monetary value to anyone? It sounds like your team just got way too lost in the abstractions and forgot that they were supposed to make a product that did something, ostensibly something that makes money.
I mean, I guess if you can persuade people to give you money to do something, it's profitable. :shrug:
Re: Why I write recursive descent parsers, despite their issues (2020)
#87Earlier quoted context omitted.
There is a great Steve Yegge post on how useful ad-hoc transformation of source code is: http://steve-yegge.blogspot.com/2007/06/rich-programmer-food... The only time I have used this myself was an expat style transformer for terraform (HCL). We had a lot of terraform and they kept changing the language, so I would build a fixer to make code written for say 0.10 to work with 0.12 and then again for 0.14. It was very…
> The only time I have used this myself was an expat style transformer for terraform (HCL). We had a lot of terraform and they kept changing the language, so I would build a fixer to make code written for say 0.10 to work with 0.12 and then again for 0.14. It was very fun and let us keep updating to newer terraform versions. Pretty simple language except for distinguishing quoted blocks from non-quoted. I hear storie…
Pre terraform it would take a half day to setup I new account, create buckets meeting our policies, replicate to backup buckets, etc etc. with terraform we could do same in thirty minutes so we could service many more development teams with same head count.
This work made it easier to keep terraform in sync with aws and so maintenance (e.g. adding a new policy to existing S3 buckets was just edit the S3 bucket module and re-applying to every account. The parser was way easier than manually editing the files manually (especially since I had so much terraform as a test bed of data).
Re: Why I write recursive descent parsers, despite their issues (2020)
#88Earlier quoted context omitted.
> ambiguities It's important to note that ambiguities are something which exist in service of parser generators and the restricted formal grammars that drive them. They do not actually exist in the language to be parsed (unless that language is not well-specified, but then all bets are off and it is meaningless to speak of parsing), because they can be eliminated by side-conditions. For example, one famous ambiguity…
> It's important to note that ambiguities are something which exist in service of parser generators and the restricted formal grammars that drive them. They do not actually exist in the language to be parsed Only partially true. How do you define the language to be parsed? It's with a grammar. If the grammar can yield two different parse trees for the same input, it's ambiguous. In LR parlance, if your grammar is amb…
> How do you define the language to be parsed? It's with a grammar.
False. This is how you define a language _to a parser generator_, but it is not how humans (and/or developers) define languages to each other.
> you won't realise you've made it
This is literally impossible in a recursive descent parser. I'm not saying getting it wrong is impossible, of course not. But what you literally cannot do (without concerted intentional effort) is make it ambiguous. Your parser will parse one first, or the other first, or either one left-to-right; and you will know which of these it does by reading the code.
Re: Why I write recursive descent parsers, despite their issues (2020)
#89Earlier quoted context omitted.
> The only time I have used this myself was an expat style transformer for terraform (HCL). We had a lot of terraform and they kept changing the language, so I would build a fixer to make code written for say 0.10 to work with 0.12 and then again for 0.14. It was very fun and let us keep updating to newer terraform versions. Pretty simple language except for distinguishing quoted blocks from non-quoted. I hear storie…
Pre terraform it would take a half day to setup I new account, create buckets meeting our policies, replicate to backup buckets, etc etc. with terraform we could do same in thirty minutes so we could service many more development teams with same head count. This work made it easier to keep terraform in sync with aws and so maintenance (e.g. adding a new policy to existing S3 buckets was just edit the S3 bucket module…
Nobody was saying Terraform is worse than configuring servers by hand--I certainly wasn't. Automation here is obviously right. If you're comparing Terraform to no automation at all, of course Terraform comes out ahead, but that's not saying much.
What isn't right is changing the language and policies constantly, and if your editing configs is so difficult that writing a parser to do it was easier, one begins to think that Terraform wasn't the right automation tool.