c++ - übung - reguläre grammatik




Ist D's Grammatik wirklich kontextfrei? (5)

Ich habe das vor einigen Monaten in der Newsgroup D gepostet, aber aus irgendeinem Grund hat mich die Antwort nie wirklich überzeugt, also dachte ich, ich würde es hier fragen.

Die Grammatik von D ist scheinbar kontextfrei .

Die Grammatik von C ++ ist jedoch nicht (auch ohne Makros). ( Bitte lesen Sie dies sorgfältig! )

Jetzt gewährt, ich weiß nichts (offiziell) über Compiler, Lexer und Parser. Alles, was ich weiß, stammt aus dem, was ich im Internet gelernt habe.
Und hier ist, was ich (glaube ich) bezüglich des Kontextes verstanden habe, im nicht so technischen Jargon:

Die Grammatik einer Sprache ist kontextfrei, wenn und nur wenn Sie die Bedeutung (auch nicht unbedingt das genaue Verhalten) eines gegebenen Teils des Codes verstehen können, ohne irgendwo anders "suchen" zu müssen.

Oder, noch weniger streng:

Die Grammatik kann nicht kontextfrei sein, wenn ich sie brauche. Ich kann den Typ eines Ausdrucks nicht einfach durch einen Blick erkennen.

So zum Beispiel, C ++ schlägt den kontextfreien Test fehl, weil die Bedeutung des confusing<sizeof(x)>::q < 3 > (2) vom Wert von q abhängt .

So weit, ist es gut.

Jetzt ist meine Frage: Kann dasselbe von D gesagt werden?

In D können Hashtabellen beispielsweise über eine Value[Key] -Deklaration erstellt werden

int[string] peoplesAges;   // Maps names to ages

Statische Arrays können in einer ähnlichen Syntax definiert werden:

int[3] ages;   // Array of 3 elements

Und Vorlagen können verwendet werden, um sie verwirrend zu machen:

template Test1(T...)
{
    alias int[T[0]] Test;
}

template Test2(U...)
{
    alias int[U] Test2;  // LGTM
}

Test1!(5) foo;
Test1!(int) bar;
Test2!(int) baz;  // Guess what? It's invalid code.

Das bedeutet, dass ich die Bedeutung von T[0] oder U einfach dadurch erkennen kann , dass ich es betrachte (dh es könnte eine Zahl sein, es könnte ein Datentyp sein, oder es könnte ein Tupel von Gott-weiß-was sein). Ich kann nicht einmal sagen, ob der Ausdruck grammatikalisch gültig ist (da int[U] sicherlich nicht ist - Sie können keine Hashtabelle mit Tupeln als Schlüssel oder Werten haben).

Jede Parsing-Struktur, die ich für Test erstellen möchte , würde keinen Sinn ergeben (da es wissen müsste, ob der Knoten einen Datentyp im Vergleich zu einem Literal oder einem Bezeichner enthält), außer es verzögert das Ergebnis, bis der Wert von T bekannt ist ( kontextabhängig machen).

Ist D tatsächlich kontextfrei, oder verkenne ich das Konzept?

Warum Warum nicht?

Aktualisieren:

Ich dachte nur, ich würde kommentieren: Es ist wirklich interessant, die Antworten zu sehen, denn:

  • Einige Antworten behaupten, dass C ++ und D nicht kontextfrei sein können
  • Einige Antworten behaupten, dass C ++ und D beide kontextfrei sind
  • Einige Antworten unterstützen die Behauptung, dass C ++ kontextsensitiv ist, während D nicht ist
  • Niemand hat bisher behauptet, dass C ++ kontextfrei ist, während D kontextsensitiv ist :-)

Ich kann nicht sagen, ob ich lerne oder verwirrt bin, aber so oder so, ich bin irgendwie froh, dass ich das gefragt habe ... danke, dass du dir die Zeit genommen hast, zu antworten, alle!


Die Grammatik kann nicht kontextfrei sein, wenn ich sie brauche. Ich kann den Typ eines Ausdrucks nicht einfach durch einen Blick erkennen.

