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 ≥ 2 {\displaystyle k\geq 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 vor, 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 {\displaystyle 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.
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 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 vor, 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 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
[Bearbeiten | Quelltext bearbeiten]- 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)