LL(1)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 3. juli 2020; checks kræver 5 redigeringer .

LL(1) - LL parser , top-down parsing algoritme . Tallet 1 siger, at der kun kræves et token for at definere parsestien .

Let at skrive i hånden uden brug af automatiske generatorer. Bruges til at parse kode i en række programmeringssprog som Pascal og Python (før 3.8 [1] ).

Den er meget hurtig i udførelse og har en karakteristisk fejlmeddelelse som "sådan og sådan en karakter var forventet."

Regelguidetegn

For hver ikke -terminal A i grammatikken genereres et sæt terminaler First(A), defineret som følger:

hvis grammatikken har en regel med et A på venstre side og en højre side, der starter med en terminal, så er den terminal i First(A)
hvis grammatikken har en regel med et A på venstre side og en højre side, der starter med en ikke-terminal (betegnet B), så er First(B) strengt taget inkluderet i First(A)
ingen andre terminaler er inkluderet i First(A)

For hver regel genereres et sæt guidetegn , defineret som følger:

hvis højre side af reglen starter med en terminal, så består sættet af guidetegn af den ene terminal
ellers starter højre side med et ikke-terminalt A, så er sættet af ledende tegn først(A)

Det er muligt at generalisere disse definitioner til de tilfælde, hvor der er regler i formen A → null.

Det er klart, at First(A) er foreningen af sættene af ledende symboler for alle regler med A på venstre side.

En grammatik er LL(1) parsabel , hvis for et hvilket som helst regelpar med samme venstre side, sættet af hjælpetegn ikke skærer hinanden.

For at finde ud af, om en grammatik er parset af LL(1) eller ej generelt, er det praktisk at bruge kriteriet for LL(1)-grammatikker [2] .

Beskrivelse af analysatoren

Stakken bruges, hvor antallet af terminaler og ikke-terminaler, input (terminaler) og output (antal regler) flows er placeret.

Først skubbes E, grammatikkens startsymbol, ind på stakken.

Derefter for hvert nyt tegn fra inputstrømmen, indtil den slutter:

hvis der er en terminal i toppen af stakken, og den matcher symbolet på inputstrømmen, så a) pop terminalen ud af stakken og b) forbruge symbolet for inputstrømmen.
hvis der er en terminal i toppen af stakken, og den ikke matcher symbolet på inputstrømmen, så er dette en syntaksfejl "sådant og sådan et symbol var forventet" (det på stakken).
ellers er der en ikke-terminal i toppen af stakken, vi betegner den med A. Alle regler med den på venstre side søges, for hver regel kigges sæt af styresymboler igennem for at finde symbolet for inputtet strøm; den kan ikke vises der mere end én gang, ellers er grammatikken ikke LL(1) parserbar.
hvis symbolet er fundet, så anvendes denne regel: nummeret på reglen udsendes til outputstrømmen, et symbol springes fra stakken (dette er A), og hele højre side af reglen skubbes ind i stedet, symbolet længst til venstre på højre side er det sidste. Inputstream-tegnet forbruges ikke.
ellers blev symbolet slet ikke fundet. Så, hvis der er en regel med formen A → null , så skubbes A fra toppen af stakken. Inputstream-tegnet forbruges ikke.
ellers er det en syntaksfejl, meddelelsen kan udskrives som "en af var forventet" efterfulgt af en liste over sættet First(A) (for sprogets vigtigste ikke-terminaler, f.eks. for ikke- terminal "udtryk", kan du formulere fejlen i form af ikke-terminale navne).

Sprog

Sprog af matematiske formler
Pascal
Python

Se også

LR-parser

Noter

↑ PEP 617 - Ny PEG-parser til CPython | peps.python.org . peps.python.org . Hentet 15. juli 2022. Arkiveret fra originalen 15. juli 2022. (ubestemt)
↑ Kozlov Sergey Valerievich, Svetlakov Alexey Vladimirovich. Om LL(1)-GRAMMATIKKER, ALGORITHMER OM DEM OG METODER TIL DERES ANALYSE I PROGRAMMERING // International Journal of Open Information Technologies. - 2022. - Vol. 10 , nr. 3 . — S. 30–38 . — ISSN 2307-8162 . Arkiveret fra originalen den 18. maj 2022.

Litteratur

Grune, D. og van Reeuwijk, K. og Bal, HE og Jacobs, CJH og Langendoen, K. Modern Compiler Design. - Springer, 2012. - 843 s. — ISBN 9781461446996 .
Mogensen, T. Æ. Introduktion til compilerdesign. - Springer, 2011. - 225 s. — ISBN 9780857298294 .
Mozgovoy, M. Algoritmer, sprog, automater og kompilatorer: en praktisk tilgang. - Jones & Bartlett Learning, 2009. - 345 s. — ISBN 9780763782948 .
Kozlov S. V., Svetlakov A. V. Om LL(1)-grammatikker, algoritmer om dem og metoder til deres analyse 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 .