Implemente PCRE en su idioma.

13

Nota: Después de probar esto yo mismo, pronto me di cuenta del error que era. Por lo tanto, estoy modificando un poco las reglas.

La funcionalidad mínima requerida:

  • Las clases de caracteres ( ., \w, \W, etc.)
  • Los multiplicadores ( +, *y ?)
  • Grupos de captura simples

Su desafío es implementar PCRE en el idioma de su elección sujeto a las siguientes condiciones:

  • No puede utilizar las instalaciones RegEx nativas de su idioma de ninguna manera . Tampoco puede usar una biblioteca RegEx de terceros.
  • Su entrada debe implementar tanto de la especificación PCRE. como sea posible.

  • Su programa debe aceptar como entrada, 2 líneas:

    • la expresión regular
    • la entrada de cadena para que coincida con

  • Su programa debe indicar en su salida:

    • Si el RegEx coincide en alguna parte de la cadena de entrada
    • Los resultados de cualquier grupo de captura

  • El ganador será la entrada que implemente la mayor parte de la especificación. como sea posible. En caso de empate, el ganador será la entrada más creativa, según mi criterio.

Editar: para aclarar algunas cosas, aquí hay algunos ejemplos de entrada y salida esperada:

  • Entrada:
^ \ s * (\ w +) $
         Hola
  • Salida:
Coincidencias: sí
Grupo 1: 'hola'
  • Entrada:
(\ w +) @ (\ w +) (?: \. com | \ .net)
[email protected]
  • Salida:
Coincidencias: sí
Grupo 1: 'sam'
Grupo 2: 'prueba'
code-challenge regular-expression Nathan Osman
fuente
Ese es un desafío realmente desafiante, dada la cantidad de características en PCRE. Recursion, backtracking, lookahead / aserciones, unicode, subpatterns condicional, ...
Arnaud Le Blanc
1
Ver documentos PCRE ; PERL RE ; Los documentos PHP PCRE también son geniales.
Arnaud Le Blanc
@ user300: El objetivo es implementar tanto como sea posible. Obviamente todo sería demasiado difícil.
Nathan Osman
2
@George: ¿Qué tal si enumeras las características que deseas y das algunos casos de prueba, solo para que todos estemos en terreno parejo?
Marko Dumic
1
@George: Creo que @Marko buscaba características específicas, o más bien, el subconjunto mínimo que querría que las personas implementaran primero. En general, sin embargo, PCRE es realmente un desafío demasiado difícil para una competencia de codificación casual. Sugiero cambiar esto a un subconjunto RE muy pequeño y específico, y hacer el desafío de implementar.
MtnViewMark

Respuestas:

10

Pitón

Como implementar PCRE completo es demasiado, implementé solo un subconjunto esencial del mismo.

Soportes |.\.\w\W\s+*(). La expresión regular de entrada debe ser correcta.

Ejemplos:

$ python regexp.py 
^\s*(\w+)$
   hello
Matches:     hello
Group 1 hello

$ python regexp.py
(a*)+
infinite loop

$ python regexp.py 
(\w+)@(\w+)(\.com|\.net)
[email protected]
Matches:  [email protected]
Group 1 sam
Group 2 test
Group 3 .net

Cómo funciona:

Para una teoría detallada, lea esta Introducción a la teoría de los autómatas, los idiomas y la computación .

La idea es convertir la expresión regular original en un autómata finito no determinista (NFA). En realidad, las expresiones regulares de PCRE son al menos gramáticas libres de contexto para las cuales necesitamos autómatas pushdown, pero nos limitaremos a un subconjunto de PCRE.

Los autómatas finitos son gráficos dirigidos en los que los nodos son estados, los bordes son transiciones y cada transición tiene una entrada coincidente. Inicialmente comienza desde un nodo de inicio, predefinido. Cada vez que recibe una entrada que coincide con una de las transiciones, lleva esa transición a un nuevo estado. Si llegó a un nodo terminal, se llama entrada de autómata aceptada. En nuestro caso, la entrada es una función coincidente que devuelve verdadero.

Se llaman autómatas no deterministas porque a veces hay más transiciones coincidentes que puede tomar del mismo estado. En mi implementación, toda transición al mismo estado debe coincidir con la misma cosa, por lo que almacené la función de coincidencia junto con el estado de destino ( states[dest][0]).

Transformamos nuestra expresión regular en un autómata finito utilizando bloques de construcción. Un bloque de creación tiene un nodo inicial ( first) y un nodo final ( last) y coincide con algo del texto (posible cadena vacía).

