Analiza składni z przesunięciem - pytania

10

Ostatnio natknąłem się na artykuł opisujący technikę parsowania wspomnianą w tytule. Niestety terminologia zastosowana we wspomnianym artykule jest nieco poza moim zrozumieniem, więc starałem się zrozumieć algorytm konstrukcji bardziej intuicyjnie. Wierzę, że mi się udało ( ta prezentacja była źródłem momentu ah-ha), ale doceniona zostanie weryfikacja poprawności przez kogoś, kto zna technikę lub zawartą w niej terminologię.

Opiszę swoje podejście do rozwiązania (jeśli jest poprawne, uważam, że mogłoby to pomóc innym osobom próbującym zrozumieć technikę) i zadam dodatkowe pytania. Aby uniknąć nieporozumień, użyję następującej standardowej notacji: , , , i, jak w artykule, dla oznaczenia reguły numer . Jednak prawdopodobnie użyję innych nazw pojęć niż oryginalny artykuł., B , C , . . . N . . . X , Y , Z N T α , β , γ , . . . { N T } A i ω ia,b,c,...TA,B,C,...N...X,Y,ZNTα,β,γ,...{NT}Aiωi

Ponadto w całym opisie stosowana jest relacja równoważności .κ0

Budowa

Istnieją dwa rodzaje elementów wewnątrz automatu analizującego: proste elementy LR (0) w postaci które nazywam elementami przesuwnymi i elementy w postaci które nazywam elementami rozstrzygania ; informują one parsera, aby wypchnął symboli z powrotem do strumienia wejściowego, a następnie zmniejszył liczbę reguł o pierwszy symbol .AiαβAiαβ,m,nm βnmβ

Gramatyka jest powiększona o regułę a konstrukcja rozpoczyna się od pozycji przesunięcia w stanie początkowym.S 0S $S0S$S0S$

Teraz, aby zbudować automat, zdecyduj pomiędzy tymi alternatywami dla każdego elementu w stanie :q

  1. Jeśli element jest przesuniętym przedmiotem , nastąpi przejście w automacie, gdzie jest pierwszym symbolem .q X q X βAiαβqXqXβ

  2. Jeśli element jest ukończonym przesunięciem elementu , dodaj element rozstrzygania dla każdej reguły .B j α A β , i , 0 B j α A βAiωBjαAβ,i,0BjαAβ

  3. Jeśli przedmiot jest elementem rozstrzygającym , niech będzie pierwszym symbolem . Jeśli , dodaj pozycję przesunięcia dla każdej reguły . Jeśli inne elementy niż mają jako kropkę przed sobą, dodaj do automatu przejście . Każdy element rozwiązać , w spowoduje w elemencie rozwiązać wX β X N X jω X j ω A i α β , m , n XAiαβ,m,nXβXNXjωXjωAiαβ,m,nX C i α X β , m , n q C i α X β , mqXqCiαXβ,m,nqq CiαXβ,m,n+1q .

  4. Jeśli przedmiot jest elementem rozstrzygającym , nie wniesie żadnych informacji dotyczących przyszłości i może zostać odrzucony, ale najpierw dodaj element rozstrzygający dla każdej reguły .B jαAβ,m,nB jαAβAiω,m,nBjαAβ,m,nBjαAβ

To oczywiście tylko szkic; w rzeczywistości najpierw należy obliczyć zamknięcie państwa, a dopiero potem możemy poradzić sobie z przejściami / zmianami i rozdzielczościami.

Przekształcenie automatu w stół analizujący z przesunięciem i przesunięciem jest trywialne; po prostu, jako niewielka odmiana, autorzy artykułu interpretują rozdzielczość jako akcję akceptacji. Biorąc pod uwagę powstały automat, uznałem, że wygodniej jest traktować zmianę jako akcję akceptacji. $r0,0$

pytania

Pierwszym z nich jest oczywiście to, czy opisany powyżej proces jest prawidłowy.

Drugi dotyczy relacji równoważności. Mogę tylko zgadywać, że relacja równoważności jest odpowiedzialna za podejmowanie decyzji, które elementy rozstrzygania są wprowadzane, gdy widzi się gotowy element zmiany. Wygląda na to, że że jest uderzająco podobny do parserów LSLR. Artykuł opisuje „dokładniejszą relację równoważności” na stronie 11; czy istnieje sposób interpretacji tej relacji w kategoriach intuicyjnych? Czy znane są inne relacje?κ 0 F O L L O W L Mκκ0FOLLOWLM

I ostatni dotyczy rozwiązywania konfliktów. Artykuł dobrze opisuje, co stanowi nieadekwatność automatu z rozdzielczością zmiany; czy istnieje sposób na rozwiązanie tych niedociągnięć, podobny do sposobów rozwiązywania konfliktów w tradycyjnym parserze LR? Czy coś takiego jak rozwiązywanie konfliktów w stylu yacc poprzez pierwszeństwo i asocjatywność można zaimplementować w generatorze parsera ShRe?

Dzięki, jeśli przeczytasz to wszystko, a wszelkie odpowiedzi będą mile widziane :)

Jakub Lédl
źródło
sugeruj migrację tego pytania do cstheory. co do artykułu, wydaje się być bardzo złożonym algorytmem, który „prawdopodobnie” (?) nie został przez nikogo zaimplementowany. wydaje się, że główną ideą jest połączenie arbitralnego spojrzenia w przyszłość, ale także z liniowym analizowaniem czasu ...? ale ile aplikacji byłoby w porządku z prostszym, bardziej standardowym, superliniowym algorytmem? jakiś pomysł, która aplikacja działałaby lepiej przy takim podejściu? masz jeden lub wiesz o jednym?
vzn
1
Bardzo fajne ćwiczenie teoretyczne (choć nie patrzyłem na szczegóły techniczne). Biorąc pod uwagę, że pełna moc LR (k) często nie jest nawet używana, można się zastanawiać nad praktycznym wpływem. Widzę 2 problemy z tego rodzaju pracą: (1) skoro algorytm staje się bardziej złożony, czy nadal jest możliwe, aby ludzki umysł zmienił gramatykę i zrozumiał konsekwencje, gdy okazuje się, że nie działa. Często zdarza się, że wysoce wyrafinowane techniki są bardzo satysfakcjonujące, gdy działają, ale pogarszają sytuację, gdy nie działają. (2) czy będzie liniowy w przypadkach, gdy ogólne algorytmy CF nie są liniowe.
babou

Odpowiedzi: