Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Kompilátory > Syntaktická analýza > Flashcards

Syntaktická analýza Flashcards

(101 cards)

Start Studying
1
Q

Aké sú úlohy syntaktickej analýzy?

A

Číta postupnosť tokenov generovanú lexikálnym analyzátorom a konštruuje strom odvodenia/syntaktický strom
Hlási syntaktické chyby ”inteligentným” spôsobom (zotavenie)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Na akom leveli pracuje syntaktická analýza?

A

Bezkontextové jazyky

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Opíš rozhranie parsera

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Aké poznáme 3 metódy syntaktickej analýzy?

A

Univerzálne - CYK napr., neefektívne
Zhora nadol - LL, z koreňa k listom
Zdola nahor - z listov ku koreňu, pravé krajné, LR

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Kedy nastane chyba pri syntaktickej analýze? (parsovaní)

A

ked’ postupnost’ tokenov nezodpovedá pravidlám gramatiky

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Prečo LL a LR metódy vedia chyby detekovať hneď?

A

Majú vlastnost’ životaschopného prefixu a chyba sa odhalí hned’ ako prefix vstupu nie je prefixom žiadneho slova

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Ako sa dajú ošetriť chyby?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Aký je problém metódy kde sa parser chce dostať do stavu kde môže pokračovať v parsovaní?

A

zotavenie z jednej chyby spôsobí d’al’šie, riešením môže byt’ konzervatívna stratégia

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Aké poznáme stratégie zotavenia sa z chýb?

A

Zotavenie v móde paniky
Zotavenie na úrovni frázy
Zotavenie pomocou chybových pravidiel
Zotavenie pomocou globálnych korekcií

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Opíš Zotavenie na úrovni frázy

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Opíš zotavenie v móde paniky

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Opíš Zotavenie pomocou chybových pravidiel

A

Rozšírime gramatiku o chybové pravidlá
Z gramatiky skonštruujeme parser, ktorý pri použití chybového pravidla generuje diagnostické hlásenie

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Zotavenie pomocou globálnych korekcií

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Opíš bezkontextové gramatiky

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Opíš odvodenie v bezkontextovej gramatike

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Čo je to strom odvodenia

A

Grafická reprezentácia odvodenia, každý vnútorný uzol zodpovedá aplikácii pravidla
Neznázorňuje poradie aplikovania pravidiel

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Aká je to nejednoznačná gramatika?

A

Pre nejaké slovo existujú dva rôzne stromy odvodenia

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Čo musíme spraviť aby bola gramatika vhodná na parsovanie v každom pripade?

A

Eliminácia nejednoznačnosti

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Čo musíme spraviť aby bola gramatika vhodná na parsovanie v parsovaní zhora nadol?

A

Eliminácia l’avej rekurzie
Ľavá faktorizácia

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Opíš algoritmy eliminácie ľavej rekurzie

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Opíš algoritmus ľavej faktorizácie

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Pri parsovaní zhora-nadol sa generuje aké odvodenie?

A

Ľavé krajné

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Opíš algoritmus rekurzívneho zostupu zhora-nadol

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Opíš algoritmus prediktívneho parsovania zhora-nadol

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Ako skonštruujeme prechodový diagram z gramatiky?
26
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
27
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
28
Opíš algoritmus výpočtu FIRST
29
Opíš výpočet FOLLOW
30
Opíš implementáciu pomocou rekurzívnych procedúr
slajdy, na konci pvej preze
31
Opíš implementáciu pomocou zásobníka
slajdy na konci prvej preze
32
Opíš zotavenie z chýb pri prediktívnom parsovaní
33
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
34
Aké CF gramatiky nie sú LL(1)?
Nejednoznačné a l’avorekurzívne gramatiky nie sú LL(1)
35
Kedy je gramatika LL(1)?
36
Aká je výhoda parsovanie zhora nadol?
Parsery zhora-nadol sa l’ahšie ručne implementujú ako parsery zdola-nahor
37
Aká je nevýhoda parsovania zdola nahor?
Gramatika je po úpravách neprehl’adná a t’ažšie sa pre ňu definuje preklad
38
Ako funguje algoritmus CYK?
Pozri FOJA skriptá
39
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
40
Akú metódu používame pri parsovaní zdola nahor?
posun-redukcia (shift-reduce)
41
Opíš handle a životaschopný prefix
42
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
43
Kde sa objavuje handle?
Vždy na vrchu zásobníka
44
Aké poznáme konflikty pri shift-reduce?
45
Č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
46
LR(k) gramatiky - opíš
Umožnujú deterministické spracovanie, nespôsobujú konflikty Väčšinou k = 1
47
Aké 2 typy LR parsovania poznáme?
Operátorovo-precedenňné parsovanie LR parsovanie
47
Čo sú LR gramatiky?
Najväčšia trieda gramatík, pre ktorú vieme implementovat’ deterministický shift-reduce parser
48
Č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
49
Opíš precedenčné relácie
50
Opíš použitie precedenčných relácií
51
Opíš príklad precedenčných relácií
52
Opíš parsovací algoritmus s precedenčnými reláciami
53
Ako vieme určiť precedenčných relácií
54
Opíš kompresiu precedenčných tabuliek
55
Opíš algoritmus konštrukcie precedenčných funkcií
56
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
57
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
58
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)
59
Aké sú výhody operátorovo precedenčného parsovania?
Jednoduchá implementácia efektívneho parsera
60
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
61
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
62
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
63
Aké sú nevýhody LL parsovania?
Náročná implementácia
64
Ako môze vyzerať model LR parsera?
65
Čo robia funkcie action a goto?
66
Opíš konfigurácie LR parsera?
67
Opíš LR parsovací algoritmus - pseudokód
67
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
67
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
68
Čo je to LR(0) položka?
Pravidlo s bodkou na pravej strane, neformálne - aká veľká časť pravidla je už známa
69
Aká je to úplná LR(0) položka?
Položka s bodkou na konci pravej strany pravidla
70
Aká je to platná LR(0) položka a platná pre čo?
Platná pre daný životaschopný prefix
71
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
72
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
73
Čo robí operácia closure?
epsilonový uzáver stavov v podstate
74
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
75
Čo robí operácia goto?
Prechodová funkcia
76
Čo robí operácia items?
vytvára stavy DKA
77
Aký je význam platnej položky pre životaschopný prefix?
78
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
79
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
80
Opíš konštrukciu SLR parsovacej tabuľky
81
Pozri príklad gramatiky mimo SLR
niekde v strede preze
82
Opíš nevýhodu SLR parsovania ako ju rieši LR(1)
83
Čo je LR(1) položka?
dvojica LR(0) položka a lookahead
84
Ako pomôže výhľad v LR(1) pri redukcii?
85
Kedy je LR(1) položka platná?
86
Opíš closure a goto pri LR(1)
87
Opíš items pri LR(1)
88
Opíš konštrukciu LR parsovacej tabuľky
89
Čo je to LALR parsovanie?
lookahead LR
90
Opíš zlučovanie množín položiek
91
Opíš konštrukciu LALR parsovacej tabuľky
92
Ako vieme optimalizovať LR parsovaciu tabuľku?
93
Čo ak máme nejednoznačné gramatiky?
94
Kedy je detekovaný chyba pri LR parsovaní?
pri prázdnych záznamoch v action tabul’ke (nikdy nie v goto!)
95
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í
96
Opíš zotavenie LR parsovania v móde paniky
97
Opíš zotavenie LR na úrovni frázy
98
Opíš hierarchické vzťahy medzi LL, LR a pod gramatikami

Kompilátory (9 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions