Dieser Artikel setzt Vorkenntnisse im Bereich Theoretische Informatik und Compilerbau voraus Eine LF k Grammatik ist eine spezielle kontextfreie Grammatik welche die Grundlage eines LF k Parsers bildet Auf Grund der sehr engen Verwandtschaft werden LF k Grammatiken auch als starke LL k Grammatiken bezeichnet Die Bezeichnung LF k Grammatik bedeutet dass jeder Ableitungsschritt eindeutig durch k Symbole der Eingabe Lookahead bestimmt ist Damit kann die Frage welches Nichtterminalsymbol mit welcher Regel als Nachstes expandiert werden soll eindeutig mit Hilfe der nachsten k Symbole der Eingabe beantwortet werden Generell gilt je grosser k gewahlt wird umso machtiger wird die Sprachklasse wobei die Ausdrucksstarke von kontextfreien Grammatiken nie erreicht wird Damit gibt es kontextfreie Grammatiken die fur kein k LF k Grammatiken sind L L F 1 L L F 2 L P D A displaystyle mathcal L mathrm LF 1 subsetneq mathcal L mathrm LF 2 subsetneq dots subsetneq mathcal L mathrm PDA Inhaltsverzeichnis 1 Formale Definition LF k Grammatik 2 Anwendung 3 Beispiel 4 LiteraturFormale Definition LF k Grammatik BearbeitenEine kontextfreie Grammatik G N S P S displaystyle G N Sigma P S nbsp ist genau dann eine LF k Grammatik wenn fur alle Linksableitungen der Form w A g l w a g l w x displaystyle wA gamma Rightarrow l w alpha gamma Rightarrow l wx nbsp S l displaystyle S Rightarrow l nbsp w A g l w b g l w y displaystyle w A gamma Rightarrow l w beta gamma Rightarrow l w y nbsp mit w w x y S a b g g N S A N displaystyle w w x y in Sigma alpha beta gamma gamma in N cup Sigma A in N nbsp und f i r s t k x f i r s t k y displaystyle first k left x right first k y nbsp gilt a b displaystyle alpha beta nbsp Fur die in der Definition benutzte Funktion zur Bestimmung der first Mengen gilt a S a k displaystyle a in Sigma a leq k nbsp f i r s t k a a displaystyle mathit first k left a right a nbsp a S a gt k displaystyle a in Sigma a gt k nbsp f i r s t k a v S a v w v k displaystyle mathit first k a v in Sigma mid a vw v k nbsp A N S S displaystyle A in N cup Sigma backslash Sigma nbsp f i r s t k A v S A w w S f i r s t k w v displaystyle mathit first k A v in Sigma mid A Rightarrow w w in Sigma mathit first k w v nbsp A 2 N S displaystyle mathcal A in 2 N cup Sigma nbsp f i r s t k A w f i r s t k a a A displaystyle mathit first k mathcal A w in first k alpha mid alpha in mathcal A nbsp Anwendung BearbeitenDie formale Definition einer LF k Grammatik ist bezuglich praktischer Anwendung nur mit grossem Aufwand uberprufbar Daher erfolgt die Prufung auf LF k Eigenschaft mithilfe eines abgewandelten Ansatzes Eine reduzierte kontextfreie Grammatik ist genau dann eine LF k Grammatik wenn fur alle Nichtterminalsymbole A displaystyle A nbsp und fur alle Produktionen A b displaystyle A to beta nbsp und A g displaystyle A to gamma nbsp mit b g displaystyle beta neq gamma nbsp gilt f i r s t k b f o l l o w k A f i r s t k g f o l l o w k A displaystyle first k beta follow k A cap first k gamma follow k A emptyset nbsp Erklarung Infolge einer Wortableitung wurde das Startsymbol der kontextfreien Grammatik in eventuell mehreren Schritten expandiert Angenommen im nachsten Schritt soll das Nichtterminalsymbol A ersetzt werden Dazu stehen aber zwei verschiedene Regeln A b displaystyle A to beta nbsp und A g displaystyle A to gamma nbsp zur Verfugung Ist die in der Gesetzmassigkeit angegebene Schnittmenge leer dann kann die Regelauswahl eindeutig getroffen werden Fur diesen Zweck wird die Funktion f o l l o w k A displaystyle follow k left A right nbsp benotigt die die Menge aller A folgenden Symbole berechnet b N S g i l t f o l l o w k b w S a g N S m i t S l a b g u n d w f i r s t k g displaystyle forall beta in N cup Sigma gilt follow k beta w in Sigma mid exists alpha gamma in N cup Sigma mit S Rightarrow l alpha beta gamma und w in first k gamma nbsp Die Prufung auf LL 1 Eigenschaft benutzt den gleichen Ansatzpunkt Eine Verallgemeinerung auf beliebige k ist dabei jedoch nicht moglich Dieser Unterschied grenzt beide Grammatikformen voneinander ab Beispiel BearbeitenDie Grammatik G displaystyle G nbsp soll auf ihre LF k Eigenschaft hin untersucht werden Mit anderen Worten Fur welches k ist G eine LF k Grammatik G S A e a b P S displaystyle G left S A varepsilon a b P S right nbsp und die Menge der Produktionen istS a A a a S b A b a A e A b displaystyle S to aAaa quad S to bAba quad A to varepsilon quad A to b nbsp Zunachst werden die first bzw follow Mengen der Nichtterminalsymbole bestimmt f i r s t 1 displaystyle first 1 nbsp f i r s t 2 displaystyle first 2 nbsp f i r s t 3 displaystyle first 3 nbsp f o l l o w 1 displaystyle follow 1 nbsp f o l l o w 2 displaystyle follow 2 nbsp f o l l o w 3 displaystyle follow 3 nbsp S displaystyle S nbsp a b displaystyle left a b right nbsp a a a b b b displaystyle left aa ab bb right nbsp a a a a b a b b a b b b displaystyle left aaa aba bba bbb right nbsp e displaystyle left varepsilon right nbsp e displaystyle left varepsilon right nbsp e displaystyle left varepsilon right nbsp A displaystyle A nbsp e b displaystyle left varepsilon b right nbsp e b displaystyle left varepsilon b right nbsp e b displaystyle left varepsilon b right nbsp a b displaystyle left a b right nbsp a a b a displaystyle left aa ba right nbsp a a b a displaystyle left aa ba right nbsp Es folgt der Vergleich der wie oben definierten Mengen fur alle Produktionen mit gleichen linken Regelseiten In diesem Beispiel werden somit die Regeln S a A a a displaystyle S to aAaa nbsp mit S b A b a displaystyle S to bAba nbsp und A e displaystyle A to varepsilon nbsp mit A b displaystyle A to b nbsp verglichen Im Fall des Nichtterminalsymbols S sind schon fur k 1 displaystyle k 1 nbsp die Mengen f i r s t 1 a A a a f o l l o w 1 S a displaystyle first 1 left aAaa right follow 1 S a nbsp und f i r s t 1 b A b a f o l l o w 1 S b displaystyle first 1 left bAba right follow 1 S b nbsp disjunkt Weitere Betrachtungen fur grossere k konnen entfallen k 1 displaystyle k 1 nbsp k 2 displaystyle k 2 nbsp k 3 displaystyle k 3 nbsp f i r s t k e f o l l o w k A displaystyle first k varepsilon follow k A nbsp a b displaystyle left a b right nbsp a a b a displaystyle left aa ba right nbsp a a b a displaystyle left aa ba right nbsp f i r s t k b f o l l o w k A displaystyle first k b follow k left A right nbsp b displaystyle left b right nbsp b a b b displaystyle left ba bb right nbsp b a a b b a displaystyle left baa bba right nbsp Erst fur k 3 displaystyle k 3 nbsp sind die zu vergleichenden Mengen disjunkt und damit die deterministische Regelauswahl gewahrleistet Die Beispielgrammatik G ist also eine LF 3 Grammatik Literatur BearbeitenDaniel Scheibler Michael Henke Peter Bachmann Skript zur Compilertechnik Februar Marz 2004 PDF 487 kB Abgerufen von https de wikipedia org w index php title LF k Grammatik amp oldid 242684537
