LL-Analyse

In der Informatik ist das LL-Parsing eine syntaktische Top- Down-Analyse für bestimmte nicht kontextbezogene Grammatiken , die als LL-Grammatiken bezeichnet werden . Es analysiert ein Eingabewort von links nach rechts ( L inks nach rechts in Englisch) und konstruiert eine Ableitung nach links ( L eftmost Ableitung in Englisch). Der Syntaxbaum wird von der Wurzel bis zum Baum erstellt.

Die LL-Analyse führt einen einzelnen Durchgang für das Eingabewort durch. Eine LL-Analyse wird als LL ( k ) -Analyse bezeichnet, wenn ein Fenster mit k Lexemen verwendet wird, um zu entscheiden, wie der Syntaxbaum des Eingabeworts erstellt werden soll.

Architektur eines LL-Analysators

Im Folgenden wird eine von links abgeleitete Top- Down-Analyse basierend auf einer Analysetabelle beschrieben . Der Begriff der linken Ableitung bedeutet, dass während des Regelanwendungsprozesses das am weitesten links stehende Nicht-Terminal ausgewählt und neu geschrieben wird. Dieser Aspekt führt zur Verwendung eines Stapels im Algorithmus des Analysators.

Allgemeiner Fall für eine LL-Analyse (1)

Der Analysator besteht aus:

einen Eingabepuffer, der die zu analysierende Zeichenfolge enthält und mit zwei Operationen ausgestattet ist: Lesen des aktuellen Zeichens und Wechseln zum nächsten Zeichen;
einen Stapel, auf den die zu analysierenden Terminals und Nicht-Terminals der Grammatik gelegt werden sollen;
Eine Analysetabelle , die angibt, welche Regel verwendet werden soll (falls vorhanden), basierend auf den Symbolen oben im Stapel und dem folgenden Lexem.

Der Parser wendet die in der Tabelle gefundene Regel an, indem er den oberen Rand des Stapels (Zeile) mit dem aktuellen Symbol im Eingabepuffer (Spalte) abgleichen.

Zu Beginn der Analyse enthält der Stapel zwei Symbole:

[ S, $ ]

Wobei '$' ein Symbol für den unteren Rand des Stapels und das Ende des Eingabepuffers ist und 'S' das Axiom der Grammatik ist.
Der Parser versucht, den Inhalt seines Stapels so umzuschreiben, wie er im Eingabepuffer angezeigt wird. Es bleibt jedoch nur das auf dem Stapel, was neu geschrieben werden muss.

Berechnung der Analysetabelle

Sei eine algebraische Grammatik (wobei V die Menge der nicht-terminalen Variablen oder Symbole bezeichnet, A das terminale Alphabet oder die Menge der terminalen Symbole, P die Menge der Regeln, S das Axiom der Grammatik, die eine Regel von P ist). Um die zur Berechnung Analysetabelle , stellen wir die Funktionen , und . ${\ displaystyle G = (V, A, S, P)}$ ${\ displaystyle Eps}$ ${\ displaystyle First}$ ${\ displaystyle Next}$

Eps

Für jeden Ausdruck , ist wahr , wenn kündbar ist, was zu sagen ist äquivalent ist wahr , wenn (der Ausdruck umschreibt auf die leere Zeichenfolge ) und ist ansonsten falsch. Diese Berechnung entspricht der der ε-Regeln , wie im Fall der Umwandlung in die Chomsky-Normalform . ${\ displaystyle \ alpha \ in (V \ cup A) ^ {+}}$ ${\ displaystyle Eps (\ alpha)}$ $\Alpha$ ${\ displaystyle \ alpha ~ {\ xrightarrow {*}} ~ \ varepsilon}$ $\Alpha$ $\ varepsilon$

Zuerst

Für jeden Ausdruck definieren wir als die Menge von Terminals, die wahrscheinlich ein von α abgeleitetes Wort beginnen. Formeller: ${\ displaystyle \ alpha \ in (V \ cup A) ^ {+}}$ ${\ displaystyle Premier (\ alpha)}$

Premier(\alpha )=\{a\in A^{*}\mid \exists \beta \in (V\cup A)^{*},\alpha {\xrightarrow {*}}a\beta \}

Wenn ja . ${\ displaystyle \ alpha = \ varepsilon}$ ${\ displaystyle Premier (\ alpha) = \ varnothing}$

folgenden

