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…
The parsing strategy described in A Dictionary of APL uses a right-to-left strategy.
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.
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.
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”?
Whoops. Yep, you’re right - I misread that and my brain jumped to rightmost derivation :P
Here’s the implementation linked in the paper: