Ask HN: Writing a recursive descent parser for arithmetic expressions
1 comments
Maybe this example will help?
https://github.com/SAP/chevrotain/blob/master/examples/gramm...
It is implemented using a parsing library so the lookaheads are automatically performed by the library, but the general pattern is still relevant.
Basically each binary precedence level gets a rule (weakest first) and each of these rules will consume as many operators of the current precedence level as it can.
It is implemented using a parsing library so the lookaheads are automatically performed by the library, but the general pattern is still relevant.
Basically each binary precedence level gets a rule (weakest first) and each of these rules will consume as many operators of the current precedence level as it can.
For simplicity's sake, let's restrict operators to `( ) * / + -` in that order of precedence. And of course we have arbitrary numbers as operands.
So, my first intuition is to view the parser as sort of the inverse of the production rules of the BNF grammar; any grammar rule that produces a symbol should have a corresponding parse rule that consumes that symbol. That all seems to make sense to me.
I'm working on the expression ` 1 + 2 * 3 - (4 + 5)` first. There's not much nesting so that part isn't bad.
My first naive approach greedily grabs the left-hand-side operand after performing a lookahead. So in this case it sees the `1 +` and makes an AddExpression where lhs = 1 and rhs = a recursive call to the parse function with the rest of the tokens as input. Then it attaches to the rhs of the add expression a MultiplyExpression where the lhs = 2 and the rhs is the recursive call...etc etc
Following this approach ends up giving me a parse tree that corresponds to the expression `1 + 2 * (3 + (4 + 5))` instead of `1 + 2 * 3 - (4 + 5)`.
So, I can intuitively see that precedence needs to be considered, and it requires either scanning ahead too many tokens (I'm trying to write an LL(1) parser) or I guess doing something like the shunting yard algorithm with an operator stack and a value stack. So I guess my question is - is there some elegant, recursive way to solve this problem without having to use a stack or look ahead an arbitrary number of tokens? Basically I want to find n elegant recursive solution, but a stack-based one is fine if it's the best way of solving the problem.
This was all pretty stream of consciousness so sorry if anything isn't clear. The goal is eventually to write a LL(1) parser generator so that's why I'm trying to make sure my understanding is as solid as possible.