Парсер для регулярных выражений в PHP?

Ответ 1

Я создатель 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 this содержит всю необходимую информацию. Я думаю, что вы очень хорошо на своем пути с вашим парсером; все, что остается, - это реализовать остальные операторы и получить правильные кромки.

:) Наслаждайтесь:

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

Ответ 2

Модуль 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:\>

Вы можете посмотреть исходный код и быстро увидеть реализацию.

Ответ 3

Вам нужна грамматика и способ генерации парсера для нее. Самый простой подход к созданию парсера - это кодирование рекурсивного спуска непосредственно на вашем целевом языке (например, на PHP), в котором вы создаете чистый парсер, который сформирован точно так же, как и ваша грамматика (что также позволяет поддерживать парсер).

Подробные сведения о том, как сделать это, как только у вас есть грамматика, приведены в моем SO описании того, как создавать рекурсивные партизаны спуска, и дополнительные подробности теории здесь

Что касается грамматик регулярных выражений, простая грамматика (возможно, не та, о которой вы имели в виду):

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

Рекурсивный парсер спуска, написанный на PHP для обработки этой грамматики, должен быть порядка нескольких сотен строк, максимальный

Учитывая это как исходное место, вы должны добавить в него функции PHP Regexes.

Счастливый разбор!

Ответ 4

Вам может быть интересен проект, который я сделал прошлым летом. Это Javascript-программа, которая обеспечивает динамическое синтаксическое выделение регулярных выражений, совместимых с PCRE:

Смотрите: Динамическое (?: выделение регулярных выражений) ++ с помощью Javascript!
и связанная страница тестера
и Страница проекта GitHub

В коде используется регулярное выражение (Javascript) для выделения (регулярного выражения) в его различных частях и применяется разметка, чтобы пользователь мог наводить курсор мыши на различные компоненты и видеть соответствующие скобки и номера групп захвата.

(Я написал его с помощью регулярного выражения, потому что я не знал ничего лучшего! 8 ^)

Ответ 5

Хорошо, вы можете взглянуть на реализацию регулярных выражений в php. Поскольку php является проектом с открытым исходным кодом, все источники и документация доступны для общественности.

Ответ 6

Я бы попытался перевести библиотеку регулярных выражений ActionScript 1/2 на PHP. Более ранние версии Flash не поддерживали поддержку регулярных выражений, поэтому в AS существует несколько библиотек, написанных в AS. Перевод с одного динамического языка на другой должен быть намного проще, чем пытаться расшифровать C.

Здесь, возможно, стоит посмотреть одну ссылку: http://www.jurjans.lv/flash/RegExp.html