LL(1)
Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från
versionen som granskades den 3 juli 2020; kontroller kräver
5 redigeringar .
LL(1) - LL-parser , uppifrån-och-ned-analysalgoritm . Siffran 1 säger att endast en token behövs för att definiera analysvägen .
Lätt att skriva för hand utan användning av automatiska generatorer. Används för att analysera kod i ett antal programmeringsspråk som Pascal och Python (före 3.8 [1] ).
Det är mycket snabbt i utförande och har ett karakteristiskt felmeddelande som "en sådan och en sådan karaktär förväntades."
Regelguidetecken
För varje icke -terminal A i grammatiken genereras en uppsättning terminaler First(A), definierade enligt följande:
- om grammatiken har en regel med ett A på vänster sida och en höger sida som börjar med en terminal, då är den terminalen i First(A)
- om grammatiken har en regel med ett A på vänster sida och en höger sida som börjar med en icke-terminal (betecknad B), så är First(B) strikt inkluderad i First(A)
- inga andra terminaler ingår i First(A)
För varje regel genereras en uppsättning guidetecken , definierade enligt följande:
- om den högra sidan av regeln börjar med en terminal, så består uppsättningen av guidetecken av den ena terminalen
- annars börjar den högra sidan med ett icke-terminalt A, då är uppsättningen av inledande tecken First(A)
Det är möjligt att generalisera dessa definitioner för de fall då det finns regler av formen A → null.
Det är tydligt att First(A) är föreningen av uppsättningarna av ledande symboler för alla regler med A på vänster sida.
En grammatik är LL(1) parserbar om, för vilket regelpar som helst med samma vänstra sida, uppsättningen guidetecken inte skär varandra.
För att ta reda på om en grammatik tolkas av LL(1) eller inte i allmänhet är det lämpligt att använda kriteriet för LL(1)-grammatik [2] .
Beskrivning av analysatorn
Stacken används, där antalet terminaler och icke-terminaler, ingångs- (terminaler) och utgående (antal regler) flöden finns.
Först skjuts E, startsymbolen för grammatiken, på stapeln.
Sedan för varje nytt tecken från inmatningsströmmen tills den slutar:
- om det finns en terminal överst i stacken och den matchar symbolen för ingångsströmmen, då a) ta ut terminalen från stacken och b) konsumera symbolen för ingångsströmmen.
- om det finns en terminal överst i stacken och den inte matchar symbolen för ingångsströmmen, är detta ett syntaxfel "en sådan och en sådan symbol förväntades" (den på stacken).
- annars finns det en icke-terminal högst upp i stapeln, vi betecknar den med A. Alla regler med den på vänster sida genomsöks, för varje regel tittas uppsättningar av styrsymboler igenom för att hitta symbolen för inmatningen ström; den kan inte förekomma där mer än en gång, annars är grammatiken inte LL(1) parserbar.
- om symbolen hittas tillämpas denna regel: regelns nummer matas ut till utdataströmmen, en symbol tas ut från stacken (detta är A) och hela den högra sidan av regeln trycks in istället, symbolen längst till vänster på höger sida är den sista. Indataströmstecknet förbrukas inte.
- annars hittades inte symbolen alls. Sedan, om det finns en regel av formen A → null , skjuts A från toppen av stapeln. Indataströmstecknet förbrukas inte.
- annars är det ett syntaxfel, meddelandet kan matas ut som "en av var förväntad" följt av en lista över uppsättningen First(A) (för de viktigaste icke-terminalerna i språket, till exempel för icke- terminal "uttryck", kan du formulera felet i termer av icke-terminala namn).
Språk
Se även
Anteckningar
- ↑ PEP 617 - Ny PEG-parser för CPython | peps.python.org . peps.python.org . Hämtad 15 juli 2022. Arkiverad från originalet 15 juli 2022. (obestämd)
- ↑ Kozlov Sergey Valerievich, Svetlakov Alexey Vladimirovich. Om LL(1)-GRAMMATIK, ALGORITHMER PÅ DEM OCH METODER FÖR DERAS ANALYS I PROGRAMMERING // International Journal of Open Information Technologies. - 2022. - Vol. 10 , nr. 3 . — S. 30–38 . — ISSN 2307-8162 . Arkiverad från originalet den 18 maj 2022.
Litteratur
- Grune, D. och van Reeuwijk, K. och Bal, HE och Jacobs, CJH och Langendoen, K. Modern Compiler Design. - Springer, 2012. - 843 sid. — ISBN 9781461446996 .
- Mogensen, T. Æ. Introduktion till kompilatordesign. - Springer, 2011. - 225 sid. — ISBN 9780857298294 .
- Mozgovoy, M. Algoritmer, språk, automater och kompilatorer: A Practical Approach. - Jones & Bartlett Learning, 2009. - 345 sid. — ISBN 9780763782948 .
- Kozlov S. V., Svetlakov A. V. Om LL(1)-grammatiker, algoritmer för dem och metoder för deras analys i programmering — International Journal of Open Information Technologies. - 2022. - T. 10. - Nr 3. - S. 30-38. — URL: https://cyberleninka.ru/article/n/o-ll-1-grammatikah-algoritmah-na-nih-i-metodah-ih-analiza-v-programmirovanii .
Länkar