4 ms·
It's commonplace, and one of a few very closely related algorithms (Pratt/TDOP, precedence climbing, shunting yard, etc.) that I guess you can call "traditional
by vidarh 3y ago
It's commonplace, and one of a few very closely related algorithms (Pratt/TDOP, precedence climbing, shunting yard, etc.) that I guess you can call "traditional", but outside of people who regularly write parsers people are still often unaware of it.
Not least, I suspect, because while the pattern is obvious once you know it, a lot of people will implement their parser from looking at a (E)BNF representation that doesn't make it explicit. E.g. this is a small subset of Oberon 07's grammar:
expression = SimpleExpression [relation SimpleExpression].
relation = "=" | "#" | "<" | "<=" | ">" | ">=" | IN | IS.
SimpleExpression = ["+"|"−"] term {AddOperator term}.
AddOperator = "+" | "−" | OR.
term = factor {MulOperator factor}.
MulOperator = "*" | "/" | DIV | MOD | "&" .
When you know any of the precedence parser techniques and how to map a grammar to it, it's instantly obvious that this is modeling precedence rules, and it's trivial to turn it straight into a table, but if you've never written a parser before, isn't familiar with the theory, and just about figured out how to read EBNF, it's a lot easier to stumble your way to a working recursive descent parser than figuring out to generalize the grammar fragment above into reusable functions and a precedence table.