[Ebene höher] [Zurück] [Weiter] [Inhalt] [Seitenende]

Unterschiede zum Happy

Linksrekursion
Die Parserfunktion
Die Fehlerfunktion
Der cut-Operator

Linksrekursion

Linksrekursionen in der Grammatik können mit Parserkombinatoren nur eingeschränkt behandelt werden [2]. Lucky erlaubt folgende linksrekursive Regeln:

bzw.

Hierbei seien  A, b  und  c  beliebige Terminal- oder Nichtterminalsymbole. Entdeckt Lucky eine Regel, in der das Symbol der Regel an erster Stelle der Symbole einer der Alternativen steht, und ist diese von anderer Struktur, als die obige, wird die Eingabedatei zurückgewiesen.

Die Parserfunktion

Der Typ der Parserfunktion %name (bzw. luckyParser) ist String -> [ %tokentype ] -> result.

Die Fehlerfunktion

Der Typ der Fehlerfunktion luckyError ist String -> [ %tokentype ] -> a.

Der cut-Operator

Der von Lucky erzeugt Parser wendet, falls eine Alternative nicht komplett geparst werden konnte, backtracking an. Das bedeutet, daß automatisch mit der nächsten Alternative fortgefahren wird, ohne zunächst mit einem Fehler abzubrechen. Erst wenn alle Alternativen einer Regel bis zum Startsymbol hin erfolglos sind, wird mit dem Fehler des dabei am längsten geparsten Ausdrucks abgebrochen. Backtracking wird jedoch nicht nur bei nicht erfolgreich geparsten Alternativen angewendet, sondern auch in den Fällen, wo eine Alternative bereits erfolgreich geparst werden konnte, denn durch die eventuell nächste Alternative könnte ja durchaus auch eine Herleitung gefunden werden. Dieses Vorgehen kann in vielen Situationen uneffektiv sein und vermieden werden.

Ist im obigen Fall bereits klar, daß die zweite Alternative b niemals erfolgreich geparst werden kann, wenn bereits die erste Alternative a erfolgreich geparst wurde, dann muß der Parser nicht mehr unnötig die zweite Alternative betrachten, sondern kann bereits nach der ersten abbrechen. Kann die erste Alternative jedoch nicht erfolgreich geparst werden, dann muß der Parser in der zweiten Alternative fortfahren. Dieses Verhalten wird durch den cut-Operator ! beschrieben. Der cut-Operator sollte jedoch nur in solchen Situationen eingesetzt werden, wo er absolut bedenkenlos ist.

[Seitenanfang]