Wojciech Muła pisze:
> Jędrzej Dudkiewicz <j...@g...com> wrote:
>
>> 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]+
?
Skoro dopasowałeś ten tekst do miejsca wystąpienia backrefa to znaczy,
że gdzieś go masz w buforze na wypadek gdybyś się wycofywał.

Teraz wystarczy automat, który porównuje zadany ciąg z wejściem.
(Pobierz znak z bufora lub zakończ, pobierz znak z wejścia lub zakończ,
porównaj, zapętl lub zakończ.) Czy coś pominąłem?

--
Pozdrawiam
Michoo

do góry

Michoo <m...@v...pl> wrote:

> >> 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ść.

> 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.

w.

--
Mamy oswojoną sarnę i w związku z tym projektuję, by dorobić do niej kłódkę.

do góry

Wojciech Muła pisze:
> Michoo <m...@v...pl> wrote:
>
>>>> 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.
>
>> 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ć.

--
Pozdrawiam
Michoo

do góry

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'

do góry

Wojciech Muła pisze:
> Jędrzej Dudkiewicz <j...@g...com> wrote:
>
>> 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ć.

Oczywiście, że nie może być dowolnym ciągiem, musi być ciągiem, który
już a) znalazłeś, oraz b) zapamiętałeś - forma nieistotna. W końcu
jeżeli używasz nawiasów (tych wyznaczających ciąg do
backreference'owania, że się wyrażę), to wynik przypasowania musi być
zapamiętany.

Kiedy pisałem "zarezerwować miejsce na dodatkowe stany", nie miałem na
myśli konkretnej liczby stanów, miałem na myśli raczej dwa stany, między
które wejdzie jeszcze cały dodatkowy ciąg znaków.

> Tzn. technicznie to jest osiągalne, jasne - przecież wszyscy tego
> używamy w VIM-ie i innych narzędziach. :) Mnie interesuje, czy są
> w informatyce teoretycznej rozważane jakiś specjalne struktury związane
> z tego typu dopasowaniami.

Myślę, że lista, kolejka i mapa :)

JD

do góry