Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Kompilátory > Syntaktická analýza > Flashcards

Syntaktická analýza Flashcards

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
Q

Ako skonštruujeme prechodový diagram z gramatiky?

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

Aký je význam prechodov na prechodových diagramoch?

A

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

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

Aké 2 funkcie potrebujeme pre implementáciu prediktívneho parsera?

A

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

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

Opíš algoritmus výpočtu FIRST

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

Opíš výpočet FOLLOW

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

Opíš implementáciu pomocou rekurzívnych procedúr

A

slajdy, na konci pvej preze

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

Opíš implementáciu pomocou zásobníka

A

slajdy na konci prvej preze

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

Opíš zotavenie z chýb pri prediktívnom parsovaní

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

Opíš LL(1) gramatiky

A

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

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

Aké CF gramatiky nie sú LL(1)?

A

Nejednoznačné a l’avorekurzívne gramatiky nie sú LL(1)

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

Kedy je gramatika LL(1)?

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

Aká je výhoda parsovanie zhora nadol?

A

Parsery zhora-nadol sa l’ahšie ručne implementujú ako parsery zdola-nahor

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

Aká je nevýhoda parsovania zdola nahor?

A

Gramatika je po úpravách neprehl’adná a t’ažšie sa pre ňu definuje preklad

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

Ako funguje algoritmus CYK?

A

Pozri FOJA skriptá

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

Opíš parsovanie zdola nahor

A

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

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

Akú metódu používame pri parsovaní zdola nahor?

A

posun-redukcia (shift-reduce)

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

Opíš handle a životaschopný prefix

A
42
Q

Aké 4 akcie parsera poznáme pri shift-reduce?

A

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
Q

Kde sa objavuje handle?

A

Vždy na vrchu zásobníka

44
Q

Aké poznáme konflikty pri shift-reduce?

A
45
Q

Čo je to Deterministický shift-reduce parser?

A

musí sa vediet’ jednoznačne rozhodnút’ pre akciu na základe
1 obsahu zásobníka
2 k symbolov zo vstupu

46
Q

LR(k) gramatiky - opíš

A

Umožnujú deterministické spracovanie, nespôsobujú
konflikty
Väčšinou k = 1

47
Q

Aké 2 typy LR parsovania poznáme?

A

Operátorovo-precedenňné parsovanie
LR parsovanie

47
Q

Čo sú LR gramatiky?

A

Najväčšia trieda gramatík, pre ktorú vieme implementovat’
deterministický shift-reduce parser

48
Q

Čo sú operátorovo precedenčné gramatiky?

A

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
Q

Opíš precedenčné relácie

A
50
Q

Opíš použitie precedenčných relácií

A
51
Q

Opíš príklad precedenčných relácií

A
52
Q

Opíš parsovací algoritmus s precedenčnými reláciami

A
53
Q

Ako vieme určiť precedenčných relácií

A
54
Q

Opíš kompresiu precedenčných tabuliek

A
55
Q

Opíš algoritmus konštrukcie precedenčných funkcií

A
56
Q

Aké poznáme 2 druhy chýb pri parsovaní s precedenčnými reláciami?

A

Nájde sa neredukovatel’ná handle (neexistuje pre ňu v
gramatike pravidlo)
Prázdne miesto v parsovacej tabul’ke

57
Q

Ako vieme riešiť chybu s neredukovateľnými handle s precedenčnými reláciami?

A

“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
Q

Ako vieme vyriešiť chybu s prázdnym miestom v parsovacej tabuľke s precedenčnými reláciami?

A

Vykoná sa lokálna korekcia na vrchu zásobníka alebo vo vstupnom bufferi (vloženie znaku, zmena znaku, zmazanie znaku)

59
Q

Aké sú výhody operátorovo precedenčného parsovania?

A

Jednoduchá implementácia efektívneho parsera

60
Q

Aké sú nevýhody operátorovo precedenčného parsovania?

A

Ť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
Q

Aké sú 3 techniky konštrukcie LR parsera?

A

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
Q

Aké sú výhody LR parsovania?

A

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
Q

Aké sú nevýhody LL parsovania?

A

Náročná implementácia

64
Q

Ako môze vyzerať model LR parsera?

A
65
Q

Čo robia funkcie action a goto?

A
66
Q

Opíš konfigurácie LR parsera?

A
67
Q

Opíš LR parsovací algoritmus - pseudokód

A
67
Q

Opíš rozdiel medzi LL a LR gramatikami

A

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
Q

Ako funguje SLR - simple LR parsovanie?

A

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
Q

Čo je to LR(0) položka?

A

Pravidlo s bodkou na pravej strane, neformálne - aká veľká časť pravidla je už známa

69
Q

Aká je to úplná LR(0) položka?

A

Položka s bodkou na konci pravej strany pravidla

70
Q

Aká je to platná LR(0) položka a platná pre čo?

A

Platná pre daný životaschopný prefix

71
Q

Ako konštruujeme NKA pre parsovanie s LR(0) položkami?

A

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
Q

Ako zostrojíme DKA pre parsovanie s LR(0) položkami?

A

Klasicky NKA -> DKA, ale vieme opísať aj pomocou operácií closure a goto a items

73
Q

Čo robí operácia closure?

A

epsilonový uzáver stavov v podstate

74
Q

Aké sú to jadrové a mimojadrové položky v LR(0)?

A

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
Q

Čo robí operácia goto?

A

Prechodová funkcia

76
Q

Čo robí operácia items?

A

vytvára stavy DKA

77
Q

Aký je význam platnej položky pre životaschopný prefix?

A
78
Q

Kedy môžu vzniknúť konflikty pri LR parsovaní?

A

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
Q

Ako vieme vyriešiť konflikty pri LR parsovaní?

A

SLR - Použitím funkcie FOLLOW pri akciách reduce
LR, LALR - Rozšírením o výhl’ad v stavoch DKA

80
Q

Opíš konštrukciu SLR parsovacej tabuľky

A
81
Q

Pozri príklad gramatiky mimo SLR

A

niekde v strede preze

82
Q

Opíš nevýhodu SLR parsovania ako ju rieši LR(1)

A
83
Q

Čo je LR(1) položka?

A

dvojica LR(0) položka a lookahead

84
Q

Ako pomôže výhľad v LR(1) pri redukcii?

A
85
Q

Kedy je LR(1) položka platná?

A
86
Q

Opíš closure a goto pri LR(1)

A
87
Q

Opíš items pri LR(1)

A
88
Q

Opíš konštrukciu LR parsovacej tabuľky

A
89
Q

Čo je to LALR parsovanie?

A

lookahead LR

90
Q

Opíš zlučovanie množín položiek

A
91
Q

Opíš konštrukciu LALR parsovacej tabuľky

A
92
Q

Ako vieme optimalizovať LR parsovaciu tabuľku?

A
93
Q

Čo ak máme nejednoznačné gramatiky?

A
94
Q

Kedy je detekovaný chyba pri LR parsovaní?

A

pri prázdnych záznamoch v action tabul’ke (nikdy nie v goto!)

95
Q

Kedy sú ohlásené chyby pri LR parsovaní?

A

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
Q

Opíš zotavenie LR parsovania v móde paniky

A
97
Q

Opíš zotavenie LR na úrovni frázy

A
98
Q

Opíš hierarchické vzťahy medzi LL, LR a pod gramatikami

A

Kompilátory (9 decks)

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