Damit eine Sprache programmierbar ist, muss sie auf einer kontextfreien Grammatik basieren

Ist es für eine Sprache, die schließlich in Anweisungen auf Systemebene kompiliert / umgewandelt werden kann, praktisch erforderlich, dass es sich um eine kontextfreie Grammatik handelt?

Beispiel: Sind alle Programmier- / Skriptsprachen kontextfrei? Java basiert auf CFGs, aber ist es tatsächlich so, dass alle Programmiersprachen auf CFGs basieren?

Es scheint nicht obligatorisch, aber es gibt Lücken in meinem Verständnis.

Einiger Kontext für die Frage: Ich war auf der Suche auf Java - Sprachspezifikation, die auch die Grammatik liefert Regeln . Das hat mich über diese Frage nachdenken lassen.

Zweimal nein.

Erstens sind die meisten HPLs nicht kontextfrei. Während sie normalerweise eine Syntax haben, die auf einer CFG basiert, haben sie auch eine sogenannte statische Semantik (die auch häufig in der Begriffssyntax enthalten ist). Dies kann Namen und Typen beinhalten, die auf ein korrektes Programm überprüft werden müssen. Zum Beispiel,

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

ist ein syntaktisch korrektes Java-Programm, wird jedoch nicht kompiliert, da des nicht definiert ist und akeinen passenden Typ hat.

Zweitens Sie können Sprachen analysieren , die nicht kontextfrei sind (wie offensichtlich durch die Existenz von Compilern bewiesen). Es ist nur so, dass CFGs effizient analysiert werden können, während CSGs dies im Allgemeinen nicht können. Sie können jedoch bestimmte nicht kontextfreie Funktionen hinzufügen, ohne die Effizienz zu beeinträchtigen.

Compiler werden häufig in Phasen ausgeführt: zuerst Tokenisierung (regulär), dann kontextfreies Parsen, dann Namens- und Typanalyse (kontextsensitiv, manchmal sogar schwieriger). Sie können dieses Verhalten anhand der Art der Fehlermeldungen beobachten, die Sie erhalten.

Das Parsen von Perl ist unentscheidbar.

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

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

Ich glaube nicht, dass Pythons Grammatik kontextfrei ist. Das Erfordernis, dass Zeilen in demselben Codeblock den gleichen Einrückungsgrad aufweisen, ist nicht das, was kontextfreie Grammatiken gut handhaben.

Genauer gesagt scheint es einen Homomorphismus aus der Sprache der Python-Blöcke der Form zu geben

wenn zustand:
     Linie 1
     Zeile 2
     line3
sonst:
     line4

$0^n10^n10^n$

Bodo Manthey und Martin Böhme zeigen, dass jeder C ++ - Compiler unbedingt vollständig ist, das heißt, dass er zur Kompilierungszeit jede teilweise rekursive Funktion berechnen kann . Es ist also viel schlimmer als nur kontextsensitiv.

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

Ich denke, dass die Deklaration vor der Verwendung von Variablen und der Funktionspolymorphismus der OOP-Sprachen andere Beispiele für Programmiersprachenspezifikationen sind, die von kontextfreien Grammatiken nicht verarbeitet werden können:

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

Ich machte eine kleine Google-Suche und fand diesen Artikel: " Eine boolesche Grammatik für eine einfache boolesche Sprache " von A.Okhotin (2004); Seiner Meinung nach besteht das eigentliche Problem darin, eine Programmiersprache zu finden, die vollständig durch eine formale Grammatik beschrieben wird:

Es wird eine prozedurale Programmiersprache für Spielzeug definiert und eine boolesche Grammatik für die Menge wohlgeformter Programme in dieser Sprache erstellt. Dies ist anscheinend die erste Spezifikation einer Programmiersprache vollständig durch eine formale Grammatik.

Der Einleitungsteil des Artikels ist kurz, aber sehr klar.

Ich glaube, dass Cs Grammatik nur technisch kontextfrei ist, da Parser immer nicht-kontextfreie Techniken verwenden, um Duffs Gerät zu unterstützen .

Einrückungsbasierte Sprachen sind natürlich auch nicht kontextfrei, wie David sagte, aber sie werden kontextfrei im Vergleich zu einem parametrisierten Einrückungs-Token.

Mit Haskell können Sie die Operatorrangfolge mit infix und infixl ändern. Perls striktes Pragma-Modul wird mit den lexikalischen Einstellungen $ ^ H und% ^ H implementiert, wodurch es nicht kontextfrei ist, wahrscheinlich auch mit anderen Einstellungen.

Es gibt Makro-Expander-Sprachen wie TeX, in denen afaik-Parsing ohne Ausführung keinen Sinn ergibt.

Es gibt wahrscheinlich sogar zwei kontextfreie Grammatiken, deren Schnittmenge nicht kontextfrei ist, aber dennoch eine Turing-Maschine beschreibt.

Java und Assembler sind wahrscheinlich beide von Natur aus kontextfrei.

Nein, und viele praktische Sprachen sind nicht kontextfrei. Zum Beispiel ist C ++ - Grammatik keine, da in einigen Kontexten die Grammatikauflösung von der Eingabe von Informationen abhängt, die nicht kontextfrei sind.

Lassen Sie mich zunächst zwischen der Syntax einer Programmiersprache und der Sprache selbst unterscheiden.

Die Syntax vieler Sprachen basiert (zumindest auf) einer kontextfreien Grammatik (Context Free Grammar, CFG), da diese gut studiert sind und es Algorithmen gibt, die eine CFG effizient analysieren können und der Randfall, der von der CFG nicht gelöst werden kann, speziell behandelt werden kann

Tatsächlich sind jedoch viele Sprachen nicht kontextfrei (wenn vor der Verwendung deklarierte Symbole verwendet werden, z. B. in Java, C (++), D).

Unterhaltsame Tatsache: D hat eine Turing-vollständige Auswertung der Kompilierungszeitfunktion und eine Vorlagenerweiterung, die die Sprache selbst nicht von Turing entscheidbar macht. Der Schöpfer der Sprache unternahm jedoch große Anstrengungen, um die Syntax zu einer CFG zu machen.

Was die "Sind alle Programmiersprachen / Skriptsprachen kontextfrei?" Teil betroffen ist, ist die Antwort ein klares Nein.

Betreff: Die Hauptfrage "für eine Sprache, die schließlich in Anweisungen auf Systemebene kompiliert / transformiert werden kann", ich weiß nicht, warum es notwendigerweise eine CFG sein muss. Es könnte jedoch bessere Erklärungen geben.

Eine Programmiersprache muss auf einer Art Grammatikformalismus basieren, wofür CFGs ein Beispiel sind. Während CFGs am häufigsten vorkommen (und in Compilerkursen an Universitäten üblich sind), gibt es andere Formalismen wie das Parsen von Ausdrucksgrammatiken, über die Sie hier mehr lesen können (pdf) oder auf Wikipedia, um mehr Informationen zu erhalten.