Teoria kategorii i parsery - potrzebne referencje

Ponieważ interesuję się parserami (głównie gramatykami wyrażeń parsera), zastanawiam się, czy jest jakaś praca, która daje kategoryczne traktowanie parsowania. Wszelkie odniesienia do zastosowania teorii kategorii do analizy składniowej są bardzo mile widziane.

Najlepsza,

Jednym z pierwszych zastosowań teorii kategorii w temacie spoza geometrii algebraicznej było parsowanie! Kluczowymi słowami, które chcesz przeprowadzić przy wyszukiwaniu, są „rachunek Lambka” i „gramatyka kategoryczna”.

Współcześnie Joachim Lambek wynalazł nieprzemienną logikę liniową w celu modelowania struktury zdań. Podstawową ideą jest to, że możesz podać podstawowe części mowy jako posiadające typy, a następnie (powiedzmy) przypisać angielskie przymiotniki rodzaj funkcji, używając wyrażeń rzeczownikowych do wyrażeń rzeczownikowych. (np. „zielony” jest postrzegany jako funkcja przenoszenia rzeczowników do rzeczowników, co oznacza, że ​​„zielone jajka” są dobrze wpisane, ponieważ „jajka” to rzeczownik).

$A\setminus{}B$$B$$A$$B/A$$B$$A$$A \ast B$$A$$B$

Okazuje się, że gramatyki Lambek są równoważne z językami bezkontekstowymi, choć najwyraźniej jest to dość trudny wynik - pokazanie CFG stanowią podzbiór gramatyki Lambek jest łatwe, ale inny kierunek został ustanowiony dopiero w 1991 roku przez Pentusa.

Dobrym ćwiczeniem ^ H ^ H ^ Publikacja dla czytelnika (tj. Nie próbowałem tego, ale myślę, że fajnie byłoby spróbować) polega na użyciu rachunku Lambka do przeformułowania prezentacji Valiant analizy CYK za pomocą mnożenia macierzy logicznej , w kategoriach warunki. Jako motywację przytaczam artykuł Lambka z 1958 r. Matematyka struktury zdań :

Rachunek przedstawiony tutaj jest formalnie identyczny z rachunkiem skonstruowanym przez GD Findlay i obecnego autora w celu omówienia odwzorowań kanonicznych w algebrze liniowej i wieloliniowej.

Wydaje się, że (bez kontekstu) parsowanie a la Parsec jest naturalnie wyrażone w kategoriach klasy typu aplikacyjnego . Z kolei klasę tę dobrze opisują tak zwane mocne luźne funktory monoidalne , o których mowa w tym bardzo ładnym pytaniu o cstheory i tym miłym pytaniu o przepełnienie stosu .

Mówiąc bardziej ogólnie, parsery Parsec to monady , które są tak dobrze znane zarówno w teorii CS, jak i teorii kategorii, że nie zamierzam podawać referencji, chyba że zostanie o to poproszony.