Dobre książki na temat teorii parserów?

Jeden z moich projektów Java jest rozwidleniem parboiled i, w przeciwieństwie do powiedzmy Antlr lub JavaCC, parsery są generowane w czasie wykonywania. Generowane gramatyki to gramatyka wyrażeń parsujących lub PEG (słyszę, że innym terminem jest „packrat”).

Podczas gdy generowanie środowiska wykonawczego zwiększa złożoność (generowanie kodu bajtowego), inny aspekt dotyczy samej teorii parsera. Ponieważ nie mam niestety solidnego doświadczenia w informatyce, brakuje mi wiedzy teoretycznej do mapowania istniejącego kodu na istniejące koncepcje - w tym przypadku parsery.

Czy istnieje dobra książka referencyjna na temat parserów, którą mogę kupić i przeczytać, a nawet linki w Internecie, które mogą pomóc mi w zbudowaniu takiego „mapowania”, biorąc pod uwagę moją słabą wiedzę teoretyczną?

Jedną z książek, którą mogę polecić, jest D. Grune, CJH Jacobs, Parsing Techniques: a Practical Guide .

Jeśli chcesz poznać teorię parserów, polecam tom 1 tej klasycznej książki:

Aho, Alfred V .; Ullman, Jeffrey D., Teoria parsowania, tłumaczenia i kompilacji , Prentice-Hall (1972).

Jeśli nie przeszkadza ci różnica językowa, rozdział 8 Perla wyższego rzędu dotyczy parsowania, aw szczególności buduje rekursywny parser descent za pomocą kombinacji parserów. Jest dostępny (jeśli nie boisz się Perla) i dostępny do czytania za darmo, jeśli chcesz. Pomogło mi to zainteresować się technikami parsowania kilka lat temu.

Podczas gdy techniki parsowania to świetna książka, a kilka razy przeczytałem kilka części, koncentruje się ona na analizie LR, która nie będzie dla ciebie interesująca. W twoim konkretnym przypadku patrzysz na PEG-y, które są rodzajem rekursywnego parsowania z góry na dół z cofaniem opartym na kolejności alternatyw.

Chciałbym zasugerować, aby spojrzeć na kombinatory parsera, które używają tej samej strategii. Możesz na przykład sprawdzić ten artykuł http://research.microsoft.com/pubs/65201/parsec-paper-letter.pdf, który używa Haskell do budowy kombinacji parserów. Sprawdź sekcję, w try której zawierają zwrot (sekcja 3.4).

W każdym razie musisz się nauczyć:

• parsowanie rekurencyjno-opadające i gramatyki LL
• naprawiony lookahead vs. nieskończony lookahead (wykonane przez backtracking)
• strategie cofania
• jak radzić sobie z lewostronnymi zasadami rekurencyjnymi
• Zapamiętywanie częściowych wyników w celu uniknięcia zachowania wykładniczego