Terapkan PCRE dalam bahasa Anda.

13

Catatan: Setelah mencoba ini sendiri, saya segera menyadari kesalahan apa ini. Karenanya, saya sedikit memodifikasi aturan.

Fungsi minimum yang disyaratkan:

  • Kelas karakter ( ., \w, \W, dll)
  • Pengganda ( +, *, dan ?)
  • Grup tangkapan sederhana

Tantangan Anda adalah menerapkan PCRE dalam bahasa yang Anda pilih dengan ketentuan sebagai berikut:

  • Anda tidak boleh menggunakan fasilitas RegEx asli bahasa Anda dengan cara apa pun . Anda juga tidak dapat menggunakan perpustakaan RegEx pihak ketiga.
  • Entri Anda harus menerapkan sebanyak spesifikasi PCRE. mungkin.

  • Program Anda harus menerima sebagai input, 2 baris:

    • ekspresi reguler
    • input string untuk dicocokkan

  • Program Anda harus menunjukkan dalam outputnya:

    • Apakah RegEx cocok di mana saja di string input
    • Hasil dari setiap grup penangkap

  • Pemenang akan menjadi entri yang mengimplementasikan sebanyak mungkin spesifikasi. mungkin. Dalam hal seri, pemenang akan menjadi entri paling kreatif, seperti yang dinilai oleh saya.

Sunting: untuk memperjelas beberapa hal, berikut adalah beberapa contoh input dan output yang diharapkan:

  • Memasukkan:
^ \ s * (\ w +) $
         Halo
  • Keluaran:
Cocok: ya
Grup 1: 'halo'
  • Memasukkan:
(\ w +) @ (\ w +) (?: \. com | \ .net)
[email protected]
  • Keluaran:
Cocok: ya
Grup 1: 'sam'
Grup 2: 'ujian'
code-challenge regular-expression Nathan Osman
sumber
Itu tantangan yang sangat menantang, mengingat banyaknya fitur di PCRE. Rekursi, backtracking, lookahead / pernyataan, unicode, subpatterns bersyarat, ...
Arnaud Le Blanc
1
Lihat dokumen PCRE ; PERL RE ; Dokumentasi PHP PCRE juga bagus.
Arnaud Le Blanc
@ user300: Tujuannya adalah untuk mengimplementasikan sebanyak mungkin. Jelas semuanya akan sedikit terlalu sulit.
Nathan Osman
2
@ George: Bagaimana kalau Anda daftar fitur yang Anda inginkan dan memberikan beberapa kasus uji, hanya agar kita semua di tanah datar.
Marko Dumic
1
@ George: Saya pikir @ Marko mengejar fitur tertentu, atau lebih tepatnya, subset minimal yang Anda ingin orang terapkan terlebih dahulu. Secara keseluruhan, PCRE benar-benar merupakan tantangan yang terlalu sulit untuk kompetisi coding biasa. Saya menyarankan mengubah ini menjadi subset RE yang sangat kecil dan spesifik, dan membuat tantangan untuk diimplementasikan.
MtnViewMark

Jawaban:

10

Python

Karena menerapkan PCRE penuh terlalu banyak, saya hanya mengimplementasikan sebagian yang penting saja.

Mendukung |.\.\w\W\s+*(). Input regexp harus benar.

Contoh:

$ 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

Bagaimana itu bekerja:

Untuk teori terperinci, baca Pengantar Teori Automata, Bahasa, dan Komputasi ini .

Idenya adalah untuk mengubah ekspresi reguler asli menjadi automata nondeterminist finite automata (NFA). Sebenarnya, ekspresi reguler PCRE setidaknya adalah tata bahasa bebas konteks yang kami perlukan push-down automata, tetapi kami akan membatasi diri kami untuk subset dari PCRE.

Automatas terbatas adalah grafik terarah di mana node dinyatakan, tepi adalah transisi dan setiap transisi memiliki input yang cocok. Awalnya Anda mulai dari simpul awal, yang telah ditentukan sebelumnya. Setiap kali Anda menerima input yang cocok dengan salah satu transisi Anda mengambil transisi itu ke keadaan baru. Jika Anda mencapai terminal node, itu disebut input diterima automata. Dalam kasus kami, input adalah fungsi yang cocok yang mengembalikan true.

Mereka disebut nondeterminist automata karena kadang-kadang ada lebih banyak transisi yang cocok yang dapat Anda ambil dari keadaan yang sama. Dalam implementasi saya semua transisi ke keadaan yang sama harus cocok dengan hal yang sama, jadi saya menyimpan fungsi yang cocok bersama-sama dengan negara tujuan ( states[dest][0]).

Kami mengubah regexp kami menjadi automata terbatas menggunakan blok bangunan. Blok penyusun memiliki simpul mulai ( first) dan simpul akhir ( last) dan cocok dengan sesuatu dari teks (kemungkinan string kosong).

Contoh paling sederhana termasuk

  • tidak ada yang cocok: True( first == last)
  • cocok dengan karakter: c == txt[pos]( first == last)
  • akhir string yang cocok: pos == len (txt) (pertama == terakhir`)

Anda juga akan membutuhkan posisi baru di teks tempat untuk mencocokkan token berikutnya.

Contoh yang lebih rumit adalah (huruf besar berarti blok).

  • pencocokan B +:

    • buat node: u, v (tidak ada yang cocok)
    • buat transisi: u -> B.first, B.last -> v, v -> u
    • ketika Anda sampai ke simpul v Anda sudah cocok B. Kemudian Anda memiliki dua opsi: melangkah lebih jauh, atau mencoba untuk mencocokkan B lagi.

  • pencocokan A | B | C:

    • buat node: u, v (tidak ada yang cocok)
    • buat transisi: u -> A.first, u -> C.first, u -> C.first,
    • buat transisi: A-> last -> v, B-> last -> v, C-> last -> v,
    • dari kamu kamu bisa pergi ke blok mana saja

Semua operator regexp dapat diubah seperti ini. Coba saja *.

Bagian terakhir adalah mengurai regexp yang membutuhkan tata bahasa yang sangat sederhana:

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

Semoga menerapkan tata bahasa sederhana (saya pikir adalah LL (1), tetapi benar kalau saya salah) jauh lebih mudah daripada membangun NFA.

Setelah Anda memiliki NFA, Anda harus mundur hingga mencapai simpul terminal.

Kode sumber (atau di sini ):

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
sumber
1
+1 Wow ... Saya mencoba melakukan ini sendiri dengan PHP dan gagal total.
Nathan Osman
TIL (a+b)+cocok abaabaaabaaaab.
Alexandru