Analiza składni z przesunięciem - pytania

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 → ω $a, b, c, ... \in T$$A, B, C, ... \in N$$... X, Y, Z \in N \cup T$$\alpha, \beta, \gamma, ... \in \{N \cup T\}^*$$A \xrightarrow{i} \omega$$i$

Ponadto w całym opisie stosowana jest relacja równoważności .$\kappa_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 .$A \xrightarrow{i} \alpha \bullet \beta$$A \xrightarrow{i} \alpha \bullet \beta, m, n$m $n$$m$$\beta$

Gramatyka jest powiększona o regułę a konstrukcja rozpoczyna się od pozycji przesunięcia w stanie początkowym.S ′ 0 → ∙ S $S' \xrightarrow{0} S \$$$S' \xrightarrow{0} \bullet S \$$

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 $A \xrightarrow{i} \alpha \bullet \beta$$q \xrightarrow{X} q'$$X$$\beta$

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 $A \xrightarrow{i} \omega \bullet$$B \xrightarrow{j} \alpha A \bullet \beta, i, 0$$B \xrightarrow{j} \alpha A \beta$

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 $A \xrightarrow{i} \alpha \bullet \beta, m, n$$X$$\beta$$X \in N$$X \xrightarrow{j} \bullet \omega$$X \xrightarrow{j} \omega$$A \xrightarrow{i} \alpha \bullet \beta, m, n$$X$ C i → α ∙ X β , m , n q C i → α X ∙ β , $q \xrightarrow{X} q'$$C \xrightarrow{i} \alpha \bullet X \beta, m, n$$q$q $C \xrightarrow{i} \alpha X \bullet \beta, m, n + 1$$q'$ .

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$A \xrightarrow{i} \omega \bullet, m, n$$B \xrightarrow{j} \alpha A \bullet \beta, m, n$$B \xrightarrow{j} \alpha A \beta$

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.$r_{0,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 $\kappa$$\kappa_0$$FOLLOW_{LM}$

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

Sprawdź, czy jest to omówione w encyklopedycznej D. Grune, CJH Jacobs, „Parsing Techniques: a Practical Guide” (Spinger, 2008). Jeśli nie, być może jest to wystarczająco podobne do omawianej techniki.