Użytkownik "Wojciech Muła" <w...@p...null.onet.pl.invalid>
napisał w wiadomości
news:20100313165516.f33b13dc.wojciech_mula@poczta.nu
ll.onet.pl.invalid...
"Wojciech \"Spook\" Sura" <s...@s...please.op.pl> wrote:

>> Nie jestem obeznany z pojęciem backtrackingu - napisz proszę w dwóch
>> słowach
>> co to jest, to pokombinuję.
>
> Odwołania wsteczne (tak to chyba jest po polsku), to fragment uprzednio
> dopasowanego tekstu i wyrażnie z czymś takim nie definiuje już języka
> regularnego. Np. "([a-z]+)\1" oznacza 'dopasuj ciąg literek, a następnie
> to samo (\1)' - czyli słowa języka są zawsze postaci XX, gdzie X to
> dowolny
> ciąg literek.

Po pierwsze zastanawiam się, czy backtracking jest realizowany automatem,
czy raczej wchodzi tam już jakieś bardziej wysokopoziomowe programowanie, w
sensie zapamiętanie odnalezionego ciągu i dopasowanie go "ręcznie".

Drugi pomysł - możliwe, że powyższe wyrażenie dałoby się zapisać jakąś
gramatyką bezkontekstową. Wówczas można byłoby zastosować automat skończony
ze stosem lub jakąś sprytną kombinację automatu skończonego i automatu
skończonego ze stosem.

> w.

Pozdrawiam -- Spook.

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



--
! ._______. Warning: Lucida Console sig! //) !
! || spk || www.spook.freshsite.pl / _ """*!
! ||_____|| spook at op.pl / ' | ""!
! | ___ | tlen: spoko_ws gg:1290136 /. __/"\ '!
! |_|[]_|_| May the SOURCE be with you! \/) \ !