hime
hime copied to clipboard
cenotelie
Operator precedence climbing parser
Consider what peg (https://docs.rs/peg/latest/peg/#precedence-climbing) was doing, I think it is suitable for us to implement precedence climbing for easier design of expression grammar
From my understanding, precedence climbing is a way to fix the inefficiency of pure recursive-descent parsers for grammars that describe expressions with operators. This incidentally allows writing simpler grammars rules.
Hime use bottom-up parsing algorithms (LR and GLR) that do not suffer from this inefficiency. So precedence climbing is not really required per-se. It is true that we still have to write grammars that explicitly encode the operators precedence, as shown on Wikipedia.
My conclusion is then that the support for precedence climbing would then be only a way to alleviate the tediousness of writing grammar rules for this case, as shown in the peg crate doc. Writing grammar rules this way for expressions leads to ambiguous grammars for LR parsing techniques.
LR parsing techniques are very different from PEG; the implementation of precedence climbing would be very different. I'll have to do some research. Maybe we can have some higher-level syntax for grammar rules with operator precedence that translates to usual grammar rules that can be used by LR techniques.
From my understanding, precedence climbing is a way to fix the inefficiency of pure recursive-descent parsers for grammars that describe expressions with operators. This incidentally allows writing simpler grammars rules.
Hime use bottom-up parsing algorithms (LR and GLR) that do not suffer from this inefficiency. So precedence climbing is not really required per-se. It is true that we still have to write grammars that explicitly encode the operators precedence, as shown on Wikipedia.
My conclusion is then that the support for precedence climbing would then be only a way to alleviate the tediousness of writing grammar rules for this case, as shown in the peg crate doc. Writing grammar rules this way for expressions leads to ambiguous grammars for LR parsing techniques.
LR parsing techniques are very different from PEG; the implementation of precedence climbing would be very different. I'll have to do some research. Maybe we can have some higher-level syntax for grammar rules with operator precedence that translates to usual grammar rules that can be used by LR techniques.
https://inst.eecs.berkeley.edu/~cs164/fa20/lectures/lecture8.pdf but it seems like bison have it...