que - ¿Un analizador para expresiones regulares en PHP?

probar expresiones regulares

Question

Necesito analizar expresiones regulares en sus componentes en PHP. No tengo problemas para crear las expresiones regulares o ejecutarlas, pero quiero mostrar información sobre la expresión regular (por ejemplo, enumerar los grupos de captura, adjuntar caracteres de repetición a sus objetivos, ...). El proyecto general es un complemento para WordPress que proporciona información sobre las reglas de reescritura, que son expresiones regulares con patrones de sustitución y pueden ser crípticos para comprender.

Yo mismo he escrito una implementación simple , que parece manejar las expresiones regulares simples que le lanzo y las convierto en árboles de sintaxis. Antes de expandir este ejemplo para admitir más la sintaxis de expresiones regulares, me gustaría saber si hay otras implementaciones buenas que pueda ver. El lenguaje de implementación realmente no importa. Supongo que la mayoría de los analizadores están escritos para optimizar la velocidad de coincidencia, pero eso no es importante para mí, e incluso puede dificultar la claridad.

Answer 1

Bueno, puedes echar un vistazo a la implementación de las funciones de expresiones regulares en php. Como PHP es un proyecto de código abierto, todas las fuentes y la documentación están disponibles al público.

Answer 2

El módulo perl YAPE::Regex::Explain probablemente se pueda portar a PHP bastante fácil. Aquí hay un ejemplo de su salida.

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

Puedes mirar el código fuente y ver rápidamente la implementación.

Answer 3

Intentaría traducir una biblioteca de expresiones regulares ActionScript 1/2 a PHP. Las versiones anteriores de Flash no tenían soporte nativo para expresiones regulares, así que hay algunas bibliotecas escritas en AS. La traducción de un lenguaje dinámico a otro debería ser mucho más fácil que tratar de descifrar C.

Aquí hay un enlace que quizás vale la pena ver: http://www.jurjans.lv/flash/RegExp.html

Answer 4

Lo que necesitas es una gramática y una forma de generar un analizador para ella. El enfoque más sencillo para producir un analizador es codificar un descenso recursivo directamente en su idioma de destino (por ejemplo, en PHP), en el que crea un analizador limpio que tiene la forma exactamente igual a su gramática (lo que hace que el analizador también sea mantenible).

Muchos detalles sobre cómo hacer esto, una vez que tenga una gramática, se proporcionan en mi descripción SO de cómo construir analizadores de descendencia recursivos y detalles teóricos adicionales aquí

En cuanto a las gramáticas regex, una gramática simple (tal vez no la que tenías en mente) es:

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

Un analizador de descenso recursivo escrito en PHP para procesar esta gramática debe ser del orden de unos cientos de líneas, máx.

Dado que esto es un punto de partida, deberías poder agregarle las características de PHP Regexes.

¡Feliz análisis!

Answer 5

Quizás te interese un proyecto que hice el verano pasado. Es un programa de Javascript que proporciona resaltado de sintaxis dinámico de expresiones regulares compatibles con PCRE:

Ver: Dynamic (?: Regex Highlighting) ++ con Javascript!
y la página de prueba asociada
y la página del proyecto GitHub

El código usa expresiones regulares (Javascript) para separar las expresiones regulares (PCRE) en sus distintas partes y aplica el marcado para permitir al usuario pasar el mouse sobre varios componentes y ver los corchetes correspondientes y capturar números de grupos.

(Lo escribí usando expresiones regulares porque no conocía nada mejor! 8 ^)

Answer 6

Soy el creador de Debuggex , cuyos requisitos son muy similares a los tuyos: optimiza la cantidad de información que se puede mostrar.

A continuación se muestra un fragmento muy modificado (para lectura) del analizador que utiliza Debuggex. No funciona como está, pero está destinado a demostrar la organización del código. Se eliminó la mayor parte del manejo de errores. Así eran muchas piezas de lógica que eran sencillas pero verbosas.

Tenga en cuenta que se utiliza el descenso recursivo . Esto es lo que has hecho en tu analizador, excepto que el tuyo se aplana en una sola función. Usé aproximadamente esta gramática para la mía:

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

Notarás que gran parte de mi código solo trata con las peculiaridades del sabor javascript de las expresiones regulares. Puede encontrar más información sobre ellos en esta referencia . Para PHP, this tiene toda la información que necesitas. Creo que estás muy bien en tu camino con tu analizador; todo lo que queda es implementar el resto de los operadores y solucionar los casos de vanguardia.

:) Disfrutar:

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