Plausibly this approach is trivial to understand and implements full regexes, but it is slower than the NFA or DFA approach: http://canonical.org/~kragen/sw/dev

Plausibly this approach is trivial to understand and implements full regexes, but it is slower than the NFA or DFA approach: http://canonical.org/~kragen/sw/dev3/redl.py http://canonical.org/~kragen/sw/dev3/redl.py PEGs are in some ways more powerful than regexes, and in other ways less powerful, but usually the former matter more. This is not trivial to understand but I think it's not that hard either; it's a page of code: https://github.com/kragen/peg-bootstrap/blob/master/peg.md https://github.com/kragen/peg-bootstrap/blob/master/peg.md That version doesn't memoize and so doesn't enjoy Packrat parsing's linear-time guarantee, but you can easily modify it to do so. Another subset of regexes that's easy to understand is this single-page pattern matcher by Rob Pike from TPOP: https://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html https://www.cs.princeton.edu/courses/archive/spr09/cos333/be... which is enormously less code than my single-page PEG parser generator above. But then, it doesn't have to compile itself.