Nachstehend meine (derzeitige) Lieblingsdemonstration, warum das Parsen von C++ (wahrscheinlich) Turing-komplett da es ein Programm zeigt, das syntaktisch korrekt ist, wenn und nur wenn eine gegebene ganze Zahl prim ist.
Ich behaupte also, dass C++ ist weder kontextfrei noch kontextsensitiv .
Wenn Sie beliebige Symbolsequenzen auf beiden Seiten einer Produktion zulassen, erzeugen Sie eine Typ-0-Grammatik ("unrestricted") in der Chomsky-Hierarchie die leistungsfähiger ist als eine kontextabhängige Grammatik; unbeschränkte Grammatiken sind Turing-komplett. Eine kontextsensitive (Typ-1) Grammatik erlaubt mehrere Kontextsymbole auf der linken Seite einer Produktion, aber derselbe Kontext muss auf der rechten Seite der Produktion erscheinen (daher der Name "kontextsensitiv"). [1] Kontextsensitive Grammatiken sind äquivalent zu linear begrenzte Turing-Maschinen .
Im Beispielprogramm könnte die Primzahlberechnung von einer linear begrenzten Turing-Maschine durchgeführt werden, so dass die Turing-Äquivalenz nicht ganz bewiesen ist, aber der wichtige Teil ist, dass der Parser die Berechnung durchführen muss, um die syntaktische Analyse durchzuführen. Es könnte jede beliebige Berechnung sein, die als Schabloneninstanziierung ausgedrückt werden kann, und es gibt allen Grund zu der Annahme, dass die C++-Schabloneninstanziierung Turing-komplett ist. Siehe zum Beispiel, Todd L. Veldhuizens Arbeit von 2003 .
Unabhängig davon kann C++ von einem Computer geparst werden, so dass es sicherlich auch von einer Turing-Maschine geparst werden könnte. Folglich könnte eine unbeschränkte Grammatik es erkennen. Eine solche Grammatik zu schreiben, wäre jedoch unpraktisch, weshalb der Standard dies auch nicht versucht. (Siehe unten.)
Das Problem der "Mehrdeutigkeit" bestimmter Ausdrücke ist meist ein Ablenkungsmanöver. Zunächst einmal ist Mehrdeutigkeit ein Merkmal einer bestimmten Grammatik, nicht einer Sprache. Selbst wenn eine Sprache nachweislich keine eindeutigen Grammatiken hat, ist sie kontextfrei, wenn sie von einer kontextfreien Grammatik erkannt werden kann. Ebenso ist sie kontextsensitiv, wenn sie nicht von einer kontextfreien Grammatik erkannt werden kann, aber von einer kontextsensitiven Grammatik erkannt werden kann. Mehrdeutigkeit ist nicht relevant.
Aber in jedem Fall, wie Zeile 21 (d.h. auto b = foo<IsPrime<234799>>::typen<1>(); ) im folgenden Programm sind die Ausdrücke überhaupt nicht mehrdeutig; sie werden einfach je nach Kontext unterschiedlich geparst. In der einfachsten Ausprägung des Problems hängt die syntaktische Kategorie bestimmter Bezeichner davon ab, wie sie deklariert wurden (z. B. Typen und Funktionen), was bedeutet, dass die formale Sprache die Tatsache erkennen müsste, dass zwei Zeichenketten beliebiger Länge im selben Programm identisch sind (Deklaration und Verwendung). Dies kann durch die "Kopier"-Grammatik modelliert werden, d.h. die Grammatik, die zwei aufeinanderfolgende exakte Kopien desselben Wortes erkennt. Es ist leicht zu beweisen mit der Schleifensatz dass diese Sprache nicht kontextfrei ist. Eine kontextsensitive Grammatik für diese Sprache ist möglich, und eine Grammatik vom Typ 0 ist in der Antwort auf diese Frage enthalten: https://math.stackexchange.com/questions/163830/context-sensitive-grammar-for-the-copy-language .
Würde man versuchen, eine kontextabhängige (oder uneingeschränkte) Grammatik für die Analyse von C++ zu schreiben, würde das Universum wahrscheinlich mit Kritzeleien gefüllt werden. Eine Turing-Maschine zu schreiben, um C++ zu parsen, wäre ein ebenso unmögliches Unterfangen. Selbst das Schreiben eines C++-Programms ist schwierig, und soweit ich weiß, wurde noch kein einziges Programm als korrekt erwiesen. Aus diesem Grund versucht die Norm nicht, eine vollständige formale Grammatik bereitzustellen, und entscheidet sich dafür, einige der Parsing-Regeln in technischem Englisch zu verfassen.
Was in der C++-Norm wie eine formale Grammatik aussieht, ist nicht die vollständige formale Definition der Syntax der Sprache C++. Es ist nicht einmal die vollständige formale Definition der Sprache nach der Vorverarbeitung, die einfacher zu formalisieren sein könnte. (Das wäre allerdings nicht die Sprache: Die C++-Sprache, wie sie in der Norm definiert ist, enthält den Präprozessor, und die Funktionsweise des Präprozessors wird algorithmisch beschrieben, da sie in einem grammatikalischen Formalismus nur sehr schwer zu beschreiben wäre. In diesem Abschnitt der Norm wird die lexikalische Dekomposition beschrieben, einschließlich der Regeln, bei denen sie mehr als einmal angewendet werden muss).
Die verschiedenen Grammatiken (zwei sich überschneidende Grammatiken für die lexikalische Analyse, von denen die eine vor der Vorverarbeitung und die andere, falls erforderlich, danach stattfindet, sowie die "syntaktische" Grammatik) sind in Anhang A zusammengestellt, mit dem folgenden wichtigen Hinweis (Hervorhebung hinzugefügt):
Diese Zusammenfassung der C++-Syntax ist als Verständnishilfe gedacht. Es handelt sich nicht um eine genaue Wiedergabe der Sprache . Insbesondere akzeptiert die hier beschriebene Grammatik eine Obermenge der gültigen C++-Konstrukte . Disambiguierungsregeln (6.8, 7.1, 10.2) müssen angewendet werden, um Ausdrücke von Deklarationen zu unterscheiden. Außerdem müssen Zugriffskontroll-, Mehrdeutigkeits- und Typregeln angewandt werden, um syntaktisch gültige, aber sinnlose Konstrukte auszusortieren.
Endlich, hier ist das versprochene Programm. Zeile 21 ist syntaktisch korrekt, wenn und nur wenn das N in IsPrime<N> ist primär. Andernfalls, typen ist eine Ganzzahl, keine Vorlage, also typen<1>() wird geparst als (typen<1)>() was syntaktisch falsch ist, weil () ist kein syntaktisch gültiger Ausdruck.
template<bool V> struct answer { answer(int) {} bool operator()(){return V;}};
template<bool no, bool yes, int f, int p> struct IsPrimeHelper
: IsPrimeHelper<p % f == 0, f * f >= p, f + 2, p> {};
template<bool yes, int f, int p> struct IsPrimeHelper<true, yes, f, p> { using type = answer<false>; };
template<int f, int p> struct IsPrimeHelper<false, true, f, p> { using type = answer<true>; };
template<int I> using IsPrime = typename IsPrimeHelper<!(I&1), false, 3, I>::type;
template<int I>
struct X { static const int i = I; int a[i]; };
template<typename A> struct foo;
template<>struct foo<answer<true>>{
template<int I> using typen = X<I>;
};
template<> struct foo<answer<false>>{
static const int typen = 0;
};
int main() {
auto b = foo<IsPrime<234799>>::typen<1>(); // Syntax error if not prime
return 0;
}
[1] Um es technisch auszudrücken, muss jede Produktion in einer kontextsensitiven Grammatik von der Form sein:
A
何所 A ist ein Nicht-Terminal und , sind möglicherweise leere Folgen von Grammatiksymbolen, und ist eine nicht leere Folge. (Grammatiksymbole können entweder Terminale oder Nicht-Terminale sein).
Dies kann wie folgt gelesen werden A nur im Zusammenhang mit [, ] . In einer kontextfreien Grammatik (Typ 2), y muss leer sein.
Es stellt sich heraus, dass man Grammatiken auch mit der "monotonen" Restriktion einschränken kann, bei der jede Produktion von der Form sein muss:
donde || || > 0 ( || bedeutet "die Länge der ")
Es ist möglich zu beweisen, dass die Menge der Sprachen, die von monotonen Grammatiken erkannt werden, genau dieselbe ist wie die Menge der Sprachen, die von kontextsensitiven Grammatiken erkannt werden, und es ist oft der Fall, dass es einfacher ist, Beweise auf monotone Grammatiken zu stützen. Daher wird "kontextsensitiv" häufig so verwendet, als ob es "monoton" bedeuten würde.
