Tools, Part 4. Regular Expressions

Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 126

In the following article I use quotes and angle brackets to help determine the type of the object I am referring to. ‘Quotes’ denote a variable or workspace and <angle brackets> refer to a function or operator or file. Often, the context is sufficient to remove ambiguities. Italicized words have a special meaning and often precede their definition. Optional items are shown within [brackets]. Monospace fonts are used for examples.

Introduction¶

In this article I present regular expressions (RX), and how to make some use of them through ⎕NA and SAX’ Intrinsic Functions (IFs). RX are not new and they’re useful. *nix users have known this for quite some time now. For example, to list all the lines in a file where words with a specific pattern are located or find all the files that start with a specific prefix. A pattern consists of characters, some of them having a special meaning. For example, dot (.) can mean any character but newline, and star (*) means 0 or more times. A pattern denoting all strings starting with the letter ‘A’ and ending with the letter ‘C’ would be written A.*C meaning the letter A followed by any number of characters and ending with the letter C. There are rules too and one of them says that the longest match is returned. There is also a standard. Here a few examples.

Examples¶

   e1←'. matches any char, ab%c shows this:'
   'ab.c'  showfirst e1
. matches any char, ab%c shows this:
                    ^^^^

** ? means 0 or 1, + means 1 or more, * means 0 or more
   'ab?.c' showfirst e1 ⍝ "a", 0 or 1 "b", any char then "c"
. matches any char, ab%c shows this:
   ^^^

** \ escapes following character; "\." means "."
   'ab\.c' showfirst 'not on ab%c but works on ab.c'
not on ab%c but works on ab.c
                         ^^^^

** sets may be specified within [brackets]
   'ab[eou]c' showfirst 'not abxc but OK with aboc!'
not abxc but OK with aboc!
                     ^^^^

** predefined sets like [:digits:] can be used
   'ab[[:digit:]]c' showfirst 'with ab3c and abzc!'
with ab3c and abzc!
     ^^^^

** sets may also be specified as ranges
   'ab[0-9]c' showfirst 'same with ab3c and abzc!'
same with ab3c and abzc!
          ^^^^

** a set of 2 sets:
   'ab[[:space:][:alpha:]]c' showfirst 'alpha or spaces matches ab c!!!'
alpha or spaces matches ab c!!!
                        ^^^^

** 2 separate sets:
   'ab[[:space:]][[:alpha:]]c' showfirst 'alpha or spaces matches ab zc!!!'
alpha or spaces matches ab zc!!!
                        ^^^^^

** exclusion is made with ^:
   'ab[^0-9]c' showfirst 'not ab4c but ab$c!!!'
not ab4c but ab$c!!!
             ^^^^

** subexpressions are specified with parentheses. Here, <rxmatch> returns the
   offset and length of the whole pattern and of each subexpression:
   '((a*)a)a'rxmatch 'zzaaaa'
 2 4
 2 3
 2 2
   'a(b[aeiou])c' rxmatch 'x abec x'
 2 4
 3 2
   'a(b[aeiou])c' showfirst 'x abec x'
x abec x
  ^^^^

** first match wins
   'ab*c' showfirst 'xxabbbbbbc abbcabc'
xxabbbbbbc abbcabc
  ^^^^^^^^

   '(wee|week)(knights|nights)' rxmatch 'weeknights'
 0 10
 0  3
 3  7

** patterns may be repeated. Here whatever sub expression found after "a" must
   also be found after "c" (\1)
   'a(b[aeo])c\1' showfirst 'not abecbi but abecbe.'
not abecbi but abecbe.
               ^^^^^^

** the number of times a character must be repeated can be specified {range}
   'ab{2,4}c' showfirst 'abbbbbc(5bs) abbbc (3) abc'
abbbbbc(5bs) abbbc (3) abc
             ^^^^^

** Here's an example of pattern to recognise an Identifier:
   NameDef←'[[:alpha:]][[:alnum:]_]*'
   NameDef showfirst '3+dsa/7'
3+dsa/7
  ^^^

   NameDef showfirst '3+dsa_7-31'
3+dsa_7-31
  ^^^^^

** here are the patterns for a word and word followed by punctuation:
Word: [[:alpha:]]+
pat1: ([[:alpha:]]+)[[:punct:]]

** <rxmatch> returns the whole match and the subexpression (word):
   pat1 rxmatch 'first one, then another.'
 6 4
 6 3

** This function finds ALL matches:
   pat1 rxmatches 'first one, then another, then the last.'
  6 4   16 8   34 5
  6 3   16 7   34 4

** here are more patterns:
simplestring: [^ ']+ ⍝ any series of char not a space or quote

quotedstring: '(''|[^'])*'
(A quoted string is a quote followed by a series of (double quotes
 OR a char not a quote) followed by a final quote)

