-
Data: 2010-03-23 07:35:06
Temat: Re: Jaki automat dla wyrażeń regularnych z bactrackigiem?
Od: Mariusz Kruk <M...@e...eu.org> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]epsilon$ while read LINE; do echo \>"$LINE"; done < "Michoo"
>>>>> Wydaje mi się, że "wystarczy" zarezerwować miejsce w automacie na
>>>>> dodatkowe stany i dołożyć je, kiedy ciąg już jest znany. Wszak to "\1"
>>>>> to nic innego, jak ustalony ciąg znaków.
>>>> Nic podobnego, \1 może być dowolnym ciągiem. Nie wiesz, ile będziesz
>>>> potrzebował zarezerwować.
>>> A ile musisz zarezerwować na [a-z]+
>>> ?
>> W automacie skończonym? Zero. Nie ma żadnego "bufora" - automat zmienia
>> stan na podstawie funkcji przejść.
>W automacie - nie (no chyba, że ze stosem), ale automat ma jakieś
>"wejście" i ono musi zadbać o odpowiednie buforowanie.
Nie ma żadnego buforowania. Czytasz po znaku z wejścia i zmieniasz stany
zgodnie z funkcją przejść. Nie masz żadnej wiedzy odnośnie znaków
wcześniejszych/późniejszych. W przypadku backrefów musisz tę wiedzę
mieć.
>>> Skoro dopasowałeś ten tekst do miejsca wystąpienia backrefa to znaczy,
>>> że gdzieś go masz w buforze na wypadek gdybyś się wycofywał.
>> Ja mogę mieć wszystko, ale który automat rozumie pojęcie "bufora"? :)
>> O to się cały czas rozchodzi - nie o algorytm, tylko o nazwę konstrukcji
>> teoretycznej.
>Automat ze stosem? - Ma "bufor". Inaczej (bez bufora) chyba nie da się
>zapewnić samego _zapamiętania_ dopasowanych ciągów. A to jest pierwszy
>etap do ich późniejszego dopasowania. Teorii niestety nie znam na tyle,
>żeby coś więcej powiedzieć.
Nie chce mi się za bardzo wgłębiać (a niewiele pamiętam ;->), ale
wikipedia twierdzi, że:
"Many features found in modern regular expression libraries provide an
expressive power that far exceeds the regular languages. For example,
many implementations allow grouping subexpressions with parentheses and
recalling the value they match in the same expression (backreferences).
This means that a pattern can match strings of repeated words like
"papa" or "WikiWiki", called squares in formal language theory. The
pattern for these strings is (.*)\1.
However, the language of squares is not regular, nor is it
context-free."
Czyli backrefy wychodzą poza języki bezkontekstowe, a więc PDA nie
wystarczy.
--
d'`'`'`'`'`'`'`'`'`'`'`'`'Yb
`b K...@e...eu.org d'
d' http://epsilon.eu.org/ Yb
`b,-,.,-,.,-,.,-,.,-,.,-,.d'
Następne wpisy z tego wątku
- 23.03.10 19:55 Jędrzej Dudkiewicz
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-06-10 wyobrazcie sobie ze
- 2024-06-10 malowanie samochodu
- 2024-06-10 News from Poland
- 2024-06-10 Czy na pewno będą CŁA na chińskie samochody?
- 2024-06-09 Dlaczego w Polsce sie nic nie udaje, na przykładzie niebieskiego lasera a teraz perskowitów
- 2024-06-09 Dlaczego w Polsce sie nic nie udaje, na przykładzie niebieskiego lasera a teraz perskowitów
- 2024-06-09 Wykrywanie przerwy w długim przewodzie zakopanym w ziemi.
- 2024-06-09 Czemu news.chmurka.nwt jest taki wolny?
- 2024-06-11 Funbox 3.0 zakres adresów DHCP
- 2024-06-11 Re: Funbox 3.0 zakres adresów DHCP
- 2024-06-09 Miernik szybkości netu
- 2024-06-11 Panele PV w pionie (prawie).
- 2024-06-11 czy ta grupa żyje?
- 2024-06-11 Warszawa => Senior React Native Developer <=
- 2024-06-11 Gdańsk => Kierownik Działu Spedycji Międzynarodowej <=