Uogólnione oddolne parsera kombinatorów w Haskell

Question

ja zastanawiałem się, dlaczego nie ma uogólnione kombinatorów parser dla Analiza wstępująca w Haskell jak parseka kombinatorów dla Analiza zstępująca.
(udało mi się znaleźć niektóre prace badawcze w 2004 roku udał się, ale nic po
https://haskell-functional-parsing.googlecode.com/files/Ljunglof-2002a.pdf http://www.di.ubi.pt/~jpf/Site/Publications_files/technicalReport.pdf)

Czy jest jakiś szczególny powód, dla nie go zrealizować?

Answer 1

To ze względu na więzy przejrzystości. Podobnie jak brak funkcji można odróżnić

let x = 1:x 
let x = 1:1:1:x 
let x = 1:1:1:1:1:1:1:1:1:... -- if this were writeable 

brak funkcji można odróżnić gramatyki, który jest skończonym wykres i gramatyki, która jest nieskończona drzewo. Zasadnicze algorytmy parsowania muszą być w stanie zobaczyć gramatykę jako wykres, aby wyliczyć wszystkie możliwe stany parsowania.

Fakt, że parser odgórne zobaczyć ich wkład jako nieskończonych drzewach pozwala im być bardziej wydajne, ponieważ drzewo może być obliczeniowo bardziej skomplikowane niż każdy wykres może być; Na przykład,

numSequence n = string (show n) *> option() (numSequence (n+1)) 

ponosi żadnej skończoną sekwencję wzrastające cyfr począwszy od n. Ma to nieskończenie wiele różnych stanów analizowania. (Może być możliwe reprezentowanie tego w sposób bezkontekstowy, ale byłoby to trudne i wymagałoby większego zrozumienia kodu, niż biblioteka parsująca jest w stanie, jak sądzę,)

U dołu biblioteka kombinatorów może być napisany, choć jest nieco brzydki, wymagając wszystkie parsery być „oznaczone” w taki sposób, że

• taka sama etykieta odnosi się zawsze do tego samego parsera i
• jest tylko zbiorem skończonym etykiet

w którym to momencie zaczyna wyglądać bardziej jak tradycyjna specyfikacja gramatyki niż kombinatoryczna specyfikacja. Jednak nadal może być przyjemny; musielibyśmy tylko etykietować produkcje rekursywne, co wykluczałoby wszelkie nieskończenie duże reguły, takie jak numSequence.

Answer 2

Jako odpowiedź luqui wskazuje na niewolną bibliotekę kombinator biblioteka nie jest realistyczna. Na przypadek, że ktoś ją na tej stronie po prostu patrząc na dnie Haskell zależy parsera generator, czego szukasz nazywa the Happy parser generator. To jest jak yacc dla haskell.

Answer 3

Jak wspomniano powyżej luqui: leczenie Haskell'a definicji parsera rekurencyjnych nie pozwala definicję oddolnych bibliotek analizy. Odwrócone biblioteki parsowania są jednak możliwe, jeśli reprezentujesz gramatykę rekursywną w inny sposób. Z przeprosinami za autopromocję jedna (badawcza) biblioteka parsera, która używa takiego podejścia, to grammar-combinators. Implementuje transformację gramatyczną zwaną jednolitą transformacją typu Paull, którą można łączyć z algorytmem parsera od góry w dół w celu uzyskania parsera oddolnego dla oryginalnej gramatyki.