Nicht-kontextuelle Grammatik

In der linguistischen und theoretischen Informatik ist eine kontextfreie Grammatik oder kontextfreie Grammatik , auch kontextfreie Grammatik oder Grammatik "kontextfrei" genannt, eine formale Grammatik, in der jede Produktionsregel von der Form

X→α{\ displaystyle X \ bis \ alpha}

Dabei ist ein Nicht-Terminal-Symbol und eine Zeichenfolge bestehend aus Terminals und / oder Nicht-Terminals. Der Begriff „nicht-kontextuelle“ kommt von der Tatsache , dass ein nicht-terminales kann durch ersetzt werden , und zwar unabhängig von dem Kontext , in dem es erscheint. Eine formale Sprache ist nicht kontextuell (oder aus dem Kontext gerissen oder sogar algebraisch), wenn es eine nicht kontextuelle Grammatik gibt, die sie erzeugt. X{\ Anzeigestil X}α{\ displaystyle \ alpha}X{\ Anzeigestil X}α{\ displaystyle \ alpha}

Im Gegensatz dazu ist eine Regel der Form kontextabhängig

vs +X→vs+α{\ displaystyle c ~ + X \ bis c + \ alpha}

aufgrund des linken Teils der Regel, der einen Kontext für X angibt. Eine solche Regel bedeutet, dass X in dem Fall (Kontext), in dem ihm das Terminalsymbol und das Literal vorangestellt sind, durch ersetzt werden kann . vs{\ Anzeigestil c}+{\ Anzeigestil +}α{\ displaystyle \ alpha}

Somit befindet sich in einer nicht-kontextuellen Grammatik ein nicht-terminales Symbol immer allein im linken Teil einer Regel, was bedeutet, dass seine syntaktische Umgebung (oder sein Kontext) nicht berücksichtigt wird.

Algebraische Grammatiken sind mächtig genug, um den Hauptteil der Syntax der meisten Programmiersprachen zu beschreiben , mit einigen Erweiterungen nach Bedarf. Die Backus-Naur-Form ist die am häufigsten verwendete Notation, um eine nicht kontextuelle Grammatik zu beschreiben, die eine Programmiersprache beschreibt. In Chomskys Hierarchie sind diese Grammatiken vom Typ 2.

Wenn wir mehrere Begriffe finden, um eine algebraische Grammatik zu benennen, liegt das daran, dass der englische Begriff „  kontextfrei  “ schwer zu übersetzen ist. Alle oben genannten Begriffe werden verwendet und sind gleichwertig.

Formale Definitionen

Eine algebraische Grammatik besteht aus: G{\ Anzeigestil G}

• ein endliches Alphabet von nicht-terminalen oder variablen Symbolen  ;V{\ Displaystil V}
• eines endlichen Alphabets , disjunkt davon , von Endsymbolen oder Endbuchstaben  ;BEIM{\ Anzeigestil A}V{\ Displaystil V}
• eines Elements von genannt das Axiom  ;S{\ Anzeigestil S}V{\ Displaystil V}
• einer endlichen Menge von Regeln von Ableitungen oder Produktionen .P⊂V×(V∪BEIM)*{\ displaystyle {\ mathcal {P}} \ Teilmenge V \ mal (V \ Tasse A) ^ {*}}

Eine Regel wird normalerweise in der Form geschrieben . Die Variable und das Wort werden als linkes bzw. rechtes Mitglied der Regel bezeichnet. Wir erweitern diese Notation und schreiben when result from, indem wir in ein linkes Regelelement (also eine Variable) durch sein rechtes Element ersetzen, also wenn es Wörter und eine Regel wie und gibt . Wir bemerken die reflexive und transitive Schließung dieser Beziehung. Wann (X,α){\ Anzeigestil (X, \ Alpha) \,}X→α{\ displaystyle X \ bis \ alpha}X{\ Anzeigestil X}α{\ displaystyle \ alpha}du→v{\ Displaystil u \ zu v}v{\ Anzeigestil v}du{\ Anzeigestil u}du{\ Anzeigestil u}x,ja{\ Anzeigestil x, y}X→α{\ displaystyle X \ bis \ alpha}du=xXja{\ Anzeigestil u = xXy}v=xαja{\ displaystyle v = x \ alpha y}→*{\ displaystyle {\ stackrel {*} {\ to}}}