token: '(''|[^'])*'|[^ ']+
(a token, here, is either a simplestring or a quotedstring)

** find all the tokens in 's1'
s1: age = 42  name= 'somkinda'' djo'
   token rxmatches s1
  0 3   4 1   6 2   10 5   16 16
                         30  1

NOTE: the first 4 matches are simplestrings which have no subexpressions in them. A quotedstring with a subexpression was found at the end and the result contains 2 rows there.

** find all lowercase letters starting a sentence, that is, here, a lowercase
   letter after a dot, ? or !: (note that the first 'b' does not fall in that
   category because there is no such character before)

e1: blah blah. blah blah? Blah blah! blah! Ah!
   '[\.\?!] *([a-z])' rxmatches e1
  9 3   31 3
 11 1   33 3

** we can show all the matches in CR delimited text.
   Show all 3 letter words in this 3 lines text:
"Now is the time for all good men to
learn more about APL and show they too can make
the world a better place to live in."

   (' ([^ ]{3}) ' 1) showall text
Now is the time for all good men to
       ^^^      ^^^          ^^^

learn more about APL and show they too can make
                 ^^^               ^^^

The APL world¶

Having RX in APL is also useful.

The bad news is, trying to program them from scratch is not for the faint of heart. Some serious (and successful) attempts have been made using techniques like finite state machines to program a subset of RX but for the most part it’s not easy. Plus, it would probably be different from any “standard”.

The good news is, someone’s already been through this. Regular expressions source is out there. DLLs have already been compiled if you’re not into doing it yourself. All you have to do is search the net¹, download it, and ⎕NA into it. This is, BTW, what J has done using 15!:0 instead of ⎕NA.

RX definition¶

There are 4 functions that compose the GNU “standard”. Their definition follows; to the left we have the routine name and its arguments definition (> means output, < means input, S=C=character, I=integer). To the right we have their C definition.

The way this works is like this: to use regular expressions we must first “compile” the pattern we’re looking for before using it on (possibly) several strings. Routine RXcomp does that. It takes 3 arguments: the 1st one is a returned structure whose detailed description isn’t necessary here. Suffices to know that less than 32 bytes are used². The 2nd, the pattern, is a NULL terminated string of what we’re looking for. The 3rd and last argument is a behaviour code, 1+2 if case insensitive+4 if CRs are to be excluded from the search (usually the case). It returns an error code if the pattern is not proper. RXerror is used to interpret this error code if needed.

RXexec is the routine that does the work. You give it 5 arguments: the compiled structure provided by RXcomp, the string to search, the number of subexpressions start-end positions to return, room for those and a behaviour code (0 for us). It returns 0 if it finds something and 1 if it finds none.

When finished with the compiled pattern we should free memory by using RXfree providing it as argument the structure that was returned by RXcomp.

This is pretty much the way it is done in APL too. To use those routines we use ⎕NA or some such to link to each one of the routines.

⎕NA¶

As usual, ⎕NA syntax varies from one APL vendor to another.

For example, with APL+Win you have to supply the NULL to NULL terminated strings. With Dyalog you tell ⎕NA if it’s a NULL terminated string (an added benefit for Unicode 16 bits handling) but you must remember to translate (to ASCII) since Dyalog’s ⎕AV isn’t based on ASCII like some other vendors. And the returned results may be different! SAX uses Intrinsic Functions (IFs) instead which can be packed to file. I’ll describe all of them.

Let’s assume the DLL file is named <regex.dll> and that the routines in it are called RXcomp, RXexec, RXerror and RXfree as above.

APL+Win (tested on V3.5)¶

For each RX routine we provide an unused APL name as right argument to ⎕NA and a descriptor of the associated routine as left argument. ⎕NA will return 1 if the function was successfully created in the workspace.

The left argument should contain ‘DLL ’ followed by

• the type of the return (B=boolean, I=int, C=character, F=float, G=general, U=unsigned) and the number of bytes
• ←
• the name of the DLL file (without the extension)
• a dot
• the routine name
• the arguments’ type and length in parentheses. Like this:

'DLL I4←regex.RXcomp(*C1, *C1, I4)' ⎕NA 'comp'

We use these functions like this:

S←32/' ' ⋄ errorcode←comp S (pattern,NULL) 5

If a 0 is returned then all is well. ‘S’ has been modified and contains a structure used to search a string, like this:

'DLL I4←regex.RXexec(*C1,*C1,*I4,I4)' ⎕NA 'find'

se←¯1 1 ⋄ found←0=find S (string,NULL) 1 se 0

