Jakie modele obliczeń można wyrazić za pomocą gramatyki?

18

To jest przeformułowanie Czy programy gramatyczne? poprzednio zadane przez Vag i z wieloma sugestiami komentujących.

W jaki sposób można postrzegać gramatykę jako model obliczeń? Jeśli na przykład weźmiemy prostą gramatykę bezkontekstową, taką jak

G ::= '1' -> '0' '+' '1'
      '1' -> '1' '+' '0'
      '2' -> '2' '+' '0'
      '2' -> '1' '+' '1'
      '2' -> '0' '+' '2'
      '3' -> '3' '+' '0'
      '3' -> '2' '+' '1'
      '3' -> '1' '+' '2'
      '3' -> '1' '+' '2'

Zakładając, że parser nie rozróżnia między symbolami terminalnymi i nieterminalnymi, jak to tutaj wykazałem, możliwe jest wykonanie prostej arytmetyki dla liczb do 3.

Na przykład weź ciąg

"2 + 0 + 1"

Uruchomienie parsera LR (1) na tym ciągu powinno dać nam następujące konkretne drzewo składniowe, w którym wynik obliczeń jest przechowywany w katalogu głównym drzewa:

           '3'
         /  |  \
        /   |   \
      '2'  '+'  '1'
     / | \
    /  |  \
  '2' '+' '0'

Zatem, jeśli weźmiemy gramatykę za program, a generator parsera za kompilator , to czy moglibyśmy postrzegać język specyfikacji gramatyki jako język programowania ?

Ponadto, czy moglibyśmy zbudować kompletne programy Turinga, określając gramatyki podobne do tego, w jaki sposób można budować kompletne programy Turinga za pomocą automatów celullarnych lub rachunku lambda ?

Innymi słowy, wiadomo, że w sensie rozpoznawania języka, zwykłe języki odpowiadają automatom skończonym , języki bezkontekstowe odpowiadają automatom przesuwającym w dół , a języki kontekstowe odpowiadają automatom ograniczonym liniowo . Jeśli jednak patrzymy na gramatykę jako urządzenia obliczeniowe (tj. Programy w rozumieniu powyższego przykładu), to w jaki sposób klasyfikujemy siłę obliczeniową każdej klasy gramatyki w hierarchii Chomsky'ego?

A co powiesz na mniej znane podklasy gramatyki, takie jak

Deterministyczne gramatyki bezkontekstowe (także LR (k) / LL (k) / SLR / LALR itp.)
Zagnieżdżone gramatyki słów
Gramatyki przylegające do drzewa
Indeksowane gramatyki

EDYTOWAĆ: Nawiasem mówiąc, to jest nitpick na moje własne pytanie, ale nie wspomniałem, że nie podałem żadnego symbolu początkowego dla gramatyki przykładowej i machałem ręką na potrzebę rozróżnienia terminali od nieterminali. Technicznie lub tradycyjnie myślę, że gramatyka prawdopodobnie musiałaby być napisana w bardziej skomplikowanej formie, takiej jak ta (gdzie S jest symbolem początkowym, a $ oznacza terminal końca strumienia):

G ::= S -> R0 '$'
      S -> R1 '$'
      S -> R2 '$'
      R0 -> '0'
      R0 -> R0 '+' '0'
      R1 -> '1'
      R1 -> R0 '+' '1'
      R1 -> '1' '+' R0
      R1 -> R0 '+' '1' '+' R0
      R2 -> '2'
      R2 -> R0 '+' '2'
      R2 -> '2' '+' R0
      R2 -> R0 '+' '2' '+' R0
      R2 -> R1 '+' '1'
      R2 -> R1 '+' '1' '+' R0

... nie żeby to naprawdę coś zmieniało, ale pomyślałem, że powinienem o tym wspomnieć.

EDYCJA: Coś innego, co przyszło mi do głowy, gdy czytam odpowiedź Gaschego, polega na tym, że każda gałąź drzewa w moim przykładzie reprezentuje obliczenia podrzędne. Jeśli spojrzysz na każdą regułę produkcyjną jako funkcję, w której LHS reprezentuje wynik, a RHS reprezentuje jej argumenty, to struktura gramatyki określa sposób tworzenia funkcji.

Innymi słowy, kontekst parsera wraz z mechanizmem lookahead pomaga nie tylko określić, które funkcje należy zastosować („trochę”, jak polimorfizm parametryczny), ale także to, jak należy je połączyć, aby utworzyć nowe funkcje.

Przynajmniej myślę, że możesz spojrzeć na to w ten sposób w przypadku jednoznacznych CFG, dla innych gramatyki gimnastyka mentalna jest dla mnie teraz trochę za dużo.

