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

Ja, C++ ist kontextabhängig, sehr kontextabhängig. Man kann den Syntaxbaum nicht einfach durch Parsen der Datei mit einem kontextfreien Parser aufbauen, weil man in einigen Fällen das Symbol aus früheren Kenntnissen kennen muss, um zu entscheiden (d.h. eine Symboltabelle beim Parsen aufbauen).

Erstes Beispiel:

A*B;

Ist dies ein Multiplikationsausdruck?

OR

Ist dies eine Erklärung der B Variable als Zeiger des Typs A ?

Wenn A eine Variable ist, ist es ein Ausdruck, wenn A ein Typ ist, ist es eine Zeigerdeklaration.

Zweites Beispiel:

A B(bar);

Ist dies ein Funktionsprototyp, der ein Argument von bar Typ?

OR

Ist diese Deklarationsvariable B vom Typ A und ruft den Konstruktor von A mit bar Konstante als Initialisierer?

Sie müssen wieder wissen, ob bar ist eine Variable oder ein Typ aus der Symboltabelle.

Drittes Beispiel:

class Foo
{
public:
    void fn(){x*y;}
    int x, y;
};

Dies ist der Fall, wenn die Erstellung der Symboltabelle beim Parsen nicht hilft, weil die Deklaration von x und y nach der Funktionsdefinition kommt. Sie müssen also zuerst die Klassendefinition durchsuchen und in einem zweiten Durchgang die Methodendefinitionen betrachten, um festzustellen, dass x*y ein Ausdruck und keine Zeigerdeklaration oder ähnliches ist.

Answer 2

Ich habe das Gefühl, dass es eine gewisse Verwirrung zwischen der formalen Definition von "kontextsensitiv" und dem informellen Gebrauch von "kontextsensitiv" gibt. Ersteres hat eine klar definierte Bedeutung. Letzteres wird verwendet, um zu sagen, dass man den Kontext braucht, um die Eingabe zu analysieren.

Diese Frage wird auch hier gestellt: Kontextsensitivität vs. Mehrdeutigkeit .

Hier ist eine kontextfreie Grammatik:

<a> ::= <b> | <c>
<b> ::= "x"
<c> ::= "x"

Die Eingabe "x" ist mehrdeutig, so dass Sie einen Kontext benötigen, um sie zu analysieren (oder Sie müssen mit der Mehrdeutigkeit leben, oder Sie geben "Warning: E8271 - Eingabe ist mehrdeutig in Zeile 115"). Aber es ist sicherlich keine kontextabhängige Grammatik.

Answer 3

C++ wird mit dem GLR-Parser geparst. Das bedeutet, dass beim Parsen des Quellcodes der Parser Mai auf eine Mehrdeutigkeit stoßen, sondern weitergehen und entscheiden, welche Grammatikregel zu verwenden ist später .

siehe auch,

Warum kann C++ nicht mit einem LR(1)-Parser geparst werden?

---

Denken Sie daran, dass die kontextfreie Grammatik kann nicht beschreiben ALLE die Regeln der Syntax einer Programmiersprache. Die Attributgrammatik wird zum Beispiel verwendet, um die Gültigkeit eines Ausdruckstyps zu überprüfen.

int x;
x = 9 + 1.0;

Sie kann nicht die folgende Regel mit einer kontextfreien Grammatik beschreiben: Die rechte Seite der Aufgabe sollte vom gleichen Typ wie die linke Seite sein.

Answer 4

Keine Algol-ähnliche Sprache ist kontextfrei, weil sie Regeln haben, die Ausdrücke und Anweisungen einschränken, in denen Bezeichner auf der Grundlage ihres Typs erscheinen können, und weil es keine Begrenzung für die Anzahl der Anweisungen gibt, die zwischen Deklaration und Verwendung auftreten können.

Die übliche Lösung besteht darin, einen kontextfreien Parser zu schreiben, der eine Obermenge gültiger Programme akzeptiert und die kontextsensitiven Teile in ad hoc "semantischer" Code, der den Regeln beigefügt ist.

C++ geht dank seines Turing-kompletten Template-Systems weit darüber hinaus. Siehe Stack Overflow Frage 794015 .

Answer 5

Sie ist kontextabhängig, da a b(c); hat zwei gültige Parsen - Deklaration und Variable. Wenn Sie sagen "Wenn c ist ein Typ", das ist Kontext, genau da, und Sie haben genau beschrieben, wie C++ darauf reagiert. Hätten Sie nicht diesen Kontext "Was ist c ?" konnte nicht eindeutig geklärt werden.

Hier wird der Kontext durch die Wahl der Token ausgedrückt - der Parser liest einen Bezeichner als typename-Token, wenn er einen Typ nennt. Dies ist die einfachste Lösung und vermeidet einen Großteil der Komplexität der Kontextsensitivität (in diesem Fall).

Edit: Es gibt natürlich noch mehr Probleme der Kontextsensitivität, ich habe mich nur auf das von Ihnen aufgezeigte konzentriert. Vorlagen sind dafür besonders unangenehm.