Für jeden Ausdruck definieren wir als die Menge von Terminals, die wahrscheinlich einem von α abgeleiteten Wort folgen. Formeller: ${\ displaystyle \ alpha \ in (V \ cup A) ^ {+}}$ ${\ displaystyle Next (\ alpha)}$

Suivant(\alpha )=\{a\in Premier(\gamma )\mid \exists \beta ,\gamma \in (V\cup A)^{*},S{\xrightarrow {*}}\beta \alpha \gamma \}

Ja dann . Wir fügen allen auch das Symbol '$' hinzu , um das Ende des Codes anzeigen zu können. ${\ displaystyle \ alpha = \ varepsilon}$ ${\ displaystyle Next (\ alpha) = \ varnothing}$ ${\ displaystyle \ {\ alpha \ in (V \ cup A) ^ {+} \ mid \ existiert \ beta \ in (V \ cup A) ^ {*} S {\ xrightarrow {*}} \ beta \ alpha \ }}$

Ausfüllen der Analysetabelle

Die Analysetabelle ist eine zweidimensionale Matrix, deren Zeilen durch Nicht-Terminals und die Spalten durch Terminals indiziert sind . Das Befüllen erfolgt als solches:

Pour toute règle de la forme X→α Pour tout a∈Premier(α) Ajouter X→α à la case d'indice (a,X) Si Eps(α) vaut vrai Alors Pour tout b∈Suivant(α) Ajouter X→α à la case d'indice (b,X) Fin pour Fin pour Fin pour

Beispiel ohne ε-Regel

Initialisierung

Um zu erklären, wie es funktioniert, verwenden wir die folgende Grammatik:

{\ displaystyle S \ bis F}

{\ displaystyle S \ to (S + F)}

{\ displaystyle F \ to 1}

und analysieren Sie die nächste Zeichenfolge

(1 + 1)

Wir berechnen Eps:

Keine Regel gibt , daher ist kein Eps (α) immer falsch. $\ varepsilon$

Wir berechnen Prime:

Premier(F) = { 1 } Premier((S + F)) = { (} Premier(1) = { 1 }

Wir berechnen die Analysetabelle:

On prend S → F, Premier(F) = { 1 } donc on ajoute '

S\to F

' à la case (S , 1). On prend S → (S + F), Premier((S + F)) = { (} donc on ajoute '

S\to (S+F)

' à la case (S , (). On prend F → 1, Premier(1)= { 1 } donc on ajoute '

F\to 1

' à la case (F , 1).

	((	)	1	+	$
S.	${\ displaystyle S \ to (S + F)}$	- -	${\ displaystyle S \ bis F}$	- -	- -
F.	- -	- -	${\ displaystyle F \ to 1}$	- -	- -

Wortanalyse ${\ displaystyle (1 + 1)}$
Der Parser liest das erste '(' aus dem Eingabepuffer und der Oberseite des Stapels (das 'S'). Wenn er sich die Tabelle ansieht, weiß er, dass er die Regel ' ' anwenden muss, und muss nun das 'S' en neu schreiben '(S + F)' auf seinen Stapel schreiben und die auf die Ausgabe angewendete Regel schreiben. Der Stapel wird (der obere Rand des Stapels befindet sich links, die Symbole werden durch Kommas getrennt): ${\ displaystyle S \ to (S + F)}$ [ (, S, +, F, ), $ ] Wir können feststellen, dass das Nicht-Terminal S entstapelt und daher vor F neu geschrieben wird. Es ist in der Tat das Nicht-Terminal ganz links im Begriff '(S + F)'. Dies veranschaulicht den Begriff der linken Ableitung . Im nächsten Schritt wird dieses Symbol eingeblendet und aus dem Eingabepuffer entfernt, da sowohl die Oberseite des Stapels als auch der Puffer das Terminal '(' darstellen. Der Stapel wird: [ S, +, F, ), $ ] Jetzt hat der Puffer das Symbol '1' und die Oberseite des Stapels ist 'S'. Gemäß der Tabelle wendet der Analysator die Regel ' ' an, die 'F' oben auf dem Stapel platziert. Der Analysator zeigt die angewendete Regel am Ausgang an. Der Stapel wird: ${\ displaystyle S \ bis F}$ [ F, +, F, ), $ ] Da der Puffer immer das Symbol '1' hat, lautet die gemäß der Tabelle anzuwendende Regel ' '. Der Analysator zeigt die angewendete Regel am Ausgang an. Der Stapel wird: ${\ displaystyle F \ to 1}$ [ 1, +, F, ), $ ] Während der nächsten beiden Schritte (für die Symbole '1' und '+') entspricht das Pufferkopfsymbol der Oberseite des Stapels. Jeder wird aus dem Puffer entfernt und nicht gestapelt. Der Stapel wird: [ F, ), $ ] In den letzten 3 Schritten wird das 'F' auf dem Stapel durch '1' ersetzt, die Regel ' ' wird daher in die Ausgabe geschrieben. Dann werden die '1' und die ')' aus dem Eingabepuffer und dem Stapel entfernt. Die Analyse endet daher, weil nur noch '$' im Stapel und im Eingabepuffer vorhanden ist. In diesem Fall akzeptiert der Parser die Zeichenfolge und zeigt die Liste in der Ausgabe an: ${\ displaystyle F \ to 1}$ [ , , , ] ${\ displaystyle S \ rightarrow (S + F)}$ ${\ displaystyle S \ bis F}$ ${\ displaystyle F \ to 1}$ ${\ displaystyle F \ to 1}$ Welches ist effektiv eine Ableitung links von der Startkette. Wir sehen, dass eine Ableitung links von der Kette lautet: S → (S + F) → (F + F) → (1 + F) → (1 + 1)

