Was ist ein IELR (1) -Parser?

14

Ich versuche mir den Umgang mit Bisons beizubringen. Die Manpage Bison (1) sagt über Bison:

Generieren Sie einen deterministischen LR-Parser oder einen generalisierten LR-Parser (GLR-Parser) unter Verwendung von LALR- (1), IELR- (1) oder kanonischen LR- (1) Parsertabellen.

Was ist ein IELR-Parser? Alle relevanten Artikel, die ich im Internet gefunden habe, sind paywalled.

FUZxxl
quelle
5
Einschließlich cs.clemson.edu/~malloy/papers/sac08/paper.pdf ?
reinierpost
@reinierpost Ich fühle mich gerade so blöd. Warum habe ich das nicht gefunden?
FUZxxl
Ich weiß nicht - Google personalisiert die Ergebnisse ...
reinierpost
@reinierpost, möchtest du diese Frage mit einem Link beantworten, um sie zu bereinigen ?
Merbs
Hmmm ... wenn das alles ist, OK.
reinierpost

Antworten:

3

Der IELR (1) -Parsing-Algorithmus

Der IELR (1) -Parsing-Algorithmus wurde 2008 von Joel E. Denny im Rahmen seiner Promotion entwickelt. Forschung unter der Aufsicht von Brian A. Malloy an der Clemson University. Der IELR (1) -Algorithmus ist eine Variation des sogenannten "minimalen" LR (1) -Algorithmus, der 1977 von David Pager entwickelt wurde und eine Variation des 1965 von Donald Knuth erfundenen LR (k) -Parsing-Algorithmus ist . Der IE in IELR (1) steht für die Beseitigung von Unzulänglichkeiten (siehe letzter Abschnitt).

LR (1) Algorithmen

Der LR (1) Teil IELR (1) steht für L inks nach rechts, R ightmost Ableitung mit 1 Vorgriffs - Token. LR (1) -Parser werden auch als kanonische Parser bezeichnet. Diese Klasse von Parsing-Algorithmen verwendet eine Bottom-up-Parsing-Strategie zur Reduzierung der Verschiebung mit einer Stapel- und Statusübergangstabelle, die die nächste Aktion bestimmt, die während des Parsings ausgeführt werden soll.

Historisch gesehen waren LR (1) -Algorithmen durch große Speicheranforderungen für ihre Übergangstabellen benachteiligt. Die Verbesserung von Pager bestand in der Entwicklung einer Methode zum Kombinieren der Übergangszustände beim Generieren der Übergangstabelle, wodurch die Größe der Tabelle erheblich reduziert wurde. Somit macht der Algorithmus von Pager LR (1) -Parser hinsichtlich der räumlichen und zeitlichen Effizienz mit anderen Parsing-Strategien konkurrenzfähig. Der Ausdruck "minimaler LR (1) -Parser" bezieht sich auf die minimale Größe der Übergangstabelle, die durch den Pager-Algorithmus eingeführt wird.

Einschränkungen des Pager-Algorithmus

Minimale LR (1) -Algorithmen erzeugen die Übergangstabelle basierend auf einer bestimmten Eingabegrammatik für die zu analysierende Sprache. Verschiedene Grammatiken können dieselbe Sprache erzeugen. In der Tat ist es möglich, dass eine Nicht-LR (1) -Grammatik eine LR (1) -Parsersprache erzeugt. In der Praxis akzeptieren LR (1) -Parsergeneratoren Nicht-LR (1) -Grammatiken mit einer Spezifikation zum Lösen von Konflikten zwischen zwei möglichen Zustandsübergängen ("Verschiebungsreduzierungskonflikte"), um dieser Tatsache Rechnung zu tragen. Denny und Malloy stellten fest, dass der Algorithmus von Pager keine Parser generiert, die leistungsfähig genug sind, um LR (1) -Sprachen zu analysieren, wenn bestimmte Nicht-LR (1) -Grammatiken bereitgestellt werden, obwohl die Nicht-LR (1) -Grammatiken eine LR (1) -Sprache generieren.

