Dieser Artikel setzt Vorkenntnisse im Bereich Theoretische Informatik und Compilerbau voraus Eine LL k Grammatik im Gegensatz zu LF k Grammatik auch schwache LL k Grammatik ist eine spezielle kontextfreie Grammatik welche die Grundlage eines LL k Parsers bildet Eine kontextfreie Grammatik heisst LL k Grammatik fur eine naturliche Zahl k wenn jeder Ableitungsschritt eindeutig durch die nachsten k Symbole der Eingabe Lookahead bestimmt ist Das bedeutet die Frage welches Nichtterminalsymbol mit welcher Regel als Nachstes expandiert werden soll kann eindeutig mit Hilfe der nachsten k Symbole der Eingabe bestimmt 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 Sprachen die fur kein k von einer LL k Grammatik erzeugt werden L L L 1 L L L 2 L L L k L L R 1 L D P D A displaystyle mathcal L mathrm LL 1 subsetneq mathcal L mathrm LL 2 subsetneq dots subsetneq mathcal L mathrm LL k subsetneq mathcal L mathrm LR 1 mathcal L mathrm DPDA Dabei steht DPDA fur die deterministischen Kellerautomaten Diese konnen genau die deterministisch kontextfreien Sprachen erkennen Inhaltsverzeichnis 1 Formale Definition LL k Grammatik 2 Anwendung 3 Beispiel 4 Siehe auch 5 LiteraturFormale Definition LL k Grammatik BearbeitenEine kontextfreie Grammatik G N S P S displaystyle G N Sigma P S nbsp ist genau dann eine LL k Grammatik wenn fur alle Linksableitungen der Form S l w A g l w a g l w x w b g l w y displaystyle S Rightarrow l wA gamma Rightarrow l left begin array l w alpha gamma Rightarrow l wx w beta gamma Rightarrow l wy end array right nbsp mit w x y S a b g N S A N displaystyle quad w x y in Sigma alpha beta 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 mathit first k x mathit 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 Anwendung BearbeitenAktuelle LL Parser benutzen meist nur einen Lookahead von 1 Daher kann in den folgenden Ausfuhrungen k 1 displaystyle k 1 nbsp gesetzt werden Bei der praktischen Anwendung ist nur mit grossem Aufwand uberprufbar ob die vorliegende Grammatik die Definition einer LL k Grammatik erfullt Es wird stattdessen ein abgewandelter Ansatz benutzt Eine kontextfreie Grammatik ist genau dann eine LL k Grammatik wenn fur alle Nichtterminalsymbole A displaystyle A nbsp 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 und S l w A a displaystyle S Rightarrow l wA alpha nbsp gilt f i r s t k b a f i r s t k g a displaystyle first k beta alpha cap first k gamma alpha emptyset nbsp w S a b g N S A N displaystyle w in Sigma alpha beta gamma in N cup Sigma A in N nbsp Erklarung Das Startsymbol der kontextfreien Grammatik S displaystyle S nbsp wurde in eventuell mehreren Schritten nach w A a displaystyle wA alpha nbsp expandiert Gemass der Linksableitung wird das Nichtterminalsymbol A displaystyle A nbsp als Nachstes ersetzt Dazu gibt es in der kontextfreien Grammatik aber zwei verschiedene Regeln A b displaystyle A to beta nbsp und A g displaystyle A to gamma nbsp Die Frage mit welcher Regel A displaystyle A nbsp expandiert wird bestimmt sich aus der Berechnung von f i r s t k b a displaystyle first k left beta alpha right nbsp und f i r s t k g a displaystyle first k left gamma alpha right nbsp Um die Frage eindeutig beantworten zu konnen mussen beide Mengen disjunkt sein Im Allgemeinen hangt f i r s t k b a displaystyle first k left beta alpha right nbsp aber vom Rechtskontext a displaystyle alpha nbsp ab wenn b ϵ displaystyle beta Rightarrow epsilon nbsp Das Ziel ist die Bestimmung von f i r s t k b a displaystyle first k left beta alpha right nbsp nur aus den Produktionen d h aus b displaystyle beta nbsp und aus den Strings die einem Vorkommen von A displaystyle A nbsp folgen konnen Fur diesen Zweck wird die Funktion f o l l o w k A displaystyle follow k left A right nbsp definiert die die Menge aller A displaystyle A nbsp folgenden Symbole berechnet b N S f o l l o w k b w S a g N S mit S l a b g und w f i r s t k g displaystyle forall beta in N cup Sigma follow k beta w in Sigma mid exists alpha gamma in N cup Sigma mbox mit S Rightarrow l alpha beta gamma mbox und w in first k gamma nbsp Damit kann die eingangs geforderte Bedingung umformuliert werden Eine reduzierte kontextfreie Grammatik ist genau dann eine LL 1 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 1 b f o l l o w 1 A f i r s t 1 g f o l l o w 1 A displaystyle first 1 beta follow 1 A cap first 1 gamma follow 1 A emptyset nbsp Achtung Dieser Satz kann auf Falle k gt 1 displaystyle k gt 1 nbsp nicht angewandt werden Die zu einer Produktion A b displaystyle A to beta nbsp berechnete Menge l a A b f i r s t 1 b f o l l o w 1 A displaystyle la A beta first 1 left beta follow 1 A right nbsp wird als Lookahead Menge bezeichnet Beispiel BearbeitenFur die folgende Grammatik G displaystyle G nbsp wird gepruft ob sie eine LL 1 Grammatik ist Dazu mussen die Lookahead Mengen aller Produktionen mit gleichen linken Regelseiten disjunkt sein G E E T T F ϵ a P E displaystyle G left E E T T F epsilon a P E right nbsp und die Menge der Produktionen ist E T E displaystyle E to TE nbsp E T E displaystyle E to TE nbsp E ϵ displaystyle E to epsilon nbsp T F T displaystyle T to FT nbsp T F T displaystyle T to FT nbsp T ϵ displaystyle T to epsilon nbsp F E displaystyle F to E nbsp F a displaystyle F to a nbsp Zunachst werden die first bzw follow Mengen der Nichtterminalsymbole bestimmt da diese fur die Berechnung der Lookahead Mengen notig sind E E T T Ff i r s t 1 displaystyle first 1 nbsp a displaystyle left a right nbsp ϵ displaystyle left epsilon right nbsp a displaystyle left a right nbsp ϵ displaystyle left epsilon right nbsp a displaystyle left a right nbsp f o l l o w 1 displaystyle follow 1 nbsp displaystyle left right nbsp ϵ displaystyle left epsilon right nbsp ϵ displaystyle left epsilon right nbsp ϵ displaystyle left epsilon right nbsp ϵ displaystyle left epsilon right nbsp Es folgt der Vergleich der Lookahead Mengen fur alle Produktionen mit gleichen linken Regelseiten Als erstes fur die beiden Produktionen E T E displaystyle E to TE nbsp und E ϵ displaystyle E to epsilon nbsp l a E T E l a E ϵ f i r s t 1 T E f o l l o w 1 E f i r s t 1 ϵ f o l l o w 1 E ϵ displaystyle la E TE cap la E epsilon first 1 TE follow 1 E cap first 1 epsilon follow 1 E cap epsilon emptyset nbsp Als Nachstes fur die beiden Produktionen T F T displaystyle T to FT nbsp und T ϵ displaystyle T to epsilon nbsp l a T F T l a T ϵ f i r s t 1 F T f o l l o w 1 T f i r s t 1 ϵ f o l l o w 1 T ϵ displaystyle la T FT cap la T epsilon first 1 FT follow 1 T cap first 1 epsilon follow 1 T cap epsilon emptyset nbsp Als letztes fur die beiden Produktionen F E displaystyle F to E nbsp und F a displaystyle F to a nbsp l a F E l a F a f i r s t 1 E f o l l o w 1 F f i r s t 1 a f o l l o w 1 F a displaystyle la F E cap la F a first 1 E follow 1 F cap first 1 a follow 1 F cap a emptyset nbsp Da alle betrachteten Schnittmengen leer sind handelt es sich bei der Grammatik G displaystyle G nbsp um eine LL 1 Grammatik Siehe auch BearbeitenLR k Grammatik LR ParserLiteratur BearbeitenDonald E Knuth Top down syntax analysis In Acta Informatica 1 1971 ISSN 0001 5903 S 79 110 Neuabdruck einer erweiterten Fassung in Donald E Knuth Selected Papers on Computer Languages Center for the Study of Language and Information Stanford CA 2003 ISBN 1 575 86381 2 CSLI lecture notes 139 Kapitel 14 LR k Analyse fur Pragmatiker von Andreas Kunert Abgerufen von https de wikipedia org w index php title LL k Grammatik amp oldid 227310851