du→*v{\ displaystyle u {\ stackrel {*} {\ to}} v},

Wir sagen , dass Drift in . du{\ Anzeigestil u} v{\ Anzeigestil v}

Die Sprache erzeugt durch die Grammatik , angemerkt , ist die Menge der terminalen Wörter ( wird nicht mehr Variablen enthält) , die aus dem Axiom ableiten , d.h. G{\ Anzeigestil G}L(G){\ Anzeigestil L (G)}S{\ Anzeigestil S}

L(G)={w∈BEIM*|S→*w}{\ displaystyle L (G) = \ {w \ in A ^ {*} \ mid S {\ stackrel {*} {\ to}} w \}}.

Wir nennen algebraische Sprache oder nicht-kontextuelle Sprache eine Sprache, die durch eine algebraische Grammatik erzeugt werden kann. Die „  Sprache erweitert  “ von der Grammatik erzeugt aus allen Wörtern von denen aus dem Axiom abzuleiten , ob die Variablen enthält. w{\ Anzeigestil w}BEIM∪V{\ Displaystil A \ Tasse V}S{\ Anzeigestil S}

Beispiele

Beispiel 1

Betrachten Sie die folgende algebraische Grammatik:

S→beimSbS→ε{\ displaystyle {\ begin {array} {l} S \ to aSb \\ S \ to \ varepsilon \ end {array}}}

wobei bezeichnet das leere Wort. Diese Grammatik erzeugt eine Sprache, die keine rationale Sprache ist . ε{\ displaystyle \ varepsilon}{beimnichtbnicht|nicht≥0}{\ displaystyle \ {a ^ {n} b ^ {n} \ mid n \ geq 0 \}}

Wir können auch einen vertikalen Balken verwenden, um die Regeln mit demselben nicht-terminalen Symbol wie das linke Element zu gruppieren und die Grammatik in der folgenden komprimierten Form zu schreiben:

S→beimSb|ε{\ displaystyle S \ to aSb \ mid \ varepsilon}.

Beispiel 2

Hier ist eine algebraische Grammatik, die die arithmetischen Ausdrücke in drei Variablen erzeugt , und , korrekt eingeklammert: x{\ Anzeigestil x}ja{\ Anzeigestil y}z{\ Anzeigestil z}

S→x|ja|z|S+S|S-S|S*S|S/S|(S){\ displaystyle S \ bis x \ mid y \ mid z \ mid S + S \ mid SS \ mid S * S \ mid S / S \ mid (S)}

Diese Grammatik erzeugt zB . (x+ja)*x-z*ja/(x+x){\ Anzeigestil (x + y) * xz * y / (x + x)}

Beispiel 3

Die folgende Grammatik erzeugt die Sprache, die sich aus den Wörtern en und en zusammensetzt und deren Anzahl von der Anzahl von verschieden ist  : beim{\ Anzeigestil a}b{\ Anzeigestil b}beim{\ Anzeigestil a}b{\ Anzeigestil b}

S→U|V{\ displaystyle S \ bis U \ mid V} U→TbeimU|TbeimT{\ displaystyle U \ to TaU \ mid TaT} V→TbV|TbT{\ displaystyle V \ to TbV \ mid TbT} T→beimTbT|bTbeimT|ε{\ displaystyle T \ to aTbT \ mid bTaT \ mid \ varepsilon}

T{\ Anzeigestil T}produziert Wörter mit der gleichen Anzahl von und , produziert Wörter mit mehr als und produziert Wörter mit weniger als . beim{\ Anzeigestil a}b{\ Anzeigestil b}U{\ Anzeigestil U}beim{\ Anzeigestil a}b{\ Anzeigestil b}V{\ Displaystil V}beim{\ Anzeigestil a}b{\ Anzeigestil b}

Beispiel 4

Die Sprachen von Dyck oder die Sprachen von gut eingeklammerten Wörtern sind algebraische Sprachen.

Ein anderes Beispiel

Nicht-kontextuelle Grammatiken sind nicht auf formale Sprachen in der Mathematik beschränkt. Sie werden auch in der Linguistik verwendet, obwohl kontextbezogene Grammatiken oft besser geeignet sind. Ein markantes Beispiel dafür ist die Arbeit der indischen Linguist Panini , Asset - IV - ten  Jahrhundert  vor Christus. AD Er beschrieb die Grammatik des Sanskrit in einem stark formalisierten System mit fast 4000 Regeln. Diese Regeln werden in einer Notation dargestellt, die der Form von Backus-Naur ähnelt .

Stichleitungen und Zweigbäume

Es gibt zwei Arten zu beschreiben, wie ein Wort aus einer gegebenen Grammatik erzeugt wurde: Die erste besteht darin, die Abfolge der Abbildungen der Regeln aufzulisten, die zweite synthetisiert diese Liste zu einem Baum, der als Ableitungsbaum bezeichnet wird.

Die erste Methode listet die Wortfolge auf (beginnend mit dem Startsymbol, dem Axiom und endend mit dem Suchwort). Zwischenworte, die Variablen enthalten, werden manchmal auch als Proto-Sätze ( Satzformen in Englisch) oder erweiterte Sprach Wort . Zusätzlich zu diesen Wörtern listen wir die Regeln auf, die angewendet werden, um von einem Wort zum nächsten zu wechseln. Wenn wir zusätzlich die Strategie anwenden, die darin besteht, "immer das am weitesten links stehende Nicht-Terminal zu ersetzen", dann reicht es tatsächlich aus, die Liste der angewendeten Regeln anzugeben. Die erhaltene Ableitung wird als Linksableitung des Wortes bezeichnet. Zum Beispiel für die folgende Grammatik:

(1)S→S+S{\ displaystyle (1) \ quad S \ bis S + S} (2)S→beim{\ displaystyle (2) \ quad S \ zu a} (3)S→1{\ displaystyle (3) \ quad S \ zu 1}

die Zeichenfolge "   " lässt daher mehrere Ableitungen zu. Die durch die Liste [(1), (1), (2), (3), (2)] dargestellte Ableitung ergibt sich wie folgt: 1+beim+beim{\ Anzeigestil 1 + a + a}

S{\ Anzeigestil S} S+S{\ Anzeigestil S + S} ((1) auf S angewendet) S+S+S{\ Anzeigestil S + S + S} ((1) auf das zweite S angewendet) S+beim+S{\ Anzeigestil S + a + S} ((2) angewendet auf zweites S) 1+beim+S{\ Anzeigestil 1 + a + S} ((3) angewendet auf das erste S) 1+beim+beim{\ Anzeigestil 1 + a + a} ((2) auf S angewendet)

in dieser Ableitung werden nicht-terminale Zeichen in keiner bestimmten Reihenfolge ersetzt.

Um einen linken Bypass zu erhalten, ersetzen wir immer das am weitesten links liegende Nicht-Terminal. Die Linksableitung des Strings "   " erhält man also auf diese Weise: 1+beim+beim{\ Anzeigestil 1 + a + a}

S{\ Anzeigestil S} S+S{\ Anzeigestil S + S} ((1) auf S angewendet) 1+S{\ Anzeigestil 1 + S} ((3) angewendet auf das erste S) 1+S+S{\ Anzeigestil 1 + S + S} ((1) auf S angewendet) 1+beim+S{\ Anzeigestil 1 + a + S} ((2) auf das erste S angewendet) 1+beim+beim{\ Anzeigestil 1 + a + a} ((2) auf S angewendet)

was die Liste [(1), (3), (1), (2), (2)] ergibt.

In ähnlicher Weise ist eine Rechtsableitung die Liste von Regeln, die verwendet wird, wenn zuerst das am weitesten rechts stehende Nicht-Terminal systematisch ersetzt wird. Im vorherigen Beispiel ist eine rechte Ableitung [(1), (2), (1), (2), (3)], die auf diese Weise erhalten wird:

S{\ Anzeigestil S} S+S{\ Anzeigestil S + S} ((1) auf S angewendet) S+beim{\ Anzeigestil S + a} ((2) auf das letzte S angewendet) S+S+beim{\ Anzeigestil S + S + a} ((1) auf S angewendet) S+beim+beim{\ Anzeigestil S + a + a} ((2) auf das letzte S angewendet) 1+beim+beim{\ Anzeigestil 1 + a + a} ((3) angewendet auf das erste S)

Die Unterscheidung zwischen linker und rechter Ableitung ist in der Praxis wichtig, da sie es in den meisten Parsern ermöglicht, die Prioritäten der Operationen zu berücksichtigen. Die LL-Analysatoren erzeugen linke Ableitungen und die Analysatoren LR gerade Verzweigungen (eigentlich bestimmen Reduktionen, dh zuerst die zuletzt angewendete Regel).

Eine Ableitung erzwingt auch eine hierarchische Struktur der abgeleiteten Kette.

{{{1} S + {a} S } S + {a} S } S

wobei {...} S einen Teilstring angibt, der als zu S gehörig erkannt wurde. Diese Hierarchie kann auch als Baum angesehen werden:

S /|\ / | \ / | \ S + S | /|\ | / | \ 1 S + S | | a a

Dieser Baum wird Ableitungsbaum , Baumanalyse oder konkreter Syntaxbaum (im Gegensatz zum abstrakten Syntaxbaum ) des Strings genannt. Der oben gezeigte linke Ast und der rechte Ast definieren den gleichen Abzweigschacht. Dies ist normal, da die beiden Ableitungen zwei Tiefenreisen des Ableitungsbaums sind, die erste durch Auswahl des am weitesten links liegenden Knotens, die zweite durch Auswahl des am weitesten rechts stehenden Knotens. Es gibt eine Bijektion zwischen den linken Ableitungen und den rechten Ableitungen.

Eine Grammatik ist mehrdeutig, wenn mindestens ein von der Grammatik erzeugtes Wort mindestens zwei separate Parse-Bäume hat, andernfalls ist es eine unzweideutige Grammatik oder eindeutig . Eine Sprache ist eindeutig oder eindeutig, wenn sie eine eindeutige Grammatik besitzt. Es heißt inhärent mehrdeutig, wenn alle Grammatiken, die es erzeugen, mehrdeutig sind.

Ein Beispiel für eine inhärent mehrdeutige Sprache ist die Sprache:

{beimnichtbnichtvsich|nicht,ich≥0}∪{beimnichtbichvsich|nicht,ich≥0}{\ displaystyle \ {a ^ {n} b ^ {n} c ^ {m} \ mid n, m \ geq 0 \} \ cup \ {a ^ {n} b ^ {m} c ^ {m} \ Mitte n, m \ geq 0 \}}

In allen Grammatiken haben Wörter zwei verschiedene Ableitungen. Der Beweis erfolgt mit dem Lemma von Ogden . beimnichtbnichtvsnicht{\ displaystyle a ^ {n} b ^ {n} c ^ {n}}

Bei der syntaktischen Analyse von Wörtern, die durch eine mehrdeutige Grammatik generiert wurden, müssen nichtdeterministische Analysetechniken und / oder angepasste Techniken ( Backtracking , Begriffsklärungsregeln, ...) verwendet werden.

Normale Formen

Eine algebraische Sprache kann durch algebraische Grammatiken verschiedener Formen erzeugt werden. Zwei Grammatiken werden als äquivalent bezeichnet, wenn sie dieselbe Sprache erzeugen.

Reduzierte und saubere Grammatik

• Eine reduzierte Grammatik ist eine Grammatik, bei der jede Variable nützlich ist, dh in mindestens einer Ableitung eines Wortes der Sprache vorkommt. Wir können immer eine Grammatik reduzieren , dh unnötige Variablen effektiv entfernen.
• Eine Grammatik ist korrekt, wenn kein rechtes Regelelement dem leeren Wort oder einer Variablen entspricht. Wir können eine Grammatik sauber machen, vorausgesetzt, dass die generierte Sprache kein leeres Wort enthält, oder die einzige -Regel zulassen , wo das Axiom ist, mit der zusätzlichen Bedingung, dass kein Regelelement für die rechte Hand erscheint.ε{\ displaystyle \ varepsilon}S→ε{\ displaystyle S \ bis \ varepsilon}S{\ Anzeigestil S}S{\ Anzeigestil S}

Chomsky-Normalform

Eine Grammatik liegt in der Chomsky- Normalform vor, wenn alle ihre Regeln eine der folgenden Formen haben

• X→JaZ{\ Displaystil X \ bis YZ}
• X→beim{\ Displaystil X \ zu a},

wobei Variablen sind und ein Buchstabe ist. Wenn die generierte Sprache das leere Wort enthält, fügen wir die Regel hinzu X,Ja,Z{\ Anzeigestil X, Y, Z}beim{\ Anzeigestil a}

• S→ε{\ displaystyle S \ bis \ varepsilon},

wo ist das axiom. S{\ Anzeigestil S}

Jede Grammatik kann in Chomskys Normalform vorliegen. Diese Normalform wird beispielsweise bei der Definition eines Algorithmus zum Parsen verwendet , dem CYK-Algorithmus , der in polynomieller Zeit entscheidet , ob ein Wort in der von dieser Grammatik erzeugten Sprache vorliegt.

Normalform von Greibach

Eine Grammatik liegt in der Greibachschen Normalform vor, wenn die richtigen Glieder aller ihrer Regeln mit einem Buchstaben beginnen und eventuell formal nur Variablen folgen

X→beimJa1⋯Jak{\ displaystyle X \ to aY_ {1} \ cdots Y_ {k}}
X→b{\ Displaystil X \ bis b}

wobei Variablen und Buchstaben sind. Zum Beispiel Grammatik X,Ja1,...,Jak{\ displaystyle X, Y_ {1}, \ ldots, Y_ {k}}beim,b{\ Anzeigestil a, b}

S→beimSS|b{\ displaystyle S \ bis aSS \ mid b}

die die Sprache von Lukasiewicz erzeugt, ist in Normalform von Greibach. Die quadratische Form von Greibach verlangt auch, dass es in jedem Regelglied der rechten Hand höchstens zwei Variablen gibt (was hier der Fall ist). Jede Grammatik kann bis auf das leere Wort in eine quadratische Greibachform gebracht werden.

Bilaterale Normalform von Greibach

Die bilaterale Normalform von Greibach ist eine bilaterale Form der Normalform von Greibach: Die rechten Elemente der Regeln sind entweder Endbuchstaben oder beginnen und enden mit Endbuchstaben und enthalten nur Variablen dazwischen. Alle Regeln sind von der Form

X→beimJa1⋯Jakb{\ displaystyle X \ to aY_ {1} \ cdots Y_ {k} b}
X→vs{\ Displaystil X \ bis c}

wobei Variablen und Buchstaben sind. Jede Grammatik kann in zweiseitige Normalform gebracht werden, und wir können sie sogar in quadratischer Form annehmen , also in diesen Regeln. X,Ja1,...,Jak{\ displaystyle X, Y_ {1}, \ ldots, Y_ {k}}beim,b,vs{\ Anzeigestil a, b, c}k≤2{\ displaystyle k \ leq 2}

Erweiterte Grammatiken

Wir treffen insbesondere in Anwendungen auf eine Form von erweiterten Grammatiken: Die richtigen Mitglieder der Regeln können reguläre Ausdrücke sein. Dies ist so in der normalen erweiterten Backus-Form . Lassen Sie uns genauer die Menge der rechten Elemente von Regeln bezeichnen, deren linkes Element ist . P(X){\ Anzeigestil P (X)}X{\ Anzeigestil X}

• In der üblichen Definition algebraischer Grammatiken sind Mengen für jede Variable endlich .P(X){\ Anzeigestil P (X)}X{\ Anzeigestil X}
• In der erweiterten Grammatiken, Sätze sind rationale Sprachen , die gegeben sind durch reguläre Ausdrücke .P(X){\ Anzeigestil P (X)}
• In einer Verallgemeinerung dieser Grammatiken sind die Mengen selbst algebraische Sprachen .P(X){\ Anzeigestil P (X)}

Wir können zeigen, dass die beiden Erweiterungen von Grammatiken immer algebraische Sprachen erzeugen.

Parsing

Algebraische Grammatiken sind einfach genug, um die Erstellung effizienter Parser (im Gegensatz zu kontextuellen Grammatiken ) in polynomieller Zeit in Bezug auf die Größe der Grammatik und die Länge des zu analysierenden Wortes zu ermöglichen. Die Aufgabe eines solchen Analysators besteht darin, für ein gegebenes Wort zu bestimmen, ob und wie es aus der Grammatik generiert werden kann. Der CYK-Algorithmus und der Analysator Earley sind Beispiele für solche Algorithmen. Die Analysatoren LR und LL Parser arbeiten in linearer Zeit in der zu analysierenden Wortlänge und werden in der Praxis eingesetzt. Andererseits erlauben sie nur die Analyse restriktiverer Familien algebraischer Grammatiken.

Anmerkungen

1. Sprache in Indien .
2. Dieses Ergebnis ist nicht bekannt. Es wurde von G. Hotz bewiesen. Ein Beweis findet sich in: Joost Engelfriet , „  Ein elementarer Beweis der doppelten Greibach-Normalform  “, Information Processing Letters , Bd.  44, n o  21992, s.  291–293. Ein Beweis und ein ausführliches Beispiel findet sich auch bei Autebert, Berstel Boasson (1997) .

Literaturverzeichnis

Aufgrund ihrer grundlegenden Natur enthalten viele theoretische Computerarbeiten mindestens einen Abschnitt über algebraische Grammatiken. Mehrere Bücher wurden auch ins Französische übersetzt.

Bücher auf Französisch

• Alfred Aho, Monica Lam, Ravi Sethi und Jeffrey Ullman ( trans.  , Aus dem Englischen) Compiler: Prinzipien, Techniken und Werkzeuge: Mit mehr als 200 Jahren , Paris, Pearson,2007, 2 nd  ed. , 928  S. ( ISBN  978-2-7440-7037-2 und 2744070378 )
• Pierre Wolper , Einführung in die Berechenbarkeit: Kurse und korrigierte Übungen , Paris, Dunod,2006, 3 e  ed. , 224  S. ( ISBN  2-10-049981-5 ).
• Jean-Michel Autebert, Algebraische Sprachen , Masson,1987, 278  S. ( ISBN  978-2-225-81087-9 )
• Jean-Michel Autebert und Luc Boasson, Rational Transductions: Application to Algebraic Languages , Masson,1988( ISBN  978-2-225-81504-1 )
• Olivier Carton , Formale Sprachen, Berechenbarkeit und Komplexität ,2008[ Detail der Ausgabe ] ( online lesen )
• Jean-Michel Autebert, Jean Berstel und Luc Boasson, „Kontextfreie Sprachen und Kellerautomaten“ , in G. Rozenberg, A. Salomaa (Hrsg.), Handbook of Formal Languages , vol.  1: Wort, Sprache, Grammatik , Springer Verlag,1997( ISBN  978-3540604204 ) , p.  111-174

Buchen Sie auf Deutsch

• (de) Katrin Erk und Lutz Priese, Theoretische Informatik: eine umfassende Einführung , Berlin, Springer,2008, 485  S. ( ISBN  978-3-540-76319-2 , OCLC  244015158 ).

Bücher auf Englisch

• (en) Seymour Ginsburg, The Mathematical Theory of Context Free Languages , McGraw-Hill,1966, ix + 232  S. - Das erste Buch über algebraische Sprachen.
• (en) Alfred V. Aho und Jeffrey D. Ullman, Die Theorie des Parsens, Übersetzens und Kompilierens , vol.  1: Analyse , Englewood Cliffs, NJ, Prentice-Hall,1972, xii + 543  p. ( ISBN  0-13-914556-7 )
• (en) Alfred V. Aho und Jeffrey D. Ullman, Die Theorie des Parsens, Übersetzens und Kompilierens , vol.  2: Kompilieren , Englewood Cliffs, NJ, Prentice-Hall,1973, xii + 460  S. ( ISBN  0-13-914564-8 )
• (en) Michael A. Harrison, Einführung in die formale Sprachtheorie , Reading, Mass., Addison-Wesley,1978, 594  S. ( ISBN  0-201-02955-3 , OCLC  266962302 ).
• (en) John E. Hopcroft, Rajeev Motwani und Jeffrey D. Ullman, Einführung in die Automatentheorie, Sprachen und Berechnung , Addison Wesley,2001, 2 nd  ed. , 521  S. ( ISBN  978-0-201-44124-6 und 0201441241 ).
• (de) Peter Linz, Eine Einführung in formale Sprachen und Automaten , Jones & Bartlett Learning,2001, 410  S. ( ISBN  978-0-7637-1422-2 und 0763714224 , online lesen ).

Klassen

• Anca Muscholl, „  Kontextfreie Sprache  “
• Jean-François Perrot, „  Kontextfreie Grammatiken und die Chomsky-Hierarchie  “
• Jean Privat, "  Nicht-kontextuelle Grammatiken  "
• Jacques Désarménien, "  Nicht-kontextuelle Grammatiken  "

Siehe auch

• Parser-Packrate
• Linksrekursion
• Normalform von Greibach
• Chomsky-Normalform
• LL-Analyse , Grammatik LL
• CYK-Algorithmus

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">