4 ms·

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

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.

bonzini 2y ago
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/b8b94c5ba81744d325f235a0409660f50ac3f361 https://github.com/gcc-mirror/gcc/commit/b8b94c5ba81744d325f...
- fatih-erikli-cg 2y ago
  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.
  - bonzini 2y ago
    You can choose: learn recursive descent parsing, or keep on being confidently incorrect.
amluto 2y ago
Better 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 ago
  There is no recursion involved in parsing. You keep a stack for the tree.
  - bonzini 2y ago
    Recursive descent uses the processor stack as the parsing stack.
    - fatih-erikli-cg 2y ago
      Recursion is mostly involved in interpreter, and most of the time it is a bad practice. No recursion needed in parser.
      - bonzini 2y ago
        Dunning-Krueger effect at its best, I am done arguing.

bonzini 2y ago

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/b8b94c5ba81744d325f235a0409660f50ac3f361 https://github.com/gcc-mirror/gcc/commit/b8b94c5ba81744d325f...

fatih-erikli-cg 2y ago
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.
- bonzini 2y ago
  You can choose: learn recursive descent parsing, or keep on being confidently incorrect.

amluto 2y ago

Better 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 ago
There is no recursion involved in parsing. You keep a stack for the tree.
- bonzini 2y ago
  Recursive descent uses the processor stack as the parsing stack.
  - fatih-erikli-cg 2y ago
    Recursion is mostly involved in interpreter, and most of the time it is a bad practice. No recursion needed in parser.
    - bonzini 2y ago
      Dunning-Krueger effect at its best, I am done arguing.