Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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

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.



Thanks for that pointer. I had no idea that what I was doing was in any way noteworthy. It just seemed kinda obvious.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: