Zasoby online do pisania parser-generator

Question

Chcę napisać generator parserów do celów edukacyjnych i zastanawiałem się, czy są jakieś fajne zasoby online lub samouczki, które wyjaśniają, jak je napisać. Coś na linii "Zbudujmy kompilator" Jacka Crenshawa.

Chcę napisać generator parsera dla gramatyki LR (1).

Mam dobre zrozumienie teorii generowania tabel akcji i goto, ale chcę mieć pewne zasoby, które pomogą mi go wdrożyć.

Preferowanymi językami są C/C++, Java, ale nawet inne języki są w porządku.

Dzięki.

Answer 1

Zgadzam się z innymi, książka Smoka jest dobrym tłem do parsowania LR.

Jeśli jesteś zainteresowany rekurencyjnych parserami schodzenie, ogromnie zabawne doświadczenie uczenia się jest to strona internetowa, która poprowadzi Cię przez budowanie całkowicie autonomiczny układ kompilatora, który można skompilować siebie i innych językach:

MetaII Compiler Tutorial

To wszystko opiera się na niesamowitym, 10-stronicowym dokumencie technicznym autorstwa Val Schorre: META II: Kompilatorowy język programowania kompilatora od uczciwego do boga 1964. Nauczyłem się budować kompilatory od tego czasu w 1970 roku. Jest niesamowity moment, kiedy wreszcie dowiadujesz się, jak kompilator może się zregenerować ...

Znam autora strony internetowej z moich dni szkolnych, ale nie mam nic wspólnego ze stroną.

Answer 2

Niezupełnie online, ale Dragon Book ma dość rozbudowane dyskusje dotyczące parsowania LR.

Answer 3

Jeśli chciałbyś pójść na trasę Pythona, poleciłbym poniższe.

• Text Processing in Python
• Pyparsing

znalazłem zarówno z nich jest bardzo pomocny i Paul McGuire autor pyparsing jest super co pomaga, gdy pojawią się problemy. Książka Przetwarzanie tekstu w Pythonie jest po prostu przydatnym odnośnikiem do twoich palców i pomaga ci we właściwym nastroju podczas próby zbudowania parsera.

Chciałbym również zwrócić uwagę, że język OO jest lepiej dopasowany do mechanizmu analizowania języka, ponieważ jest rozszerzalny, a polimorfizm jest właściwą metodą (IMHO). Patrząc na problem w kategoriach automatu stanów, zamiast "Szukaj średnika na końcu xyz", pokaże się, że twój parser staje się w końcu bardziej wydajny.

Nadzieję, że pomaga!

Answer 4

Zauważyłem, że łatwiej jest nauczyć się pisać parsery rekursywno-opadowe, zanim nauczysz się pisać parsery LR. Cóż, szczerze mówiąc, po wielu latach pisania analizatorów nigdy nie uważałem za konieczne napisania parsera LR.

Niedawno napisałem samouczek w CodeProject pod nazwą Implementing Programming Language Tools in C# 4.0, który opisuje techniki parsowania rekursywnych zniżek.