Hacker News new | past | comments | ask | show | jobs | submit login
Pratt parsing and precedence climbing are the same algorithm (2016) (oilshell.org)
3 points by sph 4 months ago | hide | past | favorite | 1 comment



I might be dumber than average, but I had a hard time understanding Pratt parsing, with its usage of 'nud' and 'led', and this article links to a much clearer explanation of precedence climbing, without the arcane and obtuse names: https://eli.thegreenplace.net/2012/08/02/parsing-expressions...

Took me an hour from reading this article to adding precedence to my hand-written parser. There's a lot of other articles that try to demystify Pratt parsing, but then they choose Rust or Java and hide what is basically a 10-line long algorithm into signal noise such as multiple classes and five functions. Simplified:

    expression(int min_precedence) {
      parse_atom();

      while ((tok = peek()) != TOKEN_EOF) {
        if (operator_precedence(tok) < min_precedence) {
          break;
        }

        int next_min_precedence = is_left_associative(tok) ? precedence + 1 : precedence;

        // process binary operator. Recurse using `expression(next_min_precedence)`
      }
    }
That's all there is to it. I'm happy I don't have any mention of 'nud' and 'led' in my code.




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

Search: