1. 27
  1.  

  2. 9

    This algorithm parses “from right to left (from the end of the input back towards the beginning).” Mind. Blown. I’ve never heard of any parser that does that…

    1. 4

      The parsing strategy described in A Dictionary of APL uses a right-to-left strategy.

      1. 1

        Ah, right — IIRC, APL is right-associative with no operator precedence, and almost every token is a single character, so right-to-left would be natural.

        1. 1

          I think op was being sarcastic – LR parsing isn’t a novel technique. It’s well known and broadly applied in basically every parser generator that isn’t based on parser combinators or packrat parsing.

          1. 1

            I’m familar with LR and LALR parsers. They still parse the input from left to right. Perhaps you misread and thought I meant “bottom-up”?

            1. 1

              Whoops. Yep, you’re right - I misread that and my brain jumped to rightmost derivation :P

      2. 4

        Here’s the implementation linked in the paper: https://github.com/lukehutch/pikaparser