Warum hat Tomita GLR erstellt und Earley nicht verwendet?

11

Wenn ich mir Earley Parsing anschaue, sieht es sehr elegant aus und ich frage mich, warum GLR-Techniken populär werden? Weiß jemand, was mit Earley falsch war, als er analysierte, dass Tomita GLR erstellt hat? Performance? Alle Veröffentlichungen zu dieser Diskussion werden sehr geschätzt.

parsing Wickoo
quelle
5
GLR ermöglicht das deterministische Parsen von Teilen der Grammatik. Siehe zum Beispiel Elkhound ( scottmcpeak.com/elkhound ), wo diese Idee angenommen wird. Für natürliche Sprachen ist es jedoch nicht so klar, dass GLR besser ist als Earley.
Sylvain
1
@ Sylvain: klingt nach einer Antwort für mich ...
Joshua Grochow

Antworten:

5

Besser spät als nie.

Wenn ich das richtig verstehe, ist Earley von oben nach unten und wird Zeit und Gedächtnis darauf verwenden, Earley-Artikel für jede Produktion bei einem bestimmten S (i) zu erstellen . Dies bedeutet, dass wir für die natürliche Sprache in S (0) ein Earley-Element für jedes mögliche Wort erstellen und überprüfen, das einen Satz beginnt, und es gibt ziemlich viele davon.

Da GLR jedoch von unten nach oben ist, wählt das erste Token unter der Annahme einer effizienten Suche nach gehashten Tabellen / Status die nächsten Übergänge in konstanter Zeit aus.

Dies gilt speziell für natürliche Sprachen mit einer Vielzahl unterschiedlicher Produktionen. Aber für Programmiersprachen mit den sehr kleinen Produktionen nicht wirklich sinnvoll.

Jeff
quelle