Jak symulować odwołania wsteczne, wyprzedzenia i spojrzenia w automatach skończonych?

Stworzyłem prosty leksymetr i analizator wyrażeń regularnych, aby pobrać wyrażenie regularne i wygenerować jego drzewo analizy. Utworzenie niedeterministycznego automatu skończonego z tego drzewa analizy jest stosunkowo proste w przypadku podstawowych wyrażeń regularnych. Wydaje mi się jednak, że nie mogę zawinąć głowy, jak symulować odwołania wsteczne, spojrzenia w przód i spojrzenia.

Z tego, co przeczytałem w książce o fioletowym smoku, zrozumiałem, że aby zasymulować wyprzedzające którym dopasowuje się wyrażenie regularne , i tylko wtedy, gdy po dopasowaniu następuje dopasowanie wyrażenia regularnego , tworzysz niedeterministyczny skończony automat stanu, w którym jest zastąpione przez . Czy można stworzyć deterministyczny automat skończony, który robi to samo?$r/s$$r$$s$$/$$\varepsilon$

A co z symulowaniem negatywnych spojrzeń w przyszłość i spojrzeń w przeszłość? Byłbym bardzo wdzięczny, gdybyś połączył mnie z zasobem, który szczegółowo opisuje, jak to zrobić.

Przede wszystkim nie można symulować odwołań wstecznych za pomocą automatów skończonych, ponieważ pozwalają one na opisanie nieregularnych języków. Na przykład ([ab]^*)\1pasuje , która nie jest nawet pozbawiona kontekstu.$\{ww \mid w \in \{a,b\}^*\}$

Spojrzenie w przyszłość i spoglądanie w przeszłość nie są niczym specjalnym w świecie automatów skończonych, ponieważ dopasowujemy tylko całe dane wejściowe. Dlatego szczególny semantyczny „po prostu sprawdź, ale nie konsumuj” jest bez znaczenia; po prostu łączymy i / lub przecinamy sprawdzanie i konsumowanie wyrażeń oraz korzystanie z powstałych automatów. Chodzi o to, aby sprawdzić wyrażenia wybiegające w przyszłość lub w przeszłość podczas „konsumpcji” danych wejściowych i zapisywania wyniku w stanie.

Wdrażając wyrażenia regularne, chcesz uruchomić dane wejściowe przez automat i odzyskać początkowe i końcowe indeksy dopasowań. To jest zupełnie inne zadanie, więc tak naprawdę nie ma konstrukcji automatów skończonych. Tworzysz automat tak, jakby pochłaniające go wyrażenie wyprzedzające lub spoglądało wstecz, i zmieniałeś odpowiednio indeks przechowujący. raportowanie odpowiednio.

