What was the first language with regexes?

Question

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)*

Answer 1

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}} .

Answer 2

(Note: This answer is pretty seriously TLDR, but I needed to work through the following analysis of the paper in order to confirm my understanding of FLIP; the paper itself is not terribly clear, IMHO. If you think that the analysis should be removed, let me know in a comment, but I have no better home for this right now.)

The first appearance of regular expressions as we know them now ([abc].*def etc.) appears to have been Ken Thompson's implementation of them in the QED editor in 1967. In the following I'll call these "Thompson regexps."

Daniel G. Bobrow's April 1966 paper "Format-directed List Processing in LISP" describes a pattern matching and replacment language called "FLIP" that is embedded in LISP using patterns and formats that are "greatly generalized versions of the left-half and right-half rules of COMIT and SNOBOL." (FLIP was implemented in LISP 1.5.) While the matching and replacement applies to lists of characters, these are clearly isomorphic to strings of charcters: "ABC" is expressed as (A B C) here. However, FLIP can also deal with deeper structure within these lists, such as (A (B C) D), as we shall see.

Unlike COMIT or SNOBOL, FLIP is in the following ways very much the modern concept of Thompson regexps in modern programming languages:

1. The pattern matching language is embedded in a general-purpose programming language (unlike COMIT or SNOBOL); patterns are executed by passing to a match function the pattern and a target list against which to match it.
2. The pattern language is similar (although differing in surface syntax) to Thompson regexps, though also offering more powerful facilities for subtitution of variables, composition, etc. (Substitution of variables and the like is also available via host programming language facilities in modern programming languages, consider the Python code pat = re.compile('Hello, ' + name); FLIP also uses the host language to aid in this.)

FLIP patterns are not, however, compiled to a finite-state automaton, as Thompson regexps are, in part because they're more general. (Arbitrary LISP functions can be included in the pattern matching language both to produce pattern fragments and to modify how the pattern matches the target.) They can, however, be translated from the "external" notation used here to a more efficient internal format.

Further, FLIP patterns are also more general in that they can deal with nested lists, matching structures within them, as mentioned above and described in more detail below. (According to the paper, "COMIT has lists only to depth 3 and SNOBOL and AXLE deal only with linear strings.")

FLIP Description

The following is my summary of the relevant parts of the paper, as best I understand it. The order here is not ideal since I'm closely following the paper, which seems to jump around a bit in its introduction of various concepts.

FLIP uses two functions, match and construct to match patterns in lists and reconstruct lists based on a format, respectively. Here I'll deal only with the former, as it's not clear to me if you were also asking about formatting of replacement strings.

match takes two arguments, a list to be parsed and a pattern to match, and returns a parsing of the list with respect to that pattern if it matches the pattern. (This parsed representation can later be passed to construct.)

Basic Constant and Pattern Matching

The first matching constructs described in the paper are:

FLIP    regexp  meaning
------------------------------------------------------------------
x       x       match constant element x
$       .*      match anything, including zero-length sequence
$n      .{n}    match a segment of length n

The first example (aligned by me for convenience in reading, and equivalant regexp added by me):

Regexp:      .*    .{3}    A   .*      .   B   .*
Pattern:    ($     $3      A   $       $1  B   $  )
List:       (A W   X Y Z   A   B C D   E   B   C D)
Parse:      [A W] [X Y Z] [A] [B D C] [E] [B] [C D]

The next example shows how both variables can be used and sublists can be matched. Given a binding of A to list (X Y Z) we can match that list as a sublist within the list we're parsing:

Pattern:    ($         (=A)      $)
List:       (A X Y Z   (X Y Z)   Q)
Parse:      [A X Y Z] [(X Y Z)] [Q])

= is actually an evaluation operator, so arbitrary LISP expressions and functions can be called for the value that will be matched.

The ** operator treats the expression to which it is applied not as a sublist but as a segment of the main list. So we can match the X Y Z segment within the main list, rather than the subsequent (X Y Z) sublist, with:

Pattern:    ($  (** (=A))  $)
List:       (A   X Y Z     (X Y Z) Q)
Parse:      [A] [X Y Z]   [(X Y Z) Q])

The * operator treats the expression to which it's applied as a single item, i.e., the standalone (=A) in the earlier example is really (* (=A)); the translator inserted * by default because it's a common use case.

Sublists can also be matched with constants:

Pattern:    ($           ($   F $)   $)
List:       (A (B C) D   (B E F  )   G)
Parse:      [A (B C) D] [(B E F  )] [G]