— Rehno Lindeque
źródło

3

Zapomniałeś wspomnieć o Automatycznie widocznym wypychaniu (Nested Words), tak pięknym i obiecującym urządzeniu! Jest to ważne, ponieważ wydaje się, że jest to minimalna poprawa w stosunku do wyrażeń regularnych, aby móc analizować programy napisane w popularnych językach programowania. ( cis.upenn.edu/~alur/nw.html )

— Vag

1

Dzięki, to bardzo interesujące, nie sprawdziłem tego! Jest jeszcze kilka innych, które pominąłem, jak deterministyczne, bezkontekstowe, przylegające do drzewa, indeksowane i tak dalej, po prostu pomyślałem, że może to być trochę za jedno pytanie ... Ale może dodam je

— Rehno Lindeque

1

@imz Mam na myśli gramatykę, ponieważ są one formalnie zdefiniowane w hierarchii Chomsky'ego (tj. jako zestawy produkcji). Ponieważ twierdzę dokładnie, co mówisz: gramatyki są programami, oznacza to po prostu klasę programów reprezentowanych przez gramatykę (co jest pytaniem).

— Rehno Lindeque

1

@imz Szczerze mówiąc, naprawdę nie jestem zaznajomiony z indeksowanymi gramatykami, dodałem je tylko w myślach.

— Rehno Lindeque

1

Zaczynam myśleć, że dobrym pomysłem byłoby opublikowanie tego pytania na forum LtU, zamiast przyglądania się fajnym dyskusjom: P. Btw @imz, być może najlepiej byłoby przeczytać pytanie jako „które klasy gramatyki odpowiadają którym klasom programów w sensie„ funkcjonalnym ”opisanym przez Jukkę w odpowiedzi Marca Hammana”. Być może powinienem to wyjaśnić ...

— Rehno Lindeque

10

Istnieje korespondencja jeden do jednego między gramatykami Chomsky'ego typu 0 a maszynami Turinga.

Jest to wykorzystywane w języku programowania Thue, który umożliwia pisanie kompletnych programów Turinga określonych przez ciąg początkowy i zestaw reguł przepisywania ciągów ( gramatyka pół-Thue , która jest równoważna gramatyce typu 0).

AKTUALIZACJA:

Inne niż ezoteryczne języki „Turing tar-pit”, takie jak Thue, różne języki ogólnego przeznaczenia, które pozwalają programiście rozszerzyć własną składnię, mogą być użyte do wykonania obliczeń Turinga podczas etapu parsowania-kompilacji.

Języki z rodziny Lisp , w szczególności Common Lisp , są prawdopodobnie najbardziej oczywistymi przykładami, ale także, ogólnie mówiąc, języki ze statycznym sprawdzaniem typów, które nie zawsze muszą się zatrzymywać, takie jak C ++ z szablonami , Scala i Qi .

— Antonio Valerio Miceli-Barone
źródło

Pytanie dotyczy jednak rzeczy, które działają na odwrót: do wyniku nie należy przepisywać początkowej sekwencji symboli zgodnie z regułami, ale „wynik” obliczenia zdefiniowanego przez gramatykę w tym pytaniu jest początkowy symbol, który może wytworzyć sekwencję „wejściową” zgodnie z zasadami gramatyki.

— imz - Ivan Zachharyaschev

2

c o n c a t (q u o t e (i n), o u t)

$concat(quote(in), out)$

T M (i n) = o u t

$TM(in) = out$

Zgadzam się, że zgodność między gramatykami Type0 i bazami TM jest prawidłową odpowiedzią na pytanie (zwłaszcza jeśli ogranicza się do obliczania funkcji tak / nie). Kolejna sugestia, aby modelować dowolną TM z gramatyką poprzez wprowadzenie jakiejś konwencji, jak reprezentować pary

— przepływów międzygałęziowych,

Rozumiem to jako pytanie o wykorzystanie dokładnie istniejących ram gramatyki i odpowiednich parserów do wykonywania obliczeń, tj. Dozwoloną formą tłumaczenia między funkcją f a gramatyką może być tylko: dane wejściowe, które przeanalizowałem jako S oznacza f ( I) = S.

— imz - Ivan Zachararychev

1

Pozornie język programowania Thue nie wydaje się wpaść w tego rodzaju użycie frameworka gramatycznego: chociaż przepisuje reguły takie jak gramatyka, obliczanie wyniku z danych wejściowych przebiega w kierunku reguł, a nie odwrotnie kierunek, jak chce Rehno. (Ale być może jest to tylko kwestia zmiany kierunku strzałek w produkcjach: przetłumaczenie gramatyki „obliczenia jako parser” w znaczeniu tego Q na Thue może polegać jedynie na zmianie kierunków reguł, a następnie na programie Thue dojdzie do symboli początkowych jako rezultatów, prawda? ..)

