1. 23
  1. 13

    I wish I had discovered the updated version prior to submitting: https://jeffreykegler.github.io/personal/timeline_v3

    1. 4

      The complete lack of functional parsers here is disappointing.

      1. 5

        Agreed. It seems mainly to tell the story from the perspective of “Early parsers are underappreciated”. No mention at all of:

        • Parsing expression grammars (2004)
        • Parser combinators (1990’s, it seems?)
        • Pratt parsers, operator-precedence parsers, etc (1960’s-1980’s-ish, very useful formal elaborations on hand-written LL parsers)

        That said, Early’s algorithm does look worth further research.

        1. 5

          Parser combinators are from 1975. They are a technique for implementing parsers though; not really an algorithm.

          Here is our complete notebook on implementing Earley parser with Leo’s optimizations and Aycock’s epsilon fixes in Python (with every step explained).

          Another interesting fact is that Earley’s parsing algorithm can be seen as the canonical parsing algorithm underlying every other context free parser. See A Graphical Model for Context-Free Grammar Parsing for details.

          1. 2

            Nearley.js is an accessible implementation of Earley’s parser (with Leo’s optimisations). I used it to define the grammars for some parts of Tridactyl.

          2. 1

            What kind of parsers are you talking about? Parser combinators?

            I think that’s an orthogonal issue. It’s a style of writing a top-down parser. It’s not an algorithm.

            If you give me a parser written with parser combinators, I can give you one written without using paraer combinators, with the exact same algorithm.