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.
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∖BBAB/ABAA∗BAB
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.
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.
Ponowne odtworzenie interpretacji Vailanta w postaci mnożenia macierzy CFG-parsowania w języku gramatyki Lambek jest prawdopodobnie czymś więcej niż tylko ćwiczeniem ...
Martin Berger
1
@MartinBerger: czy to jest lepsze? :)
Neel Krishnaswami,
Jest tylko jeden sposób, aby się przekonać!
Martin Berger,
2
Umm, ale „gramatyka kategorialna” odnosi się do lingwistycznego pojęcia kategorii ( en.wikipedia.org/wiki/Syntactic_category ), nie obejmuje teorii kategorii matematyków. Więc odpowiedź nie ma nic wspólnego z pytaniem.
Emil Jeřábek
2
Rachunek Lambka (który jest jednym z głównych formalizmów gramatyki kategorialnej) jest rzeczywiście kategoryczny w sensie teorii kategorii - jest to syntaktyczna teoria podwójnie ułożonych kategorii monoidalnych, a Lambek był tego świadomy. W języku teorii dowodu kategorie językoznawstwa dają „twierdzenia atomowe” rachunku Lambka.
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.
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.
źródło