Bemerkungen

Wie zu sehen ist, führt der Parser drei Arten von Schritten aus, abhängig von der Oberseite des Stapels (Nicht-Terminal, Terminal, '$' Symbol):

Wenn die Oberseite des Stapels ein Nicht-Terminal-Symbol ist, wird in der Analysetabelle basierend auf diesem Nicht-Terminal-Symbol und dem Symbol im Eingabepuffer nach der Regel gesucht, nach der es auf dem Stapel ersetzt werden soll. Die Regelnummer wird in die Ausgabe geschrieben. Wenn in der Analysetabelle angegeben ist, dass keine Übereinstimmungsregel vorhanden ist, wird ein Fehler ausgegeben und gestoppt.
Wenn die Oberseite des Stapels ein Terminalsymbol ist, vergleicht es es mit dem Symbol im Eingabepuffer. Wenn sie gleich sind, werden sie entfernt, andernfalls wird ein Fehler ausgegeben und gestoppt.
Wenn der obere Rand des Stapels '$' ist und der Eingabepuffer auch '$' enthält, sagt der Parser, dass er die Zeichenfolge korrekt analysiert hat, andernfalls wird ein Fehler ausgegeben. In beiden Fällen hört es auf.

Diese Schritte werden wiederholt, bis der Analysator stoppt. Es hat entweder die Zeichenfolge korrekt analysiert und eine Ableitung links von der Zeichenfolge in die Ausgabe geschrieben oder einen Fehler ausgegeben.

Beispiel mit ε-Regel

Initialisierung

Um zu erklären, wie es funktioniert, verwenden wir die folgende vereinfachte LISP / Schema-Grammatik:

{\ displaystyle S \ to (L)}

{\ displaystyle S \ to a}

{\ displaystyle L \ to SL}

{\ displaystyle L \ to \ varepsilon}

und analysieren Sie die nächste Zeichenfolge

{\ displaystyle (a ())}

Wir berechnen Eps:

Nur L kann gelöscht werden, also wahr und in den anderen Fällen falsch. ${\ displaystyle EPS (\ varepsilon) = EPS (L) =}$

Wir berechnen Prime:

