Implemente o PCRE no seu idioma.

13

Nota: Depois de tentar isso sozinho, logo percebi o que era um erro. Portanto, estou modificando um pouco as regras.

A funcionalidade mínima necessária:

  • Classes de personagens ( ., \w, \W, etc.)
  • Multiplicadores ( +, *, e ?)
  • Grupos de captura simples

Seu desafio é implementar o PCRE no idioma de sua escolha, sujeito às seguintes condições:

  • Você não pode usar as instalações RegEx nativas do seu idioma de forma alguma . Você também não pode usar uma biblioteca RegEx de terceiros.
  • Sua entrada deve implementar o máximo das especificações do PCRE. que possível.

  • Seu programa deve aceitar como entrada, 2 linhas:

    • a expressão regular
    • a entrada de string para combinar

  • Seu programa deve indicar em sua saída:

    • Se o RegEx correspondeu a qualquer lugar da sequência de entrada
    • Os resultados de qualquer grupo de captura

  • O vencedor será a entrada que implementa o máximo de especificações. que possível. Em caso de empate, o vencedor será a inscrição mais criativa, conforme julgado por mim.

Edit: para esclarecer algumas coisas, aqui estão alguns exemplos de entrada e saída esperada:

  • Entrada:
^ \ s * (\ w +) $
         Olá
  • Resultado:
Correspondências: sim
Grupo 1: 'olá'
  • Entrada:
(\ w +) @ (\ w +) (?: \ .com | \ .net)
[email protected]
  • Resultado:
Correspondências: sim
Grupo 1: 'sam'
Grupo 2: 'teste'
code-challenge regular-expression Nathan Osman
fonte
Esse é um desafio realmente desafiador, dada a quantidade de recursos no PCRE. Recursão, retrocesso, lookahead / afirmações, Unicode, subpadrões condicionais, ...
Arnaud Le Blanc
1
Veja os documentos do PCRE ; PERL RE ; Os documentos PHP PCRE também são ótimos.
Arnaud Le Blanc
@ user300: O objetivo é implementar o máximo possível. Obviamente tudo seria um pouco difícil demais.
Nathan Osman
2
@ George: Que tal você listar os recursos que você deseja e fornecer alguns casos de teste, apenas para que estejamos todos no mesmo terreno.
Marko Dumic
1
@ George: Eu acho que o @ Marko estava atrás de recursos específicos, ou melhor, o subconjunto mínimo que você gostaria que as pessoas implementassem primeiro. No geral, porém, o PCRE é realmente um desafio muito difícil para uma competição de codificação casual. Sugiro mudar isso para um subconjunto específico de ER muito pequeno e fazer o desafio de implementar.
MtnViewMark 22/02

Respostas:

10

Pitão

Como implementar o PCRE completo é demais, implementei apenas um subconjunto essencial dele.

Suporta |.\.\w\W\s+*(). Regexp de entrada deve estar correto.

Exemplos:

$ 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

Como funciona:

Para uma teoria detalhada, leia esta Introdução à Teoria dos Autômatos, Idiomas e Computação .

A idéia é converter a expressão regular original em um autômato finito não-determinista (NFA). Na verdade, as expressões regulares do PCRE são pelo menos gramáticas livres de contexto para as quais precisamos de autômatos push-down, mas nos limitaremos a um subconjunto do PCRE.

Autômatos finitos são gráficos direcionados nos quais os nós são estados, as arestas são transições e cada transição possui uma entrada correspondente. Inicialmente, você inicia a partir de um nó inicial, predefinido. Sempre que você recebe uma entrada que corresponde a uma transição, você a transfere para um novo estado. Se você alcançou um nó de terminal, é chamado de entrada automática aceita. No nosso caso, a entrada é uma função correspondente que retorna true.

Eles são chamados de autômatos não deterministas porque, às vezes, há transições mais correspondentes que você pode realizar do mesmo estado. Na minha implementação, toda transição para o mesmo estado deve corresponder à mesma coisa, então eu armazenei a função de correspondência junto com o estado de destino ( states[dest][0]).

Transformamos nossa regexp em um autômato finito usando blocos de construção. Um bloco de construção possui um nó inicial ( first) e um nó final ( last) e corresponde a algo do texto (possível sequência vazia).

Os exemplos mais simples incluem

  • não corresponde a nada: True( first == last)
  • combinando um caractere: c == txt[pos]( first == last)
  • fim da sequência correspondente: pos == len (txt) (first == last`)

Você também precisará da nova posição no texto onde corresponder ao próximo token.

Exemplos mais complicados são (letras maiúsculas representam blocos).

  • B + correspondente:

    • criar nós: u, v (que não corresponde a nada)
    • criar transições: u -> B.first, B.último -> v, v -> u
    • quando você chega ao nó v, você já corresponde a B. Em seguida, você tem duas opções: vá mais longe ou tente corresponder B novamente.

  • combinando A | B | C:

    • criar nós: u, v (que não corresponde a nada)
    • criar transições: u -> A.first, u -> C.first, u -> C.first,
    • criar transições: A-> último -> v, B-> último -> v, C-> último -> v,
    • de você você pode ir para qualquer bloco

Todos os operadores regexp podem ser transformados assim. Apenas tente *.

A última parte é analisar o regexp, que requer uma gramática muito simples:

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

Espero que implementar uma gramática simples (acho que seja LL (1), mas me corrija se estiver errado) é muito mais fácil do que criar um NFA.

Depois de ter o NFA, você precisa voltar atrás até chegar ao nó do terminal.

Código fonte (ou aqui ):

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
fonte
1
+1 Uau ... Eu tentei fazer isso sozinho com PHP e falhei completamente.
Nathan Osman
TIL (a+b)+corresponde abaabaaabaaaab.
Alexandru