Wie macht man die Sprache C kontextfrei?

Question

Ich weiß, dass C nicht eine kontextfreie Sprache ist, ein berühmtes Beispiel ist:

int foo; 
typedef int foo; 
foo x; 

In diesem Fall wird die Lexer nicht, ob foo in der 3. Zeile nicht kennt, eine Kennung ist, oder typedef.

Meine Frage ist, ist dies der einzige Grund, dass C eine Kontextsensitive Sprache macht?

Ich meine, wenn wir typedef loswerden, würde es kontextfreie Sprache werden? Oder gibt es andere Gründe (Beispiele), die das verhindern?

Answer 1

Ja. C kann mit einer klassischen lex + yacc-Kombination geparst werden. Die Lexer Definition und die yacc Grammatik

http://www.quut.com/c/ANSI-C-grammar-l-2011.html und frei verfügbar ist http://www.quut.com/c/ANSI-C-grammar-y-2011.html

Wie Sie aus der lex Datei sehen können, ist es einfach, mit Ausnahme der kontextsensitiven check_type() (und comment(), aber Kommentar Verarbeitung technisch gehört zum Präprozessor), wodurch typedef die einzige Quelle der Kontextsensitivität ist. Da die yacc-Datei auch keine kontextsensitiven Tricks enthält, wäre ein typedef -less C eine vollkommen kontextfreie Sprache.

Answer 2

Nein. C kann keine strikt kontextunabhängige Sprache sein. Dafür sollten Sie eine Syntax beschreiben, die es nicht erlaubt, eine nicht deklarierte Variable (das ist ein Kontext) auf ähnliche Weise zu verwenden, wie Sie es in Ihrer Frage beschreiben. Die Sprachautoren beschreiben die Syntax immer mit einer Art kontextfreier Grammatik, aber nur um die wichtigsten syntaktischen Konstrukte der Sprache zu beschreiben. Der Fall, den Sie beschreiben (indem Sie einen Typ-Bezeichner in eine andere Tokenklasse einfügen, um dort hingelangen zu können, wo er nicht hingehört), ist nur ein Beispiel. Wenn Sie zum Beispiel schauen, die Freiheit in der Reihenfolge für Dinge wie static unsigned long long int variable vereinfacht die Syntax Erinnern von Programmierern, aber kompliziert die Dinge für den Compiler-Autoren.