Реализуйте PCRE на своем языке.

Примечание: попробовав это сам, я вскоре понял, что это за ошибка. Поэтому я немного изменяю правила.

Минимально необходимый функционал:

• Классы символов ( ., \w, \Wи т.д.)
• Множители ( +, *и ?)
• Простые группы захвата

Ваша задача - реализовать PCRE на выбранном вами языке при соблюдении следующих условий:

• Вы не можете использовать собственные средства RegEx вашего языка в любом случае . Вы также не можете использовать стороннюю библиотеку RegEx.
• Ваша заявка должна реализовывать как можно больше спецификации PCRE. насколько это возможно.

• Ваша программа должна принять в качестве ввода 2 строки:

  • регулярное выражение
  • строка ввода для сравнения

• Ваша программа должна указать в своем выводе:

  • Соответствует ли RegEx где-либо во входной строке
  • Результаты любых групп захвата

• Победителем должна стать запись, которая реализует как можно большую часть спецификации. насколько это возможно. В случае ничьей победитель должен быть самым креативным, как мне кажется.

Изменить: чтобы уточнить некоторые вещи, вот несколько примеров ввода и ожидаемого вывода:

• Входные данные:

^ \ S * (\ ш +) $
         Здравствуйте

• Выход:

Матчи: да
Группа 1: «Привет»

• Входные данные:

(\ Ш +) @ (\ W +) (?:. \ Ком | \ .net)
sam@test.net

• Выход:

Матчи: да
Группа 1: «Сэм»
Группа 2: «тест»

питон

Поскольку реализация полного PCRE - это слишком много, я реализовал только его существенную часть.

Опоры |.\.\w\W\s+*(). Входное регулярное выражение должно быть правильным.

Примеры:

$ 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

Как это устроено:

Для детальной теории прочитайте это Введение в теорию автоматов, языков и вычислений .

Идея состоит в том, чтобы преобразовать исходное регулярное выражение в недетерминированный конечный автомат (NFA). На самом деле регулярные выражения PCRE - это, по крайней мере, контекстно-свободные грамматики, для которых нам нужны автоматные выпадающие меню, но мы ограничимся подмножеством PCRE.

Конечные автоматы - это ориентированные графы, в которых узлы - это состояния, ребра - это переходы, и каждый переход имеет соответствующий вход. Первоначально вы начинаете с начального узла, предопределенного. Всякий раз, когда вы получаете вход, соответствующий одному из переходов, вы переходите в новое состояние. Если вы достигли терминального узла, это называется, что автоматы приняли ввод. В нашем случае input - это функция соответствия, которая возвращает true.

Они называются недетерминированными автоматами, потому что иногда есть больше подходящих переходов, которые вы можете взять из одного и того же состояния. В моей реализации все переходы в одно и то же состояние должны совпадать, поэтому я сохранил соответствующую функцию вместе с целевым состоянием ( states[dest][0]).

Мы преобразуем наше регулярное выражение в конечный автомат, используя строительные блоки. Строительный блок имеет начальный узел ( first) и конечный узел ( last) и соответствует чему-то из текста (возможно, пустая строка).

Простейшие примеры включают

• ничего не соответствует: True( first == last)
• соответствие персонажа: c == txt[pos]( first == last)
• соответствующий конец строки: pos == len (txt) (first == last`)

Вам также понадобится новая позиция в тексте, где будет соответствовать следующий токен.

Более сложные примеры (заглавные буквы обозначают блоки).

• соответствие B +:

  • создать узлы: U, V (ничего не соответствует)
  • создать переходы: u -> B.first, B.last -> v, v -> u
  • когда вы добираетесь до узла v, вы уже подобрали B. Тогда у вас есть два варианта: пойти дальше или попытаться снова сопоставить B.

• соответствие A | B | C:

  • создать узлы: U, V (ничего не соответствует)
  • создать переходы: u -> A.first, u -> C.first, u -> C.first,
  • создать переходы: A-> last -> v, B-> last -> v, C-> last -> v,
  • от вас вы можете пойти в любой блок

Все операторы регулярных выражений могут быть преобразованы следующим образом. Просто попробуйте *.

Последняя часть - это синтаксический анализ регулярного выражения, который требует очень простой грамматики:

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

Надеюсь, реализовать простую грамматику (я думаю, что это LL (1), но поправьте меня, если я ошибаюсь) гораздо проще, чем создать NFA.

Когда у вас есть NFA, вам нужно возвращаться назад, пока вы не достигнете конечного узла.

Исходный код (или здесь ):

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)