Weźmy na przykład za siebie. Możemy naśladować semantykę wyrażeń regularnych, wykonując sprawdzanie wyrażeń regularnych jednocześnie z domyślnie konsumującym wyrażeniem regularnym „dopasuj wszystko”. tylko ze stanów, w których automat wyrażenia spoglądającego znajduje się w stanie końcowym, można wprowadzić automat zabezpieczonego wyrażenia. Na przykład wyrażenie regularne /(?=c)[ab]+/(przy założeniu, że jest pełnym alfabetem) - zauważ, że przekłada się na wyrażenie regularne { a , b , c } ∗ c { a , b } + { a , b , c $\{a,b,c\}$ - można by dopasować$\{a,b,c\}^*c\{a,b\}^+\{a,b,c\}^*$

^{[ źródło ]}

i musiałbyś

• zapisz bieżący indeks jako za każdym razem, gdy wpiszesz q 2 (początkowo lub z q 2 ) i$i$$q_2$$q_2$
• zgłaszaj (maksymalne) dopasowanie od do bieżącego indeksu ( - 1 ) za każdym razem, gdy trafisz (wyjdziesz) q 2 .$i$$-1$$q_2$

Zwróć uwagę, że lewa część automatu jest automatem równoległym automatów kanonicznych odpowiednio dla ( [abc]*i citerowanych).

$i$$j$$i$$j$

Zauważ, że nieodłączny od tego jest nieodłączny charakter: główny i wybiegający w przyszłość / -automat może się nakładać, więc musisz zapisać wszystkie przejścia między nimi, aby zgłosić pasujące później lub cofnąć się.

Autorytatywnym odniesieniem do pragmatycznych kwestii związanych z wdrażaniem silników regex jest seria trzech postów na blogu Russa Coxa . Jak opisano tam, ponieważ odwołania wsteczne powodują, że Twój język jest nieregularny, są one implementowane przy użyciu śledzenia wstecznego .

Spojrzenia na przyszłość i spojrzenia, podobnie jak wiele funkcji silników dopasowywania wyrażeń regularnych, nie pasują do paradygmatu decydowania, czy łańcuch znaków należy do języka, czy nie. Zamiast wyrażeń regularnych zwykle szukamy podciągów w większym ciągu. „Dopasowanie” to podciągi będące elementami języka, a zwracana wartość to początek i koniec podłańcucha w obrębie większego łańcucha.

Istota lookaheads i lookbehinds to nie tyle wprowadzenie umiejętności dopasowania nietypowych języków, co raczej dostosowanie miejsca, w którym silnik zgłasza początkowe i końcowe punkty dopasowanego podłańcucha.

Opieram się na opisie pod adresem http://www.regular-expressions.info/lookaround.html . Silniki wyrażeń regularnych, które obsługują tę funkcję (Perl, TCL, Python, Ruby, ...) wydają się być oparte na cofaniu (tj. Obsługują znacznie większy zestaw języków niż tylko zwykłe języki). Wydaje się, że wdrażają tę funkcję jako stosunkowo „proste” rozszerzenie cofania, zamiast próbować zbudować prawdziwe skończone automaty do wykonania zadania.

Pozytywne spojrzenie w przyszłość

Składnia pozytywnego oczekiwania jest (?=wyrażeniem regularnym) . Na przykład q(?=u)dopasowuje qtylko, jeśli następuje po nim u, ale nie pasuje do u. Wyobrażam sobie, że wprowadzają to z pewną odmianą cofania. Utwórz FSM dla wyrażenia przed pozytywnym wyprzedzeniem. Kiedy to się zapamięta, pamiętaj, gdzie się skończyło i uruchom nowy FSM, który reprezentuje wyrażenie wewnątrz pozytywnego spojrzenia w przyszłość. Jeśli to pasuje, to masz „dopasowanie”, ale dopasowanie „kończy się” tuż przed pozycją, w której rozpoczęło się pozytywne spojrzenie z wyprzedzeniem.

Jedyną częścią tego, która byłaby trudna bez cofania, jest to, że musisz pamiętać punkt na wejściu, w którym rozpoczyna się przeglądarka, i przenieść taśmę wejściową z powrotem do tej pozycji po zakończeniu dopasowania.

Negatywne spojrzenie w przyszłość

Składnia negatywnego wyglądu jest (?!wyrażeniem regularnym) . Na przykład q(?!u)dopasowuje qtylko wtedy, gdy nie następuje po nim u. Może to być albo qnastępująca po nim inna postać, albo a qna samym końcu łańcucha. Wyobrażam sobie, że jest to realizowane przez utworzenie NFA dla wyrażenia wyprzedzającego, a następnie odniesie sukces tylko wtedy, gdy NFA nie dopasuje kolejnego ciągu.

Jeśli chcesz to zrobić bez polegania na cofaniu, możesz zignorować NFA wyrażenia lookahead, a następnie potraktuj to tak samo, jak pozytywny lookahead.

Pozytywny wygląd

(?<=)(?=q)uuqq$n$$n$$n$

Możesz być w stanie to zaimplementować bez cofania się, biorąc przecięcie „łańcucha zakończonego wyrażeniem regularnym ” z dowolną częścią wyrażenia regularnego występującego przed operatorem lookbehind. Będzie to trudne, ponieważ wyrażenie regularne może wymagać spojrzenia wstecz niż obecny początek danych wejściowych.

Negatywne spojrzenie

Składnia negatywnego wyglądu jest (?<!wyrażeniem regularnym) . Na przykład (?<!q)upasuje u, ale tylko wtedy, gdy nie jest poprzedzone znakiem q. Więc byłoby dopasować usię umbrellai una doubt, ale nie uw quick. Znowu wydaje się, że dzieje się to poprzez obliczenie długości wyrażenia regularnego , utworzenie kopii zapasowej tylu znaków, testowanie dopasowania z wyrażeniem regularnym , ale teraz niepowodzenie całego dopasowania, jeśli wygląd jest zgodny.

Możesz być w stanie to zaimplementować bez cofania się, biorąc negację wyrażenia regularnego, a następnie robiąc to samo, co zrobiłbyś dla pozytywnego wyglądu.

Przynajmniej w przypadku odwołań wstecznych nie jest to możliwe. Na przykład wyrażenie regularne (.*)\1reprezentuje język, który nie jest regularny. Oznacza to, że niemożliwe jest stworzenie skończonego automatu (deterministycznego lub nie), który rozpoznałby ten język. Jeśli chcesz to formalnie udowodnić, możesz użyć lematu pompującego .

Przyglądałem się temu samemu i powinieneś być w stanie zaimplementować lookahead za pomocą przemiennego automatu skończonego . Kiedy napotkasz lookahead, niedeterministycznie uruchamiasz zarówno lookahead, jak i pozostałą część wyrażenia, akceptując tylko wtedy, gdy obie ścieżki akceptują. Możesz przekonwertować AFA na NFA z rozsądnym powiększeniem (a tym samym na DFA), chociaż nie zweryfikowałem, że oczywista konstrukcja dobrze pasuje do grup przechwytywania.

Wygląd przy stałej szerokości powinien być możliwy bez cofania się. Niech n będzie szerokością. Zaczynając od punktu w NFA, w którym rozpoczął się wygląd, rozdzielisz stany patrząc wstecz, tak aby każda ścieżka do spojrzenia kończyła się znakami o wartości n znaków, które przechodziły tylko w wygląd. Następnie dodaj lookahead na początku tych stanów (i w razie potrzeby natychmiast skompiluj wykres podrzędny z AFA do NFA).

Referencje wsteczne, jak wspomnieli inni, nie są regularne, więc nie mogą być zaimplementowane przez automat skończony. W rzeczywistości są kompletne NP. W implementacji, nad którą pracuję, szybkie dopasowanie tak / nie jest najważniejsze, więc postanowiłem nie implementować żadnych odwołań wstecznych.