Denny und Malloy zeigen, dass diese Einschränkung nicht nur akademisch ist, indem sie zeigen, dass Gawk und Gpic, beide weit verbreitete, ausgereifte Software, falsche Parser-Aktionen ausführen.

Verbesserungen von IELR (1)

Denny und Malloy untersuchten die Ursache der Mängel des Pager-Algorithmus, indem sie die vom Pager-Algorithmus erzeugte Übergangstabelle mit der Übergangstabelle einer äquivalenten LR (1) -Grammatik verglichen und zwei Ursachen für die von ihnen als Unzulänglichkeiten bezeichneten Fehler in der Übergangstabelle von Pager identifizierten Algorithmus, aber nicht in der LR (1) -Übergangstabelle. Der IELR (1) -Algorithmus (Inadequacy Elimination LR (1)) von Denny und Malloy wurde entwickelt, um diese Unzulänglichkeiten beim Generieren der Übergangstabelle zu beseitigen, deren Größe praktisch mit der des Pager-Algorithmus identisch ist.

Robert Jacobson
quelle
6

Ein Artikel, der behauptet, ihn einzuführen: IELR (1): Praktische LR (1) -Parser-Tabellen für Nicht-LR (1) -Grammatiken mit Konfliktlösung von Joel E. Denny und Brian A. Malloy, Clemson University, ist bei Malloy frei erhältlich Seite? ˅.

Was sie wert sind, kann ich nicht beantworten. (Persönlich verstehe ich die Notwendigkeit eines solchen verkrüppelten CFG-Parsings nicht. Warum sollten Sie Ihre Ausdruckskraft einschränken, wenn Sie nur GLR verwenden können ? Was für mich Sinn macht, ist so etwas wie TAG oder PEG (sie scheinen natürlich zu sein und verleihen Ausdruckskraft) oder Tree Grammatiken (für Sprachen wie XML, in denen das Erkennen von Analysebäumen von Natur aus unproblematisch ist.)

reinierpost
quelle
Ich stimme zwar dem Prinzip der Technologie zu, aber das Problem ist oft, dass traditionelles deterministisches Parsen bessere und vollständigere Implementierungen hat. Ein weiteres Problem ist, dass das General CF-Parsen leistungsfähiger ist, GLR jedoch möglicherweise nicht die beste Version davon ist.
Babou
4
Der Hauptgrund für die Entwicklung von manipulierten CFG-Parsern ist, dass ein GLR-Parser nicht unbedingt in linearer Zeit ausgeführt wird - dies ist ein großes Problem für viele Anwendungen. Ein IELR-Parser kann eine lineare Laufzeit und mehr garantieren.
FUZxxl
Ich verstehe nicht, warum es ein Problem wäre.
Reinierpost
2
@reinierpost Es ist lineare Zeit vs.Ö(n4) (GLR) oder Ö(n3)(GLL). Dies kann z. B. beim Kompilieren großer Quelldateien viel Zeit in Anspruch nehmen. Darüber hinaus vernachlässigt die Haltung, Ausdruckskraft der Einschränkung ohne Unterstützung vorzuziehen, das damit verbundene Zeitopfer. Technisch könnten wir die superexpressiven sLMG- und / oder PMCFG-Formalismen verwenden, aber dann würden wir uns mit bis beschäftigenlichmxÖ(nx). Das mag ein absurdes Beispiel sein, aber die Motivation ist immer die Zeit . Menschen leben nicht für immer und haben viel zu tun. Ihre Zeit zu verschwenden ist im Allgemeinen schlecht.
Benutzer
3
Ich möchte darauf hinweisen, dass "ich persönlich nicht verstehe, dass ein derart verkrüppeltes CFG-Parsing erforderlich ist - warum sollten Sie Ihre Ausdruckskraft einschränken, wenn Sie nur GLR verwenden können?" ist in diesem Zusammenhang eher fehlgeleitet. IELR (1) wird verwendet, um effizientere LR (1) -Parsertabellen zu generieren, die effizientere GLR-Parser ermöglichen .
Orlp