Uogólnienia metody Brzozowskiego pochodnych wyrażeń regularnych do gramatyki?

Metoda pochodnych Brzozowskiego jest bardzo ładną techniką do budowania deterministycznych automatów z wyrażeń regularnych w ładnie algebraiczny sposób. Opracowałem kilka uroczych uogólnień tej techniki do obsługi niektórych większych klas gramatycznych, ale algorytmy są na tyle proste, że wydaje się całkiem możliwe, że zostały wcześniej odkryte. Ale wydaje się, że odniesienia do potomków tej techniki nie pojawiają się zbyt wiele. Czy ktoś coś wie?

W Total Parser Combinators (ICFP 2010) używam pochodnych Brzozowskiego, aby ustalić, że członkostwo w języku jest decydujące dla pewnej klasy potencjalnie nieskończonych gramatyk.

Ten artykuł może Cię zainteresować:

Yacc is Dead według Matthew Might i David Darais, 2010

Prezentujemy dwa nowe podejścia do parsowania języków bezkontekstowych. Pierwsze podejście opiera się na rozszerzeniu pochodnej Brzozowskiego z wyrażeń regularnych na gramatyki bezkontekstowe. Drugie podejście opiera się na uogólnieniu pochodnej na kombinatory parsera. Zaletą tych technik jest niewielka (mniej niż 250 linii kodu), łatwa do wdrożenia biblioteka parsująca, zdolna do parsowania dowolnych gramatyk bezkontekstowych w leniwych parsach. Zapewniono implementacje zarówno dla Scali, jak i Haskell. Wstępne eksperymenty z wyrażeniami S analizowały miliony tokenów na sekundę, co sugeruje, że ta technika jest wystarczająco wydajna do zastosowania w praktyce.

Również potencjalnie interesujące:

• Yacc is Not Dead , recenzja tego artykułu autorstwa Russ Cox, o sławie re2 .
• Yacc nie żyje: aktualizacja , odpowiedź Matt Might.
• Functional Pearl: Parsing with Derivatives autorstwa Matthew Might, David Darais i Daniel Spiewak - zaktualizowana wersja artykułu „Yacc is Dead”, zaprezentowanego na ICFP 2011 w Tokio.

W połowie lat 80., kiedy pracowałem nad rekurencyjnymi parserami wynurzania i faktoringiem gramatyki, zacząłem od zdefiniowania częściowych pochodnych gramatyk.

Dużo ładnej teorii.

Czy masz jakieś konkretne pytania?