Frage Wer ist schneller: PEG oder GLR?


Ich versuche etwas zu erschaffen lint Werkzeug für die C / AL Programmiersprache. Also muss ich im Grunde Syntax und lexikalische Analyse gegen den Quellcode durchführen. Ich habe geplant, Parser von Grund auf zu schreiben, aber dann entdeckte ich, dass es viele Tools gibt, die helfen, diese Parser automatisch zu generieren.

Ich brauche Leistung, da das Überprüfen von 20 Megabyte Code an einem Stück das normale Szenario ist und ich brauche, dass dieses Werkzeug durch benutzerdefinierte Regeln erweiterbar ist. Also entschied ich mich für JavaScript.

Soweit habe ich zwei Generatoren gefunden, die ich benutzen kann Jison und PEG.js.

Welche von ihnen gibt mir mehr Parsing-Leistung? Vielleicht nicht Bibliotheken vergleichen, sondern Algorithmen?

Welches ist besser für meine Bedürfnisse (Parsing Allzweck-Programmiersprache)?

AKTUALISIEREN: Ich habe ähnliche Fragen und Antworten gefunden:


5
2017-08-01 11:51


Ursprung


Antworten:


Im Allgemeinen erhalten Sie eine sehr gute Parsing-Leistung von einem Shift-Reduce-Parser wie dem von Jison implementierten. Es ist vielleicht ein bisschen Old-School, aber es kann in sehr engen Speicheranforderungen und in linearer Zeit arbeiten.

PEG erzeugt eine andere Art von Parser, der vielleicht leistungsfähiger ist, aber mehr Speicher benötigt, um das gleiche Ergebnis zu erzielen. I.e. PEG benötigt eine Menge an Speicher, die proportional zur Eingabe ist, während ein LALR-Parser es in viel weniger Speicherplatz (einige Tabellen und einen kleinen Stapel) tun wird.


7
2017-08-01 11:55



"Ich brauche Leistung (für 20MB) ... also entschied ich Javascript". Diese sind widersprüchlich.

Sorgfältig codierte Recursive-Descent-Parser können ziemlich schnell sein, aber Sie müssen viel Code schreiben. Im Allgemeinen sind LALR (1) Parser (von Bison aus einer Grammatik usw. erzeugt) ziemlich schnell und ziemlich einfach zu programmieren. (Es gibt technische Arbeiten, die zeigen, wie man LALR-Parser direkt in den Maschinencode übersetzt; Diese Parser sind blitzschnell, aber Sie müssen viele benutzerdefinierte Maschinen implementieren, um einen zu bauen).

Wenn Sie ein Hochleistungs-Parsing mit minimalem Schweißaufwand durchführen möchten, sollten Sie darüber nachdenken LRStar. (Ich kenne und respektiere den Autor sehr, habe aber sonst nichts zu tun). Dies produziert sehr schnelle LALR-Parser. Nachteil: Sie müssen Ihre Grammatik LALR kompatibel machen. Sie müssen Ihre "Regeln" auf die gleiche Weise erweitern wie Sie erweitern Sie jedes andere C-Programm: indem Sie C-Code schreiben. Das scheint nicht viel schlimmer zu sein als das Schreiben von JavaScript IMHO, aber die Regeln werden wahrscheinlich viel schneller ausgeführt und auf der Skala, über die du nachdenkst, wird das von Bedeutung sein.

GLR-Parsing ist notwendigerweise langsamer als LALR, weil es mehr Buchhaltung zu tun hat. Aber das ist nur ein konstanter Faktor. Es kann signifikant (z. B. 100x) gegenüber einem Hoch sein Leistungsmotor wie LRStar. Es lohnt sich vielleicht, weil es viel einfacher ist, Ihre Grammatik in Form zu bringen, und eine weniger komplizierte Grammatik wird das Schreiben von benutzerdefinierten Regeln wahrscheinlich einfacher machen. Wenn Sie wirklich 1 MSLOC-Dateien haben, werden diese Parser bestenfalls mittlerer Geschwindigkeit sein.

PEG ist grundsätzlich ein Backtracking. Es muss Dinge ausprobieren und zurückgehen, wenn sie nicht funktionieren. Sie müssen langsamer als LALR-Parser sein, zumindest um die Menge an Backtracking, die sie tun. Sie haben auch das Problem der Grammatikformung.

Was Sie jedoch entdecken werden, ist, dass Parsing einfach nicht genug ist, wenn Sie tun möchten alles, was ein wenig raffiniert ist. In diesem Fall möchten Sie das Parsing nicht optimieren. Sie möchten die Infrastruktur für die Programmanalyse optimieren. Siehe meinen Aufsatz auf Leben nach dem Parsing für eine andere Alternative.


5
2017-08-01 14:23



Soweit ich zwei Generatoren gefunden habe, kann ich Jison und PEG.js verwenden.   Welche von ihnen gibt mir mehr Parsing-Leistung?

Nach dem JavaScript Parser Libraries Benchmark habe ich erstellt Es scheint, dass PEG.js schneller ist (zumindest in Chrome / V8).

Sie können es online hier ausführen: http://sap.github.io/chevrotain/performance/

Beachten Sie, dass dieser Benchmark die sehr einfache JSON-Grammatik zum Vergleichen verwendet die Leistung der Parsing-Bibliotheken keine größere und komplexere Programmiersprachengrammatik.


1
2018-03-30 12:05