LL(1)
Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od
verze recenzované 3. července 2020; kontroly vyžadují
5 úprav .
LL(1) - LL parser , algoritmus analýzy shora dolů . Číslo 1 říká, že k definování cesty analýzy je potřeba pouze jeden token .
Snadné ruční psaní bez použití automatických generátorů. Používá se k analýze kódu v řadě programovacích jazyků , jako je Pascal a Python (před 3.8 [1] ).
Je velmi rychlý v provádění a má charakteristickou chybovou hlášku jako "takový a takový znak se očekával."
Znaky průvodce pravidly
Pro každý neterminál A v gramatice se vygeneruje sada terminálů First(A), která je definována takto:
- pokud má gramatika pravidlo s A na levé straně a pravou stranou začínající terminálem, pak je tento terminál v First(A)
- pokud má gramatika pravidlo s A na levé straně a pravou stranou začínající neterminálem (označeno B), pak First(B) je přísně zahrnuto do First(A)
- v First(A) nejsou zahrnuty žádné další terminály
Pro každé pravidlo se vygeneruje sada vodících znaků definovaných takto:
- pokud pravá strana pravidla začíná terminálem, pak se sada vodících znaků skládá z tohoto jednoho terminálu
- v opačném případě pravá strana začíná nekoncovým A, potom je sada vedoucích znaků První(A)
Tyto definice je možné zobecnit pro případ, kdy existují pravidla formuláře A → null.
Je jasné, že First(A) je spojením sad vedoucích symbolů pro všechna pravidla s A na levé straně.
Gramatika je LL(1) parsovatelná , pokud se pro žádnou dvojici pravidel se stejnou levou stranou množina vodících znaků neprotíná.
Pro zjištění, zda je gramatika analyzována pomocí LL(1) nebo ne obecně, je vhodné použít kritérium LL(1)-gramatiky [2] .
Popis analyzátoru
Používá se zásobník, kde jsou umístěna čísla terminálů a neterminálů, vstupní (terminály) a výstupní (čísla pravidel) toky.
Nejprve se na hromádku vloží E, počáteční symbol gramatiky.
Poté pro každý nový znak ze vstupního proudu až do konce:
- pokud je na vrcholu zásobníku terminál a odpovídá symbolu vstupního toku, pak a) vytáhne terminál ze zásobníku ab) spotřebuje symbol vstupního toku.
- pokud je v horní části zásobníku terminál a neodpovídá symbolu vstupního toku, jedná se o chybu syntaxe „byl očekáván takový a takový symbol“ (ten na zásobníku).
- jinak je v horní části zásobníku neterminál, označíme ho A. Prohledají se všechna pravidla s ním na levé straně, pro každé pravidlo se prohlédnou sady směrovacích symbolů, aby se našel symbol vstupu proud; nemůže se tam objevit více než jednou, jinak není gramatika LL(1) parsovatelná.
- pokud je symbol nalezen, použije se toto pravidlo: číslo pravidla se odešle do výstupního proudu, ze zásobníku se vyskočí jeden symbol (toto je A) a místo toho se vloží celá pravá strana pravidla, symbol nejvíce vlevo na pravé straně je poslední. Znak vstupního proudu není spotřebován.
- jinak symbol nebyl vůbec nalezen. Pak, pokud existuje pravidlo formuláře A → null , je A vytlačeno z horní části zásobníku. Znak vstupního proudu není spotřebován.
- v opačném případě se jedná o chybu syntaxe, zpráva může být vydána jako "jeden z byl očekáván" následovaný seznamem množiny First(A) (pro nejdůležitější neterminály jazyka, např. terminálový "výraz", můžete chybu formulovat z hlediska neterminálních jmen).
Jazyky
Viz také
Poznámky
- ↑ PEP 617 – Nový PEG parser pro CPython | peps.python.org . peps.python.org . Získáno 15. července 2022. Archivováno z originálu dne 15. července 2022. (neurčitý)
- ↑ Kozlov Sergej Valerijevič, Světlakov Alexej Vladimirovič. O LL(1)-GRAMATIKÁCH, ALGORITECH NA NICH A METODÁCH JEJICH ANALÝZY V PROGRAMOVÁNÍ // International Journal of Open Information Technologies. - 2022. - Svazek 10 , č. 3 . — S. 30–38 . — ISSN 2307-8162 . Archivováno z originálu 18. května 2022.
Literatura
- Grune, D. a van Reeuwijk, K. a Bal, HE a Jacobs, CJH a Langendoen, K. Modern Compiler Design. - Springer, 2012. - 843 s. — ISBN 9781461446996 .
- Mogensen, T. Æ. Úvod do návrhu překladačů. - Springer, 2011. - 225 s. — ISBN 9780857298294 .
- Mozgovoy, M. Algoritmy, jazyky, automaty a kompilátory: Praktický přístup. - Jones & Bartlett Learning, 2009. - 345 s. — ISBN 9780763782948 .
- Kozlov S. V., Svetlakov A. V. O LL(1)-gramatikách, algoritmech na nich a metodách jejich analýzy v programování — International Journal of Open Information Technologies. - 2022. - T. 10. - č. 3. - S. 30-38. — URL: https://cyberleninka.ru/article/n/o-ll-1-grammatikah-algoritmah-na-nih-i-metodah-ih-analiza-v-programmirovanii .
Odkazy