Sunday, June 12, 2016

[ahnojrec] Context free matching

We don't seem to have easy to use tools like grep or regular expression libraries for the next step up in the Chomsky hierarchy, namely context free grammars.  (Bison and yacc, happy, parsec, etc., exist, but they are rather cumbersome compared to regular expressions.)

Two cubic time parsing algorithms: the Earley algorithm and the Cocke Younger Kasami algorithm, with plenty of opportunities for optimization.

It might be lack of demand.  Regular expressions might be enough, especially with non-regular extensions like matching backreferences in perlre.

Regular expression matching by default is unanchored: look for a match anywhere in the string.  Context free grammars are by default anchored at the beginning of a document.

Regular expressions typically process one line at a time.  Context free grammars typically process the entire document at once.

No comments :