Nein, das ist völlig falsch. Die Grammatik kann nicht kontextfrei sein, wenn Sie nicht erkennen können, ob es sich um einen Ausdruck handelt, indem Sie sie und den aktuellen Status des Parsers betrachten (bin ich in einer Funktion, in einem Namensraum usw.).

Der Typ eines Ausdrucks ist jedoch eine semantische Bedeutung, nicht syntaktisch, und der Parser und die Grammatik geben keinen Pfiff über Typen oder semantische Validität oder ob Tupel als Werte oder Schlüssel in Hashmaps vorliegen können oder nicht Definieren Sie diesen Bezeichner, bevor Sie ihn verwenden.

Der Grammatik ist es egal, was es bedeutet, oder ob das Sinn macht. Es interessiert nur, was es ist .


Die Eigenschaft, kontextfrei zu sein, ist ein sehr formales Konzept; Sie können hier eine Definition here . Beachten Sie, dass dies für Grammatiken gilt : Eine Sprache wird als kontextfrei bezeichnet, wenn es mindestens eine kontextfreie Grammatik gibt, die sie erkennt. Beachten Sie, dass es möglicherweise andere Grammatiken gibt, die möglicherweise nicht kontextfrei sind und die dieselbe Sprache erkennen.

Grundsätzlich bedeutet das, dass sich die Definition eines Sprachelements nicht ändern kann, je nachdem welche Elemente es umgeben. Mit Sprachelementen meine ich Konzepte wie Ausdrücke und Bezeichner und nicht spezifische Instanzen dieser Konzepte in Programmen wie a + b oder count .

Lassen Sie uns versuchen, ein konkretes Beispiel zu erstellen. Betrachten Sie diese einfache COBOL-Anweisung:

   01 my-field PICTURE 9.9 VALUE 9.9.

Hier definiere ich ein Feld, dh eine Variable, die so dimensioniert ist, dass sie eine ganze Zahl, den Dezimalpunkt und eine Dezimalziffer mit dem Anfangswert 9.9 enthält. Eine sehr unvollständige Grammatik dafür könnte sein:

field-declaration ::= level-number identifier 'PICTURE' expression 'VALUE' expression '.'
expression ::= digit+ ( '.' digit+ )

Leider sind die gültigen Ausdrücke, die PICTURE folgen können, nicht die gleichen gültigen Ausdrücke, die VALUE folgen können. Ich könnte die zweite Produktion in meiner Grammatik wie folgt umschreiben:

'PICTURE' expression ::= digit+ ( '.' digit+ ) | 'A'+ | 'X'+
'VALUE' expression ::= digit+ ( '.' digit+ )

Dies würde meine Grammatik kontextsensitiv machen, weil expression anders wäre, je nachdem, ob er nach 'PICTURE' oder nach 'VALUE' . Wie gesagt, sagt dies jedoch nichts über die zugrunde liegende Sprache aus. Eine bessere Alternative wäre:

field-declaration ::= level-number identifier 'PICTURE' format 'VALUE' expression '.'
format ::= digit+ ( '.' digit+ ) | 'A'+ | 'X'+
expression ::= digit+ ( '.' digit+ )

Das ist kontextfrei.

Wie Sie sehen können, unterscheidet sich dies sehr von Ihrem Verständnis. Erwägen:

a = b + c;

Es gibt sehr wenig, was man über diese Aussage sagen kann, ohne die Erklärungen von a, b und c in irgendeiner der Sprachen nachzuschlagen, für die dies eine gültige Aussage ist, aber dies bedeutet nicht, dass irgendeine dieser Sprachen nicht ist Kontext frei. Wahrscheinlich verwirrt Sie die Tatsache, dass die Kontextfreiheit sich von der Mehrdeutigkeit unterscheidet. Dies ist eine vereinfachte Version Ihres C ++ Beispiels:

a < b > (c)

Dies ist insofern mehrdeutig, als dass man alleine nicht sehen kann, ob es sich um einen Funktionsschablonenaufruf oder einen booleschen Ausdruck handelt. Das vorherige Beispiel ist andererseits nicht zweideutig; Aus der Sicht von Grammatiken kann es nur interpretiert werden als:

