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

10

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 2 nnn2n

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!

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
2
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:

2

Gramatyka

ST0TnaTn+1TnbTn+1TnbTn+1tnTNtN

TNtN˙
2N{t0tN1}N2N/N

TNT0

AProgrammer
źródło
0

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)=214(nk)/n2k=0,1;...,n1Lnn3f(n,k)f(n,k)

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

vzn
źródło
2(n1)/4/n22n/4/n2związany z wielkością automatu LR (0) dla tego języka. Tak więc ta odpowiedź nie odpowiada na zadane pytanie.
DW
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