O ile większy może być automat LR (1) dla języka niż odpowiedni automat LR (0)?

W parserze LR (0) każdy stan składa się z kolekcji elementów LR (0), które są produkcjami opatrzonymi adnotacją pozycją. W parserze LR (1) każdy stan składa się z kolekcji elementów LR (1), które są produkcjami opatrzonymi adnotacją pozycją i znakiem z wyprzedzeniem.

Wiadomo, że biorąc pod uwagę stan w automacie LR (1), zestaw konfiguracyjny utworzony przez upuszczenie tokenów oczekujących z każdego elementu LR (1) daje zestaw konfiguracyjny odpowiadający niektórym stanom w automacie LR (0). W tym sensie główna różnica między automatem LR (1) a automatem LR (0) polega na tym, że automat LR (1) ma więcej kopii stanów w automacie LR (0), z których każdy jest opatrzony adnotacją z wyprzedzeniem Informacja. Z tego powodu automaty LR (1) dla danego CFG są zwykle większe niż odpowiedni parser LR (0) dla tego CFG.

Moje pytanie brzmi, o ile większy może być automat LR (1). Jeśli w alfabecie gramatyki znajduje się różnych symboli końcowych, wówczas w zasadzie może zaistnieć potrzeba powtórzenia każdego stanu w automacie LR (0) co najmniej raz na podzbiór tych różnych symboli końcowych, potencjalnie prowadząc do LR (1) ) automat, który jest razy większy niż oryginalny automat LR (0). Biorąc pod uwagę, że każdy pojedynczy element w automacie LR (0) składa się z zestawu różnych elementów LR (0), możemy uzyskać jeszcze większe powiększenie. $n$ $n$ $2^n$

To powiedziawszy, nie mogę znaleźć sposobu na zbudowanie rodziny gramatyk, dla których automat LR (1) jest znacznie większy niż odpowiedni automat LR (0). Wszystko, co próbowałem, doprowadziło do niewielkiego wzrostu wielkości (zwykle około 2-4x), ale nie mogę znaleźć wzoru, który prowadzi do dużego powiększenia.

Czy istnieją znane rodziny gramatyk bezkontekstowych, których automaty LR (1) są wykładniczo większe niż odpowiadające im automaty LR (0)? Czy też wiadomo, że w najgorszym przypadku nie można uzyskać gwałtownego wybuchu?

Dzięki!

context-free parsers lr-k

— templatetypedef
źródło

problemy takie jak te czasami są podatne na testy empiryczne. co byś pomyślał o poszczególnych instancjach generowanych losowo, które (są wybrane) wykazują wysadzenie? w tego typu pytaniach istnieje pewien wzorzec, że „losowo wyglądające” konstrukcje wykazują najbardziej „złożoność” ...

— dniu

Przypadki najgorszego przypadku są zwykle trudne do znalezienia przez losowe próbkowanie, przynajmniej jeśli średni przypadek jest znacznie lepszy.

— Raphael

ps byłoby pomocne, gdybyś zamieścił gdzieś przykłady przypadków

— wysadzenia

idea / lead: LR parsing permutations (cstheory.se)

— vzn

LALR (1) jest powszechnie przedstawiany jako sposób na dostateczne zbliżenie się do mocy LR (1), aby był użyteczny przy wielu mniejszej liczbie stanów (aby użyć słów z książki Smoka). Zastanawiam się, czy wystarczyłby czynnik 2 do 4, aby odrzucić LR (1) jako wygórowany aż do wynalezienia LALR (1). Jeśli pomyślę o tym, kiedy będą dostępne, przejdę do Aho & Ullman Teoria parsowania, tłumaczenia i kompilacji oraz w technikach parsowania Grune, jeśli mają coś na temat liczb.

— AProgrammer

Odpowiedzi:

Gramatyka

\begin{array}{l} S \to T_{0} \\ T_{n} \to a T_{n + 1} \\ T_{n} \to b T_{n + 1} \\ T_{n} \to b T_{n + 1} t_{n} \\ T_{N} \to t_{N} \end{array}

$\begin{array}{l} S \rightarrow T_0 \\ T_n \rightarrow a \; T_{n+1} \\ T_n \rightarrow b \; T_{n+1} \\ T_n \rightarrow b \; T_{n+1} \; t_n \\ T_N \rightarrow t_N \end{array}$

T_{N} \to t_{N} \dot{}

$T_N \rightarrow t_N \dot \\$

2^{N}

$2^N$

{t_{0} \dots t_{N - 1}}

$\{t_0 \dots t_{N-1}\}$

N

$N$

2^{N} / N

$2^N/N$

~~$T_N \rightarrow T_0$~~

— AProgrammer
źródło

Takie dolne granice są czasem trudne do skonstruowania i mogą wywoływać głębszą teorię CS (np. W przypadkach separacji klas złożoności). Ten artykuł wydaje się dać teoretyczną konstrukcję / dolne granice, których szukasz, np. W Twierdzeniu 5, które nakłada dolną granicę na wszystkie symbole, a zatem także na stany. Odniesienia obejmują również inne podobne konstrukcje / dolne granice.

$f(n,k) = 2^{\frac{1}{4}(n - k)} / n^2$ $k = 0,1;...,n−1$ $L_n$ $n \geq 3$ $f(n,k)$ $f(n,k)$

Na temat wielkości parserów i gramatyk LR (k) / Leunga, Wotschkeb

— vzn
źródło

2^{(n - 1) / 4} / n^{2}

$2^{(n-1)/4}/n^2$

2^{n / 4} / n^{2}

$2^{n/4}/n^2$ związany z wielkością automatu LR (0) dla tego języka. Tak więc ta odpowiedź nie odpowiada na zadane pytanie.

— DW

1.1892

$1.1892$

DW uważa, że Twój sprzeciw jest zarówno uzasadniony, jak i dotyczy rozszczepiania włosów. bardzo dziękuję za wyjaśnienie / szczegół. jest to odpowiednia / prawie bezpośrednia odpowiedź naukowa na / systematyczne badanie jego pytania, które zasadniczo dotyczy konstrukcji najgorszego przypadku / wysadzenia w LR (n). możliwe, że są to (prawie?) „najbardziej znane wyniki” w tej dziedzinie. prawidłowa odpowiedź na pytanie może być przecząca, inaczej NIE, nie są znane lepsze wyniki niż te znalezione przez pytającego (jeszcze go nie pokazał ) lub w literaturze. z niecierpliwością oczekuję na ostateczne odpowiedzi!

— vzn