— imz - Ivan Zacharyaschev

6

Moja odpowiedź nie jest formalna, precyzyjna i absolutnie tematyczna. Myślę, że odpowiedź Marca Hammana jest solidna, ale twoje pytanie przypomniało mi pokrewny temat.

Gramatyki można uznać za szczególne przypadki systemów dedukcyjnych: dane wejściowe to sąd, a drzewo analizy jest pochodną wyroku lub dowód, że wyrok jest ważny zgodnie z (gramatycznymi) regułami.

W tym sensie twoje pytanie może być związane z podejściem pewnej części społeczności programistów logicznych / wyszukiwarki proofów (myślę na przykład o Dale Millerze ), co oznacza, że wyszukiwanie proofów ma treść obliczeniową, w przeciwieństwie do bardziej klasycznych teoria typu / dowód z punktu widzenia, w którym obliczenia są normalizacją dowodu .

Uwaga: ponownie czytając moją odpowiedź, myślę, że pomysł, że „budowa drzewa parsowania jest wyszukiwaniem dowodu” jest tutaj nieco przesadny. Wyszukiwanie dowodu płynie raczej w innym kierunku: jeden zaczyna się od danego, dość złożonego osądu, a poprzez wielokrotne stosowanie reguł wnioskowania działających na strukturze dowodu, miejmy nadzieję, że uzyskuje się prostsze aksjomaty, których nie trzeba dalej dowodzić. Bardziej naturalne byłoby zatem postrzeganie w kategoriach gramatycznych złożonych osądów jako nieterminali, atomów jako terminali, a wyszukiwanie dowodu jako problemu z generowaniem słów lub testu braku pustki.

— gasche
źródło

Bardzo ciekawe uwagi. Mój mózg jest trochę zbyt zmęczony, aby dać dobrą odpowiedź w tej chwili, jednak w moim przykładzie gałęzie drzewa zasadniczo reprezentują

— podliczenia,

6

Ponadto, czy moglibyśmy zbudować kompletne programy Turinga, określając gramatykę…?

Nie jestem pewien, czy poprawnie zrozumiałem twoje pytanie, ale jeśli szukasz języka programowania opartego na pewnego rodzaju systemie przepisywania ciągów, prawdopodobnie zainteresowałbyś się Refal , który opiera się na formalizmie algorytmu Markowa (Turing- kompletny formalizm, który jest także gramatycznym systemem przepisywania ciągów znaków).

— Artem Pelenitsyn
źródło

1

Zrozumiałem pytanie w następujący sposób: Rehno interesuje się procesem analizy bootom-up (zdefiniowanym przez gramatykę), który należy postrzegać jako obliczenie wyniku. Obliczenia powinny budować wynik z części idących w kierunku przeciwnym do reguł produkcji gramatyki. Reguły przepisywania Refal (IIUC, podobnie jak wspomniany wyżej język programowania Thue) będą zmierzać w innym kierunku (od wprowadzania do wyniku).

— imz - Ivan Zachharyaschev

Teraz, gdy o tym myślę, gramatyki kontekstowe mają więcej niż jeden symbol na LHS reguł produkcji. Myślę więc, że nie ma praktycznej różnicy. Parser dla języka kontekstowego byłby systemem przepisywania ciągów, bez względu na to, jak na to spojrzysz, prawda?

— Rehno Lindeque

@imz dziękuję za wyjaśnienie pytania Rehno. @ Rehno „Parser dla języka kontekstowego byłby systemem przepisywania ciągów znaków, bez względu na to, jak na to spojrzysz, prawda?” - prawdopodobnie ma to sens, tak.

— Artem Pelenitsyn,

Ale czy reguły przepisywania Refal są traktowane niedeterministycznie? (Lub inaczej: czy Refal wykona backtracking w poszukiwaniu działającej ścieżki przepisywania?) Jeśli chcemy modelować to podejście „parsowania jako obliczenia” z regułami przepisywania w odwrotnym kierunku, potrzebujemy reguł niedeterministycznych; rozważ gramatykę jakS -> A a; S -> B b; A -> 0; B -> 0 . Jeśli zaprogramujemy to poprzez odwrócenie reguł, będziemy musieli wybrać inne reguły przetwarzania 0w czasie wykonywania, aby ocenić „0a” lub „0b” do S.

— imz - Ivan Zachharyaschev

6

(Tylko kilka drobiazgów. Może to być komentarz, ale za długi.)

