Pyton
Ponieważ wdrożenie pełnego PCRE to za dużo, zaimplementowałem tylko jego niezbędny podzbiór.
Podpory |.\.\w\W\s+*(). Wyrażenie regularne danych wejściowych musi być poprawne.
Przykłady:
$ python regexp.py
^\s*(\w+)$
hello
Matches: hello
Group 1 hello
$ python regexp.py
(a*)+
infinite loop
$ python regexp.py
(\w+)@(\w+)(\.com|\.net)
sam@test.net
Matches: sam@test.net
Group 1 sam
Group 2 test
Group 3 .net
Jak to działa:
Aby uzyskać szczegółową teorię, przeczytaj to wprowadzenie do teorii automatów, języków i obliczeń .
Chodzi o to, aby zamienić oryginalne wyrażenie regularne na niedeterministyczne skończone automaty (NFA). W rzeczywistości wyrażenia regularne PCRE to co najmniej gramatyka bezkontekstowa, dla której potrzebujemy automatów push-down, ale ograniczymy się do podzbioru PCRE.
Automaty skończone to skierowane wykresy, w których węzły to stany, krawędzie to przejścia, a każde przejście ma pasujące wejście. Początkowo zaczynasz od wstępnie zdefiniowanego węzła początkowego. Za każdym razem, gdy otrzymasz dane pasujące do jednego z przejść, przenosisz je do nowego stanu. Jeśli dotarłeś do terminala, nazywa się to wejściem akceptowanym przez automaty. W naszym przypadku wejście jest funkcją dopasowania, która zwraca true.
Nazywa się je niedeterministycznymi automatami, ponieważ czasami istnieje więcej pasujących przejść, które można pobrać z tego samego stanu. W mojej implementacji całe przejście do tego samego stanu musi pasować do tego samego, więc zapisałem funkcję dopasowania wraz z stanem docelowym ( states[dest][0]).
Przekształcamy nasze wyrażenie regularne w skończone automaty przy użyciu bloków konstrukcyjnych. Blok konstrukcyjny ma węzeł początkowy ( first) i końcowy ( last) i dopasowuje coś z tekstu (możliwy pusty ciąg).
Najprostsze przykłady to
- nic nie pasuje:
True( first == last)
- dopasowanie znaku:
c == txt[pos]( first == last)
- pasujący koniec łańcucha: pos == len (txt)
(pierwszy == ostatni`)
Będziesz także potrzebować nowej pozycji w tekście, gdzie dopasować następny token.
Bardziej skomplikowane przykłady to (wielkie litery oznaczają bloki).
pasujące B +:
- utwórz węzły: u, v (nic nie pasuje)
- utwórz przejścia: u -> B. pierwszy, B. ostatni -> v, v -> u
- kiedy dojdziesz do węzła v, już dopasowałeś B. Następnie masz dwie opcje: idź dalej lub spróbuj ponownie dopasować B.
pasujące A | B | C:
- utwórz węzły: u, v (nic nie pasuje)
- utwórz przejścia: u -> A. pierwszy, u -> C. pierwszy, u -> C. pierwszy,
- twórz przejścia: A-> ostatnie -> v, B-> ostatnie -> v, C-> ostatnie -> v,
- od ciebie możesz przejść do dowolnego bloku
Wszystkie operatory regularne można przekształcić w ten sposób. Po prostu spróbuj *.
Ostatnią częścią jest parsowanie wyrażenia regularnego, które wymaga bardzo prostej gramatyki:
or: seq ('|' seq)*
seq: empty
seq: atom seq
seq: paran seq
paran: '(' or ')'
Mam nadzieję, że implementacja prostej gramatyki (myślę, że to LL (1), ale popraw mnie, jeśli się mylę) jest znacznie łatwiejsza niż zbudowanie NFA.
Po uzyskaniu NFA musisz cofnąć się, aż dotrzesz do węzła końcowego.
Kod źródłowy (lub tutaj ):
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 = 'sam@test.net'
regexp = raw_input()
string = raw_input()
states, last = compile(regexp)
backtrack(states, last, string)