PHP 中的正则表达式解析器? [英] A parser for regular expressions in PHP?

问题描述

我需要在 PHP 中将正则表达式解析为它们的组件.我创建或执行正则表达式没有问题，但我想显示有关正则表达式的信息(例如，列出捕获组，将重复字符附加到其目标，...).整个项目是一个 WordPress 插件，它提供有关重写规则的信息，这些规则是具有替换模式的正则表达式，并且可能难以理解.

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.

推荐答案

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

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

下面是来自 Debuggex 使用的解析器的经过大量修改(为了可读性)的片段.它不能按原样工作，但旨在演示代码的组织.大多数错误处理已被删除.许多简单但冗长的逻辑也是如此.

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

您会注意到我的很多代码只是处理 javascript 风格的正则表达式的特殊性.您可以在此参考资料中找到有关它们的更多信息.对于 PHP，this 包含您需要的所有信息.我认为您的解析器进展顺利；剩下的就是实现其余的运算符并正确处理边缘情况.

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.

:) 享受:

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  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,  means backspace
      return new CharInfo('');
    } else if (!inCharset && (c === 'b' || c === 'B')) {
      // Outside a charset,  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(); };

这篇关于PHP 中的正则表达式解析器?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！