13

According to Wikipedia, Regular Expressions (AKA regexes) have only been around since 1956:

Regular expressions originated in 1956, when mathematician Stephen Cole Kleene described regular languages... Other early implementations of pattern matching include the SNOBOL language, which did not use regular expressions, but instead its own pattern matching constructs.

Regular expressions entered popular use from 1968 in two uses: pattern matching in a text editor and lexical analysis in a compiler.

The description of SNOBOL's pattern matching abilities is vague: I'm not sure if they are actually able to match all regular languages. The article doesn't confirm if anything else came earlier either. I think that there must be something before regexes first became popular in 1968.

I really want to know what was the earliest regex flavor. And how does its syntax compare to "modern" regex syntax (PCRE, for example)?


Just to be clear, a regex flavor must be able to do the following things (just not necessarily with this syntax):

  1. Concatenation
    • Match "cat" by stringing together three regexes: c + a + t
  2. Union (AKA alternation)
    • Match either "c" or "d": [cd]
  3. Star (AKA repetitions)
    • Match "cccccc": c*
  4. Any combination of the above
    • Concatenation and Union
      Match either "cat" or "dog": cat|dog
    • Concatenation and Star
      Match "c"s followed by "d"s: c*d*
    • Union and Star
      Match any pattern of "c" and "d": [cd]*
    • All three
      Match any pattern of "cat" and "dog": (cat|dog)*
  • 1
    A SNOBOL manual is e.g. here. It can also match e.g. balanced parenthesis, which regular expressions cannot, but doesn't really have alternation in tha form, so I'd say there's no real overlap with regular expressions. – dirkt May 29 '16 at 7:12
  • grep and ed used regular expressions. They appear at least in Unix v4, so 1974. But I'm sure there were earlier uses ... – dirkt May 29 '16 at 7:14
  • I feel that this question belongs on StackOverflow. This is really no different than Which version of GCC contains feature X. – pipe May 30 '16 at 16:55
  • @pipe This is discussed on Meta. As a member of both sites, I asked here because (a) Stack Overflow might see it as a recommendation question, (b) I was certain the answer fell well within retro-land, (c) the question gets more visibility to experts here, and (d) this is a history question, not a specific programming question. – Laurel May 30 '16 at 17:07
  • 2
    @dirkt SNOBOL's pattern matching capability far exceeded regular expressions (even today's regular expressions) as pattern matching was a first class facility in the language: you could assign patterns to variables, then build pattern matching expressions up from smaller named expressions using recursion, indirection, and full control flow constructs including ifs and loops (built from SNOBOL's only control flow primitive: conditional goto). BTW, it did have an alternation operator | (just like regexp syntax) - see here. – davidbak Jun 1 '16 at 18:38
11

I think I found it. It's called COMIT, and it dates back to 1957, just one year after Kleene's work was published. Wikipedia calls it the "first string processing language", so it fits the bill very nicely.

Wikipedia also says that its creation led to the creation of SNOBOL. After reading up on SNOBOL a bit, I realized it's actually pretty powerful too, capable of parsing Context-free grammars (CFGs).

An introduction to COMIT programming is the best reference for the grammar that I've found so far. Keep in mind, it's an ENTIRE programming language. I am sure it's possible to do all of the things I mentioned; the language is Turing-complete, but it seems like it is geared towards non-recursive parsing.

The syntaxes for the "patterns" and the "strings" are a little weird (but mutually similar), so I doubt that modern regex syntax was derived from it.

(The oldest regex flavor with syntax like modern regexes that I know of are Unix utilities, as dirkt mentioned: grep, ed, sed, awk. This could be an entirely different question to ask about.)

Characters can be grouped together into arbitrary groups called constituents, which are separated by plus signs. Ironically, my initial example of concatenation is exactly how it looks:

C + A + T

It can also be written as one constituent:

CAT

To include a space, the dash (-) character is used:

THE + -CAT

Or, as a single constituent:

THE-CAT

Strings are stored in memory called the workspace. "Rules" are matched against the workspace, and replacements can be made.

It's pretty easy to do a replacement, actually. To change THE-CAT into THE-DOG, you could use this rule:

* CAT = DOG *

Deletion is easy too. To remove THE- from THE-DOG, you could use this rule:

* THE- = 0 *

If you have DOG and wanted to double the G, you could use numbers. Numbers are meta characters, as my deletion example shows you. Ignoring 0, they have a similar meaning to modern capture groups, if you imagine each constituent as a capture group. For example, G could be doubled by using the following rule:

* G = 1 + 1 *

(No, one plus one isn't two, it's GG!)

Moving onto more complex constructs, $ is essentially equivalent to the modern .*. On the other hand, in order to do something similar to the modern .{3} (three characters), you would use $3 in COMIT (assuming each constituent was a character, I think).

If you had THE-CAT + , + -WHO-WISHED + -IT-WAS + -A-DOG + , + -BARKED and you wanted to remove everything between the commas, you would use:

* , + $ + , = 0 *

Like I said, there's a whole lot more past this. It has some type of GOTO, but I don't have any experience with using GOTOs (I come from an era where GOTO is something to be avoided, not taught).

It also might help me if I had a way to run this stuff. I guess I'll have to write up a flowchart instead or something :) Edit: Just remembered this site gives me flowcharts automatically from regexes... No paper needed .

  • 1
    I browsed the manual, and it doesn't look like a full regular expression to me. What's missing is the ability to compose the primitives arbitrarily, e.g. to have something like (a(b(ab|c)*|a)b)*. What's also missing is the correspondence to finite automata, and compilation to what's basically a table for the automaton. So I don't think it counts. :-) – dirkt May 30 '16 at 4:43
  • @dirkt I encourage you to read Machine methods for proving logical arguments expressed in English. Let the language speak for itself if you aren't convinced by me. :) – Laurel May 30 '16 at 6:51
  • 1
    Still not convinced. That looks like they are using a set of COMAL rules to implement a term rewriting system. Term rewriting systems can implement type-0 (unrestricted) grammars, which are provably distinct from type-3 (regular) grammars, but that doesn't make the rules themselves regular expressions (which is what you were looking for, if I understood your question correctly). Yes, you also can write down type-3 grammars this way. But regular expressions as in grep are used very differently. – dirkt May 30 '16 at 7:42
  • @dirkt I have very little knowledge about the the computer science side of things, but from what I understand, type 0 is a superset of all the other types. Relevant material. I originally considered mentioning BNF in my Q but decided against it. That being said, I think that there is more than one answer to this question; COMIT is not the ancestor of regex syntax nor implementation. – Laurel May 30 '16 at 8:04
  • 2
    If you don't know the CS part: The selling point of regular expressions is that they have a comparatively cheap implementation as finite automatons, and one of the forms to describe them is a single expression as compared to a complete grammar with several rules (BNF etc.). That's why you can conveniently use them from the commandline in programs like grep, and a PDP-11 has enough memory to make that work. On the IBM 701 where COMIT was developed this wouldn't have worked, so COMIT does repeated transformations on a smallish buffer, which is slower, but more general. – dirkt May 30 '16 at 8:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.