imported>Aka: Abkürzung korrigiert

2018-04-15T13:00:00Z

Abkürzung korrigiert

Neue Seite

Ein '''LF-Parser''' ({{EnS|''strong LL-parser''}}) ist ein Top-Down-[[Parser]], der ausschließlich auf der Grundlage der k nächsten Eingabe-[[Token (Compilerbau)|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 [[disjunkt|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 Grammatik]]en, die [[LF(k)-Grammatik]]en. 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 <math>k\ge 2</math> 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 <math>k</math> 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 [[Rekursiver Abstieg|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)

{{DEFAULTSORT:Lf-Parser}}
[[Kategorie:Compilerbau]]
[[Kategorie:Computerlinguistik]]
[[Kategorie:Programmierwerkzeug]]

LF-Parser - Versionsgeschichte

imported>Aka: Abkürzung korrigiert