21 ms·
I don't think it's true that a lot of people really reinvent recursive descent parsing. Or rather I think a lot more programmers who don't understand language c
by joe_the_user 10y ago
I don't think it's true that a lot of people really reinvent recursive descent parsing. Or rather I think a lot more programmers who don't understand language concepts wind-up writing broken pieces of what could be a recursive descent parser. The programming piece of a recursive descent parser all easy - the tricky parts are having a language spec, operating on the language spec to get the appropriate normal forms (Chomsky and Greibach) and then turning the spec into a parser.
- SamReidHughes 10y agoNo, you don't need to know anything about normal forms to make a good parser.
- mcguire 10y agoHow do you handle those sorts of things?
- SamReidHughes 10y agoLooking these things up, Chomsky normal form is clearly irrelevant, and Greibach normal form forces "progress" to be made. The equivalent of this is, let's say you hand-roll a parser and notice that it's recursing infinitely. Then you realize, "Durr, you bozo, you need to force it to consume something or it'll recurse forever without going anywhere!" And then you solve that problem by having it consume something first. For example, if you're parsing an expression a+b*c+d, and thanks to some naive thinking about left-associative operators, it recursively calls itself without consuming data. So you'll say, okay, first I need to chew off something that consumes data. Then -- what else can you do -- see if you've got an operator, and grow an expression from there. That's a well-contained situation that marches you straight into the right solution.