Se även LL(1)
En LL-parser ( LL-parser ) är en top- down - parser inom datavetenskap för en delmängd av sammanhangsfria grammatiker som kallas LL-grammatik . Men inte alla sammanhangsfria grammatiker är LL-grammatiker.
Bokstäverna L i uttrycket "LL parser" betyder att inmatningssträngen tolkas från vänster till höger, och samtidigt byggs dess härledning längst till vänster.
En LL-parser kallas en LL(k)-parser om denna parser använder en lookahead för k tokens (tokens) när den analyserar ingångsströmmen. En grammatik som kan kännas igen av en LL(k)-parser utan bakåtspårning kallas en LL(k)-grammatik. Ett språk som kan representeras som en LL(k)-grammatik kallas ett LL(k)o-språk. Det finns LL(k+n)-språk som inte är LL(k)-språk.
Följande beskriver analysatorn, som är baserad på konstruktionen av tabeller; ett alternativ är en rekursiv descent -parser, som vanligtvis skrivs för hand (även om det finns undantag, som ANTLR- parsergeneratorn för LL(*)-grammatik).
LL(1)-grammatiker är mycket vanliga eftersom deras motsvarande LL-parsers tittar på strömmen endast ett tecken framåt när de bestämmer vilken grammatikregel som ska tillämpas. Språk baserade på grammatik med stora k-värden har traditionellt sett ansetts vara svåra att känna igen, även om med den utbredda användningen av parsergeneratorer som stöder LL(k) grammatiker med godtyckliga k, är denna kommentar inte längre relevant.
En LL-parser kallas en LL(*)-parser om det inte finns någon strikt begränsning på k och parsern kan känna igen språket om tokens tillhör någon vanlig uppsättning (till exempel med deterministiska finita automater ).
Det finns motsättningar mellan den så kallade "europeiska skolan" för språkkonstruktion, som bygger på LL-grammatiker, och den "amerikanska skolan", som föredrar LR-grammatik. Sådana motsättningar beror på undervisningens traditioner och detaljerna i beskrivningen av olika metoder och verktyg i specifika läroböcker; även influerad av N. Wirth från ETHZ , vars forskning beskriver olika metoder för att optimera LL(1)-upplösare och kompilatorer.
Parsern är utformad för att lösa problemet om en sträng tillhör en given grammatik och för att bygga ett utdataträd om den gör det.
Parsern består av:
I raderna i tabellen finns symboler för butiksalfabetet, och i kolumnerna - symboler för terminalalfabetet.
När analysen startar innehåller stacken redan två tecken:
[S, $]Där '$' är en speciell terminal som används för att indikera slutet på stacken, och 'S' är ett axiom för grammatiken. Parsern försöker, med hjälp av grammatikregler, ersätta axiomet på stacken med en teckensträng som liknar strängen på inmatningsbandet, och läser sedan bandet helt och tömmer stacken.
För att förklara hur LL-parsern fungerar, överväg följande grammatik:
Och låt oss analysera analysen av exemplet på en sträng:
(1+1)Analystabellen för denna grammatik ser ut så här:
| ( | ) | ett | + | $ | |
| S | 2 | — | ett | - | - |
| F | — | — | 3 | - | - |
Det finns också en kolumn för en speciell terminal, betecknad med $, som används för att indikera slutet på ingångsströmmen. Siffrorna (i fetstil) i cellerna anger numren på reglerna som anges ovan.
Parsern tittar på det första tecknet '(' från ingångsströmmen, i det ögonblicket är tecknet 'S' överst i stacken, i skärningspunkten mellan dessa värden i analystabellen finns en regel från grammatiken lista. I det här exemplet är detta regel nummer 2, som instruerar att ersätta tecknet 'S' på strängen '(S + F)' i stacken. Stackens tillstånd efter tillämpning av denna regel är:
[(, S, +, F, ), $ ]Vid nästa steg läser analysatorn tecknet '(' från inmatningsströmmen. Eftersom det finns ett liknande tecken '(' överst i stacken, läses detta tecken från bandet och tas bort från stacken. Tillståndet för stacken efter att ha tillämpat denna regel är:
[S, +, F, ), $]Nästa på bandet är symbolen '1', och högst upp i stapeln 'S', i skärningspunkten mellan dessa symboler i tabellen, finns regel 1. Efter att ha tillämpat denna regel, enligt tabellen, gäller analysatorn regel 3. Stackens tillstånd efter tillämpning av reglerna:
[ F, +, F, ), $ ] [ 1, +, F, ), $ ]Därefter läser parsern '1' och '+' från inmatningsströmmen och, eftersom de motsvarar de nästa två elementen i stacken, tar den också bort dem från stacken. Som ett resultat ser stacken ut så här:
[F, ), $ ]I de kommande tre stegen kommer tecknet 'F' på högen att ändras till '1', varefter tecknen '1' och ')' läses från bandet och tas bort från högen. Som ett resultat kommer symbolen '$' att finnas på toppen av stapeln och på bandet, enligt definitionen, betyder detta framgångsrik analys av kedjan.
I det här fallet kommer analysatorn att rapportera framgång och returnera en lista över reglerna som tillämpades under slutledningsprocessen:
[2, 1, 3, 3]Dessa regler är verkligen slutledningar längst till vänster:
S → (S + F) → (F + F) → (1 + F) → (1 + 1)Som du kan se i exemplet gör parsern tre olika saker beroende på om toppen av stacken är en icke-terminal, en terminal eller specialtecknet $:
Dessa steg upprepas tills ett stopp inträffar. Efter stoppet får vi antingen ett felmeddelande eller ett meddelande om att kedjan har identifierats.
För att fylla i analystabellen är det nödvändigt att fastställa vilken grammatikregel som analyseraren ska välja om den icke-terminala A är överst i sin stack och tecknet a finns i inmatningsströmmen. Det är lätt att se att en sådan regel måste ha formen A → w och att språket som motsvarar w måste ha minst en rad som börjar med a . För detta ändamål definierar vi den första uppsättningen av w , skriven här som Fi(w) , som den uppsättning terminaler som kan hittas i början av en rad i w , och ε om den tomma raden också tillhör w . Givet en grammatik med reglerna A 1 → w 1 , …, An → w n , kan man beräkna Fi(w i ) och Fi(A i ) för varje regel enligt följande:
Tyvärr räcker inte de första uppsättningarna för att bygga en analystabell. Detta beror på att den högra sidan w av regeln så småningom kan kastas till den tomma strängen. Således måste analysatorn också använda regeln A → w om ε är i Fi(w) och i ingångsströmmen ett tecken som kan följa A . Därför är det också nödvändigt att konstruera en Nästa uppsättning A (här skriven som Fo(A) ) som definieras som en uppsättning terminaler a sådan att det finns en teckensträng αAaβ som kan erhållas från starttecknet. Att beräkna följande uppsättningar för icke-terminaler i en grammatik kan göras på följande sätt:
Nu kan du definiera exakt vilka regler som ska finnas i analystabellen. Om T[A, a] anger en post i tabellen för en icke-terminal A och en terminal a , då
T[A,a] innehåller regeln A → w om och endast om:
Om tabellen inte innehåller mer än en regel i varje cell, kommer parsern att entydigt kunna bestämma vilken regel som måste tillämpas vid varje analyssteg. I det här fallet kallas grammatiken LL(1) grammatik .
Analystabellens storlek har exponentiell komplexitet som en funktion av k i värsta fall . Men efter lanseringen av Compiler Construction Toolkit (PCCTS, nu känd som ANTLR ) runt 1992, visades det att storleken på analystabellen för de flesta programmeringsspråk inte tenderar att öka exponentiellt, eftersom den inte är den värsta fall. Dessutom var det i vissa fall till och med möjligt att skapa LL( * )-analysatorer. Men trots detta använder traditionella parsergeneratorer som yacc / GNU bison LALR( 1 ) parsetabeller för att skapa en begränsad LR-parser .
Moderna parsergeneratorer , för LL-grammatik med multireläförväntning, inkluderar:
| Formella språk och formella grammatiker | |
|---|---|
| Allmänna begrepp | |
| Typ 0 | |
| Typ 1 |
|
| Typ 2 | |
| Typ 3 |
|
| analysera | |