Hacker News new | past | comments | ask | show | jobs | submit login

Where and how do you handle the operator precedence? I couldn't find in the codebase.



I wrote about it at length here:

https://www.nhatcher.com/post/a-rustic-invitation-to-parsing...

The implementation in IronCalc follows that.


I'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/2c2228c2c26386b019...


[flagged]


The 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


I 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.


You'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/b8b94c5ba81744d325f...


Operator 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.


You can choose: learn recursive descent parsing, or keep on being confidently incorrect.


Better not use popular toolchains then:

https://gcc.gnu.org/wiki/New_C_Parser

https://clang.llvm.org/features.html

I think this is a quite popular approach for multiple reasons. That being said, tree sitter uses GLR.


There is no recursion involved in parsing. You keep a stack for the tree.


Recursive descent uses the processor stack as the parsing stack.


Recursion is mostly involved in interpreter, and most of the time it is a bad practice. No recursion needed in parser.


Dunning-Krueger effect at its best, I am done arguing.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: