Eine Grammatik ist ein Formalismus, der es ermöglicht, eine Syntax und damit eine formale Sprache zu definieren , dh eine Reihe zulässiger Wörter in einem bestimmten Alphabet.
Der Begriff der formalen Grammatik wird insbesondere in der Logikprogrammierung , Kompilierung ( syntaktische Analyse ), in der Berechenbarkeitstheorie und in der Behandlung natürlicher Sprachen (insbesondere hinsichtlich ihrer Morphologie und Syntax) verwendet.
Eine Sprache ist eine Menge von Wörtern , bei denen es sich einfach um Folgen von Symbolen handelt, die aus einer Menge (normalerweise endlich) ausgewählt wurden, die als Alphabet bezeichnet wird . Wenn es sich um eine Menge handelt, bezeichnen wir formal das freie Monoid on , dh die Menge endlicher Folgen von Elementen von , die mit der Operation der Verkettung zweier Wörter versehen sind. Eine Sprache über das Alphabet ist per Definition eine Teilmenge von .
Oft bestehen die "Symbole", die wir bei der Definition einer Sprache durch eine formale Grammatik berücksichtigen, aus mehreren Zeichen, so dass sie eher den sogenannten Wörtern in der aktuellen Sprache entsprechen. Ebenso entsprechen die "Wörter" der Sprache eher Sätzen oder Texten. Wenn es Mehrdeutigkeiten gibt, sprechen wir von Buchstaben oder Zeichen für die Symbole des Alphabets, die zum Codieren der Informationen verwendet werden. und wir behalten uns das Wortsymbol für diejenigen des abstrakten Alphabets vor, die die Grundelemente der Sprache sind.
Beispielsweise :
Eine formale Grammatik (oder einfach Grammatik) besteht aus den folgenden vier Objekten:
Das Anwenden einer Produktionsregel besteht darin, das Auftreten des linken Mitglieds dieser Regel durch das rechte Mitglied in einem Wort zu ersetzen. Die sukzessive Anwendung von Produktionsregeln wird als Ableitung bezeichnet. Die durch eine Grammatik definierte Sprache ist die Menge von Wörtern, die nur aus Endsymbolen bestehen und durch Ableitung aus dem Axiom erreicht werden können.
Somit ist die Grammatik durch die Terminals , das Nicht-Terminal , das Axiom und die folgenden zwei Produktionsregeln definiert:
(Wo ist das leere Wort?)ist die Sprache der Wörter der Form (eine Zahl von - möglicherweise 0 nach der zweiten Regel - gefolgt von derselben Zahl ) .
Als der Linguist Noam Chomsky den Begriff der formalen Grammatik veröffentlichte, schlug er eine Klassifikation vor, die jetzt als Chomsky-Hierarchie bezeichnet wird . Es besteht aus den folgenden vier Ebenen, von der restriktivsten bis zur breitesten.
Neben den vier Arten der Chomsky-Hierarchie gibt es einige bemerkenswerte Zwischenklassen, zum Beispiel:
Die oben genannten sechs Typen sind streng ineinander eingeschlossen. Wenn wir in Typ 1 "nicht deterministisch" in "deterministisch" umwandeln, erhalten wir einen kleineren Typ, aber wir wissen nicht, wie wir zeigen sollen, ob er streng in Typ 1 enthalten ist oder ob er diesem entspricht.
Ein Analysator für eine formale Sprache ist ein Computerprogramm , das entscheidet, ob ein bestimmtes Eingabewort zur Sprache gehört oder nicht, und möglicherweise eine Ableitung daraus erstellt.
In der Chomsky-Hierarchie stehen systematische Methoden zum Schreiben von Analyseprogrammen für Sprachen des Typs 2 oder 3 zur Verfügung. Die Interpreten oder Compiler enthalten fast immer eine Phase der lexikalischen Analyse , bei der der Sprachtyp 3 erkannt wird, gefolgt von einer Phase der syntaktischen Analyse, bei der es sich um eine Art Sprachanalyse 2 handelt. Die lexikalische Analyse konzentriert sich auf die Zeichenfolge und erzeugt eine Folge von Lexemen , die wiederum beim Parsen als Teile des Alphabets dienen.
Tools wie lex und yacc erleichtern das Schreiben von lexikalischen Analysatoren bzw. Parsern, indem Teile von Programmen automatisch aus einer Spezifikation dieser Sprache erstellt werden. Parser-Konstruktoren verwenden am häufigsten eine Variante der Backus-Naur-Form , bei der es sich um eine Notation für kontextfreie Grammatiken handelt. Während Konstrukteure von lexikalischen Analysatoren den weniger schweren Formalismus regulärer Ausdrücke verwenden .
Wir können die Grammatik arithmetischer Ausdrücke wie folgt definieren:
exp ::= exp + exp | exp × exp | (exp) | num num ::= chiffre num | chiffre chiffre ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9Die Nicht-Terminals hier sind implizit exp , num und digit , die Terminals sind +, ×, (,) und die Ziffern. Das Axiom ist exp .
Die folgende Ableitung ist ein Beispiel für die Verwendung dieser Grammatik.
exp → exp × exp → num × exp → chiffre × exp → 3 × exp → 3 × num → 3 × chiffre num →3 × 1 num → 3 × 1 chiffre → 3 × 18Die Definition gegeben
Das Definieren einer einfachen Programmiersprache ist nicht sehr kompliziert. Diese Grammatik erkennt eine Programmiersprache, die Pascal ähnelt . Hier ist ein Beispiel eines Programms zur Berechnung von Tatsachen (10)
begin int a; int b; a:=10; b:=1; while(a>1) do b:=a*b; a:=a-1; od; print b; endDie entsprechende Grammatik lautet:
program ::= ''begin'' listinstr ''end'' listinstr ::= instr listinstr | instr instr ::= ''int'' id '';'' | id '':='' expr '';'' | ''print'' expr '';'' | ''while'' ''('' cond '')'' ''do'' listinstr ''od'' '';'' expr ::= expr ''-'' expr1 | expr1 expr1 ::= expr1 ''*'' expr2 | expr2 expr2 ::= id | num | ''('' expr '')'' cond ::= expr condsymb expr condsymb ::= ''>'' | ''<'' | ''>='' | ''<='' | ''!='' | ''=''Die Terminals sind id, num, begin, end, int, print, während, (,), do, od,; und die Vergleichssymbole. Beachten Sie, dass wir mit einer solchen Grammatik (vom Typ 2 in der Chomsky-Hierarchie) nicht überprüfen können, ob alle Variablen deklariert wurden (hierfür benötigen wir eine Grammatik vom Typ 1). Wir sollten auch Regeln für num (wie oben) und für id hinzufügen.
Die Syntax der klassischen Aussagenlogik oder der Satzrechnung kann wie folgt definiert werden:
P, Q, ... sind die aussagekräftigen (terminalen) Variablen.
Ein L-System (oder Lindenmayer- System ) ist eine formale generative Grammatik, die die Entwicklung von Lebewesen beschreiben soll: Hefen, Pilze, Algen, Pflanzen, Muscheln ... Sie wurden zuerst in Verbindung mit Botanik in Verbindung mit 2D-Modellen entwickelt insbesondere auf 3D-Modelle erweitert.
Zwei Grammatiken sollen genau dann stark äquivalent sein, wenn
Zwei Grammatiken gelten genau dann als schwach äquivalent, wenn sie genau dieselbe Sprache erkennen.