identifier assignment identifier binary-operator identifier semi-colon

In einigen Fällen können Sie Mehrdeutigkeiten auflösen, indem Sie die Kontextsensitivität auf Grammatikebene einführen. Ich denke nicht, dass dies bei dem obigen mehrdeutigen Beispiel der Fall ist: In diesem Fall können Sie die Mehrdeutigkeit nicht beseitigen, ohne zu wissen, ob a eine Vorlage ist oder nicht. Beachten Sie, dass, wenn solche Informationen nicht verfügbar sind, beispielsweise wenn sie von einer bestimmten Vorlagenspezialisierung abhängen, die Sprache Möglichkeiten zum typename von Mehrdeutigkeiten bietet. Aus diesem Grund müssen Sie manchmal typename , um auf bestimmte Typen innerhalb von Vorlagen zu verweisen oder Vorlagen zu verwenden Rufen Sie Memberfunktionsvorlagen auf.


Es gibt bereits viele gute Antworten, aber da Sie über Grammatiken, Parser und Compiler usw. nicht informiert sind, lassen Sie mich dies an einem Beispiel demonstrieren.

Erstens ist das Konzept der Grammatiken ziemlich intuitiv. Stellen Sie sich eine Reihe von Regeln vor:

S -> a T
T -> b G t
T -> Y d
b G -> a Y b
Y -> c
Y -> lambda (nothing)

Und stellen Sie sich vor, Sie beginnen mit S Die Großbuchstaben sind Nicht-Terminals und die Kleinbuchstaben sind Terminals. Das bedeutet, wenn Sie einen Satz von allen Terminals erhalten, können Sie sagen, dass die Grammatik diesen Satz als "Wort" in der Sprache generiert hat. Stellen Sie sich solche Substitutionen mit der obigen Grammatik vor (Die Phrase zwischen * Phrase * ist diejenige, die ersetzt wird):

*S* -> a *T* -> a *b G* t -> a a *Y* b t -> a a b t

Also könnte aabt mit dieser Grammatik etwas schaffen.

Ok, zurück zur Hauptlinie.

Nehmen wir eine einfache Sprache an. Sie haben Zahlen, zwei Typen (int und string) und Variablen. Sie können Multiplikationen für ganze Zahlen und Addition für Strings durchführen, aber nicht umgekehrt.

Das erste, was du brauchst, ist ein Lexer. Das ist normalerweise eine reguläre Grammatik (oder gleich, ein DFA oder gleich ein regulärer Ausdruck), die den Programm-Tokens entspricht. Es ist üblich, sie in regulären Ausdrücken auszudrücken. In unserem Beispiel:

(Ich mache diese Syntaxen auf)

number: [1-9][0-9]*    // One digit from 1 to 9, followed by any number
                       // of digits from 0-9
variable: [a-zA-Z_][a-zA-Z_0-9]*  // You get the idea. First a-z or A-Z or _
                                  // then as many a-z or A-Z or _ or 0-9
                                  // this is similar to C
int: 'i' 'n' 't'
string: 's' 't' 'r' 'i' 'n' 'g'
equal: '='
plus: '+'
multiply: '*'

whitespace: (' ' or '\n' or '\t' or '\r')*   // to ignore this type of token

So, jetzt hast du eine normale Grammatik, die deine Eingabe in Tokens umwandelt, aber sie versteht nichts von der Struktur.

Dann brauchst du einen Parser. Der Parser ist normalerweise eine kontextfreie Grammatik. Eine kontextfreie Grammatik bedeutet, dass Sie in der Grammatik nur einzelne Nichtterminale auf der linken Seite der Grammatikregeln haben. Im Beispiel am Anfang dieser Antwort die Regel

b G -> a Y b

macht die Grammatik kontextsensitiv, weil auf der linken Seite b G und nicht nur G . Was bedeutet das?

