FJP

Question 1

Jaké jsou důvody pro použití víceprůchodového překladače?

Answer 1

• Překlad probíhá ve více fázích – dříve kvůli paměti – jen jedna část překladače je v paměti.
• Snadněji jde rozdělit práci na překladači mezi více programátorů
• Algoritmy pro optimalizaci jsou často složité – mají proto vlastní průchod, často i více průchodů.
• zajímají nás meziprodukty – mezipřeklady:

1. Průchod -> 1. meziprodukt -> … -> n. průchod -> Finální produkt
   - lze optimalizovat překládaný program – kvůli dopředným skokům

Question 2

Jaká vlastnost gramatiky podmiňuje nekonečnost generovaného jazyka

Answer 2

Rekurzivnost, cyklus v gramatice. Např.: A -> aA

Question 3

Jak řeší lexikální analyzátory problém nalezení symbolu v případě, kdy je jeden symbol prefixem druhého?

Answer 3

Testuje další znaky na výskyt v jiném delším symbolu. Hledá nejdelší možný symbol.

Question 4

Kdy označujeme větu jazyka jako víceznačnou

Answer 4

Věta generovaná gramatikou G je víceznačná, existují-li alespoň dva různé derivační stromy této věty. G pak rovněž nazýváme víceznačnou.

Question 5

Jaké vlastnosti musí splňovat jazyk analyzovatelný rekurzivním sestupem

Answer 5

Musí splňovat vlastnosti LL gramatik, nesmí obsahovat levou rekurzi.

Question 6

Popište princip metody rekurzivního sestupu

Answer 6

Derivační strom je budován postupným voláváním procedur odpovídajících jednotlivým neterminálům gramatiky a jejich prováděním. Tělo procedury určují pravé strany pravidel pro daný neterminální symbol. Pravé strany musí být rozlišitelné na základě symbolů vstupního řetězce aktuálních v okamžiku uplatnění příslušné pravé strany.

Question 7

Charakterizujte syntetizované atributy

Answer 7

Atributy vyhodnocované průchodem derivačního stromu zdola nahoru nazýváme syntetizované

Question 8

Popište způsob vyhodnocování dědičných atributů

Answer 8

Atributy vyhodnocované průchodem derivačního stromu shora dolů nazýváme dědičné.

Question 9

Popište zásady konstrukce postfixového výrazu z infixového

Answer 9

Vytvoříme derivační strom výrazu a poté jej vypíšeme metodou postorder. Nebo lze vytvořit pomocí zachování pořadí operandů, operátory následují za operandy.

Question 10

Popište význam částí dynamické adresy (adresové dvojice)

Answer 10

Adresová dvojice se skládá z Báze, která určuje hloubku zanoření aktuálního bloku ve vykonávaném programu) + offset (posun od začátku bloku/adres v daném bloku)

Question 11

Formulujte podmínku, kterou musí splňovat program, aby statický řetězec výpočtového zásobníku stále splýval s dynamickým řetězcem

Answer 11

Podprogramy mohou volat pouze podprogramy, které jsou v dané úrovni deklarované, žádná rekurzivní volání.

Question 12

Jaké informace o proměnných jsou uloženy v tabulce symbolů překladače jazyka pascalského typu

Answer 12

• druh (návěští, konstanta, typ, proměnná, procedura, funkce)
• hladina popisu (udává hladinu bloku, ve kterém byla popsána)
• adresa
• použití (Ano/Ne)
• typ – údaj o standardním jednoduchém typu
• údaj o typu definovaném uživatelem
• údaj o strukturovaném typu
• formální parametr
• druhy formálních parametrů
• způsob volání a hodnota

Question 13

Popište odlišnost zpřístupnění nelokálních proměnných Pascalu a C

Answer 13

V C nelze definovat vnořené procedury, všechny proměnné jsou buď lokální, nebo globální.
V Pascalu lze definovat libovolně vnořené procedury, v nejnižší proceduře jsou přístupné proměnné všech nadřazených procedur.

Question 14

Uveďte, jaké údaje ukládá překladač v aktivačním záznamu

Answer 14

návratová adresa, statický a dynamický ukazatel, další potřebné informace k uspořádání aktivačních záznamů.

Question 15

Vysvětlete, jakým mechanismem překladač zajišťuje respektování lokality identifikátorů v blokově strukturovaném jazyce.

Answer 15

Tabulka symbolů je uspořádána do podoby zásobníku (pro jazyky s blokovou strukturou). Rozsahová jednotka je blok, modul, funkce, balík,…

Question 16

Může pro víceznačnou gramatiku existovat ekvivalentní gramatika jednoznačná?

Answer 16

Ano může, ale nemusí. Jednoznačnost gramatik je algoritmicky nerozhodnutelná (důvodů může být nekonečně mnoho). Existují gramatiky, jejichž nejednoznačnost nelze odstranit (inherentně nejednoznačné).

Question 17

Existuje pro libovolnou gramatiku typu 2 algoritmus pro převod na a)ekvivalentní nelevorekurzivní gramatiku, b) LL(k) gram., c)LR(k) gram., d) …pro výpočet množin LR(0) položek?

Answer 17

a) Ano – Známe algoritmus pro odstranění levé rekurze, b) Ne, c) Ano, d) Ano

Question 18

Jaké podmínky musí splňovat množiny LR(0) položek, aby gramatika byla SLR(1)

Answer 18

X -> a . - provedu, pokud následující symbol je prvkem follow(x)
X -> a . B - provedu, pokud následující symbol patří do first(B)
Pokud je tam kolize v jedné množině, tečka na konci a v jiném pravidle tečka někde jinde (uprostřed, na začátku) pak není SLR(1).

Question 19

K čemu slouží úprava gramatiky zvaná “pohlcení terminálu”? Uveďte příklad

Answer 19

K odstraněni first-follow či first-first kolize. Př.: Převeďte G(N, T, P, A) na LL(1):
A  BaC
B  e | abC
C  c | cBC
Pro odstranění použijeme pohlcení follow symbolu:

A –> [Ba]C
[Ba] –> a | abCa
B –> e | abC
C –> c | cBC

Question 20

Popište mechanismus zpracování statických metod

Answer 20

c . f() překlad volání f závisí na typu objektové proměnné c
překladač vyhledá třídu C objektu c
v C hledá metodu f, když jí nenajde, hledá jí v rodiči C…
pokud program není chybný, v nějakém předkovi jí najde
volání se přeloží do skoku na její vstupní bod.

Question 21

Popište mechanismus zpracování dynamických metod

Answer 21

Mohou být překryty ve třídě potomka.
V době překladu nelze určit zda se jedná o metodu předka či potomka.
Řešení:
Deskriptor třídy musí obsahovat vektor s metodami pro každé ze jmen nestatických metod (VMT).
Když třída P dědí z R, pak VMT pro P začíná se vstupními body všech metod platných pro R a pokračuje s novými metodami zavedenými v P.
Pokud třída PPP překryje metodu R_f, bude na místě R_f ve VMT pro PPP adresa PPP_f.
Při exekuci pp.f () musí přeložený kód provést
1. Zjistit deskriptor třídy objektu na který ukazuje pp,
2. Z něj zjistit adresu vstupního bodu metody f
3. Skok do podprogramu na adresu tohoto vstupního bodu