Modern C

A recent discussion on the Gophers Slack caught my eye regarding the performance of Go's standard library regexp package when handling massive alternations of literal strings. The user posted the following observation: "I've been looking at why a certain regexp is slow, and I find that anything with over 500 instructions (maxBacktrackProg) gets run by the NFA engine. However every literal character in the regex consumes an instruction, so this penalizes simple regexps which contain a bunch of long strings." The "Monster" Regex The user provided an obfusctaed version of the regular expression causing the bottleneck. It is essentially a massive list of pipe-separated literals, wrapped in a dot-star sandwich to search for substrings: ^(?s:.*zQPbMkNO.*|.*NNSPdvMi.*|.*iWuuSoAl.*|...many more...|.*wYtnhdYb.*)$ Because the standard library counts every literal character as an instruction, this regex exceeds the threshold for the efficient One-Pass...

modernc.org/rec is a regexp to Go code compiler tool. It is still a bit rough around the edges. For example, it converts the regexps to a DFA, but it does not yet support intersecting character classes ending up in the same DFA state. Anyway, rec can already handle some nontrivial tasks, like generating a usable, working Go scanner. Here are those 1,219 bytes - in scanner.sh . The shell script is used in the generate target of the Makefile . Note the Perl Unicode character classes in the regexp for Go indentifiers. The respective EBNF  lexical grammar   part of Go specification is identifier = letter { letter | unicode_digit } . The above production expands and translates to the regexp (\pL|_)(\pL|_|\p{Nd})* .  As mentioned above, constructing DFAs from regexps using character classes is a bit challenging per se when considering Unicode. A similar program, lx(1) , part of libfsm , seems to not support Unicode so far, possibly because facing similar difficulties. The...