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

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?

• Regularne gramatyki
• Gramatyki bezkontekstowe
• Gramatyki kontekstowe
• Nieograniczone gramatyki (dla języków z wyliczaniem rekurencyjnym )

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.

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 .

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.

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).

(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).

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.

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!