On 29/08/2007, Nicholas Cole nicholas.cole@gmail.com wrote:

But it would still be nice to search and replace matching things....

You can, using the recursion feature of Onigurama regular expressions.

For your footnote example, search for the following regular expression:

(?x: \footnote{ (?<balanced> ( [^{}] | {\g<balanced>} )* ) } )

being careful *not* to put a newline after the final parenthesis, and replace with

($1)

I've tested this, and it seems to work.

Robin

A few days ago I posted to the list a regular expression that matches a balanced nest of brackets. The OP expressed curiosity as to how it works, and since he probably isn't the only one who found it confusing, I thought I'd post an explanation to the list.

If you have ever studied automata theory, perhaps you remember that nested brackets are the classic example of something that *can't* be matched by a regular expression. So you might be surprised (or disbelieving) to see a regular expression that does exactly that. The explanation, of course, is that theory and practice are closer in theory than in practice: Onigurama regular expressions, in common with many other flavours, are more powerful than the things that computer scientists call "regular expressions".

The key in this case is the recursion (or "subexpression call") feature. (For those of you who know about such things, this feature makes it possible to represent any context-free language — a step up the Chomsky hierarchy.) I like to think that I invented this feature; certainly I wrote the initial implementation for the PCRE engine, which as far as I know is the first place that it appeared. However, the Onigurama implementation may be a case of independent rediscovery: the manual describes it as "Tanaka Akira special".

Because the expressions quickly become complicated, it is very helpful to use the (?x: ... ) container, within which whitespace and comments are ignored, so that the expression can be laid out more clearly. (That is why you cannot put a newline *after* the closing parenthesis: outside the ?x group, whitespace is matched literally.)

For example, here is an expression to match a parenthesised string (which may have (nested) parentheses inside it). I hope the comments make it self-explanatory: please ask, if not!

(?x: ( # match the initial opening parenthesis

# Now make a named group 'balanced' which matches # a balanced substring. (?<balanced>

# A balanced substring is either something that is not a parenthesis: [^()]

| # …or a parenthesised string:

( # A parenthesised string begins with an opening parenthesis \g<balanced>* # …followed by a sequence of balanced substrings ) # …and ends with a closing parenthesis

)* # Look for a sequence of balanced substrings

) # Finally, the outer closing parenthesis

)

(Remember not to put a newline after that final parenthesis!)

It's brain-twisting in the same way that recursive functions are brain-twisting when you first encounter them; but once you've got the hang of it, it is quite easy to do and very useful.

Robin

Excellent, glad it was helpful.

It really ought to be possible to combine subexpression calls and back references to do things like matching well-formed XML elements. Unfortunately this doesn't work with the Onigurama engine, because subexpression calls mess up back referencing. That's a real shame: it does work in PCRE.

If you change \k<name> to \g<name> in the code below, then it will work (but then of course it doesn't check that the closing tag has the same name as the opening one).

Robin

(?x) # Enable layout and comments

(?<element> (?<stag> < (?<name> # An XML name begins with a letter, underscore or colon: [[:alpha:]_:] # followed by a sequence of NameChars (see the XML definition): [[:alnum:].-_:]* ) (?<attr> # In XML, the whitespace chars are space, tab, CR and LF. (?<space>[\ \t\r\n]+) \g<name>\g<space>?=\g<space>? (?<attrval> '[^']*' | "[^"]*" ) )* \g<space>? > ) (?<content> [^<] # This is not quite technically correct, but is probably good enough | \g<element> )* (?<etag> </ \k<name> \g<space>? > ) | (?<emptyelemtag> < \g<name> \g<attr>* \g<space>? /> ) )