In der Informatik ist ein rekursiver Abstieg parser eine Art verfeinernder aus einer Reihe gegenseitig rekursiver Verfahren gebauter parser (oder eine nichtrekursive Entsprechung), wo jedes solches Verfahren gewöhnlich eine der Produktionsregeln der Grammatik durchführt. So spiegelt die Struktur des resultierenden Programms nah die der Grammatik wider, die es anerkennt.

Ein prophetischer parser ist ein rekursiver Abstieg parser, der das Zurückverfolgen nicht verlangt. Prophetische Syntaxanalyse ist nur für die Klasse von LL (k) Grammatiken möglich, die die Grammatiken ohne Zusammenhänge sind, für die dort eine positive ganze Zahl k besteht, der einem rekursiven Abstieg parser erlaubt, der Produktion zu entscheiden, durch das Überprüfen nur der folgenden k Jetons des Eingangs zu verwenden. (Die LL (k) Grammatiken schließen deshalb alle zweideutigen Grammatiken, sowie alle Grammatiken aus, die verlassenen recursion enthalten. Jede Grammatik ohne Zusammenhänge kann in eine gleichwertige Grammatik umgestaltet werden, die keinen recursion übrighat, aber die Eliminierung von linkem recursion gibt keinen LL (k) Grammatik immer nach.) Ein prophetischer parser läuft in der geradlinigen Zeit.

Der rekursive Abstieg mit der Unterstützung ist eine Technik, die der Produktion bestimmt, durch das Versuchen jeder Produktion der Reihe nach zu verwenden. Der rekursive Abstieg mit der Unterstützung wird auf LL (k) Grammatiken nicht beschränkt, aber wird nicht versichert zu enden, wenn die Grammatik LL (k) nicht ist. Selbst wenn sie, parsers enden, dass der rekursive Abstieg des Gebrauches mit der Unterstützung Exponentialzeit verlangen kann.

Obwohl prophetisch, werden parsers weit verwendet, Programmierer ziehen häufig es vor, LR oder LALR parsers über parser Generatoren zu schaffen, ohne die Grammatik in LL (k) Form umzugestalten.

Beispiel parser

Die folgende EBNF ähnliche Grammatik (für die PL/0 Programmiersprache von Niklaus Wirth, von Algorithmen + Datenstrukturen = Programme) ist in LL (1) Form:

Programm = Block ".".

blockieren Sie =

["const" ident "=" Zahl {"," ident "=" Zahl}";"]

["var" ident {"," ident}";"]

{"Verfahren" ident";" Block";"} Behauptung.

Behauptung =

[ident ": =" Ausdruck

| "nennen Sie" ident

| "beginnen Sie" Behauptung {";" Behauptung} "beendet"

| "wenn" Bedingung "dann" Behauptung

| "während" Bedingung Behauptung "tut"

].

Bedingung =

"sonderbarer" Ausdruck