The parse there is actually the "top-level" parsing; parsing of the nested pattern is also done, meaning that [B E] [F] [] is also somehow in the output parse. (The paper doesn't go into the details of the parse representation.)

The expressions in the example above produced constants to be matched (e.g., =A matched the constant (X Y Z)), but it's also possible to have expressions produce patterns to be matched. For this the * and ** operators have corresponding $* and $** operators. Thus one could set A to ($ F $) and ($ ($* (=A)) $) would be the same pattern as given in the example above.

Alternation and Repetition

The paper now moves on to the remaining missing bits from the requirements in the question: alternation and repetitions.

Alternation is expressed with the EITHER function which takes a list of the alternates to match:

  digit = ( (EITHER (1) (2) (3) (4) (5) (6) (7) (8) (9)) )
integer = ( (EITHER (=digit) (($** (=digit)) ($** (=integer)))) )

(I corrected the parens for the definition of integer; the right-hand side appears to be cut off in the paper.)

digit matches any digit from 1 to 9. (Don't ask why 0 was left out. It's just that kind of paper.) integer matches a single digit or a single digit followed by an integer, i.e. a list of digits of any length. Note the use of $** here to ensure that the value returned by (=digit) or (=integer) is interpreted as a pattern, rather than a constant list. This would be used in a top-level expression just as it is internally, with ($** (=integer)) to match a sequence of digits within a list.

Repetition is expressed with (REPEAT p) which matches zero or more occurrences of pattern p, or (REPEAT n p) which matches n or more occurances of p. A sequence of patterns p q ... may be also be given in which case REPEAT matches zero or more (n or more) segments matching that sequence. Examples:

• ((REPEAT $2)) would match a list only if it had an even number of items. (Note the lack of $ before and after the (REPEAT $2), leaving that expression anchored to the beginning and end of the list it's attempting to match.)
• ((REPEAT 1 (=digit))) would match a list consisting of one or more digits, as with (($** (=integer))) above.
• (REPEAT A $1 B) would match (A X B A Y B A Z B).

(Presumably EITHER and REPEAT produce parse output with the details of the matches in the same way as given in the initial Pattern/List/Parse examples; that's not described in this paper.)

At this point Bobrow points out that FLIP can directly express regular expressions:

The EITHER and REPEAT subpatterns are similar to the operations of disjunction, "v" and * in the formation of regular expressions. In fact, given the definition of a regular expression, it is very easy to write the FLIP matching pattern which will parse a string if, and only if, it is an example of that regular expression. For example, the pattern

  (REPEAT (EITHER (A B) ((REPEAT (EITHER (B C) (D E F)) )) ))

will be equivalent to the regular expression

  (A B v (B C v D E F) * ) *

and will match with

  A B D E F B C B C D E F A B.

Further Notes

The paper goes on to say that "the operation of the match is a sequential, left to right process." Thus, matching ($ C $) against (A B C D C D E) will result in the parse [A B] [C] [D C D E], not [A B C D] [C] [D E].

Because of this left-to-right process, back-matches are available. Each "elementary pattern" is assigned a numerical mark corresponding to its position in the total pattern (sort of an automatic version of Thompson regexp grouping with \( and \)): in ($ $2 A $) mark 2 references whatever $2 matched and mark 3 references the A match. This can be referenced with a number; e.g., to match two repeated items in a list:

Pattern:    ($   $2    $     2     $)
List:       (A   B C   D E   B C   D)
Parse:      [A] [B C] [D E] [B C] [D]

(Note that the 2 in $2 refers just to two items, and is no relation to the later 2 referring to the second item in the pattern list. I think this example could be better written, but I didn't want to change what the paper gave.)

Items can be named using the NAME operator, e.g. ($ (NAME FOO $2) A $) will assign to variable FOO whatever was matched by $2.

There's a lot more functionality and notation for marks, such as describing segments of subpatterns, little of which is discussed in the paper.

Particularly powerful is the ability to attach predecates to patterns which can take previously matched segments as arguments.

Pattern:    ($3      $3 / (EQUAL (=REVERSE 1)) )
List:       (A B C   C B A)
Parse:      [A B C] [C B A]

There are also optimizations available because full information about the parse is kept. The paper mentions that ($1 $ 1 $5 $), which matches any target list where the first item is repeated at least five times before the end of the target list, can involve continuing to try matches when there's no possibility of the pattern actually matching. Attaching a special failure predeciate to $ can optimize this, though the paper doesn't give the details.

There is also a method of doing a reverse (right-to-left) search, $R, which can be convenient in certain situations.

Conclusion

There's even more before the paper gets on to the construct process, but I think what we've got to this point makes it pretty clear that FLIP is indeed a (particularly powerful) implementation of matching that can do everything done with regular expressions in programs as we know them today.