4 ms·
Where and how do you handle the operator precedence? I couldn't find in the codebase.
by fatih-erikli-cg 2y ago
Where and how do you handle the operator precedence? I couldn't find in the codebase.
- mdaniel 2y agoI'm cognizant it's just documentation, because the code is its own thing, but it seems to be a recursive descent parser https://github.com/ironcalc/IronCalc/blob/2c2228c2c26386b0197858879eeac195ca39839f/base/src/expressions/parser/mod.rs#L9-L15 https://github.com/ironcalc/IronCalc/blob/2c2228c2c26386b019...
- fatih-erikli-cg 2y ago[flagged]
- bonzini 2y agoThe function for asterisks and slashes is called from the functions for pluses and minuses. The result is that asterisks and slashes are evaluated before pluses and minuses. It's actually very easy to understand once you get the idea. https://en.wikipedia.org/wiki/Recursive_descent_parser https://en.wikipedia.org/wiki/Recursive_descent_parser
- fatih-erikli-cg 2y agoI don't think a recursion should be involved in the parser. Shift-reduce may be an answer but it does not fix the problem either if you try to implement that. I would like to see real code rather than written homework pieces.
- bonzini 2y agoYou're conflating parsing of expressions with operator precedence parsers (aka Pratt parsers). IronCalc uses a recursive descent parser, and Pratt parsers are an optimization of recursive descent parsers. Pratt parsers have one function that implements all precedence levels, while recursive descent parsers have one function per precedence level, but they contain basically the same logic. Source: 20 years ago I converted GCC's C++ parser from recursive descent to an operator precedence parser; obviously GCC respected precedence even before my work, which was purely an optimization. In fact the code I replaced had the note "The expression parser recurses through the various levels of precedence as specified in the grammar, rather than using an operator-precedence technique". https://github.com/gcc-mirror/gcc/commit/b8b94c5ba81744d325f235a0409660f50ac3f361 https://github.com/gcc-mirror/gcc/commit/b8b94c5ba81744d325f...
- fatih-erikli-cg 2y agoOperator precedence is an addition to parsing of expressions. Both of them is needed if you accept "2 + 1" kind of expression. "2 + 2 * 2" must be evaluated like "2 + (2 * 2)". Only expression parsing will evaluate them like 8.
- bonzini 2y agoYou can choose: learn recursive descent parsing, or keep on being confidently incorrect.
- amluto 2y agoBetter not use popular toolchains then: https://gcc.gnu.org/wiki/New_C_Parser https://gcc.gnu.org/wiki/New_C_Parser https://clang.llvm.org/features.html https://clang.llvm.org/features.html I think this is a quite popular approach for multiple reasons. That being said, tree sitter uses GLR.
- fatih-erikli-cg 2y agoThere is no recursion involved in parsing. You keep a stack for the tree.
- bonzini 2y agoRecursive descent uses the processor stack as the parsing stack.
- fatih-erikli-cg 2y agoRecursion is mostly involved in interpreter, and most of the time it is a bad practice. No recursion needed in parser.
- bonzini 2y agoDunning-Krueger effect at its best, I am done arguing.
- nhatcher 2y agoI wrote about it at length here: https://www.nhatcher.com/post/a-rustic-invitation-to-parsing/ https://www.nhatcher.com/post/a-rustic-invitation-to-parsing... The implementation in IronCalc follows that.