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.
Ein LF-Parser heißt LF(k)-Parser, wenn er während des Parsens k Token vorausschauen kann. Diese Token werden auch als look-ahead-Token bezeichnet.
Um zu jedem Zeitpunkt mit k look-ahead-Token die richtigen Alternativen verwenden zu können muss jedes Tupel von Metasymbol und k-look-ahead-Token eindeutig auf eine Alternative verweisen. Daher funktioniert dieses Verfahren nur für spezielle kontextfreie Grammatiken, die LF(k)-Grammatiken.
[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)