Premier(a) = { a } Premier((L)) = { (} Premier(SL) = { (, a } Premier(ε) = ∅

Wir berechnen Folgendes:

Suivant(S) = { $, a, (, ) } Suivant(L) = { ) }

Wir berechnen die Analysetabelle:

On prend S → (L), Premier((L)) = { (} donc on ajoute '

S\to (L)

' à la case (S , (). On prend S → a, Premier(a) = { a } donc on ajoute '

S\to a

' à la case (S , a). On prend L → SL, Premier(SL)={ (, a } donc on ajoute '

L\to SL

' aux cases (L , () et (L, a). On prend L → ε, Premier(ε) = ∅ et Eps(ε) = vrai et Suivant(L)={ ) }, donc on ajoute '

L\to \varepsilon

' à la case (L ,)).

	((	)	beim	$
S.	${\ displaystyle S \ to (L)}$	- -	${\ displaystyle S \ to a}$	- -
L.	${\ displaystyle L \ to SL}$	${\ displaystyle L \ to \ varepsilon}$	${\ displaystyle L \ to SL}$	- -

Zur Erinnerung: Der Analysator verarbeitet einen Stapel und einen Eingabepuffer, die die Symbole der Zeichenfolge liefern können. Das Lesen des Puffers bedeutet nicht, zum nächsten Symbol überzugehen. Das Lesen des Puffers bedeutet nur den Zugriff auf das aktuelle Symbol. Wir gelangen nur dann zum nächsten Symbol im Puffer, wenn das nicht gestapelte Symbol ein Terminal ist, das dem aktuellen Symbol des Puffers entspricht. Diese Gleichheit übersetzt die Tatsache, dass die gelesene Zeichenfolge zum gegenwärtigen Zeitpunkt der Grammatik entspricht. Der Vorschub im Puffer ist nicht reversibel (der Analysator kehrt nie in die Kette zurück). Dies kann durch einen Lesekopf dargestellt werden, der mit einem Speicher versehen ist. Wenn dieser Lesekopf im Puffer voranschreitet, speichert der Speicher das gelesene Zeichen. Dieser Speicher kann beliebig oft abgerufen werden. Diese Konsultation entspricht der Leseoperation des Puffers. Der Abspielkopf kann auf das folgende Symbol vorrücken: das, was im Puffer als Vorschub bezeichnet wird.

Wortanalyse ${\ displaystyle (a ())}$
[ S, $ ] Der Parser liest das erste '(' aus dem Eingabepuffer und öffnet den oberen Rand des Stapels (das 'S'). Wenn er sich die Tabelle ansieht, weiß er, dass Regel 1 angewendet werden muss, und muss nun das 'S' neu schreiben '(L)' auf seinem Stapel, so dass der Stapel wird: [ (, L,), $ ] Am oberen Rand des Stapels befindet sich das Terminalsymbol '('. Da es dem aktuellen Symbol des Puffers entspricht (die Zeichenfolge folgt im Moment der Grammatik), wird dieses Symbol eingeblendet und zum nächsten Symbol in weitergeleitet der Puffer, der 'a' ist Der Stapel ist geworden: [ L,), $ ] Es knallt 'L' und liest den Buchstaben 'a', es muss Regel 3 anwenden; es schreibt das 'L' in 'SL' um: [S, L,), $ ] Es knallt 'S' und liest den Buchstaben 'a', es muss Regel 2 anwenden; es schreibt das 'S' in 'a' um und entfernt dann in einem zusätzlichen Schritt das 'a' aufgrund der Entsprechung mit der Oberseite des Stapels. Danach ist das aktuelle Puffersymbol das zweite '(' und der Stapel ist geworden: [ L,), $ ] Es öffnet nun das 'L' und liest den Buchstaben '(', es schreibt das 'L' in 'SL' (Regel 3) und dann das 'S' in '(L)' (Regel 1), damit es das entfernen kann '('. Das aktuelle Symbol ist das erste ')' und der Stapel ist geworden: [ L,), L,), $ ] Es öffnet das 'L' und liest den Buchstaben ')', so dass es das 'L' gemäß Regel 4 entfernen kann, dann kann es das ')' entfernen. Das aktuelle Symbol ist das zweite ')' und der Stapel ist geworden: [ L,), $ ] Auf die gleiche Weise wie zuvor erlaubt ihm Regel 4, das 'L' zu entfernen, und er kann dann das ')' entfernen. Der Stapel ist leer geworden: [ $ ] Der Algorithmus schließt daher positiv und unter Anwendung der linken Ableitungssequenz: $S\rightarrow (L)\rightarrow (SL)\rightarrow (aL)\rightarrow (aSL)\rightarrow (a(L)L)\rightarrow (a()L)\rightarrow (a())$ .

LL ( k ) Parser-Generatoren

ANTLR : (de) Offizielle Seite
Coco / R : (de) Offizielle Website
JavaCC : (de) Offizielle Seite
PCCTS : alter Name von ANTLR, (en) archivierte Site
Ocaml Genlex-Modul : (de) Offizielle Website

Anmerkungen und Referenzen

Romain Legendre und François Schwarzentruber, Zusammenstellung: Lexikalische und syntaktische Analyse - vom Text bis zu seiner Struktur in der Informatik , Paris, Ellipsen ,31. März 2015312 p. ( ISBN 978-2-340-00366-8 ).

Zum Thema passende Artikel