Dies ist ein handcodiertes Pedal zur Metalfrage und nicht ANTLR vs BISON.
Dies ist auch für die Analyse eines Binärformats. Es gibt keine lexikalische Analyse.Sind LL (1) Parser effizienter für eine Präfix-Codierung und LR (1) effizienter für Postfix?
Die Kosten für das Parsen eines strikten Ausdruckes vor oder nach der Reihenfolge sind trivial und verwenden entweder Top-Down- oder Bottom-Up-Techniken. Es wird von jeder anderen Aufgabe, sogar lexikalischen Analyse, in den Schatten gestellt werden. Die winzigen Geschwindigkeitsunterschiede sind eher das Ergebnis von Implementierungsdetails als algorithmischer Strategie.
Es macht keinen Sinn, einen LR (1) -Parser zu verwenden, da Sie kein Token-Lookahead für Darstellungen vor oder nach der Bestellung benötigen, vorausgesetzt, die Darstellung ist rein vor/nach der Bestellung. LR (0) wäre in Ordnung. Es ist unwahrscheinlich, dass Sie einen nützlichen LR (0) -Parser-Generator finden, aber wenn Sie einen Parser manuell schreiben möchten, wird diese Tatsache Ihre Aufgabe vereinfachen.
Wenn Sie LL (1) und LR (1) jetzt ignorieren, analysieren Sie diese Ausdrücke normalerweise, indem Sie Ihren eigenen Parsing-Code rollen. Sie würden einen Stapel von zuvor geparsten und ausgewerteten Teilausdrücken beibehalten und dann entweder die beiden obersten Elemente vom Stapel entfernen und zusammenführen (wenn Sie einen anderen Operator lesen) oder etwas auf den Stapel schieben (wenn Sie eine Zahl lesen).
Es gibt ein paar Möglichkeiten, wie Sie diese Stapel tatsächlich umsetzen könnte. Sie könnten den Stack als eine explizite Stack-Datenstruktur definieren, in der Sie von links nach rechts über die Eingabe scannen und die Dinge entsprechend schieben und öffnen. Dies ist dem Stil eines LR (1) -Parsers am nächsten, da Sie in Bezug auf Verschieben (Schieben) und Reduzieren (Poppen) denken würden. Sie könnten auch einen rekursiven Algorithmus verwenden und den Aufrufstack an die Stelle des expliziten Stacks setzen, der näher an die Funktionsweise von LL (1) Parsing erinnert.
Sowohl LL (1) als auch LR (1) Parsing in diesem Fall, wenn Sie nur auf rohe Leistung achten, scheinen wie totaler Overkill. Sie sind so konzipiert, dass sie mit großen Klassen allgemeiner Grammatiken umgehen können, und der Overhead der Tabellen würde wahrscheinlich zu Ihrer Leistung führen. Ich würde den Code einfach auf zwei verschiedene Arten schreiben (explizite Stapel/Bottom-Up vs. implizite Stack/Top-Down) und sehen, welche der beiden tatsächlich schneller ist.
Danke. Dies ist ein Pedal zum Metall, wo die Parse Latency kritisch ist. Meine Intuition sagt, dass LL besser ist für Prefix und LR ist besser für Postfix. Aber wie Sie vorschlagen, schreibe ich beides und teste. Eigentlich werde ich wahrscheinlich alle vier Fälle testen, LL/Pre, LL/Post, LR/Pre, LR/Post und Test. – Olsonist
Tatsächlich haben Call Stacks explizite HW Unterstützung auf modernen x86s. Das ergibt einen Vorteil gegenüber rekursiv-dezent über Tisch getrieben, an den ich nicht gedacht hatte. – Olsonist
Dieser Artikel, LL and LR Parsing Demystified, sichert meine Intuition auf:
polnischen und Reverse Polish Notation direkt entspricht, meiner Meinung nach, zu LL und LR-Parsing bezeichnet.
Willkommen bei Stack Overflow! Ich habe deine Frage soweit bearbeitet, wie ich dein Problem erraten konnte. Fügen Sie jedoch weitere Beschreibungen hinzu, damit mehr Personen mit Wissen über das Thema sie sehen können. P Viel Glück! – manetsus
Auch wenn Sie ein Binärformat haben, müssen Sie immer noch Tokens identifizieren (z. B. eine 4-Byte-Ganzzahl aus dem Eingabedatenstrom extrahieren - je nach Protokoll in Little-Endian- oder Big-Endian-Byte-Reihenfolge) ist das moralische Äquivalent der lexikalischen Analyse. Und in den meisten Fällen wird dies immer noch mehr Zyklen benötigen als die relativ trivialen Kosten der Zuordnung von Token zu syntaktischen Formen ("Parsing"). – rici