3 ms·

Very cool. Thanks for the cool post. I am not sure I got the difference between the LL and LR parser. Is what you have above an LR parser? Also, why did you c

by ivan_ah 14y ago

Very cool. Thanks for the cool post. I am not sure I got the difference between the LL and LR parser. Is what you have above an LR parser? Also, why did you choose to represent both + and - as "ADD" tokens (and * and / as "MUL") is this to enforce evaluation priority? It would be interesting to see if you can add or ^ as an exponent for this calculator. Maybe you intended this post strictly as as an educational post, but I think doing parsing right (and from first principles) is a really cool thing to have. Check out how khan-exercises framework uses to parse math expressions into an AST: https://github.com/Khan/khan-exercises/blob/master/utils/math-model.js https://github.com/Khan/khan-exercises/blob/master/utils/mat...

erezsh 14y ago
An LR-parser tries to reduce the input over and over again into rules, eventually ending with the 'start' rule. So a+b+c+d becomes [add]+c+d -> [add]+d -> [add] -> [start] An LL-parser tries to expand the initial rule into a more complex rule structure, until it matches the input. So to match a+b+c+d it will do [start] -> [add] -> [add] + [num] -> [add] + [num] + [num] -> etc. What I wrote is an LL-parser, simply because it's much much simpler to write and to understand. Yes, both ADD and MUL are used for precedence. Since any list of +- or of */ will evaluate correctly if reduced from left to right, I didn't mind grouping them together and making my life easier (and shorter). It was strictly educational, and also a shtick; a short code hack. If I was to write an actual parser (and I don't think I would ever try to), it would look very different!