Difference between revisions of "Programovací jazyky a překladače"

Latest revision as of 16:51, 2 October 2012

[edit] Otázky

Následující seznam otázek shnuje mou představu o tom, co je z okruhu Programovací jazyky a překladače ke státnicím potřeba umět. Tato představa nebyla konzultována s vyučujícím(i).

[edit] Struktura kompilátoru a navazujících nástrojů (linkery, loadery, debuggery, knihovny, preprocesory)

• schéma překladače
• popis linkeru
• popis loaderu (Unix, Windows)
• statické knihovny, dynamické knihovny, implmentace
• popis C preprocesoru

[edit] Konečné automaty a lexikální analýza

• úkol lexikální analýzy
• výstup lexikální analýzy, varianty, problémy
• typické způsoby implementace
• lex, flex

[edit] Syntaktická analýza - LL, LR techniky

• úkol syntaktické analýzy
• výstup syntaktické analýzy (vč. možností při analýze shora dolů a zdola nahoru)
• pojmy: gramatika, bezkontextová gramatika, derivace, levá/pravá derivace
• definice: FIRST a FOLLOW
• analýza shora dolů, vztah s LL, definice a popis LL, pojmy rozepsání a krácení
• rozdíly mezi slabou a silnou LL
• implementace analýzy shora dolů rekurzivním sestupem
• analýza zdola nahoru, vztah s LR, definice a popis LR, pojmy shift a reduction
• rozdíly mezi LR, SLR a LALR
• konstrukce LR, SLR a LALR automatu
• yacc, bison
• gramatiky s regulární pravou stranou

[edit] Syntaxí řízený překlad a atributové gramatiky

• derivační strom vs. AST
• definice: AG, Attr, Syn, Inh, normální forma, atributový výskyt, In, Out Popis
• definice: acyklické AG, k-průchodové AG, jednoduše k-průchodové AG, zleva-doprava k-průchodové AG, jednoduše zleva-doprava k-průchodové AG
• algoritmus konstrukce průchodů jednoduše zleva-doprava k-průchodovou AG

[edit] Reprezentace programu mezikódem

• důvody reprezentace mezikódem
• pojem základní blok
• formáty mezikódu: sekvenční (2-adresový, 3-adresový (trojice, čtveřice), prefixová/postfixová notace), graf základních bloků, strom, DAG
• operandy mezikódu
• SSA
• funkce φ u trojic a SSA
• generování mezikódu (použití AG, zisk z proházení operací, problém LHS a RHS u přiřazení a jeho řešení, synchronizace u DAGů)

[edit] Překlad výrazů a programových struktur

• preklad programove struktur - control-flow, tedy if/when/for/goto pripadne try/catch
• vyrazy - zakladni princip vyhodnocovani, CSE, eventualne eliminace duplicitnich read/write operaci.

[edit] Rozsahy platnosti proměnných, aktivační záznamy, implementace vnořených procedur, volací konvence

• obsah aktivačního záznamu
• způsoby implementace vnořených procedur (odkaz na všechny záznamy, odkaz na předchozí záznam, displej) a jejich vlastnosti (režie volání, přístupu k proměnným a prostorová náročnost)
• implementace procedurálních parametrů v Pascalu
• volací konvence: co vše zahrnují (registry vs. zásobník, zachovávání registrů, pořadí předávání parametrů, návratová hodnota, úklid zásobníku)
• popis cdecl, stdcall, fastcall

[edit] Vliv architektury počítače na generování kódu a optimalizaci

[edit] Zdroje

• Wikipedia: Microarchitecture

[edit] Obsah otázky

• registry (počet, typy, způsob přístupu, (ne)ortogonalita)
• instrukční sada (RISC, CISC, (ne)ortogonalita)
• pipelining
• superskalarita
• out-of-order execution
• spekulativní vykonávání instrukcí
• SIMD
• práce s pamětí (heap, stack), zarovnávání

[edit] Metody generování kódu, přidělování registrů, optimalizace

[edit] Zdroje

• Wikipedia: Category: Compiler optimizations

[edit] Obsah otázky

• klasifikace základních bloků podle rozsahu platnosti, výpočet liveBegin a liveEnd, určení kolizí
• výběr a uspořádání instrukcí (1:1, 1:n, m:1, m:n), pojem generator-generator, řazení instrukcí
• objekty umisťované do registrů
• algoritmus obarvování grafu
• optimalizace: důvody, čas vs. prostor, úroveň, požadované vlastnosti
• druhy optimalizací: lokální, globální, v rámci programu
• lokální optimalizace: CSE, copy propagation, dead-code elimination, constant folding, algebraické operace
• globální optimalizace: CSE, copy propagation, dead-code elimination, optimalizace cyklů (přesun invariantního kódu, redukce síly operace, odstranění indukční proměnné)
• paralelizace a vektorizace
• profilem řízená optimalizace
• scheduling (ma Bednarek ve slidech)

[edit] Podpora kompilátorů pro synchronizační primitiva, vlákna

[edit] Zdroje

• Using wait(), notify() and notifyAll()
• Thread Local Storage

[edit] Obsah otázky

• Java: kritické sekce, monitory (synchronized), wait, notify
• Java: vytvoření vlákna, paměťový model, TLS, podpora v knihovnách (thread (un)safe)
• volatile proměnné
• podpora knihovnami při absenci podpory kompilátoru

[edit] Objektově orientované jazyky a principy jejich implementace

[edit] Zdroje

• Memory Layout for Multiple and Virtual Inheritance
• Compilation of object oriented languages
• C++ Vtable Examples

[edit] Obsah otázky

• principy OO: zapouzdření, dědičnost a polymorfismus
• class-based languages vs. prototype-based languages
• OO podle Smalltalk: zasílání zpráv
• implementace dědičnosti: tabulka virtuálních funkcí, volání virtuálních funkcí, princip pozdní vazby, layout objektů při jednonásobné a vícenásobné dědičnosti, diamond problem, virtuální dědičnost, RTTI a jeho implementace (typeid, dynamic_cast)
• vtable obsahuje: pointer na nadrazenou tridu, adresy metod, (pri virtualni dedicnosti) offset k datum virtualne dedene tridy, (pri RTTI) pointer na type information strukturu

[edit] Překladače vs. interpretry, skriptovací jazyky

• rozdíly mezi překladačem a interpretrem
• výhody/nevýhody překladačů a interpretrů
• typické příklady použití překladačů a interpretrů
• bytecode, virtuální stroj (zásobník vs. registry), JIT, příklady (Java, Lua)
• optimalizační techniky u interpreterů: method caching, direct threading, value tagging
• typické vlastnosti skriptovacích jazyků (dynamické typování, reflexivita, dynamičnost)
• typické použití skriptovacích jazyků (skripty, web,...), důvody

[edit] Materiály

• Web předmětu Principy překladačů
• Web předmětu Konstrukce překladačů