Pomóż zrozumieć parsery LR (1), generowanie tabel? Wszelkie inne zasoby?

Question

Obecnie zajmuję się klasą kompilatorów i mam problem ze zrozumieniem algorytmów analizowania LR (1) za pomocą tabeli akcji/goto oraz sposobu generowania tych tabel. W tej chwili używamy Inżynierii Kompilatora przez Coopera i Torczona jako podręcznika naszej klasy, a także czytałem strony wikipedii na temat generacji stołów, ale wciąż nie rozumiem tych pojęć. Jeśli to możliwe, czy ktoś może polecić jakąkolwiek inną książkę, która wyjaśniałaby parsowanie lub zasoby online? Myślę, że wiele uniwersytetów miałoby dobre internetowe zasoby/slajdy na ten temat, ale nie mam pojęcia, od czego zacząć. Dzięki!

Answer 1

kilka przyzwoitych notatki wykładowe ...

http://cs.oberlin.edu/~jdonalds/331/lecture14.html

zrozumieniem i pisania Kompilatory posiada sekcję, jakie są Prawdziwi Zalety LR (1) analizy?

http://www.amazon.com/Understanding-Writing-Compilers-Yourself-Macmillan/dp/0333217322

(dostępny również swobodnie online)

Tu jest link do godnej Podsumowując, chociaż wyjaśnienie brakuje.

http://arantxa.ii.uam.es/~modonnel/Compilers/LR1Summary.pdf

więcej wykład notatki ...

http://www.cs.umd.edu/class/spring2011/cmsc430/lectures/lec07.pdf

i zauważa tutaj ...

http://cobweb.ecn.purdue.edu/~smidkiff/ece495S/files/handouts/w3w4bBW.pdf

(w tym goto i działania tabel)

Przepraszam, nie mogę osobiście wyjaśnić, sam nie jestem zbyt pewien. Może znajdziesz wokół siebie rodzaj mądrzejszej duszy.

Answer 2

Książki są zawsze trudne do odczytania ze względu na szczegóły algorytmu. Greckie symbole i abstrakcyjne operacje są trudne do zinterpretowania, chyba że już wiesz, co one oznaczają.

Sposób dowiedziałem się, jak to zrobić, to napisać drobny gramatyki (proste wyrażenie, instrukcji przypisania, jeśli wtedy oświadczenie, sekwencji instrukcji), a następnie ręka symulacji algorytmu. Zdobądź naprawdę dużą kartkę papieru. Narysuj początkowy stan konfiguracji za pomocą symbolu celu i kropki [G = DOT RHS1 ... RHSM]. Następnie przetwarzaj nieprzetworzone stany, postępując zgodnie z algorytmem; zapisz co symbol grecki reprezentuje w tym momencie. Gdy zdobędziesz pewność siebie, poczujesz się lepiej i szybciej.

Zasadniczo, co masz zamiar zrobić, to dla każdej pozycji I

[LHS RHS1 DOT RHS2 RHS3 ... RHSN] 

w stanie wcisnąć kropkę w punkcie o jedno miejsce w prawo produkować nowy artykuł

[LHS RHS1 RHS2 DOT RHS3 ... RHSN ] 

remisu nowy stan na twoim papierze nowy stan z tym elementem, jako materiałem siewnym, wypełnij rdzeń przedmiotu zestawami uprzedzającymi w oparciu o PIERWSZY (RHS3), rozwiń stan i powtórz.

To zajmie Ci kilka godzin przy pierwszym użyciu. Warto co sekundę. Użyj ołówka!