Nun, wenn Sie eine Grammatik schreiben, hat jedes der Nichtterminale eine Bedeutung. Lassen Sie uns eine kontextfreie Grammatik für unser Beispiel schreiben (| bedeutet oder. Als ob viele Regeln in derselben Zeile geschrieben wären):

program -> statement program | lambda
statement -> declaration | executable
declaration -> int variable | string variable
executable -> variable equal expression
expression -> integer_type | string_type
integer_type -> variable multiply variable |
                variable multiply number |
                number multiply variable |
                number multiply number
string_type -> variable plus variable

Jetzt kann diese Grammatik diesen Code akzeptieren:

x = 1*y
int x
string y
z = x+y

Grammatikalisch ist dieser Code korrekt. Also, zurück zu dem, was kontextfrei bedeutet. Wie Sie im obigen Beispiel sehen können, generieren Sie beim Erweitern der executable eine Anweisung der Formvariable variable = operand operator operand ohne zu überlegen, in welchem ​​Teil des Codes Sie sich befinden. Ob am Anfang oder in der Mitte, ob die Variablen definiert sind oder nicht, oder ob die Typen übereinstimmen, Sie wissen es nicht und es ist Ihnen egal.

Als nächstes brauchen Sie eine Semantik. Dies ist, wo kontextsensitive Grammatiken ins Spiel kommen. Zuerst möchte ich Ihnen sagen, dass in Wirklichkeit niemand eine kontextsensitive Grammatik schreibt (weil das Parsing zu schwierig ist), sondern Teile von Code, die der Parser beim Analysieren der Eingabe aufruft (Aktionsroutinen genannt) der einzige Weg). Formal können Sie jedoch alles definieren, was Sie brauchen. Zum Beispiel, um sicherzustellen, dass Sie eine Variable definieren, bevor Sie sie verwenden

executable -> variable equal expression

Du musst etwas haben wie:

declaration some_code executable -> declaration some_code variable equal expression

komplexer, um sicherzustellen, dass die variable in der Deklaration mit der berechneten übereinstimmt.

Jedenfalls wollte ich dir nur die Idee geben. All diese Dinge sind kontextsensitiv:

  • Typprüfung
  • Anzahl der zu funktionierenden Argumente
  • Standardwert für die Funktion
  • wenn ein member in obj im Code existiert: obj.member
  • Fast alles, was nicht wie: fehlt ; oder }

Ich hoffe, du hast eine Idee, was die Unterschiede sind (Wenn du es nicht getan hättest, wäre ich mehr als glücklich, das zu erklären).

Also zusammenfassend:

  • Lexer verwendet eine normale Grammatik, um Eingaben zu tokenisieren
  • Parser verwendet eine kontextfreie Grammatik, um sicherzustellen, dass das Programm in der richtigen Struktur ist
  • Semantic Analyzer verwendet eine kontextsensitive Grammatik, um Typ-Checking, Parameter-Matching usw. durchzuführen

Es ist nicht unbedingt immer so. Dies zeigt Ihnen nur, wie jedes Level leistungsfähiger werden muss, um mehr Sachen machen zu können. Allerdings könnte jede der genannten Compiler-Ebenen tatsächlich leistungsfähiger sein.

Zum Beispiel verwendete eine Sprache, die ich nicht erinnere, Array-Subskription und Funktionsaufruf beide mit Klammern und deshalb musste der Parser den Typ (kontextsensitives verwandtes Zeug) der Variablen nachschlagen und bestimmen, welche Regel (function_call oder array_substitution) zu übernehmen.

Wenn Sie eine Sprache mit Lexer entwerfen, die reguläre Ausdrücke enthält, die sich überlappen, müssen Sie auch den Kontext nachschlagen, um zu bestimmen, welche Art von Token Sie abgleichen.

Um zu deiner Frage zu kommen! Mit dem von Ihnen erwähnten Beispiel ist klar, dass die C ++ - Grammatik nicht kontextfrei ist. Die Sprache D, ich habe absolut keine Ahnung, aber du solltest jetzt darüber nachdenken können. Stellen Sie sich das so vor: In einer kontextfreien Grammatik kann ein Nichtterminal expandieren, ohne etwas zu berücksichtigen, ABER die Struktur der Sprache. Ähnlich wie du es gesagt hast, dehnt es sich aus, ohne irgendwo anders zu "schauen".

