Aby język był programowalny, musi być oparty na gramatyce bezkontekstowej

W praktyce, dla języka, który można ostatecznie skompilować / przekształcić w instrukcje na poziomie systemu, czy konieczne jest, aby była to gramatyka bezkontekstowa?

np .: Czy wszystkie języki programowania / skryptów są wolne od kontekstu? Java oparta jest na CFG, ale czy w rzeczywistości wszystkie języki programowania są oparte na CFG?

Nie wydaje się to obowiązkowe, ale w moim rozumieniu są luki.

Pewien kontekst pytania: patrzyłem na specyfikację języka Java, która zawiera także reguły gramatyczne . To sprawiło, że pomyślałem o tym pytaniu.

Dwa razy nie.

Po pierwsze, większość HPL nie jest pozbawiona kontekstu. Chociaż zwykle mają składnię opartą na CFG, mają również to, co ludzie nazywają semantyką statyczną (co często jest również zawarte w składni terminu). Może to obejmować nazwy i typy, które muszą sprawdzić poprawność programu. Na przykład,

class A {
  String a = "a";
  int b = a + d;
}

jest poprawnym składniowo programem Java, ale nie będzie się kompilował, ponieważ dnie jest zdefiniowany i anie ma odpowiedniego typu.

Po drugie, można analizować w językach, które nie są wolne od kontekstu (jak oczywiście świadczy o istnieniu kompilatorów). Tyle tylko, że CFG mogą być skutecznie analizowane, podczas gdy CSG ogólnie nie. Można jednak dodawać pewne funkcje bezkontekstowe, zachowując jednocześnie wydajność.

Kompilatory często działają w fazach: najpierw tokenizacja (zwykła), następnie parsowanie bez kontekstu, a następnie analiza nazw i typów (kontekstowa, czasem nawet trudniejsza). Możesz zaobserwować to zachowanie, wyświetlając komunikaty o błędach.

Parsowanie perla jest nierozstrzygalne.

http://www.jeffreykegler.com/Home/perl-and-undecidability/perl-and-undecidability-files/TPR3.pdf?attredirects=0

http://www.perlmonks.org/?node_id=663393

Nie wierzę, że gramatyka Pythona jest pozbawiona kontekstu. Wymóg, aby wiersze w tym samym bloku kodu miały tę samą wielkość wcięcia, nie jest czymś, co gramatyki bezkontekstowe dobrze sobie radzą.

Mówiąc ściślej, wydaje się, że istnieje homomorfizm z języka bloków pythonowych formy

jeśli warunek:
     linia 1
     linia 2
     linia3
jeszcze:
     linia4

$0^n10^n10^n$

Bodo Manthey i Martin Böhme pokazują, że każdy kompilator C ++ jest koniecznie kompletny Turinga, to znaczy, że może obliczyć dowolną częściową funkcję rekurencyjną podczas kompilacji . Jest więc znacznie gorszy niż tylko kontekstowy.

http://wwwhome.math.utwente.nl/~mantheyb/journals/BotEATCS_BoehmeManthey_CompilingCPP.pdf

Myślę, że deklaracja przed użyciem zmiennych i polimorfizm funkcji języków OOP to inne przykłady specyfikacji języków programowania, których nie można obsłużyć za pomocą gramatyki bezkontekstowej:

int myfun(int a) { ... }
int myfun(int a, int b) { ... }
int myfun(int a, int b, int c, ...) { ... }
...
int I_m_I_cfg = myfun(1,2);
...

Przeprowadziłem małe wyszukiwanie w Google i znalazłem ten artykuł: „ A Boolean Grammar for a Simple Boolean Language ” autorstwa A.Okhotin (2004); jego zdaniem prawdziwym problemem jest znalezienie języka programowania, który jest całkowicie opisany przez gramatykę formalną:

Zdefiniowano zabawkowy język programowania proceduralnego i zbudowano logikę gramatyczną dla zestawu poprawnie utworzonych programów w tym języku. Jest to najwidoczniej pierwsza specyfikacja języka programowania całkowicie oparta na gramatyce formalnej.

Część wstępna tego artykułu jest krótka, ale bardzo wyjaśniająca.

Uważam, że gramatyka języka C jest technicznie bezkontekstowa, ponieważ parsery zawsze używają technik bezkontekstowych do obsługi urządzenia Duffa .

Języki oparte na wcięciach nie są oczywiście pozbawione kontekstu, jak powiedział David, ale stają się pozbawione kontekstu względem sparametryzowanego tokena wcięcia.

Haskell umożliwia zmianę pierwszeństwa operatora za pomocą infix i infixl. Moduł ścisłej pragmy Perla jest implementowany przy użyciu ustawień leksykalnych $ ^ H i% ^ H, co sprawia, że ​​nie jest on kontekstowy, prawdopodobnie też inne ustawienia.

Istnieją języki ekspanderów makr, takie jak TeX, w których parsowanie afaik nie ma sensu bez wykonywania.

Prawdopodobnie istnieją nawet dwie bezkontekstowe gramatyki, których przecięcie nie jest pozbawione kontekstu, ale wciąż opisuje maszynę Turinga.

Java i asembler są prawdopodobnie naturalnie pozbawione kontekstu.

Nie, a wiele praktycznych języków nie jest pozbawionych kontekstu. Na przykład gramatyka C ++ nie jest, ponieważ w niektórych kontekstach rozdzielczość gramatyki zależy od pisania informacji, które nie są pozbawione kontekstu.

Najpierw pozwól mi dokonać rozróżnienia między składnią języka programowania a samym językiem.

Składnia wielu języków jest (przynajmniej oparta) na gramatyce bezkontekstowej (CFG), ponieważ są one dobrze zbadane i istnieją algorytmy, które mogą skutecznie analizować CFG, a przypadek krawędzi, którego nie można rozwiązać za pomocą CFG, można traktować specjalnie

Jednak wiele języków w rzeczywistości nie jest pozbawionych kontekstu (gdy używane są symbole deklaracji przed użyciem, na przykład w języku Java, C (++), D).

Ciekawostka: D ma całkowitą ocenę funkcji czasu kompilacji Turinga i rozszerzenie szablonu, dzięki czemu sam język nie jest rozstrzygalny przez Turinga. Jednak twórca języka dołożył wszelkich starań, aby uczynić składnię CFG.

O ile „Czy wszystkie języki programowania / skryptów są wolne od gramatyki?” część dotyczy, odpowiedź jest jednoznaczna Nie.

Re: główne pytanie „dla języka, który można ostatecznie skompilować / przekształcić w instrukcje na poziomie systemu”, „nie wiem, dlaczego koniecznie musi to być CFG. Jednak mogą pojawić się lepsze wyjaśnienia.

Język programowania musi opierać się na pewnym formalizmie gramatycznym, którego przykładem są CFG. Podczas gdy CFG są najczęstsze (i są to zwykłe rzeczy nauczane na kursach kompilatora na uniwersytetach), istnieją inne formalizacje, takie jak gramatyka wyrażeń parsingowych, o których więcej można przeczytać tutaj (pdf) lub na Wikipedii, aby przeczytać więcej.