Ist die Syntax der C-Sprache vollständig durch CFGs definiert?

7

Ich denke, die Frage ist autark. Ist die Syntax der C-Sprache vollständig durch kontextfreie Grammatiken definiert, oder haben wir Sprachkonstrukte, für die im Verlauf des Parsens möglicherweise nicht kontextfreie Definitionen erforderlich sind?

Ein Beispiel für ein Nicht-CFL-Konstrukt, das ich dachte, war die Deklaration von Variablen vor ihrer Verwendung. In Compilern (Aho Ullman Sethi) wird jedoch angegeben, dass die C-Sprache Identifikatoren nicht anhand ihrer Namen unterscheidet. Alle Bezeichner werden vom Lexical Analyzer als "ID" gekennzeichnet. Wenn C nicht vollständig durch CFGs definiert ist, kann jemand ein Beispiel für ein Nicht-CFL-Konstrukt in C geben?

context-free programming-languages compilers parsing c Madeyedexter
quelle
Die Antwort hängt ganz davon ab, wie Sie die Sprache der "C-Programme" definieren. Ist eine Zeichenfolge ein C-Programm, wenn sie die richtige Syntax hat, oder ist sie ein C-Programm, wenn sie die C-Sprachspezifikation in ihrer Gesamtheit einhält? Oder handelt es sich um ein C-Programm, wenn einige (Teilmengen) standardkonforme C-Compiler in der Lage sind, daraus eine funktionsfähige ausführbare Datei zu generieren? Ich habe immer Definitionen von Programmiersprachen bevorzugt, die einen Anschein semantischer Gültigkeit erfordern, obwohl dies normalerweise bedeutet, dass die Sprachen nicht kontextfrei sind, wie in Ihrer Erklärung.
Patrick87

Antworten:

13

Die C-Sprache hat Tippregeln. Sie können beispielsweise nicht zwei Zeiger teilen, und wenn Sie eine Prozedur aufrufen, die einen Zeiger akzeptiert, können Sie kein Double verwenden. Der AC-Compiler analysiert seine Quelle in mehreren Phasen: Zuerst wird eine lexikalische Analyse durchgeführt, dann wird die Quelle analysiert und so weiter. Diese Phasen sind Abstraktion, und tatsächlich werden zusätzliche Informationen von Phase zu Phase weitergegeben. Obwohl sich die Grammatik von C nicht um die Namen von Variablen kümmert, werden diese Informationen übergeben, und auf diese Weise kann die zugewiesene Grammatik die Tippregeln überprüfen. Es gibt also zusätzliche Mechanismen, die zusätzlich zur Grammatik arbeiten.

Ein noch einfacheres Beispiel ist das von Aho und Ullman. In der Analysephase sehen alle Variablennamen "gleich" aus. Sie können eine Variable jedoch nur verwenden, wenn sie deklariert wurde. Diese Informationen sind vor dem kontextfreien Parser verborgen, bleiben jedoch als Attribut für die lexikalische Phase erhalten und werden beim Parsen überprüft. Die kontextfreie Grammatik von C repräsentiert nur einige Aspekte des legalen C-Codes, die für die Implementierung eines schnellen Parsers nützlich sind. Zusätzlich zu diesem Parser werden die anderen Regeln überprüft, der C-Code wird semantisch und der Maschinencode wird generiert.

Yuval Filmus
quelle