Ist C++ kontextfrei oder kontextabhängig?

Question

Ich höre oft, dass C++ eine kontextabhängige Sprache ist. Nehmen Sie das folgende Beispiel:

a b(c);

Ist dies eine Variablendefinition oder eine Funktionsdeklaration? Das hängt von der Bedeutung des Symbols c . Si c ist eine variabel entonces a b(c); definiert eine Variable namens b vom Typ a . Sie wird direkt initialisiert mit c . Aber wenn c ist eine Typ entonces a b(c); deklariert eine Funktion namens b die eine c und gibt eine a .

Wenn Sie die Definition von kontextfreien Sprachen nachschlagen, werden Sie feststellen, dass alle Grammatikregeln linke Seiten haben müssen, die aus genau einem nicht-terminalen Symbol bestehen. In kontextsensitiven Grammatiken hingegen sind auf der linken Seite beliebige Zeichenketten aus terminalen und nichtterminalen Symbolen zulässig.

Beim Durchblättern des Anhangs A von "The C++ Programming Language" konnte ich keine einzige Grammatikregel finden, die auf ihrer linken Seite etwas anderes als ein einzelnes nichtterminales Symbol enthielt. Das würde bedeuten, dass C++ kontextfrei ist. (Natürlich ist jede kontextfreie Sprache auch kontextsensitiv in dem Sinne, dass die kontextfreien Sprachen eine Teilmenge der kontextsensitiven Sprachen bilden, aber das ist nicht der Punkt.)

Ist C++ also kontextfrei oder kontextsensitiv?

Answer 1

Der einfachste Fall einer nicht kontextfreien Grammatik ist das Parsen von Ausdrücken, die Schablonen enthalten.

a<b<c>()

Dies kann entweder als

template
   |
   a < expr > ()
        |
        <
      /   \
     b     c

Oder

 expr
   |
   <
 /   \
a   template
     |
     b < expr > ()
          |
          c

Die beiden ASTs können nur durch Untersuchung der Deklaration von "a" disambiguiert werden - der erste AST, wenn "a" eine Vorlage ist, oder der zweite, wenn nicht.

Answer 2

Die Produktionen im C++-Standard sind kontextfrei geschrieben, definieren die Sprache aber bekanntlich nicht wirklich genau. Einiges von dem, was die meisten Leute als Mehrdeutigkeit in der aktuellen Sprache ansehen, könnte (meiner Meinung nach) mit einer kontextsensitiven Grammatik eindeutig gelöst werden.

Das offensichtlichste Beispiel ist das "Most Vexing Parse": int f(X); . Si X ein Wert ist, dann definiert dies f als eine Variable, die mit X . Si X ein Typ ist, definiert er f als Funktion mit einem einzigen Parameter des Typs X .

Vom grammatikalischen Standpunkt aus betrachtet, könnte man das so sehen:

A variable_decl ::= <type> <identifier> '(' initializer ')' ';'

B function_decl ::= <type> <identifier> '(' param_decl ')' ';'

A ::= [declaration of X as value]
B ::= [declaration of X as type]

Natürlich müssten wir, um ganz korrekt zu sein, etwas zusätzliches "Zeug" hinzufügen, um die Möglichkeit zwischengeschalteter Deklarationen anderer Typen zu berücksichtigen (d.h., A und B sollten beide wirklich "Deklarationen einschließlich der Deklaration von X als..." sein, oder etwas in dieser Reihenfolge).

Dies unterscheidet sich jedoch immer noch ziemlich von einer typischen CSG (oder zumindest von dem, was ich von ihnen in Erinnerung habe). Dies hängt davon ab, dass eine Symboltabelle erstellt wird - der Teil, der speziell die X als Typ oder Wert, nicht nur irgendeine Art von Anweisung, die diesem vorausgeht, sondern die richtige Art von Anweisung für das richtige Symbol/den richtigen Bezeichner.

Um sicher zu sein, müsste ich ein wenig nachschauen, aber ich vermute, dass es sich nicht wirklich um eine CSG handelt, zumindest nicht so, wie der Begriff normalerweise verwendet wird.

Answer 3

Stimmt :)

J. Stanley Warford. Computer-Systeme . Seiten 341-346.

Answer 4

Manchmal ist es noch schlimmer: Was meinen die Leute, wenn sie sagen, C++ habe eine "unentscheidbare Grammatik"?

Answer 5

C++-Vorlagen haben sich als Turing-fähig erwiesen. Auch wenn es sich nicht um eine formale Referenz handelt, kann man hier nachsehen, ob dies der Fall ist:

http://cpptruths.blogspot.com/2005/11/c-templates-are-turing-complete.html

Ich will eine Vermutung wagen (so alt wie ein folkorischer und prägnanter CACM-Beweis, der zeigt, dass ALGOL in den 60er Jahren nicht durch eine CFG repräsentiert werden konnte) und sagen, dass C++ daher nicht nur durch eine CFG korrekt geparst werden kann. CFGs in Verbindung mit verschiedenen TP-Mechanismen entweder in einem Baumdurchlauf oder während Reduktionsereignissen - das ist eine andere Geschichte. Im Allgemeinen gibt es aufgrund des Halting-Problems einige C++-Programme, die sich nicht als korrekt/inkorrekt erweisen, aber dennoch korrekt/inkorrekt sind.

{PS- Als Autor von Meta-S (von mehreren Personen oben erwähnt) kann ich mit Sicherheit sagen, dass Thothic weder nicht mehr existiert, noch die Software kostenlos erhältlich ist. Vielleicht habe ich diese Version meiner Antwort so formuliert, dass ich nicht gelöscht oder auf -3 heruntergestuft werde }.