LF-Parser

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 Metasymbol 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 die LF(k)-Eigenschaft besitzen.

Definition der LF(k)-Eigenschaft

Eine kontextfreie Grammatik hat die LF(k)-Eigenschaft, falls für alle Ableitungen

	$\varphi A\beta \Rightarrow \varphi \alpha \beta \Rightarrow ^{*}\varphi \psi$
$S\Rightarrow ^{*}$
	$\varphi 'A\beta '\Rightarrow \varphi '\alpha '\beta '\Rightarrow ^{*}\varphi '\psi '$

mit ${\mathit {pre}}_{\rm {k}}(\psi )={\mathit {pre}}_{\rm {k}}(\psi ')$ gilt, dass $\alpha =\alpha '$, wobei $S,A\in M,\alpha ,\alpha ',\beta ,\beta '\in V^{*},\varphi ,\varphi ',\psi ,\psi '\in \Sigma$ und

${\mathit {pre}}_{\rm {k}}(\alpha ):={\begin{cases}\alpha ,&{\mbox{falls }}|a|\leq k\\\alpha ',&{\mbox{falls }}\alpha =\alpha '\alpha ''\land |\alpha '|=k\end{cases}}$