4 ms·
Let’s Build a Simple Interpreter. Part 6
- kevin_thibedeau 11y agoThe shunting yard or precedence climbing algorithms are better approaches to expression parsing. They make it trivial to add operators and change precedence levels without the convolutions of a recursive grammar. They also clear the way for user defined operators since the machinery is controlled with a table that can change dynamically.
- userbinator 11y agoI think shunting yard is a bit more complex since it requires a separate stack, but precedence climbing is definitely better than pure recursive-descent and follows quite straightforwardly if you try to refactor an RD parser by noticing that most of the functions are very similar, of this form: while(token in tokens[level]) consume token result = result operator[level] func[level+1]() Then you realise that you don't need to climb up each level of precedence with a function call, and instead can go right to the level of the token and consume everything "above" that level... so it's really more like "precedence jumping". This also means the call stack doesn't get deeper in proportion to the number of levels, unlike with a pure RD parser. There could be 10 or 1000 levels in the table and the running time will still be the same - linear in the number of tokens in the input. This is especially good for languages with many precedence levels like C, or more complex applications with dynamically defined operators as you mention. A more detailed explanation of this derivation is here: https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing
- marktangotango 11y agoA less verbose, in loc and exposition, example can be found here: http://www.jroller.com/languages/entry/python_writing_a_compiler_and http://www.jroller.com/languages/entry/python_writing_a_comp...