A note on "conforming strings"

Edward G Nilges — Sun, 30 Dec 2007 06:28:36 -0800

In wanting to return the start index and the length of the string that conforms I return counterintuitive results such as an index of 0 and a length of 1 for the regex CC* and the string CC, and, even worse, an index of 0 AND A LENGTH OF 0 for the regex C* and the string CC, using Pike's code, because Pike's code gets shortest string.

Independent of programmer implementation, there is a mathematics of regular expressions (that is not necessarily the property of professional mathematicians, any more than a regex processor defines human reality).

A programmer would observe that there isn't one and only one conforming substring, and that the conformant string is defined by the User, assuming you can find one (the "user" is an undefinable buzz word). A mathematician would say that the conformant strings are a plurality which can be thought of as a SET.

Therefore, any real regular expression processor has to by default give the caller the start index and length of the longest conformant string, NOT the shorter: Pike's code is mislabeled.

The longest conformant string can stand for the set since the set of conforming strings is just the set of substrings starting at the index i of the longest string, and then substring (i+1, maxlength-1), (i+2, maxlength-2) .. (i + maxlength - 1, 1). If the regex ends in an asterisk then the set also includes the null string.

This model can be extended to carat and dollar (the characters representing start and end of string) by transforming the input string s to ^s$ in a meta-notation.

Which means that a solid regex would return an object, a class, that allows retrieval of each conformant string from a set model. This class could implement laziness in a sweet fashion: if asked for the first and shortest conformant string, it could get only the conformants just-in-time by using an algorithm where the maximum length of conformant string, relative to the minimum, would be a parameter!

Indeed, a solid regex would be a class with methods that would EXPLAIN regular expressions, producing outputs such as "gets at least one C" for CC*, allowing its use as a real tool as opposed to a rather misleading snippet.

The ability to think in sets as opposed to bytes doesn't seem to transfer across the boundaries between languages, between languages that explicitly handle sets, and languages like C. In Beautiful Code, I don't see the beauty of ontology...making objects that correspond to thought.

A Microsoft Visual Studio C++ version of Brian Kernighan's Beautiful (?) Code

Edward G Nilges — Sun, 30 Dec 2007 05:03:10 -0800

developer.* Blogs - A Microsoft Visual Studio C++ version of Brian Kernighan's Beautiful (?) Code - Comments

A note on "conforming strings"

A Microsoft Visual Studio C++ version of Brian Kernighan's Beautiful (?) Code