LF-Parser

Ein LF-Parser (englisch strong LL-parser) ist ein Top-Down-Parser, der ausschließlich auf der Grundlage der k nächsten Eingabe-Token entscheidet, zu welcher Alternative ein Nichtterminalsymbol ersetzt wird. Von einem LL-Parser unterscheidet ihn, dass die Entscheidungsmengen, die beim Vorausschauen verwendet werden, für jedes Nichtterminalsymbol paarweise disjunkt sein müssen, das heißt, zu jedem Zeitpunkt muss jedes Tupel von Metasymbol und k-lookahead-Token eindeutig auf eine Alternative verweisen. Daher funktioniert dieses Verfahren nur für spezielle kontextfreie Grammatiken, die LF(k)-Grammatiken. LF-Parser werden auch als strong-LL-Parser bezeichnet.

Ein LF-Parser heißt LF(k)-Parser, wenn er während des Parsens k Token vorausschauen kann. Diese Token werden auch als lookahead-Token bezeichnet.

Die Klasse der LF(1)-Grammatiken ist gleich der Klasse der LL(1)-Grammatiken. Für $k\ge 2$ unterscheiden sich jedoch die Klassen, wie man an folgender Grammatik erkennt, die in LL(2), nicht jedoch in LF(2) liegt:

S → a A | b B

A → C a b

B → C b

C → a | ε

Diese Grammatik kann mit einem LF(2)-Parser nicht umgesetzt werden, denn sind die nächsten beiden Tokens ab, so könnte sowohl eine ε-Ableitung notwendig sein, wenn von A aus abgeleitet wurde als auch eine Ableitung nach a, wenn von B aus abgeleitet wurde. Es liegt eine LL-Grammatik, da zwischen zwei möglichen Ableitungen mit demselben Kontext stets mittels der Lookaheads unterschieden werden kann. Trivialerweise ist jede LF-Grammatik eine LL-Grammatik. Das Beispiel lässt sich auf beliebige k ausweiten, etwa:

S → a A | b B

A → C aᵏ⁻¹ b

B → C aᵏ⁻² b

C → a | ε

LF-Parser lassen sich wesentlich einfacher implementieren, etwa mittels rekursiven Abstiegs, der Begriff LL-Parser ist jedoch wesentlich häufiger verwendet, da LL(1)/LF(1)-Parser am verbreitetsten sind, und dort kein Unterschied besteht. Jede LL(1)-Grammatik ist auch eine LF(1)-Grammatik, denn wenn der Kontext zur Auswahl einer Ableitung entscheidend wäre, so wäre dies höchstens ein Token a im Lookahead, d.h. eine ε-Ableitung oder eine mit a beginnende Ableitung wären möglich, dies geschähe dann jedoch auch unter Berücksichtigung des Kontexts.

Literatur

• Derick Wood: The theory of left factored languages: part 1. Comp. Journal  12:4 (1969)
• Derick Wood: The theory of left factored languages: part 2. Comp. Journal  13:1 (1970)
• Derick Wood: A further note on top-down deterministic languages. Comp. Journal  14:4 (1971)