I'm just keeping this here, to keep me honest about what I'm reading.
A Play on Regular Expressions: A Functional Pearl. Sebastian Fischer, Frank Huch, Thomas Wilke.
- Solid introduction to parsing with semirings in Haskell
- Haskell is straightforward and accessible
- Readable, breezy style
- Semirings covered: Recognition, Counting, Viterbi-Best (Maxlong, Firstlong)
Algebraic Foundations of Semiring Parsing. Yudong Liu
- Discusses semiring parsing as unified framework
- Unites semiring parsing and finite state transducers
- Describes a mechanical C++ framework for the pieces/parts
- Looks a lot like Barge/Barre
- Good overview, fairly accessible.
An Algorithm for RELAX NG Validation James Clark.
- Describes the Interleaf operator in some detail.
Bit Coded Regular Expression Parsing. Lasse Nielsen.
- Presentation, so short on details
- Describes bit coding as a way to do comparisons on regexs with less than machine-width alternatives
Bitsets Match Regular Expressions, Compactly. Paul Khuong
- Describes the Bitap algorithm for bitmap encoding
- Describes graph minimization as assuming that all states are singular, and breaking them up as we prove the assumption wrong.
Constructing Human Grade Parsers. Joe Karter.
- Wish-list of parser capabilities outside the actual parsing engine
- Parse errors should be recoverable
- Parser should be able to produce partial output
- Requires tooling outside the formalities of regex and semiring parsing
Design and Analysis of String Representation. R. Sekar.
- Describes Owens, et. al.'s DFA generator as a realization of McNaughton-Yamada
- Describes alternative search algorithms
Efficient and Flexible Incremental Parsing. S. L. Graham
- Describes incremental parsing, in which a document tree and parse tree are maintained and updated together.
Error-Correcting Parser Combinators S. Doaitse Swierstra, Pablo R. Azero Alcocer
- Haskell-based parsing language
- Describes error-handling in parsing processes
- Describes recovering from errors to continue parsing
- Uses combinators, though
Total Parser Combinators Guillaume Allais
- Describes a combinator-based parser with guaranteed termination
- Uses Brzozowski as its basis
- Proves that the combinator recognizer is a semiring
- Written in Agda (eek!)
Kleene Meets Church. Fritz Henglein
- Has the "theory vs practice" description
- Ideal: parsing + catamorphic processing
- Actual: FAs + ad-hoc instrumentation
On the Complexity and Performance of Parsing with Derivatives Michael D. Adams, Celeste Hollenbeck, Matthew Might
- Provides both theoretical and mechanical optimizations
- Replaces the recursion nullability with data-flow analysis
- Provides basis for Darais's implementation
Recognising and Generating Terms using Derivatives of Parsing Expression Grammars. Tony Garnock-Jones, Mahdi Eslamimehr, Alessandro Warth.
- Describes the derivatives of PEGs
- Describes the δPEG algorithm without backtracking for negation
- Describes the derivation of prioritized choice
Regular Expression Derivatives Reexamined Scott Owens, John Reppy, Aaron Turon.
- The paper that started the current project.
- Section 3.3: Using derivatives for DFA construction.
- Describes equivalence sets in the face of symbol class operators
- Describes regular vectors for multithreaded matching.
- Describes integration of complement and intersection operations
Regular Expressions as Types. Fritz Henglein
- Introduced the "ad-hoc" slander about PCRE. 😊
- Describes regex as a set membership problem
- Describes types systems as "regular languages"
- Clarifies emitter location for stream-processing
- On the Kleene star operation
- May require different Kleene stars, or a visitor with some context awareness.
Semiring Parsing. Joshua Goodman.
- Mentioned by Liu
- Covers the initial history of semiring parsing
- Describes derivations forests (see Might & Adams) in a concise way (sec 2.5.1)
- Describes Viterbi n-best as a probablistic disambiguation strategy
Stream Processing Using Grammars and Regular Expressions Urlik Turk Rasmussen
Has a great explanation of the "Regular Expressions as Types" approach.
Leads into regex equivalence sets
Discusses disambiguation strategies with equivalence sets
Discusses bit coding of unions (no μ-regex or e-regex)
(Con) Uses bit-coding as a parse tree extraction tool
Discusses alternative needs
- Matching (capture groups)
- Parsing (parse trees)
Discusses two-pass analysis (Might) vs one-pass (Adams)
Discusses difficulty of regex composition (see Conway 2018)
Discusses CFGs as an alternative DSL for regex composition (PEG, EBNF)
Is actually 5 papers; the other 4 cover algorithm's evolution
Fantastic overview overall
Taxonomies and Toolkits of Regular Expression Algorithms Bruce William Watson
- Solid overview
- Fairly long
- Excellent coverage of DFA minimization
- Discusses prefix/suffix scanning via Aho-Corasik, et.al.
- Cover Brzozowski's algorithm as a performance-based alternative DFA constructor
Yacc is Dead Matthew Might, David Darais
- Started this whole mess
- Still a pretty good introduction.