W rzeczywistości to , co opisujesz, wygląda na bardzo naturalny pogląd na to, czym jest język (w ludzkim rozumieniu „języka”, jego celu) i jak gramatyka definiuje język.

Język zawiera (nieskończenie wiele) poprawnych form składniowych, które są interpretowane w celu uzyskania wartości semantycznych .

Jeśli interpretacja jest obliczalna, to formy składniowe języka można postrzegać jako programy, które obliczają wartości semantyczne.

Jeśli założymy, że język jest zaimplementowany jako urządzenie skończone, możemy nazwać tę skończoną reprezentację języka „gramatyką”. Zgodnie z tym rozumieniem gramatyka dba o składnię, ale także o semantykę, tj. Jak obliczyć wartość semantyczną całego wyrażenia na podstawie wartości jego części (części atomowe i ich wartości są przechowywane w „leksykonie”) .

Niektóre teorie języka naturalnego mają taką formę (formę, która jest zgodna z powyższymi rozważaniami; została już wspomniana w odpowiedzi @ gasche tutaj): system dedukcyjny, który szuka pochodnej danych wejściowych (w połączeniu z obliczeniem semantycznym wartość lub budowanie terminu próbnego; por. korespondencja Curry-Horward). Jeśli więc przyjrzymy się takim systemom i uznamy je za gramatykę, twoje pytanie jest trywialne : systemy te są dokładnie zaprojektowane do wykonywania obliczeń w opisany sposób.

$f$ $G$ $I$ $f(I)=S$ $I$ $S$ $G$

(W rzeczywistości prawdziwe kompilatory dla języków programowania wyglądają bardziej jak system ze składnią i semantyką: przekształcają składniową postać programu w plik wykonywalny, który jest semantycznym znaczeniem programu, a nie tylko początkowym symbolem gramatyki).

— imz - Ivan Zakharyaschev
źródło

4

Aby dodać:

Czysty program logiczny ma odczyt deklaratywny i odczyt proceduralny. Ten raport omawia ideę, że można je uzupełnić odczytem gramatycznym, w którym klauzule są uważane za przepisujące reguły gramatyki. Celem jest wykazanie, że ten punkt widzenia ułatwia transfer wiedzy specjalistycznej z programowania logicznego do innych badań nad językami programowania i odwrotnie. Omówiono niektóre przykłady takiego przeniesienia. Z drugiej strony przedstawiony widok gramatyczny uzasadnia niektóre rozszerzenia ad hoc do czystego programowania logicznego i ułatwia opracowanie podstaw teoretycznych dla takich rozszerzeń.

Gramatyczne spojrzenie na programowanie logiki Pierre'a Deransarta i Jana Maluszyńskiego.

— Vag
źródło

Najwyraźniej Prolog powstał z gramatyki atrybutów, więc ten widok rozpoczął programowanie logiki.

— reinierpost

1

Co powiesz na coś takiego jak liczby Peano:

S    -> int
int  -> zero
int  -> succ
zero -> "0"
succ -> "#" int

rozpozna dowolny ciąg (liczbę) tego formularza:

0   // zero
#0  // one
##0 // two

i powinna zwrócić zagnieżdżoną strukturę, przy czym głębokość jest liczbą.

Ale zaczyna się komplikować, gdy chce się implementować, wystarczy powiedzieć:

S    -> int
int  -> sum
int  -> zero
int  -> succ
zero -> "0"
succ -> "#" int
sum  -> int "+" int

Ma to sens, ponieważ rozpozna tylko dobrze uformowane ints takie jak to:

#####0 + ####0

Ale ta gramatyka wprowadza podział na parsowanie za każdym razem, gdy istnieje suma, więc zamiast mieć ładne jedno rozgałęzione drzewo, które bezpośrednio odwzorowuje na liczbę, mamy strukturę wyrażenia, wciąż kilka obliczeń od efektywnego wartość. Tak więc żadne obliczenia nie są wykonywane, tylko rozpoznawanie. Problemem może nie być gramatyka, ale parser. Zamiast tego można użyć czegoś innego, idk ... Kolejną rzeczą, która przychodzi na myśl, jest adekwatność formalizmu gramatycznego do wyrażenia obliczeń. Kiedy spojrzysz na aksjomat Peano (w notacji podobnej do Haskella):

1) Nat = Zero
2) Nat = Succ Nat
3) Sum ( Succ X ) ( Y ) = Succ ( X + Y )
4) Sum Zero X = X

Trzecia reguła wyraźnie określa transformację. Czy ktokolwiek mógłby sobie wyobrazić, że ma to samo znaczenie w kontekście gramatyki bezkontekstowej. A jeśli tak, to jak!

— tancerz
źródło