PHP中正则表达式的解析器？

我是 Debuggex 的创建者，其要求与您的要求非常相似：针对可以显示的信息量进行优化。

下面是 Debuggex 使用的解析器中经过大量修改（用于可读性）的代码段。它不是按原样工作的，但旨在演示代码的组织。删除了大部分错误处理。许多直截了当但冗长的逻辑也是如此。

请注意，使用递归下降。这是您在解析器中所做的，除了您的解析器被扁平化为单个函数。我用了大约这个语法来表达我的语法：

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)? '}'

你会注意到我的很多代码只是在处理正则表达式的javascript风格的特殊性。您可以在此参考中找到有关它们的更多信息。对于 PHP，它具有您需要的所有信息。我认为你在使用解析器方面做得很好;剩下的就是实现其余的运算符并正确处理边缘情况。

:)享受：

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(); };

perl 模块 YAPE：：Regex：：Explain 模块可能可以很容易地移植到 PHP 上。下面是其输出的示例

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:\>

您可以查看源代码并快速查看实现。