If found then <se> contains the offset of the first pattern found and the offset of the first char following it, effectively providing its length by doing |-/ on it. The NULL is necessary for the pattern and strings to search as specified by the specs.

Once defined all these functions can be saved in a workspace.

Dyalog APL (tested on V8.2 & 10.0)¶

Things are a bit different here.

For each RX routine we provide an unused APL name as LEFT argument to ⎕NA and a descriptor of the associated routine as RIGHT argument (this is the reversed of APL+Win). Note that if you fail to provide a name ⎕NA will use the same name as the name of the routine in the DLL. ⎕NA does not return a result and will signal a DOMAIN error if anything goes wrong.

The right argument should contain

• Optional result type (I=int, U=unsigned, C=character, T=translated character, F=float, A=APL array) and length
• the name of the DLL file
• | (ASCII | or APL modulo)
• the routine name
• the arguments. Like this:

⎕NA 'I regex|RXcomp =C[] <0T I'

Because Dyalog’s ⎕AV isn’t based on ASCII we must tell ⎕NA to translate them where appropriate by using T instead of C. We can also tell ⎕NA which strings are NULL terminated in its definition by prepending a ‘0’. Thus ‘0T’ tells ⎕NA that this is a NULL terminated Translated string.

Dyalog also differs in the way it returns results. You can specify whether an argument is a pointer and will be used as input, output or both by prepending the characters ‘<’, ‘>’ and ‘=’ to the argument descriptors. Thus, an output list of integer would be written '>I []'. A returned argument is part of the result and not modified “by reference” as with APL+Win. The only real difference between ‘>’ and ‘=’ lies in the argument itself: with ‘>’ you tell how much memory to allocate. With ‘=’ you supply an array whose copy will be returned, modified. For example, assuming routine <try> returns an integer and returns 16 bytes by reference it would be described as

⎕NA 'I4 dllfile|try >C[16]'

and called like this:

try 16

but if it takes a specific array of 16 bytes and returns them it would be

⎕NA 'I4 dllfile|try =C[16]

and called like this (16=⍴data):

try data

The result will be a 2 elements nested array that includes the 16 bytes as second element in both cases.

In the RX context we would have

'comp' ⎕NA 'I regex|RXcomp >C[] <0T I'

and do

(errcode S)←2↑comp (32 pattern 5)

If errcode is 0 then all is well and ‘S’ contains a structure used to search a string, like this:

'find' ⎕NA 'I regex|RXexec <C[] <0T I >I[] I'
(notfound se)←find (S string 1 se 0)

If found then <se> contains the offset of the first pattern found and the offset of the first char following it, just like in APL+Win.

Functions cannot be saved in the workspace. They have to be redefined each time the workspace is loaded.

APLX (tested on V2.0.2 beta)¶

Looks like Dyalog, but again, different.

For each RX routine we provide an APL name as LEFT argument to ⎕NA and a descriptor of the associated routine as RIGHT argument. If you fail to provide name ⎕NA will use the same name as the name of the routine in the DLL. But be careful! It will redefine the name even if it is already in use. ⎕NA returns 0 0⍴'' and will signal a DOMAIN error if anything goes wrong.

The right argument should contain

• Optional result type (I=int, U=unsigned, C=translated character, P=translated Pascal string) and length
• the full name of the DLL file
• |
• the routine name
• the arguments. Like this:

⎕NA 'I4 regex.dll|RXcomp =I[8] <CT[*] I4'

Because APLX’s ⎕AV isn’t based on ASCII all character strings are translated by default or by using T after the C. If untranslated strings are requires a U should follow the C. We don’t need to tell ⎕NA which strings are NULL terminated. All ‘C’ strings are padded with one.

Because we don’t want APLX to add a NULL to the first argument of RXcomp we define it as a pointer to a series of 8 integers (8x4=32 bytes) instead.

APLX is like Dyalog in the way it returns results. You can specify whether an argument will be used as input, output or both by prepending the characters ‘<’, ‘>’ and ‘=’ to the argument descriptors. Thus, an output list of integer would be written '>I []'. A returned argument is part of the result and not modified “by reference” as with APL+Win. In both cases you supply an array whose copy will be returned, modified (see the Dyalog examples above for the RX context).

Unlike Dyalog, the functions do not need to be redefined at each load and can even be saved in the workspace and overlays.

Note that since APLX is identical in behaviour under Linux the above will also work (at least under Red Hat 7.0 and Mandrake 9.1) if you change the location of the RX routines. For example:

⎕NA 'I4 /lib/libc.so.6|RXcomp =I[8] <CT[*] I4'

would be the statement to use for RXcomp under Linux.

