Wie funktionieren rekursive Aufstiegsparser?

Question

Wie funktionieren rekursive Aufstiegsparser? Ich habe einen rekursiven Abstieg Parser selbst geschrieben, aber ich verstehe LR Parser nicht so gut. Was ich found on Wikipedia habe, hat nur zu meiner Verwirrung beigetragen.

Eine andere Frage ist, warum rekursive Aufstieg Parser nicht mehr als ihre Tabellen-basierte Gegenstücke verwendet werden. Es scheint, dass rekursive Aufstiegsparser insgesamt eine größere Leistung aufweisen.

Answer 1

Die klassische dragon book erklärt sehr gut, wie LR-Parser arbeiten. Es gibt auch Parsing Techniques. A Practical Guide., wo Sie über sie lesen können, wenn ich mich gut erinnere. Der Artikel in Wikipedia (zumindest die Einleitung) ist nicht richtig. Sie wurden von Donald Knuth erstellt, und er erklärt sie in seinem Buch The Art of Computer Programming 5. Wenn Sie Spanisch verstehen, gibt es eine komplette Liste der Bücher here von mir gepostet. Nicht alle diese Bücher sind auch auf Spanisch.

Bevor Sie verstehen, wie sie funktionieren, müssen Sie ein paar Konzepte wie erstens, folgen und Lookahead verstehen. Außerdem empfehle ich Ihnen, die Konzepte hinter LL-Parsern zu verstehen, bevor Sie versuchen, LR (Aszendent) Parser zu verstehen.

Es gibt eine Familie von Parser LR, speziell LR (K), SLR (K) und LALR (K), wobei K ist, wie viele Lookahead sie arbeiten müssen. Yacc unterstützt LALR (1) Parser, aber Sie können Tweaks machen, nicht Theorie basiert, um es mit leistungsfähigeren Arten von Grammatiken arbeiten zu lassen.

Über die Leistung hängt es von der zu analysierenden Grammatik ab. Sie werden in linearer Zeit ausgeführt, aber wie viel Speicherplatz sie benötigen, hängt davon ab, wie viele Zustände Sie für den letzten Parser erstellen.

Answer 2

Ich persönlich habe es schwer zu verstehen, wie ein Funktionsaufruf schneller sein kann - viel weniger "deutlich schneller" als eine Tabellensuche. Und ich vermute, dass sogar "wesentlich schneller" unbedeutend ist im Vergleich zu allem, was ein Lexer/Parser tun muss (hauptsächlich das Lesen und Token der Datei). Ich schaute auf die Wikipedia-Seite, folgte aber nicht den Referenzen; Hat der Autor tatsächlich einen kompletten Lexer/Parser erstellt?

Interessanter für mich ist die Abnahme von Tabellen-getriebenen Parsern in Bezug auf rekursive Abstammung. Ich komme von einem C-Hintergrund, wo yacc (oder gleichwertig) der Parsergenerator der Wahl war. Als ich nach Java wechselte, fand ich eine tabellengesteuerte Implementierung (JavaCup) und mehrere rekursive Abstiegsimplementierungen (JavaCC, ANTLR).

Ich vermute, dass die Antwort ähnlich der Antwort "warum Java statt C" ist: Geschwindigkeit der Ausführung ist nicht so wichtig wie die Geschwindigkeit der Entwicklung. Wie im Wikipedia-Artikel erwähnt, sind tabellengesteuerte Parser aus Code kaum zu verstehen (damals, als ich sie benutzte, konnte ich ihren Aktionen folgen, wäre aber nie in der Lage gewesen, die Grammatik aus dem Parser zu rekonstruieren). Rekursive Abstammung ist im Vergleich dazu sehr intuitiv (was zweifellos darauf hindeutet, dass sie seit etwa 20 Jahren tabellengesteuert ist).

Answer 3

Der Wikipedia-Artikel über rekursive Aufstieg Parsing verweist, was scheint, die Originalarbeit zum Thema zu sein ("Sehr schnelle LR Parsing"). Durch das Überfliegen dieses Papiers haben sich einige Dinge für mich geklärt. Dinge, die ich bemerkte:

1. Das Papier spricht über die Generierung von Assembly-Code. Ich frage mich, ob Sie die gleichen Dinge tun können, die Sie tun, wenn Sie stattdessen C- oder Java-Code generieren. siehe Abschnitte 4 und 5, "Fehlerbehebung" und "Stapelüberlaufprüfung". (Ich versuche nicht, ihre Technik zu FUD zu machen - es könnte gut funktionieren - nur zu sagen, dass es etwas ist, was Sie sich vor dem Commit ansehen sollten.)

2. Sie vergleichen ihr rekursives Aufstiegswerkzeug mit ihrem eigenen tabellengesteuerten Parser. Aus der Beschreibung in ihrem Ergebnisabschnitt sieht es so aus, als ob ihr tabellengesteuerter Parser "vollständig interpretiert" ist; Es erfordert keinen benutzerdefinierten generierten Code. Ich frage mich, ob es einen Mittelweg gibt, bei dem die Gesamtstruktur immer noch tabellengesteuert ist, aber Sie generieren benutzerdefinierten Code für bestimmte Aktionen, um die Dinge zu beschleunigen.

das Papier von der Seite Wikipedia verwiesen:

• "Sehr schnelles LR-Parsing" (1986)
• http://portal.acm.org/citation.cfm?id=13310.13326

Ein weiteres Papier über Codegenerierung statt Tabelle -interpretation:

• "Sehr schnelle YACC-kompatiblen Parser (für sehr wenig Aufwand)" (1999)
• http://www3.interscience.wiley.com/journal/1773/abstract

Beachten Sie auch, dass rekursiv absteigende Parsing nicht der schnellste Weg ist LL-Grammatik-basierte Sprachen zu analysieren:

• Difference between an LL and Recursive Descent parser?