Syntaktická analýza Flashcards
Aké sú úlohy syntaktickej analýzy?
Číta postupnosť tokenov generovanú lexikálnym analyzátorom a konštruuje strom odvodenia/syntaktický strom
Hlási syntaktické chyby ”inteligentným” spôsobom (zotavenie)
Na akom leveli pracuje syntaktická analýza?
Bezkontextové jazyky
Opíš rozhranie parsera
Aké poznáme 3 metódy syntaktickej analýzy?
Univerzálne - CYK napr., neefektívne
Zhora nadol - LL, z koreňa k listom
Zdola nahor - z listov ku koreňu, pravé krajné, LR
Kedy nastane chyba pri syntaktickej analýze? (parsovaní)
ked’ postupnost’ tokenov nezodpovedá pravidlám gramatiky
Prečo LL a LR metódy vedia chyby detekovať hneď?
Majú vlastnost’ životaschopného prefixu a chyba sa odhalí hned’ ako prefix vstupu nie je prefixom žiadneho slova
Ako sa dajú ošetriť chyby?
Hlásenie chyby - miesto detekovania a chybová hláška
Zotavenie sa z chyby - veľa stratégií, Parser sa pokúša dostat’ do stavu, z ktorého môže
pokračovat’ v spracovávaní vstupu
Je potrebný kompromis
Aký je problém metódy kde sa parser chce dostať do stavu kde môže pokračovať v parsovaní?
zotavenie z jednej chyby spôsobí d’al’šie, riešením môže byt’ konzervatívna stratégia
Aké poznáme stratégie zotavenia sa z chýb?
Zotavenie v móde paniky
Zotavenie na úrovni frázy
Zotavenie pomocou chybových pravidiel
Zotavenie pomocou globálnych korekcií
Opíš Zotavenie na úrovni frázy
Ked’ sa nájde chyba, parser vykoná lokálnu korekciu (Prefix zostávajúceho vstupu sa nahradí iným ret’azcom)
nevýhoda - Je zložité ošetrovat’ chyby, ktoré sa vyskytujú d’aleko pred bodom detekcie
Opíš zotavenie v móde paniky
Zvolí sa množina synchronizaňných tokenov (vzhl’adom na vsupný jazyk)
Pri detekovaní chyby sa vynechá čast’ vstupu až kým sa nenájde synchronizačný token
nevýhoda - vynechá veľkú časť vstupu
Opíš Zotavenie pomocou chybových pravidiel
Rozšírime gramatiku o chybové pravidlá
Z gramatiky skonštruujeme parser, ktorý pri použití chybového pravidla generuje diagnostické hlásenie
Zotavenie pomocou globálnych korekcií
Používajú sa algoritmy pre hl’adanie najvýhodnejšej korekcie (vyžadujúcej minimálnu postupnost’ zmien)
Drahé ale zaujímavé z teoretického hľadiska
Opíš bezkontextové gramatiky
Opíš odvodenie v bezkontextovej gramatike
Čo je to strom odvodenia
Grafická reprezentácia odvodenia, každý vnútorný uzol zodpovedá aplikácii pravidla
Neznázorňuje poradie aplikovania pravidiel
Aká je to nejednoznačná gramatika?
Pre nejaké slovo existujú dva rôzne stromy odvodenia
Čo musíme spraviť aby bola gramatika vhodná na parsovanie v každom pripade?
Eliminácia nejednoznačnosti
Čo musíme spraviť aby bola gramatika vhodná na parsovanie v parsovaní zhora nadol?
Eliminácia l’avej rekurzie
Ľavá faktorizácia
Opíš algoritmy eliminácie ľavej rekurzie
Opíš algoritmus ľavej faktorizácie
Pri parsovaní zhora-nadol sa generuje aké odvodenie?
Ľavé krajné
Opíš algoritmus rekurzívneho zostupu zhora-nadol
Opíš algoritmus prediktívneho parsovania zhora-nadol
Ako skonštruujeme prechodový diagram z gramatiky?
Aký je význam prechodov na prechodových diagramoch?
Prechod na terminál a - Posun na vstupe o jeden znak doprava (prečítaný symbol
musí byt’ a)
Prechod na neterminál A - volanie procedúry pre A
Aké 2 funkcie potrebujeme pre implementáciu prediktívneho parsera?
FIRST(α) - Možina terminálov, ktorými môže začínat’ ret’azec odvodený
z α
FOLLOW (A), A ∈ N - Množina terminálov a, ktoré sa môžu vyskytnút’ hned’ vedl’a
A v nejakej vetnej forme, aj $ ak môže byť A posledný vo vetnej forme
Opíš algoritmus výpočtu FIRST
Opíš výpočet FOLLOW
Opíš implementáciu pomocou rekurzívnych procedúr
slajdy, na konci pvej preze
Opíš implementáciu pomocou zásobníka
slajdy na konci prvej preze
Opíš zotavenie z chýb pri prediktívnom parsovaní
Opíš LL(1) gramatiky
LL(1) je trieda CF gramatík, pre ktorú vieme zostrojit’ prediktívne parsery
L - čítame zľava doprava, L - ľavé krajné odvodenie, 1 - 1 lookahead
Aké CF gramatiky nie sú LL(1)?
Nejednoznačné a l’avorekurzívne gramatiky nie sú LL(1)
Kedy je gramatika LL(1)?
Aká je výhoda parsovanie zhora nadol?
Parsery zhora-nadol sa l’ahšie ručne implementujú ako parsery zdola-nahor
Aká je nevýhoda parsovania zdola nahor?
Gramatika je po úpravách neprehl’adná a t’ažšie sa pre ňu definuje preklad
Ako funguje algoritmus CYK?
Pozri FOJA skriptá
Opíš parsovanie zdola nahor
Pre vstupný ret’azec sa konštruuje strom odvodenia od listov ku koreňu
Hovoríme o redukcii vstupného ret’azca na počiatočný symbol gramatiky
Ciel’om je získat’ pravé krajné odvodenie
Akú metódu používame pri parsovaní zdola nahor?
posun-redukcia (shift-reduce)
Opíš handle a životaschopný prefix
Aké 4 akcie parsera poznáme pri shift-reduce?
shift (posun): vstupné symboly sa ukladajú do zásobníka
reduce (redukcia): ked’ sa na vrchu zásobníka objaví nejaká handle, redukuje sa podl’a príslušného pravidla gramatiky
accept
error
Kde sa objavuje handle?
Vždy na vrchu zásobníka
Aké poznáme konflikty pri shift-reduce?
Čo je to Deterministický shift-reduce parser?
musí sa vediet’ jednoznačne rozhodnút’ pre akciu na základe
1 obsahu zásobníka
2 k symbolov zo vstupu
LR(k) gramatiky - opíš
Umožnujú deterministické spracovanie, nespôsobujú
konflikty
Väčšinou k = 1
Aké 2 typy LR parsovania poznáme?
Operátorovo-precedenňné parsovanie
LR parsovanie
Čo sú LR gramatiky?
Najväčšia trieda gramatík, pre ktorú vieme implementovat’
deterministický shift-reduce parser
Čo sú operátorovo precedenčné gramatiky?
Podmnožina LR gramatík, umožňuje jednoduchú implementáciu shift-reduce parsera
Pravá strana pravidla nemôže byt’ ε
Neterminály na pravej strane pravidla sa nesmú vyskytovat’ priamo vedl’a seba
Opíš precedenčné relácie
Opíš použitie precedenčných relácií
Opíš príklad precedenčných relácií
Opíš parsovací algoritmus s precedenčnými reláciami
Ako vieme určiť precedenčných relácií
Opíš kompresiu precedenčných tabuliek
Opíš algoritmus konštrukcie precedenčných funkcií
Aké poznáme 2 druhy chýb pri parsovaní s precedenčnými reláciami?
Nájde sa neredukovatel’ná handle (neexistuje pre ňu v
gramatike pravidlo)
Prázdne miesto v parsovacej tabul’ke
Ako vieme riešiť chybu s neredukovateľnými handle s precedenčnými reláciami?
“Zlá”handle sa vyberie zo zásobníka
Namiesto redukcie sa vypíše diagnostická správa - určí sa
porovnávaním handle s pravými stranami pravidiel
Ako vieme vyriešiť chybu s prázdnym miestom v parsovacej tabuľke s precedenčnými reláciami?
Vykoná sa lokálna korekcia na vrchu zásobníka alebo vo vstupnom bufferi (vloženie znaku, zmena znaku, zmazanie znaku)
Aké sú výhody operátorovo precedenčného parsovania?
Jednoduchá implementácia efektívneho parsera
Aké sú nevýhody operátorovo precedenčného parsovania?
Ťažko sa narába s tokenmi, ktoré majú viac precedencií
(napr. mínus - môže byt’ unárne aj binárne)
Slabá previazanost’ parsera s gramatikou - niekedy si nie
sme istí, že parser akceptuje práve zdrojový jazyk
Malá množina gramatík
Aké sú 3 techniky konštrukcie LR parsera?
Jednoduchý LR parser (simple LR - SLR) - Najjednoduchší na implementáciu, ale najslabší
Kanonický LR parser (LR) - Najsilnejší, ale najnáročnejší na implementáciu
LR parser s výhl’adom (lookahead LR - LALR) - kompromis
Aké sú výhody LR parsovania?
Umožňuje rozpoznávat’ takmer všetky programovacie
jazyky
Je to najsilnejšia metóda bez backtrackingu pre
shift-reduce parsovanie
Nadmnožina LL gramatík
Aké sú nevýhody LL parsovania?
Náročná implementácia
Ako môze vyzerať model LR parsera?
Čo robia funkcie action a goto?
Opíš konfigurácie LR parsera?
Opíš LR parsovací algoritmus - pseudokód
Opíš rozdiel medzi LL a LR gramatikami
LR - Pravidlo sa rozpoznáva podl’a všetkého, čo sa odvodí z
jeho pravej strany a k symbolov výhl’adu dopredu
LL - Pravidlo sa rozpoznáva podl’a neterminálu na l’avej strane, a k symbolov z toho, čo sa odvodí z jeho pravej strany
Ako funguje SLR - simple LR parsovanie?
Konštruujeme SLR parsovaciu tabul’ku
Dá sa použit’ pre SLR gramatiky
Základnou ideou je skonštruovat’ pre vstupnú gramatiku DKA rozpoznávajúci životaschopné prefixy
Čo je to LR(0) položka?
Pravidlo s bodkou na pravej strane, neformálne - aká veľká časť pravidla je už známa
Aká je to úplná LR(0) položka?
Položka s bodkou na konci pravej strany pravidla
Aká je to platná LR(0) položka a platná pre čo?
Platná pre daný životaschopný prefix
Ako konštruujeme NKA pre parsovanie s LR(0) položkami?
stavy - LR(0) položky
nový neterminál S’ a pravidlo S’ -> S
Počiatočný stav [S’ -> .S]
prechody čítanie znaku alebo keď je neterminál tak prechod na epsilon do počiatočnej položky s daným neterminálom naľavo
Ako zostrojíme DKA pre parsovanie s LR(0) položkami?
Klasicky NKA -> DKA, ale vieme opísať aj pomocou operácií closure a goto a items
Čo robí operácia closure?
epsilonový uzáver stavov v podstate
Aké sú to jadrové a mimojadrové položky v LR(0)?
jadrové - Počiatočná položka [S′ → .S] a všetky položky, ktoré nemajú bodku na začiatku pravej strany.
mimojadrové - Položky, ktoré majú bodku na začiatku pravej strany okrem počiatočnej
Čo robí operácia goto?
Prechodová funkcia
Čo robí operácia items?
vytvára stavy DKA
Aký je význam platnej položky pre životaschopný prefix?
Kedy môžu vzniknúť konflikty pri LR parsovaní?
Shift/reduce: máme dve rôzne platné položky a každá určí inú akciu
Reduce/reduce: máme viac úplných platných položiek
Ako vieme vyriešiť konflikty pri LR parsovaní?
SLR - Použitím funkcie FOLLOW pri akciách reduce
LR, LALR - Rozšírením o výhl’ad v stavoch DKA
Opíš konštrukciu SLR parsovacej tabuľky
Pozri príklad gramatiky mimo SLR
niekde v strede preze
Opíš nevýhodu SLR parsovania ako ju rieši LR(1)
Čo je LR(1) položka?
dvojica LR(0) položka a lookahead
Ako pomôže výhľad v LR(1) pri redukcii?
Kedy je LR(1) položka platná?
Opíš closure a goto pri LR(1)
Opíš items pri LR(1)
Opíš konštrukciu LR parsovacej tabuľky
Čo je to LALR parsovanie?
lookahead LR
Opíš zlučovanie množín položiek
Opíš konštrukciu LALR parsovacej tabuľky
Ako vieme optimalizovať LR parsovaciu tabuľku?
Čo ak máme nejednoznačné gramatiky?
Kedy je detekovaný chyba pri LR parsovaní?
pri prázdnych záznamoch v action tabul’ke (nikdy nie v goto!)
Kedy sú ohlásené chyby pri LR parsovaní?
hned’, ako je to možné
LR parser nevykoná už žiadnu akciu pred ohlásením chyby
SLR a LALR parsery môžu vykonat’ ešte niekol’ko redukcií
Opíš zotavenie LR parsovania v móde paniky
Opíš zotavenie LR na úrovni frázy
Opíš hierarchické vzťahy medzi LL, LR a pod gramatikami