Los ejemplos más simples incluyen

  • nada coincidente: True( first == last)
  • emparejar un personaje: c == txt[pos]( first == last)
  • final de cadena coincidente: pos == len (txt) (first == last`)

También necesitará la nueva posición en el texto donde coincidir con el próximo token.

Ejemplos más complicados son (las letras mayúsculas representan bloques).

  • B + a juego:

    • crear nodos: u, v (sin coincidencia)
    • crear transiciones: u -> B.first, B.last -> v, v -> u
    • cuando llegas al nodo v, ya has coincidido con B. Entonces tienes dos opciones: ir más allá o intentar hacer coincidir B nuevamente.

  • coincidencia A | B | C:

    • crear nodos: u, v (sin coincidencia)
    • crear transiciones: u -> A.first, u -> C.first, u -> C.first,
    • crear transiciones: A-> último -> v, B-> último -> v, C-> último -> v,
    • desde usted puede ir a cualquier bloque

Todos los operadores regexp pueden transformarse así. Solo inténtalo *.

La última parte es analizar la expresión regular que requiere una gramática muy simple:

 or: seq ('|' seq)*
 seq: empty
 seq: atom seq
 seq: paran seq
 paran: '(' or ')'

Con suerte, implementar una gramática simple (creo que es LL (1), pero corrígeme si me equivoco) es mucho más fácil que construir un NFA.

Una vez que tenga el NFA, debe retroceder hasta llegar al nodo terminal.

Código fuente (o aquí ):

from functools import *

WORDCHAR = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ01234567890_'


def match_nothing(txt, pos):
  return True, pos

def match_character(c, txt, pos):
  return pos < len(txt) and txt[pos] == c, pos + 1

def match_space(txt, pos):
  return pos < len(txt) and txt[pos].isspace(), pos + 1

def match_word(txt, pos):
  return pos < len(txt) and txt[pos] in WORDCHAR, pos + 1

def match_nonword(txt, pos):
  return pos < len(txt) and txt[pos] not in WORDCHAR, pos + 1

def match_dot(txt, pos):
  return pos < len(txt), pos + 1

def match_start(txt, pos):
  return pos == 0, pos

def match_end(txt, pos):
  return pos == len(txt), pos


def create_state(states, match=None, last=None, next=None, name=None):
  if next is None: next = []
  if match is None: match = match_nothing

  state = len(states)
  states[state] = (match, next, name)
  if last is not None:
    states[last][1].append(state)

  return state


def compile_or(states, last, regexp, pos):
  mfirst = create_state(states, last=last, name='or_first')
  mlast = create_state(states, name='or_last')

  while True:
    pos, first, last = compile_seq(states, mfirst, regexp, pos)
    states[last][1].append(mlast)
    if pos != len(regexp) and regexp[pos] == '|':
      pos += 1
    else:
      assert pos == len(regexp) or regexp[pos] == ')'
      break

  return pos, mfirst, mlast


def compile_paren(states, last, regexp, pos):
  states.setdefault(-2, [])   # stores indexes
  states.setdefault(-1, [])   # stores text

  group = len(states[-1])
  states[-2].append(None)
  states[-1].append(None)

  def match_pfirst(txt, pos):
    states[-2][group] = pos
    return True, pos

  def match_plast(txt, pos):
    old = states[-2][group]
    states[-1][group] = txt[old:pos]
    return True, pos

  mfirst = create_state(states, match=match_pfirst, last=last, name='paren_first')
  mlast = create_state(states, match=match_plast, name='paren_last')

  pos, first, last = compile_or(states, mfirst, regexp, pos)
  assert regexp[pos] == ')'

  states[last][1].append(mlast)
  return pos + 1, mfirst, mlast


def compile_seq(states, last, regexp, pos):
  first = create_state(states, last=last, name='seq')
  last = first

  while pos < len(regexp):
    p = regexp[pos]
    if p == '\\':
      pos += 1
      p += regexp[pos]

    if p in '|)':
      break

    elif p == '(':
      pos, first, last = compile_paren(states, last, regexp, pos + 1)

    elif p in '+*':
      # first -> u ->...-> last -> v -> t
      # v -> first (matches at least once)
      # first -> t (skip on *)
      # u becomes new first
      # first is inserted before u

      u = create_state(states)
      v = create_state(states, next=[first])
      t = create_state(states, last=v)

      states[last][1].append(v)
      states[u] = states[first]
      states[first] = (match_nothing, [[u], [u, t]][p == '*'])

      last = t
      pos += 1

    else:  # simple states
      if p == '^':
    state = create_state(states, match=match_start, last=last, name='begin')
      elif p == '$':
    state = create_state(states, match=match_end, last=last, name='end')
      elif p == '.':
    state = create_state(states, match=match_dot, last=last, name='dot')
      elif p == '\\.':
    state = create_state(states, match=partial(match_character, '.'), last=last, name='dot')
      elif p == '\\s':
    state = create_state(states, match=match_space, last=last, name='space')
      elif p == '\\w':
    state = create_state(states, match=match_word, last=last, name='word')
      elif p == '\\W':
    state = create_state(states, match=match_nonword, last=last, name='nonword')
      elif p.isalnum() or p in '_@':
    state = create_state(states, match=partial(match_character, p), last=last, name='char_' + p)
      else:
    assert False

      first, last = state, state
      pos += 1

  return pos, first, last


def compile(regexp):
  states = {}
  pos, first, last = compile_or(states, create_state(states, name='root'), regexp, 0)
  assert pos == len(regexp)
  return states, last


def backtrack(states, last, string, start=None):
  if start is None:
    for i in range(len(string)):
      if backtrack(states, last, string, i):
    return True
    return False

  stack = [[0, 0, start]]   # state, pos in next, pos in text
  while stack:
    state = stack[-1][0]
    pos = stack[-1][2]
    #print 'in state', state, states[state]

    if state == last:
      print 'Matches: ', string[start:pos]
      for i in xrange(len(states[-1])):
    print 'Group', i + 1, states[-1][i]
      return True

    while stack[-1][1] < len(states[state][1]):
      nstate = states[state][1][stack[-1][1]]
      stack[-1][1] += 1

      ok, npos = states[nstate][0](string, pos)
      if ok:
    stack.append([nstate, 0, npos])
    break
      else:
    pass
    #print 'not matched', states[nstate][2]
    else:
      stack.pop()

  return False



# regexp = '(\\w+)@(\\w+)(\\.com|\\.net)'
# string = '[email protected]'
regexp = raw_input()
string = raw_input()

states, last = compile(regexp)
backtrack(states, last, string)
Alexandru
fuente
1
+1 Wow ... Traté de hacer esto yo mismo con PHP y fallé por completo.
Nathan Osman
TIL (a+b)+coincide abaabaaabaaaab.
Alexandru