Parsery Scala: dostępność, różnice i łączenie?

Question

Moje pytanie jest o Scala parserami:

• Które z nich są dostępne (w bibliotece standardowej i na zewnątrz),
• jaka jest różnica między nimi,
• one mają wspólny API i
• Czy można łączyć różne parsery w celu przeanalizowania jednego ciągu wejściowego?

znalezionych w przynajmniej te:

• Scala "standardowe" parser (wydaje się parser LL)
• Scala Packrat parser (od 2,8 to parser LALR)
• Parboiled parser (PEG parser?)
• Śpiewak na GLL parser syntezatora

Answer 1

Chciałbym zaktualizować tę odpowiedź z wskaźnik do najnowszej iteracji projektu parzony, zwany parboiled2:

https://github.com/sirthias/parboiled2

parboiled2 cele tylko Scala (w przeciwieństwie do Scala + Java), wykorzystuje Makra Scala i są bardzo aktywnie utrzymywane.

Answer 2

Istnieje również implementacja Dana Śpiewaka: GLL parser combinators.

Answer 3

Istnieje również nowe podejście znane jako "parsowanie za pomocą instrumentów pochodnych". Podejście to opisano here. Jest implementation in Scala autorstwa Daniela Śpiewaka.

Answer 4

Warto zauważyć, że standardowe kombinatory parsera Scali nie są LL, ani też kombinatory Packrat LALR. Kombinatory parserów są formą rekurencyjnego zejścia z nieskończonym cofaniem. Możesz myśleć o nich trochę jak "LL (*)". Klasa języków obsługiwanych przez tę technikę to dokładnie klasa jednoznacznych języków bezkontekstowych lub ta sama klasa co LALR (1) i Packrat. Jednak klasa gramatyki gramatycznej jest trochę inna, z najbardziej znaczącą słabością jest brak wsparcia dla rekursji lewej.

packrat kombinatorów zrobić wsparcia lewej rekursji, ale nadal nie obsługują wiele innych, bardziej subtelnych cech LALR. Ta słabość generalnie wynika z uporządkowanego operatora wyboru, który może prowadzić do kilku diabelnie trudnych błędów gramatycznych, a także zapobiega pewnym przyjemnym formułom gramatycznym. Najczęściej spotykany przykład tych błędów pojawia się, gdy przypadkowo zlecasz niejednoznaczne wybory jako najkrótsze, co powoduje chciwą zapowiedź, która uniemożliwia wypróbowanie prawidłowej gałęzi. LALR nie ma tego problemu, ponieważ po prostu próbuje wszystkie możliwe gałęzie naraz, odraczając punkt decyzyjny do końca produkcji.