Ist C eine reguläre Sprache?

8

Sind C oder C ++ reguläre Sprachen ? Wenn nicht, in welche Kategorie stellen wir die Programmiersprachen wie C / C ++, Perl, Python?

programming-languages c++ c perl Robert Harvey
quelle
Nein, egrep ist eine reguläre Sprache. C ist nicht.
Tchrist
Die meisten Programmiersprachen sind eine Art kontextfreie Sprache. Aus diesem Grund werden sie beim Kompilieren normalerweise als Baum dargestellt. en.wikipedia.org/wiki/Context-free_grammar
Laurent Bourgault-Roy
1
@ LaurentBourgault-Roy Ich würde denken, dass die meisten nicht einmal kontextfrei waren, da selbst wenn sie eine CFG haben, normalerweise zusätzliche Regeln außerhalb der CFG angewendet werden
jk.
Sogar Regex sind nicht mehr regelmäßig
CodesInChaos

Antworten:

30

Die einzige mir bekannte universelle Definition für "reguläre Sprache" ist eine, die mit einem deterministischen endlichen Automaten analysiert oder als echter regulärer Ausdruck ausgedrückt werden kann (nicht die erweiterten REs in vielen aktuellen Implementierungen). Ein regulärer Ausdruck kann in einer Reihe von Zeichen mit möglicherweise unendlichen Wiederholungen und alternativen Auswahlen geschrieben werden.

Da sowohl C als auch C ++ das Verschachteln von Klammern, Klammern und Klammern in beliebige Tiefen ermöglichen, sind sie keine regulären Sprachen (Einzelheiten finden Sie im Pumping Lemma).

David Thornley
quelle
2
Ich würde hinzufügen, dass keine Programmiersprache irgendeiner Art regulär sein kann, weil sie nicht einmal numerische Ausdrücke zulässt.
Giorgio
1
@Giorgio Sie können einen numerischen Ausdruck als reguläre Sprache ausdrücken (eine abwechselnde Folge von Operator und Zahl, die mit einer Zahl beginnt und endet). Das Parsen (mit Prioritäten) erfordert jedoch eine Grammatik
Ratschenfreak
@ Ratschenfreak: Wie würden Sie mit den Klammern umgehen, zB in (1 + 2) * 6?
Giorgio
@ Giorgio Ich hätte "ohne Klammern" hinzufügen sollen
Ratschenfreak
1
@Giorgio: Es ist trivial wahr, dass syntaktisch korrekte Postfix-Ausdrücke keine reguläre Sprache bilden. Ganz gleich. Eine Sprache kann sowohl regulär als auch willkürlich ausdrucksstark sein, einschließlich Postfix-Ausdrücken, solange die Stapelprüfung bis zur Laufzeit verschoben wird. Forth ist ein hervorragendes Beispiel, und DC wäre ein anderes.
david.pfx