Programovací jazyky a překladače

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

Otázky[editovat | editovat zdroj]

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).

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

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

Konečné automaty a lexikální analýza[editovat | editovat zdroj]

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

Syntaktická analýza - LL, LR techniky[editovat | editovat zdroj]

  • ú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

Syntaxí řízený překlad a atributové gramatiky[editovat | editovat zdroj]

  • 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

Reprezentace programu mezikódem[editovat | editovat zdroj]

  • 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ů)

Překlad výrazů a programových struktur[editovat | editovat zdroj]

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

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

  • 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

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

Zdroje[editovat | editovat zdroj]

Obsah otázky[editovat | editovat zdroj]

  • 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í

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

Zdroje[editovat | editovat zdroj]

Obsah otázky[editovat | editovat zdroj]

  • 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)

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

Zdroje[editovat | editovat zdroj]

Obsah otázky[editovat | editovat zdroj]

  • 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

Objektově orientované jazyky a principy jejich implementace[editovat | editovat zdroj]

Zdroje[editovat | editovat zdroj]

Obsah otázky[editovat | editovat zdroj]

  • 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

Překladače vs. interpretry, skriptovací jazyky[editovat | editovat zdroj]

  • 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

Materiály[editovat | editovat zdroj]