APLX also works under MacOS X. According to Richard Nabavi of microAPL: “Under MacOS X, the regular expression stuff is again built-in to the OS libraries. (It’s not available under MacOS 9, as far as I know). The library name to use in the []NA definition is ‘System.framework’. However, there’s a slight gotcha: under MacOS X the offsets in the returned structure are defined as 64-bit integers, not 32-bit integers as in all the other systems. So you need to double the size of the array passed as the fourth argument of ‘regexec’, and pick up the results from the 2nd, 4th… elements: a match from position 4 to 7 comes out as: 0 4 0 7.”

SAX¶

This is Linux/Unix world. ⎕NA, here, is a different thing altogether. To achieve the same result we can use intrinsic functions (IFs) instead. An added benefit being to allow packing, like APLX. The procedure is like this:

Create an IF group that will contain the 4 functions. In file ~/.saxif add the lines that define the groups and how the functions work:

regex dynamic   ~/regex.si
comp  Cfunction int  RXcomp(char*,char*,int)
exec  Cfunction int  RXexec(char*,char*,int,int *,int)
error Cfunction int  RXerror(int,char*,char*, int)
free  Cfunction void RXfree(char *)

Then do ‘ifgen ~/.saxif regex’. This will produce a <regex.stub> file that contains precompiled definitions for the compilation to come.

We now have to write the C code. All the RX code should already be all there and all we really have to do is put an ‘#include’ statement to reference it. We put the following 3 lines in file <regex.c>:

#include <sys/types.h> // standard types
#include <regex.h>     // the regex code
.include "regex.stub"  // the definitions above

We are now ready to compile. We do so by issuing

ifcc regex.si regex.stub regex.c

which produces file <regex.si> that SAX will use to produce the binds.

When we start SAX we can verify that the group ‘regex’ is in the list of intrinsic functions by doing )iflist and that all 4 functions are in it by doing )iflist regex. To associate an APL name with one of them we do, for ex:

'regex.comp' ⎕bind 'rxcomp'

and voilà! <rxcomp> is now a full-fledged IF that is used like this:

code←rxcomp S⊃pattern⊃5  ⊣  S←32/' '

S now contains the compiled pattern (unless code is not 0).

Note for Solaris users: the RX definition is slightly different and even though the ⎕bind will work, the APL functions won’t work as is. You need to triple the size of the array passed as the fourth argument of ‘regexec’, and pick up the results from the 3rd and 4th elements.

Cover functions¶

Now, all these functions are cute but not very useful by themselves. We’ve seen how to interface with the system but that is not enough. We must use them like building blocks. We need a function that, given a string and a pattern, compiles the pattern, runs it through RXexec, frees memory and returns the desired result, possibly ALL the matches, not just the first one.

I wrote these functions:

RXmatch: find the first match

RXmatches: find ALL matches

Showfirst: show the first line where a match is found with carets to show the positions

Showall: same for all matches

They’re only prototypes. I put them, along with an <example> function, in a workspace you can download if you wish.

Now, what about searching an entire workspace? Well, those of you who have been reading Vector carefully for the past year may remember about a ‘wssearch’ workspace I described in Vol 20 no.1 of July 2003 entitled ‘Tools, part 2’. I had mentioned in that article that a pattern matching function would allow searching the workspace for, well, patterns.

Well, search (!) no more. You’ll find, in the same workspace, along with those other functions above, function <OSSPATMATCH>, which can be copied into workspace ‘wssearch’ to allow searching with patterns, like this:

oss'/p/⎕[[:alpha:]]+'

which will find occurrences of, in this case, all ⎕functions and variables in the workspace (no ⎕ alone will be reported).

<OSSPATMATCH> will only be called if the ‘p’ option is supplied (see the article for details). It is basically ⍷ using a pattern as left argument. It uses local names to associate with IFs or DLL functions.

Final note¶

I don’t know of any complete standalone APL implementation of RX. There was a paper published circa 1984 on RX by some I. P. Sharp people but its code was only ever included in Logos, a SAPL product. It turned out to be a powerful tool as it was geared towards APL and included some features like ⍵ to denote a number (even complex numbers as SAM had them) and ⍺ to denote an identifier plus a lot much more.

For example, one could look in code for strings denoting APL filenames like this: ' *⍵ +⍺ *' meaning “look for quote followed by 0 or more spaces, then a number, then 1 or more spaces, then an identifier, then 0 or more spaces, then a quote”. Even more, Logos included features that could never be part of the actual available RX such as line number and char position and the use of ⍎ in replace mode.

In the filename example above, you could have replaced ALL similar hardcoded filenames with unique variable names. Extremely powerful! Unfortunately, few people had the chance to deal with Logos.

As usual the code shown in this article and the DLL are available at www.milinta.com/english. Feel free to play with it.