| Ausdruck (" = "| "#" |"

Ausdruck = [" + "|" - "] Begriff {(" + "|" - ") Begriff}.

nennen Sie = Faktor {(" * "|" / ") Faktor}.

Faktor =

ident

| Zahl

|" (" Ausdruck")".

</pre>

Terminals werden in Notierungen ausgedrückt. Jedes Nichtterminal wird durch eine Regel in der Grammatik, abgesehen von ident und Zahl definiert, die, wie man annimmt, implizit definiert werden.

C Durchführung

Was folgt, ist eine Durchführung eines rekursiven Abstiegs parser für die obengenannte Sprache in C. Der parser liest im Quellcode, und geht mit einer Fehlermeldung ab, wenn der Code scheitert, grammatisch zu analysieren, still abgehend, wenn der Code richtig grammatisch analysiert.

Bemerken Sie wie nah der prophetische parser unter Spiegeln die Grammatik oben. Es gibt ein Verfahren für jedes Nichtterminal in der Grammatik. Syntaxanalyse steigt auf eine verfeinernde Weise hinunter, bis das Endnichtterminal bearbeitet worden ist. Das Programm-Bruchstück hängt von einer globalen Variable, sym ab, der das folgende Symbol vom Eingang und die Funktion getsym enthält, der sym, wenn genannt, aktualisiert.

Die Durchführungen der Funktionen getsym und des Fehlers werden für die Einfachheit weggelassen.

typedef enum {ident, Zahl, lparen, rparen, Zeiten, Hieb, plus,

minus, eql, neq, lss, leq, gtr, geq, callsym, beginsym, Strichpunkt,

endsym, ifsym, whilesym, wird thensym, dosym, constsym, Komma,

varsym, procsym, Periode, oddsym} Symbol;

Symbol sym;

Leere getsym (Leere);

leerer Fehler (const Rotforelle msg []);

leerer Ausdruck (Leere);

interne Nummer akzeptiert (Symbol s) {\

wenn (sym == s) {\

getsym ;

kehren Sie 1 zurück;

}\

kehren Sie 0 zurück;

}\

interne Nummer erwartet (Symbol s) {\

wenn (akzeptieren (s))

, kehren Sie 1 zurück;

Fehler ("erwarten Sie: unerwartetes Symbol");

kehren Sie 0 zurück;}\

leerer Faktor (leerer) {\

wenn (akzeptieren (ident)), {\

;

} sonst wenn (akzeptieren (Zahl)), {\

;

} sonst wenn (akzeptieren (lparen)), {\

Ausdruck ;

erwarten Sie (rparen);

} sonst {\

Fehler ("Faktor: Syntax-Fehler");

getsym ; }\}\

leerer Begriff (leerer) {\

Faktor ;

während (sym == Zeiten || sym == Hieb) {\

getsym ;

Faktor ;

}\}\

leerer Ausdruck (leerer) {\

wenn (sym == plus || sym == minus)

getsym ;

Begriff ;

während (sym == plus || sym == minus) {\

getsym ;

Begriff ;

}\}\

leere Bedingung (leerer) {\

wenn (akzeptieren (oddsym)), {\

Ausdruck ; } sonst {\ Ausdruck ;

wenn (sym == eql || sym == neq || sym == lss || sym == leq || sym == gtr || sym == geq) {\

getsym ;

Ausdruck ;

} sonst {\

Fehler ("Bedingung: ungültiger Maschinenbediener");

getsym ;

}\

}\}\

leere Behauptung (leerer) {\

wenn (akzeptieren (ident)), {\

erwarten Sie (wird);

Ausdruck ;

} sonst wenn (akzeptieren (callsym)), {\

erwarten Sie (ident);

} sonst wenn (akzeptieren (beginsym)), {\

tun Sie {\

Behauptung ;

} während (akzeptieren (Strichpunkt));

erwarten Sie (endsym);

} sonst wenn (akzeptieren (ifsym)), {\

Bedingung ;

erwarten Sie (thensym);

Behauptung ;

} sonst wenn (akzeptieren (whilesym)), {\

Bedingung ;

erwarten Sie (dosym);

Behauptung ; }\}\

leerer Block (leerer) {\

wenn (akzeptieren (constsym)), {\

tun Sie {\

erwarten Sie (ident);

erwarten Sie (eql);

erwarten Sie (Zahl);

} während (akzeptieren (Komma));

erwarten Sie (Strichpunkt);

}\

wenn (akzeptieren (varsym)), {\

tun Sie {\ erwarten Sie (ident); } während (akzeptieren (Komma)); erwarten Sie (Strichpunkt); }\

während (akzeptieren (procsym)), {\

erwarten Sie (ident); erwarten Sie (Strichpunkt);

Block ;

erwarten Sie (Strichpunkt); }\

Behauptung ;

}\

leeres Programm (leerer) {\

getsym ;

Block ;

erwarten Sie (Periode);

}\</Quelle>

Durchführung auf funktionellen Sprachen

Rekursiver Abstieg parsers ist besonders leicht, auf funktionellen Sprachen wie Haskell, Lispeln oder ML durchzuführen, weil sie dazu neigen, für recursion im Allgemeinen besser angepasst zu werden.

Sieh funktionelle Perlen: Monadische Syntaxanalyse in Haskell

Siehe auch

• JavaCC - ein rekursiver Abstieg parser Generator
• Coco/R - ein rekursiver Abstieg parser Generator
• ANTLR - ein rekursiver Abstieg parser Generator
• Die Syntaxanalyse der Ausdruck-Grammatik - eine andere Form, die rekursive Abfallgrammatik vertritt
• Geist Parser Fachwerk - ein C ++ rekursiver Abstieg parser Generator-Fachwerk, das nicht verlangt, vorkompiliert Schritt
• Schwanz rekursiver parser - eine Variante des rekursiven Abstiegs parser
• halb gekocht - eine rekursive Abfall-HAKEN-Syntaxanalyse-Bibliothek für Java
• Rekursiver Aufstieg parser

• Erstausgabe, Alfred V Aho, Ravi Sethi und Jeffrey D Ullman, im besonderen Abschnitt 4.4.
• Moderne Bearbeiter-Durchführung in Java, der Zweiten Ausgabe, Andrew Appel, 2002, internationale Standardbuchnummer 0 521 82060 X.
• Rekursive Programmiertechniken, W.H. Burge, 1975, internationale Standardbuchnummer 0-201-14450-6
• Einen Bearbeiter mit C, Charles N Fischer und Richard J LeBlanc dem Jüngeren, 1991, internationale Standardbuchnummer 0-8053-2166-7 fertigend.
• Syntaxanalyse:: RecDescent: Ein vielseitiger rekursiver Abstieg Modul von Perl.
• pyparsing: Rekursives Syntaxanalyse-Modul einer vielseitigen Pythonschlange, das nicht rekursiver Abstieg (Posten der Pythonschlange-Liste) ist.
• Jparsec ein javanischer Hafen des Parsec Moduls von Haskell.
• Mit C# und Java, Pat Terry, 2005, internationale Standardbuchnummer 0 321 26360 X, 624 kompilierend
• Algorithmen + Datenstrukturen = Programme, Niklaus Wirth, 1975, internationale Standardbuchnummer 0-13-022418-9
• Bearbeiter-Aufbau, Niklaus Wirth, 1996, internationale Standardbuchnummer 0-201-40353-6

Links

• Einführung in die Syntaxanalyse - ein leichter, um Einführung in die Syntaxanalyse mit einer umfassenden Abteilung auf dem rekursiven Abstieg zu lesen, der grammatisch analysiert
• Wie man eine Grammatik in den C-Code - ein kurzer Tutorenkurs beim Einführen rekursiven Abstiegs parser verwandelt
• ExprTk Rekursiver Abstieg mathematischer Ausdruck parser und Schätzer in C ++
• Einfache mathematische Ausdrücke parser in Ruby
• Jack W. Crenshaw: Wollen Wir Einen Bearbeiter (1988-1995), in Pascal mit der Assemblerproduktion Bauen, das Verwenden "hält es einfache" Annäherung