LF-Parser
aus Wikipedia, der freien Enzyklopädie
Ein LF-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 seien 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.
[Bearbeiten] 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)