Czy istnieje jakiś nieogólny algorytm analizowania CFG, który rozpoznaje EPAL?

EPAL, język parzystych palindromów, jest definiowany jako język generowany przez następującą jednoznaczną, bezkontekstową gramatykę:

$S \rightarrow a a$

$S \rightarrow b b$

$S \rightarrow a S a$

$S \rightarrow b S b$

EPAL jest „zmorą” wielu algorytmów parsowania: jeszcze nie spotkałem się z żadnym algorytmem parsowania dla jednoznacznych CFG, które potrafią parsować dowolną gramatykę opisującą język. Jest często używany do pokazania, że istnieją jednoznaczne CFG, których nie można przeanalizować przez konkretny analizator składni. To zainspirowało moje pytanie:

Czy istnieje jakiś algorytm analizujący akceptujący tylko jednoznaczne CFG, który działa na EPAL?

Oczywiście można zaprojektować parser dwuprzebiegowy ad-hoc dla gramatyki, która analizuje język w czasie liniowym. Interesują mnie metody analizy, które nie zostały zaprojektowane specjalnie z myślą o EPAL.

formal-languages formal-grammars parsers Alex ten Brink
źródło

Niemal boję się zapytać: co jest nie tak z LL (1) przez rekurencyjne zejście?

Raphael

Rekurencyjne zejście bez wstecznego śledzenia nie obsługuje EPAL, ponieważ językiem nie jest LL (k) dla żadnego k. Rekurencyjne zejście z cofaniem może obsłużyć gramatykę w czasie , ale jest to ogólny algorytm z wykładniczym zachowaniem w najgorszym przypadku, czego nie szukam.

O (n^{2})

$O(n^2)$

Alex ten Brink

O (N^{2})

$O(N^2)$ nie jest wykładnicze, jest kwadratowe. ma charakter wykładniczy.

O (2^{N})

$O(2^N)$

Victor Stafusa,

@Victor: nawracanie ma charakter wykładniczy na niektórych gramatykach, ale nie na tej konkretnej gramatyce. Jest to jednak algorytm działający na dwuznacznych gramatykach, pomija go jako odpowiedź na moje pytanie.

Alex ten Brink

@jmad: moim zamiarem nie jest parsowanie języka (możesz to zrobić trywialnie w czasie liniowym), ale raczej zaspokojenie mojej ciekawości: widziałem, że jest używany jako przykład języka, którego nie można przeanalizować za pomocą metody parsowania tyle razy, że jestem ciekawy, czy istnieje jakaś metoda analizy, która to rozpoznaje.

Alex ten Brink

Odpowiedzi:

Rozważ poniższy szkic strategii analizowania na własne ryzyko.

Zamiast czytać dane wejściowe tylko z jednego końca, czytamy z obu stron i szukamy pasujących reguł. Możemy to zrobić w rekurencyjnym stylu opadania; w wywołaniu znajdź prefiks i sufiks na wejściu, tak że istnieje reguła , zejdź do na pozostałym słowie. Jeśli nie ma pasującej reguły, odrzuć słowo. $A()$ $w$ $v$ $A \to wBv$ $B()$

Algorytm analizuje wszystkie liniowe, jednoznaczne gramatyki. Zajmuje to czas liniowy, jeśli wszystkie pary reguł i mają lub ¹. Obejmuje to EPAL. W przeciwnym razie musimy spojrzeć w przyszłość, abyśmy mogli zająć . $A \to wBv$ $A \to w'B'v'$ $w \not\equiv_p w'$ $v \not\equiv_s v'$ $\Theta(n^2)$

Pomysł w ogóle nie działa w przypadku gramatyki nieliniowej. Gramatyki liniowej, ale niejednoznacznej, nie można na ogół analizować bez cofania (przynajmniej dla negatywnych danych wejściowych).

$w \not\equiv_p v$ oznacza tutaj, że oraz , tzn. żadne słowo nie jest przedrostkiem drugiego. jest podobny do sufiksów. $w \not\sqsubseteq v$ $v \not\sqsubseteq w$ $\not\equiv_s$

Raphael
źródło

Doskonały! Dokładnie tego szukałem. To wspaniałe, że język, który nie jest dla dowolnego jest analizowalny przez tak prosty algorytm.

N L R (k)

$NLR(k)$

k

$k$

Alex ten Brink

Po głębszym zastanowieniu odkryłem drobny błąd w twoim opisie: gramatyka liniowa jest jednoznaczny, ale nie ma takiego unikalnego prefiksu, jak to opisujesz. Nadal istnieje unikalny prefiks, ale może być konieczne zajrzenie do nieterminala, aby go uzyskać, a czas działania zmienia się na . Twój algorytm działa jednak na .

S \to a A b | a B b, A \to a, B \to b

$S \rightarrow a A b | a B b, A \rightarrow a, B \rightarrow b$

O (n^{2})

$O(n^2)$

E P A L

$EPAL$

Alex ten Brink

@AlextenBrink Dobry połów. Zedytowałem, aby to uwzględnić.

Raphael