LL(1)
Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de
versiunea revizuită la 3 iulie 2020; verificările necesită
5 modificări .
LL(1) - LL parser , algoritm de parsare de sus în jos . Numărul 1 spune că este nevoie de un singur simbol pentru a defini calea de analiză .
Ușor de scris de mână fără utilizarea generatoarelor automate. Folosit pentru a analiza codul într-un număr de limbaje de programare, cum ar fi Pascal și Python (înainte de 3.8 [1] ).
Este foarte rapid în execuție și are un mesaj de eroare caracteristic de genul „se aștepta un astfel de personaj”.
Caracterele ghidului de reguli
Pentru fiecare non -terminal A din gramatică , este generat un set de terminale First(A), definite după cum urmează:
- dacă gramatica are o regulă cu un A pe partea stângă și o parte dreaptă care începe cu un terminal, atunci acel terminal este în primul (A)
- dacă gramatica are o regulă cu un A pe partea stângă și o parte dreaptă care începe cu un non-terminal (notat B), atunci First (B) este strict inclus în First (A)
- nu sunt incluse alte terminale în First(A)
Pentru fiecare regulă, este generat un set de caractere ghid , definite după cum urmează:
- dacă partea dreaptă a regulii începe cu un terminal, atunci setul de caractere ghid este format din acel terminal
- în caz contrar, partea dreaptă începe cu un A non-terminal, apoi setul de caractere principale este First(A)
Este posibilă generalizarea acestor definiții pentru cazul în care există reguli de forma A → null.
Este clar că First(A) este uniunea setului de simboluri principale pentru toate regulile cu A în partea stângă.
O gramatică este analizabilă LL(1) dacă, pentru orice pereche de reguli cu aceeași parte stângă, setul de caractere ghid nu se intersectează.
Pentru a afla dacă o gramatică este analizată de LL(1) sau nu în general, este convenabil să folosiți criteriul LL(1)-gramatici [2] .
Descrierea analizorului
Se folosește stiva, unde se află numărul de terminale și non-terminale, fluxurile de intrare (terminale) și de ieșire (număr de reguli).
Mai întâi, E, simbolul de început al gramaticii, este împins pe stivă.
Apoi, pentru fiecare caracter nou din fluxul de intrare până la sfârșit:
- dacă există un terminal în partea de sus a stivei și se potrivește cu simbolul fluxului de intrare, atunci a) scoateți terminalul din stivă și b) consumați simbolul fluxului de intrare.
- dacă există un terminal în partea de sus a stivei și nu se potrivește cu simbolul fluxului de intrare, atunci aceasta este o eroare de sintaxă „s-a așteptat un astfel de simbol” (cel de pe stivă).
- în caz contrar, există un non-terminal în partea de sus a stivei, îl notăm cu A. Se caută toate regulile cu acesta în partea stângă, pentru fiecare regulă, se caută seturi de simboluri de direcție pentru a găsi simbolul intrării curent; nu poate apărea acolo de mai multe ori, altfel gramatica nu este analizabilă LL(1).
- dacă simbolul este găsit, atunci se aplică această regulă: numărul regulii este scos în fluxul de ieșire, un simbol este scos din stivă (acesta este A) și toată partea dreaptă a regulii este împinsă în loc, cel mai din stânga simbol al părții drepte este ultimul. Caracterul fluxului de intrare nu este consumat.
- altfel simbolul nu a fost găsit deloc. Apoi, dacă există o regulă de forma A → null , atunci A este împins din partea de sus a stivei. Caracterul fluxului de intrare nu este consumat.
- în caz contrar, este o eroare de sintaxă, mesajul poate fi scos ca „unul dintre a fost așteptat” urmat de o listă cu setul First(A) (pentru cele mai importante non-terminale ale limbii, de exemplu, pentru non-terminale). „expresie” terminală, puteți formula eroarea în termeni de nume non-terminale).
Limbi
Vezi și
Note
- ↑ PEP 617 - Nou analizator PEG pentru CPython | peps.python.org . peps.python.org . Preluat la 15 iulie 2022. Arhivat din original la 15 iulie 2022. (nedefinit)
- ↑ Kozlov Serghei Valerievici, Svetlakov Alexey Vladimirovici. Despre LL(1)-GRAMATE, ALGORITMI ASUPRA LOR ŞI METODE DE ANALIZA LOR ÎN PROGRAMARE // International Journal of Open Information Technologies. - 2022. - Vol. 10 , nr. 3 . — S. 30–38 . — ISSN 2307-8162 . Arhivat din original pe 18 mai 2022.
Literatură
- Grune, D. și van Reeuwijk, K. și Bal, HE și Jacobs, CJH și Langendoen, K. Modern Compiler Design. - Springer, 2012. - 843 p. — ISBN 9781461446996 .
- Mogensen, T. Æ. Introducere în proiectarea compilatorului. - Springer, 2011. - 225 p. — ISBN 9780857298294 .
- Mozgovoy, M. Algoritmi, limbi, automate și compilatori: o abordare practică. - Jones & Bartlett Learning, 2009. - 345 p. — ISBN 9780763782948 .
- Kozlov S. V., Svetlakov A. V. Despre LL(1)-gramatici, algoritmi pe ele și metode de analiză a acestora în programare — 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 .
Link -uri