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 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!
źródło
Odpowiedzi:
Gramatyka
ź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.
Na temat wielkości parserów i gramatyk LR (k) / Leunga, Wotschkeb
źródło