Implémentez PCRE dans votre langue.

13

Remarque: Après avoir essayé cela moi-même, j'ai vite réalisé à quel point c'était une erreur. Par conséquent, je modifie un peu les règles.

La fonctionnalité minimale requise:

  • Les classes de caractères ( ., \w,\W , etc.)
  • Multiplicateurs ( +, *et? )
  • Groupes de capture simples

Votre défi est d'implémenter PCRE dans la langue de votre choix sous les conditions suivantes:

  • Vous ne pouvez pas utiliser dans des installations RegEx natifs de votre langue toute façon . Vous ne pouvez pas non plus utiliser une bibliothèque RegEx tierce.
  • Votre entrée doit implémenter autant de la spécification PCRE. que possible.

  • Votre programme doit accepter en entrée, 2 lignes:

    • l'expression régulière
    • l'entrée de chaîne à comparer

  • Votre programme doit indiquer dans sa sortie:

    • Si le RegEx correspond à n'importe où dans la chaîne d'entrée
    • Les résultats de tous les groupes de capture

  • Le gagnant sera l'entrée qui implémentera autant de spécifications. que possible. En cas d'égalité, le gagnant sera la participation la plus créative, selon moi.

Edit: pour clarifier quelques points, voici quelques exemples d'entrées et de sorties attendues:

  • Contribution:
^ \ s * (\ w +) $
         Bonjour
  • Production:
Matchs: oui
Groupe 1: «bonjour»
  • Contribution:
(\ w +) @ (\ w +) (?: \. com | \ .net)
[email protected]
  • Production:
Matchs: oui
Groupe 1: «sam»
Groupe 2: «test»
code-challenge regular-expression Nathan Osman
la source
C'est un défi vraiment difficile, compte tenu de la quantité de fonctionnalités de PCRE. Récursion, retour arrière, anticipation / assertions, unicode, sous-modèles conditionnels, ...
Arnaud Le Blanc
1
Voir les documents PCRE ; PERL RE ; Les documents PHP PCRE sont également excellents.
Arnaud Le Blanc
@ user300: L'objectif est d'implémenter autant que possible. Évidemment, tout serait un peu trop dur.
Nathan Osman
2
@George: Que diriez-vous de lister les fonctionnalités que vous voulez et de donner quelques cas de test, juste pour que nous soyons tous sur un pied d'égalité.
Marko Dumic
1
@George: Je pense que @Marko était après des fonctionnalités spécifiques, ou plutôt, le sous-ensemble minimal que vous voudriez que les gens implémentent en premier. Dans l'ensemble, cependant, PCRE est vraiment un défi beaucoup trop difficile pour un concours de codage occasionnel. Je suggère de changer cela en un très petit sous-ensemble RE spécifique, et de faire le défi de l'implémenter.
MtnViewMark

Réponses:

10

Python

Étant donné que la mise en œuvre de PCRE complet est trop, je n'en ai implémenté qu'un sous-ensemble essentiel.

Prise en charge |.\.\w\W\s+*(). L'expression rationnelle d'entrée doit être correcte.

Exemples:

$ 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

Comment ça fonctionne:

Pour une théorie détaillée, lisez cette introduction à la théorie des automates, aux langages et au calcul .

L'idée est de convertir l'expression régulière d'origine en automates finis non déterministes (NFA). En fait, les expressions régulières PCRE sont au moins des grammaires sans contexte pour lesquelles nous avons besoin d'automates déroulants, mais nous nous limiterons à un sous-ensemble de PCRE.

Les automates finis sont des graphes dirigés dans lesquels les nœuds sont des états, les arêtes sont des transitions et chaque transition a une entrée correspondante. Au départ, vous démarrez à partir d'un nœud de démarrage, prédéfini. Chaque fois que vous recevez une entrée correspondant à l'une des transitions, vous passez cette transition à un nouvel état. Si vous avez atteint un nœud terminal, il est appelé cette entrée acceptée par les automates. Dans notre cas, l'entrée est une fonction de correspondance qui renvoie vrai.

Ils sont appelés automates non déterministes car il existe parfois plus de transitions correspondantes que vous pouvez prendre à partir du même état. Dans mon implémentation, toute transition vers le même état doit correspondre à la même chose, j'ai donc stocké la fonction correspondante avec l'état de destination ( states[dest][0]).

Nous transformons notre expression rationnelle en automates finis en utilisant des blocs de construction. Un bloc de construction a un nœud de départ (first ) et un nœud de fin (last ) et correspond à quelque chose du texte (chaîne vide possible).

Les exemples les plus simples incluent

  • ne correspondant à rien: True (first == last )
  • correspondant à un caractère: c == txt[pos] (first == last )
  • fin de chaîne correspondante: pos == len (txt)( first == last`)

Vous aurez également besoin de la nouvelle position dans le texte où faire correspondre le prochain jeton.

Des exemples plus compliqués sont (les majuscules représentent les blocs).

  • B + correspondant:

    • créer des nœuds: u, v (ne correspondant à rien)
    • créer des transitions: u -> B.first, B.last -> v, v -> u
    • lorsque vous arrivez au nœud v, vous avez déjà mis en correspondance B. Ensuite, vous avez deux options: allez plus loin ou essayez de faire correspondre B à nouveau.

  • correspondant à A | B | C:

    • créer des nœuds: u, v (ne correspondant à rien)
    • créer des transitions: u -> A.first, u -> C.first, u -> C.first,
    • créer des transitions: A-> dernier -> v, B-> dernier -> v, C-> dernier -> v,
    • à partir de vous, vous pouvez aller à n'importe quel bloc

Tous les opérateurs d'expression rationnelle peuvent être transformés comme ceci. Essayez juste *.

La dernière partie consiste à analyser l'expression rationnelle qui nécessite une grammaire très simple:

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

Espérons que la mise en œuvre d'une grammaire simple (je pense que c'est LL (1), mais corrigez-moi si je me trompe) est beaucoup plus facile que de construire un NFA.

Une fois que vous avez le NFA, vous devez revenir en arrière jusqu'à ce que vous atteigniez le nœud terminal.

Code source (ou ici ):

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
la source
1
+1 Wow ... J'ai essayé de le faire moi-même avec PHP et j'ai complètement échoué.
Nathan Osman
(a+b)+Matchs TIL abaabaaabaaaab.
Alexandru