Implementieren Sie PCRE in Ihrer Sprache.

13

Hinweis: Nachdem ich das selbst ausprobiert hatte, wurde mir schnell klar, was für ein Fehler das war. Deshalb ändere ich die Regeln ein wenig.

Die minimal erforderliche Funktionalität:

  • Charakterklassen ( ., \w, \W, etc.)
  • Multipliers ( +, *, und ?)
  • Einfache Erfassungsgruppen

Ihre Herausforderung besteht darin, PCRE in der Sprache Ihrer Wahl unter den folgenden Bedingungen zu implementieren :

  • Sie dürfen die systemeigenen RegEx-Funktionen Ihrer Sprache in keiner Weise verwenden . Sie dürfen auch keine RegEx-Bibliothek eines Drittanbieters verwenden.
  • Ihr Eintrag sollte so viel von der PCRE-Spezifikation implementieren. wie möglich.

  • Ihr Programm sollte als Eingabe 2 Zeilen akzeptieren:

    • der reguläre Ausdruck
    • die Zeichenfolge, mit der verglichen werden soll

  • Ihr Programm sollte in seiner Ausgabe Folgendes angeben:

    • Stimmt die RegEx mit der Eingabezeichenfolge überein?
    • Die Ergebnisse aller Erfassungsgruppen

  • Der Gewinner ist der Beitrag, der einen Großteil der Spezifikation implementiert. wie möglich. Im Falle eines Gleichstands ist der Gewinner nach meiner Einschätzung der kreativste Beitrag.

Bearbeiten: um ein paar Dinge zu klären, sind hier einige Beispiele für Eingaben und erwartete Ausgaben:

  • Eingang:
^ \ s * (\ w +) $
         Hallo
  • Ausgabe:
Übereinstimmungen: ja
Gruppe 1: "Hallo"
  • Eingang:
(\ w +) @ (\ w +) (?: \. com | \ .net)
[email protected]
  • Ausgabe:
Übereinstimmungen: ja
Gruppe 1: 'sam'
Gruppe 2: "Test"
code-challenge regular-expression Nathan Osman
quelle
Angesichts der Vielzahl von Funktionen in PCRE ist dies eine echte Herausforderung. Rekursion, Backtracking, Lookahead / Assertions, Unicode, bedingte Submuster, ...
Arnaud Le Blanc
1
Siehe PCRE-Dokumente ; PERL RE ; PHP PCRE- Dokumente sind auch großartig.
Arnaud Le Blanc
@ user300: Ziel ist es, so viel wie möglich zu implementieren. Offensichtlich wäre alles etwas zu schwer.
Nathan Osman
2
@George: Wie wäre es, wenn Sie die Funktionen auflisten, die Sie möchten, und einige Testfälle angeben, damit wir alle auf einer Ebene sind.
Marko Dumic
1
@George: Ich denke, @Marko war nach bestimmten Funktionen, oder eher nach der minimalen Teilmenge, die die Leute zuerst implementieren sollten. Im Großen und Ganzen ist PCRE jedoch eine viel zu harte Herausforderung für einen gelegentlichen Programmierwettbewerb. Ich schlage vor, dies in eine sehr kleine, spezifische RE-Teilmenge zu ändern und die Implementierung herauszufordern.
MtnViewMark

Antworten:

10

Python

Da die Implementierung von vollständigem PCRE zu viel ist, habe ich nur eine wesentliche Teilmenge davon implementiert.

Unterstützt |.\.\w\W\s+*(). Der reguläre Ausdruck muss korrekt sein.

Beispiele:

$ 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

Wie es funktioniert:

Eine detaillierte Theorie finden Sie in dieser Einführung in Automatentheorie, Sprachen und Berechnung .

Die Idee ist, den ursprünglichen regulären Ausdruck in nichtdeterministische endliche Automaten (NFA) umzuwandeln. Tatsächlich sind reguläre PCRE-Ausdrücke zumindest kontextfreie Grammatiken, für die wir Pushdown-Automaten benötigen, aber wir beschränken uns auf eine Teilmenge von PCRE.

Endliche Automaten sind gerichtete Graphen, in denen Knoten Zustände sind, Kanten Übergänge sind und jeder Übergang eine passende Eingabe hat. Zunächst starten Sie von einem vordefinierten Startknoten. Wann immer Sie eine Eingabe erhalten, die einem der Übergänge entspricht, nehmen Sie diesen Übergang in einen neuen Zustand. Wenn Sie einen Endknoten erreicht haben, wird dies als Eingabe bezeichnet, die von Automaten akzeptiert wurde. In unserem Fall ist die Eingabe eine Matching-Funktion, die true zurückgibt.

Sie werden als nichtdeterministische Automaten bezeichnet, da es manchmal mehr übereinstimmende Übergänge gibt, die Sie aus demselben Zustand ableiten können. In meiner Implementierung müssen alle Übergänge in denselben Zustand mit demselben übereinstimmen, daher habe ich die Übereinstimmungsfunktion zusammen mit dem Zielzustand ( states[dest][0]) gespeichert .

Wir wandeln unseren regulären Ausdruck mit Hilfe von Bausteinen in endliche Automaten um. Ein Building Block hat einen Startknoten ( first) und einen Endknoten ( last) und stimmt mit etwas aus dem Text überein (mögliche leere Zeichenfolge).

Die einfachsten Beispiele sind

  • nichts passendes: True( first == last)
  • einem Zeichen entsprechen: c == txt[pos]( first == last)
  • passendes Ende der Zeichenkette: pos == len (txt) (first == last`)

Sie benötigen auch die neue Position im Text, an der das nächste Token gefunden werden soll.

Kompliziertere Beispiele sind (Großbuchstaben stehen für Blöcke).

  • passendes B +:

    • Erstelle Knoten: u, v (nichts passendes)
    • Übergänge erstellen: u -> B.first, B.last -> v, v -> u
    • Wenn Sie zu Knoten v gelangen, haben Sie bereits eine Übereinstimmung mit B. Dann haben Sie zwei Möglichkeiten: Gehen Sie weiter oder versuchen Sie erneut, eine Übereinstimmung mit B herzustellen.

  • passend zu A | B | C:

    • Erstelle Knoten: u, v (nichts passendes)
    • Übergänge erstellen: u -> A.first, u -> C.first, u -> C.first,
    • Übergänge erstellen: A-> last -> v, B-> last -> v, C-> last -> v,
    • Von dir aus kannst du zu jedem Block gehen

Alle Regexp-Operatoren können auf diese Weise transformiert werden. Probieren Sie es einfach aus *.

Der letzte Teil ist das Parsen des regulären Ausdrucks, der eine sehr einfache Grammatik erfordert:

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

Hoffentlich ist die Implementierung einer einfachen Grammatik (ich denke, sie ist LL (1), aber korrigieren Sie mich, wenn ich falsch liege) viel einfacher als die Erstellung einer NFA.

Sobald Sie die NFA haben, müssen Sie zurückverfolgen, bis Sie den Endknoten erreichen.

Quellcode (oder hier ):

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
quelle
1
+1 Wow ... Ich habe versucht, dies selbst mit PHP zu tun und bin völlig gescheitert.
Nathan Osman
TIL (a+b)+entspricht abaabaaabaaaab.
Alexandru