3 ms·
Not at all experienced in Lisp, but I believe this is the core algorithm in that parser... (cond ((and (binop? $next) (> new-priority priority))
by userbinator 8y ago
Not at all experienced in Lisp, but I believe this is the core algorithm in that parser...
(cond
((and (binop? $next) (> new-priority priority))
(scan)
(loop (list op result (parse-expression new-priority))))
(t result)))))
...and is what amounts to the widely-used "precedence climbing" algorithm described here:
https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing
I like to think of it more as a clever refactoring of recursive descent that condenses all the very similar recursive functions at each level into one which is parameterised by level, and also handles associativity by choosing whether to recurse (right-associative) or loop (left-associative) with the RHS after a binary operator.
- lisper 8y agoThanks for that pointer. I had no idea that what I was doing was in any way noteworthy. It just seemed kinda obvious.