Ein bekanntes Beispiel wären natürliche Sprachen. Zum Beispiel auf Englisch, sagst du:

sentence -> subject verb object clause
clause -> .... | lambda

Nun, sentence und clause sind hier nichtterminiert. Mit dieser Grammatik können Sie diese Sätze erstellen:

I go there because I want to

oder

I jump you that I is air

Wie Sie sehen können, hat der zweite die richtige Struktur, ist aber bedeutungslos. Solange eine kontextfreie Grammatik betroffen ist, spielt die Bedeutung keine Rolle. Es erweitert einfach das verb zu jedem Verb, ohne auf den Rest des Satzes zu "schauen".

Wenn Sie also denken, dass D irgendwann überprüfen muss, wie etwas an anderer Stelle definiert wurde, nur um zu sagen, dass das Programm strukturell korrekt ist, dann ist seine Grammatik nicht kontextfrei. Wenn Sie einen Teil des Codes isolieren und immer noch sagen, dass er strukturell korrekt ist, ist er kontextfrei.


Es gibt ein Konstrukt in D'lexer:

string ::= q" Delim1 Chars newline Delim2 "

wobei Delim1 und Delim2 übereinstimmende Bezeichner sind und Chars keine Zeilenumschaltung Delim2 enthält.

Dieses Konstrukt ist kontextabhängig, daher ist D's Lexer-Grammatik kontextsensitiv.

Es ist ein paar Jahre her, dass ich viel mit Ds Grammatik gearbeitet habe, so dass ich mich nicht mehr an all die Schwierigkeiten im Kopf erinnern kann oder auch nur, wenn einer von ihnen Ds Parsergrammatik kontextsensitiv macht, aber ich glaube, dass sie es tun nicht. Vom Rückruf her würde ich sagen, D's Grammatik ist kontextfrei, nicht LL (k) für irgendein k, und es hat eine anstößige Menge an Mehrdeutigkeit.


Um die Frage zu beantworten, ob eine Programmiersprache kontextfrei ist, müssen Sie zuerst entscheiden, wo die Grenze zwischen Syntax und Semantik gezogen werden soll. Als extremes Beispiel ist es in C unzulässig, wenn ein Programm den Wert einiger Arten von ganzen Zahlen verwendet, nachdem sie überlaufen konnten. Natürlich kann dies nicht zur Kompilierungszeit überprüft werden, geschweige denn Zeit analysieren:

void Fn() {
  int i = INT_MAX;
  FnThatMightNotReturn();  // halting problem?
  i++;
  if(Test(i)) printf("Weeee!\n");
}

Als ein weniger extremes Beispiel, auf das andere hingewiesen haben, können Verzögerungen vor Benutzungsregeln nicht in einer kontextfreien Syntax erzwungen werden. Wenn Sie also Ihren Syntax-Pass-Kontext frei lassen wollen, muss dieser auf den nächsten Durchlauf verschoben werden.

Als praktische Definition würde ich mit der Frage beginnen: Können Sie den Syntaxbaum aller korrekten Programme mit einer kontextfreien Grammatik richtig und eindeutig bestimmen und für alle fehlerhaften Programme (die die Sprache zurückweisen muss) entweder ablehnen als syntaktisch ungültig oder erzeugen Sie einen Parse-Baum, den der spätere Durchlauf als ungültig identifizieren und ablehnen kann?

Angesichts der Tatsache, dass die am besten geeignete Spezifikation für die D-Syntax ein Parser ist (IIRC und LL-Parser), vermute ich stark, dass er tatsächlich durch die von mir vorgeschlagene Definition kontextfrei ist.

Hinweis: Obiges sagt nichts darüber aus, welche Grammatik die Sprachdokumentation oder ein bestimmter Parser verwendet, nur wenn eine kontextfreie Grammatik existiert. Die einzige vollständige Dokumentation der D-Sprache ist der Quellcode des Compilers DMD.





d2