A parser for regular expressions in PHP?

Question

I need to parse regular expressions into their components in PHP. I have no problem creating the regular expressions or executing them, but I want to display information about the regular expression (e.g. list the capture groups, attach repetition characters to their targets, ...). The overall project is a plugin for WordPress that gives info about the rewrite rules, which are regexes with substitution patterns, and can be cryptic to understand.

I have written a simple implementation myself, which seems to handle the simple regexes I throw at it and convert them to syntax trees. Before I expand this example to support more op the regex syntax I would like to know whether there are other good implementations I can look at. The implementation language does not really matter. I assume most parsers are written for optimizing matching speed, but that is not important for me, and may even hinder clarity.

Answer 1

I'm the creator of Debuggex, whose requirements are very similar to yours: optimize for the amount of information that can be shown.

Below is a heavily modified (for readablity) snippet from the parser that Debuggex uses. It doesn't work as-is, but is meant to demonstrate the organisation of the code. Most of the error handling was removed. So were many pieces of logic that were straightforward but verbose.

Note that recursive descent is used. This is what you've done in your parser, except yours is flattened into a single function. I used approximately this grammar for mine:

Regex -> Alt Alt -> Cat ('|' Cat)* Cat -> Empty | (Repeat)+ Repeat -> Base (('*' | '+' | '?' | CustomRepeatAmount) '?'?) Base -> '(' Alt ')' | Charset | Literal Charset -> '[' (Char | Range | EscapeSeq)* ']' Literal -> Char | EscapeSeq CustomRepeatAmount -> '{' Number (',' Number)? '}' 

You'll notice a lot of my code is just dealing with the peculiarities of the javascript flavor of regexes. You can find more information about them at this reference. For PHP, this has all the information you need. I think you are very well on your way with your parser; all that remains is implementing the rest of the operators and getting the edge cases right.

:) Enjoy:

var Parser = function(s) {   this.s = s; // This is the regex string.   this.k = 0; // This is the index of the character being parsed.   this.group = 1; // This is a counter for assigning to capturing groups. };  // These are convenience methods to make reading and maintaining the code // easier. // Returns true if there is more string left, false otherwise. Parser.prototype.more = function() {   return this.k < this.s.length; }; // Returns the char at the current index. Parser.prototype.peek = function() { // exercise }; // Returns the char at the current index, then advances the index. Parser.prototype.next = function() { // exercise }; // Ensures c is the char at the current index, then advances the index. Parser.prototype.eat = function(c) { // exercise };  // We use a recursive descent parser. // This returns the root node of our tree. Parser.prototype.parseRe = function() {   // It has exactly one child.   return new ReTree(this.parseAlt());   // We expect that to be at the end of the string when we finish parsing.   // If not, something went wrong.   if (this.more()) {     throw new Error();   } };  // This parses several subexpressions divided by |s, and returns a tree // with the corresponding trees as children. Parser.prototype.parseAlt = function() {   var alts = [this.parseCat()];   // Keep parsing as long as a we have more pipes.   while (this.more() && this.peek() === '|') {     this.next();     // Recursive descent happens here.     alts.push(this.parseCat());   }   // Here, we allow an AltTree with single children.   // Alternatively, we can return the child if there is only one.   return new AltTree(alts); };  // This parses several concatenated repeat-subexpressions, and returns // a tree with the corresponding trees as children. Parser.prototype.parseCat = function() {   var cats = [];   // If we reach a pipe or close paren, we stop. This is because that   // means we are in a subexpression, and the subexpression is over.   while (this.more() && ')|'.indexOf(this.peek()) === -1) {     // Recursive descent happens here.     cats.push(this.parseRepeat());   }   // This is where we choose to handle the empty string case.   // It's easiest to handle it here because of the implicit concatenation   // operator in our grammar.   return (cats.length >= 1) ? new CatTree(cats) : new EmptyTree(); };  // This parses a single repeat-subexpression, and returns a tree // with the child that is being repeated. Parser.prototype.parseRepeat = function() {   // Recursive descent happens here.   var repeat = this.parseBase();   // If we reached the end after parsing the base expression, we just return   // it. Likewise if we don't have a repeat operator that follows.   if (!this.more() || '*?+{'.indexOf(this.peek()) === -1) {     return repeat;   }    // These are properties that vary with the different repeat operators.   // They aren't necessary for parsing, but are used to give meaning to   // what was parsed.   var min = 0; var max = Infinity; var greedy = true;   if (this.peek() === '*') { // exercise   } else if (this.peek() === '?') { // exercise   } else if (this.peek() === '+') {     // For +, we advance the index, and set the minimum to 1, because     // a + means we repeat the previous subexpression between 1 and infinity     // times.     this.next(); min = 1;   } else if (this.peek() === '{') { /* challenging exercise */ }    if (this.more() && this.peek() === '?') {     // By default (in Javascript at least), repetition is greedy. Appending     // a ? to a repeat operator makes it reluctant.     this.next(); greedy = false;   }   return new RepeatTree(repeat, {min:min, max:max, greedy:greedy}); };  // This parses a "base" subexpression. We defined this as being a // literal, a character set, or a parnthesized subexpression. Parser.prototype.parseBase = function() {   var c = this.peek();   // If any of these characters are spotted, something went wrong.   // The ) should have been eaten by a previous call to parseBase().   // The *, ?, or + should have been eaten by a previous call to parseRepeat().   if (c === ')' || '*?+'.indexOf(c) !== -1) {     throw new Error();   }   if (c === '(') {     // Parse a parenthesized subexpression. This is either a lookahead,     // a capturing group, or a non-capturing group.     this.next(); // Eat the (.     var ret = null;     if (this.peek() === '?') { // excercise       // Parse lookaheads and non-capturing groups.     } else {       // This is why the group counter exists. We use it to enumerate the       // group appropriately.       var group = this.group++;       // Recursive descent happens here. Note that this calls parseAlt(),       // which is what was initially called by parseRe(), creating       // a mutual recursion. This is where the name recursive descent       // comes from.       ret = new MatchTree(this.parseAlt(), group);     }     // This MUST be a ) or something went wrong.     this.eat(')');     return ret;   } else if (c === '[') {     this.next(); // Eat the [.     // Parse a charset. A CharsetTree has no children, but it does contain     // (pseudo)chars and ranges, and possibly a negation flag. These are     // collectively returned by parseCharset().     // This piece can be structured differently depending on your     // implementation of parseCharset()     var opts = this.parseCharset();     // This MUST be a ] or something went wrong.     this.eat(']');     return new CharsetTree(opts);   } else {     // Parse a literal. Like a CharsetTree, a LiteralTree doesn't have     // children. Instead, it contains a single (pseudo)char.     var literal = this.parseLiteral();     return new LiteralTree(literal);   } };  // This parses the inside of a charset and returns all the information // necessary to describe that charset. This includes the literals and // ranges that are accepted, as well as whether the charset is negated. Parser.prototype.parseCharset = function() {   // challenging exercise };  // This parses a single (pseudo)char and returns it for use in a LiteralTree. Parser.prototype.parseLiteral = function() {   var c = this.next();   if (c === '.' || c === '^' || c === '$') {     // These are special chars. Their meaning is different than their     // literal symbol, so we set the 'special' flag.     return new CharInfo(c, true);   } else if (c === '\\') {     // If we come across a \, we need to parse the escaped character.     // Since parsing escaped characters is similar between literals and     // charsets, we extracted it to a separate function. The reason we     // pass a flag is because \b has different meanings inside charsets     // vs outside them.     return this.parseEscaped({inCharset: false});   }   // If neither case above was hit, we just return the exact char.   return new CharInfo(c); };  // This parses a single escaped (pseudo)char and returns it for use in // either a LiteralTree or a CharsetTree. Parser.prototype.parseEscaped = function(opts) {   // Here we instantiate some default options   opts = opts || {};   inCharset = opts.inCharset || false;    var c = peek();   // Here are a bunch of escape sequences that require reading further   // into the string. They are all fairly similar.   if (c === 'c') { // exercises   } else if (c === '0') {   } else if (isDigit(c)) {   } else if (c === 'x') {   } else if (c === 'u') {     // Use this as an example for implementing the ones above.     // A regex may be used for this portion, but I think this is clearer.     // We make sure that there are exactly four hexadecimal digits after     // the u. Modify this for the escape sequences that your regex flavor     // uses.     var r = '';     this.next();     for (var i = 0; i < 4; ++i) {       c = peek();       if (!isHexa(c)) {         throw new Error();       }       r += c;       this.next();     }     // Return a single CharInfo desite having read multiple characters.     // This is why I used "pseudo" previously.     return new CharInfo(String.fromCharCode(parseInt(r, 16)));   } else { // No special parsing required after the first escaped char.     this.next();     if (inCharset && c === 'b') {       // Within a charset, \b means backspace       return new CharInfo('\b');     } else if (!inCharset && (c === 'b' || c === 'B')) {       // Outside a charset, \b is a word boundary (and \B is the complement       // of that). We mark it one as special since the character is not       // to be taken literally.       return new CharInfo('\\' + c, true);     } else if (c === 'f') { // these are left as exercises     } else if (c === 'n') {     } else if (c === 'r') {     } else if (c === 't') {     } else if (c === 'v') {     } else if ('dDsSwW'.indexOf(c) !== -1) {     } else {       // If we got to here, the character after \ should be taken literally,       // so we don't mark it as special.       return new CharInfo(c);     }   } };  // This represents the smallest meaningful character unit, or pseudochar. // For example, an escaped sequence with multiple physical characters is // exactly one character when used in CharInfo. var CharInfo = function(c, special) {   this.c = c;   this.special = special || false; };  // Calling this will return the parse tree for the regex string s. var parse = function(s) { return (new Parser(s)).parseRe(); }; 

Answer 2

The perl module YAPE::Regex::Explain module can probably be ported to PHP pretty easy. Here is an example of its output

C:\>perl -e "use YAPE::Regex::Explain;print YAPE::Regex::Explain->new(qr/['-])->explain;"
The regular expression:

(?-imsx:['-])

matches as follows:

NODE                     EXPLANATION
----------------------------------------------------------------------
(?-imsx:                 group, but do not capture (case-sensitive)
                         (with ^ and $ matching normally) (with . not
                         matching \n) (matching whitespace and #
                         normally):
----------------------------------------------------------------------
  ['-]                     any character of: ''', '-'
----------------------------------------------------------------------
)                        end of grouping
----------------------------------------------------------------------



C:\>perl -e "use YAPE::Regex::Explain; print YAPE::Regex::Explain->new(qr/(\w+), ?(.)/)->explain;"
The regular expression:

(?-imsx:(\w+), ?(.))

matches as follows:

NODE                     EXPLANATION
----------------------------------------------------------------------
(?-imsx:                 group, but do not capture (case-sensitive)
                         (with ^ and $ matching normally) (with . not
                         matching \n) (matching whitespace and #
                         normally):
----------------------------------------------------------------------
  (                        group and capture to \1:
----------------------------------------------------------------------
    \w+                      word characters (a-z, A-Z, 0-9, _) (1 or
                             more times (matching the most amount
                             possible))
----------------------------------------------------------------------
  )                        end of \1
----------------------------------------------------------------------
  ,                        ','
----------------------------------------------------------------------
   ?                       ' ' (optional (matching the most amount
                           possible))
----------------------------------------------------------------------
  (                        group and capture to \2:
----------------------------------------------------------------------
    .                        any character except \n
----------------------------------------------------------------------
  )                        end of \2
----------------------------------------------------------------------
)                        end of grouping
----------------------------------------------------------------------

C:\>

You can look at the source code and quickly see the implementation.

Answer 3

What you need is a grammar and a way to generate a parser for it. The easiest approach to producing a parser is to code a recursive descent directly in your target language (e.g., in PHP), in which you build a clean parser that is shaped exactly like your grammar (which makes the parser maintainable, too).

Lots of details on how do to this, once you have a grammar, are provided in my SO description of how to build recursive descent parsers and additional theory details here

As for regex grammars, a simple grammar (maybe not the one you had in mind) is:

REGEX =  ALTERNATIVES ;
ALTERNATIVES = TERM ( '|' TERM )* ;
TERM = '(' ALTERNATIVES ')' |  CHARACTER | SET | TERM ( '*' | '+' | '?' ) ;
SET = '~' ? '[' ( CHARACTER | CHARACTER '-' CHARACTER )* ']' ;
CHARACTER = 'A' | 'B' | ... | '0' ... '9' | ...  ;

A recursive descent parser written in PHP to process this grammar should be on the order of few hundred lines, max.

Given this as a starting place, you should be able to add the features of PHP Regexes to it.

Happy parsing!