15

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)*
  • 2
    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
  • 2
    @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
14

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
  • 2
    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
  • 4
    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
4

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

  • Very nice answer - though I disagree with your brief dismissal of COMIT as an acceptable (and earlier!) language with REs. – davidbak 2 days ago
  • @davidbak Fair enough. I suppose one thing I was personally focused on, to the detriment of the question perhaps, was the modern idea of a regex being just part of a general purpose language, rather than the core of a language that was not suitable for non-text-processing uses, as with Perl vs. sed. In fact, LISP with FLIP might have very much the same relationship to COMIT as Perl does to sed. – Curt J. Sampson 2 days ago
  • 1
    You could be right and I very much wish I had known about FLIP - which I only learned about here! - back in the day when I was working with LISP. But TBH I have long preferred the SNOBOL/SPITBOL/Icon family of languages when working with strings: pattern matching turned up to 11! – davidbak 2 days ago
  • @davidbak I think if you would post an answer here about your personal experience with COMIT and SNOBOL, explaining how they map to sed/awk/Perl/etc.-type regex use, that would be incredibly valuable. So far, we don't have any answers from anyone who's actually used these earlier languages in any serious way. And from a quick scan of the Wikipedia page it seems that SNOBOL was probably more general-purpose than I'd originally thought. – Curt J. Sampson 2 days ago

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.