Se også LL(1)
En LL-parser ( LL-parser ) er en top- down - parser i datalogi for en undergruppe af kontekstfri grammatikker kendt som LL-grammatikker . Det er dog ikke alle kontekstfrie grammatikker, der er LL-grammatikker.
Bogstaverne L i udtrykket "LL parser" betyder, at inputstrengen er parset fra venstre mod højre, og samtidig bygges dens afledning længst til venstre.
En LL-parser kaldes en LL(k)-parser, hvis denne parser bruger et lookahead for k tokens (tokens) ved parsing af inputstrømmen. En grammatik, der kan genkendes af en LL(k)-parser uden tilbagesporing, kaldes en LL(k)-grammatik. Et sprog, der kan repræsenteres som en LL(k)-grammatik, kaldes et LL(k)o-sprog. Der er LL(k+n)-sprog, der ikke er LL(k)-sprog.
Det følgende beskriver analysatoren, som er baseret på konstruktion af tabeller; et alternativ er en rekursiv descent -parser, som normalt skrives i hånden (selvom der er undtagelser, såsom ANTLR- parser -generatoren til LL(*)-grammatikker).
LL(1)-grammatikker er meget almindelige, fordi deres tilsvarende LL-parsere kun ser på strømmen et tegn foran, når de beslutter, hvilken grammatikregel der skal anvendes. Sprog baseret på grammatikker med store k-værdier har traditionelt været anset for vanskelige at genkende, selvom med den udbredte brug af parser-generatorer, der understøtter LL(k) grammatikker med vilkårlig k, er denne bemærkning ikke længere relevant.
En LL-parser kaldes en LL(*)-parser, hvis der ikke er nogen streng begrænsning på k, og parseren kan genkende sproget, hvis tokens tilhører et regulært sæt (for eksempel ved hjælp af deterministiske endelige automater ).
Der er modsætninger mellem den såkaldte "europæiske skole" for sprogkonstruktion, som er baseret på LL-grammatikker, og den "amerikanske skole", som foretrækker LR-grammatikker. Sådanne modsætninger skyldes undervisningens traditioner og detaljerne i beskrivelsen af forskellige metoder og værktøjer i specifikke lærebøger; også påvirket af N. Wirth fra ETHZ , hvis forskning beskriver forskellige metoder til optimering af LL(1) resolvere og compilere.
Parseren er designet til at løse problemet med, om en streng hører til en given grammatik, og til at bygge et outputtræ, hvis det gør det.
Parseren består af:
I rækkerne i tabellen er der symboler for butikalfabetet, og i kolonnerne - symboler for terminalalfabetet.
Når parsing starter, indeholder stakken allerede to tegn:
[S, $]Hvor '$' er en speciel terminal, der bruges til at angive slutningen af stakken, og 'S' er et aksiom for grammatikken. Parseren forsøger, ved hjælp af grammatikregler, at erstatte aksiomet på stakken med en streng af tegn, der ligner strengen på inputbåndet, og læser derefter båndet fuldstændigt og tømmer stakken.
For at forklare, hvordan LL-parseren fungerer, skal du overveje følgende grammatik:
Og lad os analysere parsingen på eksemplet med en streng:
(1+1)Parsetabellen for denne grammatik ser sådan ud:
| ( | ) | en | + | $ | |
| S | 2 | — | en | - | - |
| F | — | — | 3 | - | - |
Der er også en kolonne for en speciel terminal, betegnet med $, som bruges til at angive slutningen af inputstrømmen. Tallene (med fed tekst) i cellerne angiver numrene på reglerne angivet ovenfor.
Parseren ser på det første tegn '(' fra inputstrømmen, i det øjeblik er tegnet 'S' øverst på stakken, i skæringspunktet mellem disse værdier i parsetabellen er der en regel fra grammatikken liste. I dette eksempel er dette regel nummer 2, som instruerer om at erstatte tegnet 'S' i stakken på strengen '(S + F)' Stakkens tilstand efter anvendelse af denne regel er:
[(, S, +, F, ), $ ]Ved næste trin læser analysatoren tegnet '(' fra inputstrømmen. Da der er et lignende tegn '(' øverst i stakken, læses dette tegn fra båndet og fjernes fra stakken. Status for stakken efter anvendelse af denne regel er:
[S, +, F, ), $]Næste på båndet er symbolet '1', og i toppen af stakken 'S', i skæringspunktet mellem disse symboler i tabellen, er der regel 1. Efter at have anvendt denne regel, ifølge tabellen, gælder analysatoren regel 3. Stakkens tilstand efter anvendelse af reglerne:
[F, +, F, ), $ ] [ 1, +, F, ), $ ]Dernæst læser parseren '1' og '+' fra inputstrømmen, og da de svarer til de næste to elementer på stakken, fjerner den også dem fra stakken. Som et resultat ser stakken sådan ud:
[F, ), $ ]I de næste tre trin vil tegnet 'F' på stakken blive ændret til '1', hvorefter tegnene '1' og ')' læses fra båndet og fjernes fra stakken. Som et resultat vil symbolet '$' være øverst på stakken og på båndet, ifølge definitionen, betyder dette en vellykket parsing af kæden.
I dette tilfælde vil analysatoren rapportere succes og returnere en liste over de regler, der blev anvendt under slutningsprocessen:
[2, 1, 3, 3]Disse regler er faktisk slutningen længst til venstre:
S → (S + F) → (F + F) → (1 + F) → (1 + 1)Som du kan se fra eksemplet, gør parseren tre forskellige ting, afhængigt af om toppen af stakken er en ikke-terminal, en terminal eller specialtegnet $:
Disse trin gentages, indtil der opstår et stop. Efter stoppet modtager vi enten en fejlmeddelelse eller en besked om, at kæden er blevet genkendt.
For at udfylde parsetabellen er det nødvendigt at fastslå, hvilken grammatikregel parseren skal vælge, hvis den ikke-terminale A er øverst på sin stak, og tegnet a er i inputstrømmen. Det er let at se, at en sådan regel skal have formen A → w , og at sproget, der svarer til w , skal have mindst én linje, der begynder med a . Til dette formål definerer vi det første sæt af w , skrevet her som Fi(w) , som det sæt af terminaler, der kan findes i begyndelsen af enhver linje i w , og ε hvis den tomme linje også hører til w . Givet en grammatik med reglerne A 1 → w 1 , …, An → w n , kan man beregne Fi ( w i ) og Fi(A i ) for hver regel som følger:
Desværre er de første sæt ikke nok til at bygge en parse-tabel. Dette skyldes, at højre side w af reglen til sidst kunne støbes til den tomme streng. Parseren skal således også bruge reglen A → w hvis ε er i Fi(w) og i inputstrømmen et tegn der kan følge A . Derfor er det også nødvendigt at konstruere et Næste sæt A (her skrevet som Fo(A) ), der er defineret som et sæt af terminaler a sådan, at der er en tegnstreng αAaβ , der kan fås fra starttegnet. Beregning af følgende sæt for ikke-terminaler i en grammatik kan gøres som følger:
Nu kan du definere præcis, hvilke regler der skal være indeholdt i parsetabellen. Hvis T[A, a] angiver en post i tabellen for en ikke-terminal A og en terminal a , så
T[A,a] indeholder reglen A → w hvis og kun hvis:
Hvis tabellen ikke indeholder mere end én regel i hver celle, så vil parseren være i stand til entydigt at bestemme, hvilken regel der skal anvendes ved hvert parsingtrin. I dette tilfælde kaldes grammatikken LL(1) grammatik .
Parse-tabelstørrelsen har eksponentiel kompleksitet som funktion af k i værste fald . Men efter udgivelsen af Compiler Construction Toolkit (PCCTS, nu kendt som ANTLR ) omkring 1992, blev det vist, at størrelsen af parsetabellen for de fleste programmeringssprog ikke har en tendens til at stige eksponentielt, da den ikke er den værste sag. Desuden var det i visse tilfælde endda muligt at oprette LL( * )-analysatorer. På trods af dette bruger traditionelle parser-generatorer såsom yacc / GNU bison LALR( 1 ) parsetabeller til at skabe en begrænset LR-parser .
Moderne parser-generatorer til LL-grammatikker med multi-relæ-forventning inkluderer:
| Formelle sprog og formelle grammatikker | |
|---|---|
| Generelle begreber | |
| Type 0 | |
| Type 1 |
|
| Type 2 | |
| Type 3 |
|
| parsing | |