Re:On the Complexity and Performance of Parsing with Derivat...
by joe_the_user on Saturday June 25, 2016 @01:28PM
(#11977111)
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.
Re:On the Complexity and Performance of Parsing with Derivat...
by SamReidHughes on Saturday June 25, 2016 @04:42PM
(#11977899)
No, you don't need to know anything about normal forms to make a good parser.
Re:On the Complexity and Performance of Parsing with Derivat...
by mcguire on Saturday June 25, 2016 @05:15PM
(#11978026)
How do you handle those sorts of things?
Re:On the Complexity and Performance of Parsing with Derivat...
by SamReidHughes on Saturday June 25, 2016 @05:40PM
(#11978123)
Looking 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.
Does recursive-descent count? If so, I've come across material on the Internet suggesting that a simple arithmetic expression parser/evaluator is an assignment in some first and second-year CS courses, often covered at the same time as trees and tree-traversal.
Of course, being taught and doing an assignment on something is not quite the same as really knowing, as according to some sources many of those graduates can barely manage FizzBuzz.
On the other hand, recursive descent seems to be one of those techniques that everyone eventually manages to reinvent even if they've never been taught about it, as long as they're aware of recursion.