Témata ke zkoušce z předmětu Programovací jazyky a překladače

Programovací jazyky - obecná otázka - 13 bodů

Popište, co to je paradigma programování. Jaký je jeho vztah k programovacím jazykům. Stručně charakterizujte tři existující paradigmata programování.
Čím se vyznačují imperativní programovací jazyky? Co je odlišuje od deklarativních programovacích jazyků? Uveďte tři příklady imperativních programovacích jazyků.
Čím se vyznačují deklarativní programovací jazyky? Co je odlišuje od imperativních programovacích jazyků? Uveďte tři příklady deklarativních programovacích jazyků.
Čím se vyznačují obektově orientované programovací jazyky? Na jakých základních principech jsou postaveny? Uveďte tři přiklady objektově orientovaných programovacích jazyků.
Čím se vyznačují vyšší programovací jazyky? V kterých oblastech se zásadně liší od strojově orientovaných programovacích jazyků?
Co popisuje syntaxe a co sémantika programovacího jazyka? Ukažte na příkladech. Jaké metody se používají k popisu syntaxe a jaké k popisu sémantiky?
Čím se vyznačují skriptovací programovací jazyky? Jaké jsou typické oblasti, ve kterých se používají? Uveďtě tři příklady skriptovacích jazyků.
Co to je typový systém? Jaké funkce typicky zajišťuje?
Jaký je rozdíl mezi staticky a dynamicky typovanými programovacími jazyky? Uveďte příklad konkrétních jazyků z obou kategorií.
Charakterizujte rozdíly mezi silně a slabě typovanými programovacími jazyka. Demonstrujte na příkladě.

Programovací jazyky - konkrétní otázka - 7 bodů

Čím se vyznačují logické programovací jazyky? Uveďte nějakého zástupce rodiny logických programovacích jazyků.
Co to je Backus-Naur Form (BNF) a k čemu se používá? Demonstrujte na příkladě!
Co to je lambda kalkul a jaký je jeho vztah k funkcionálním programovacím jazykům?
Co to je Extended Backus-Naur Form (EBNF) a k čemu se používá? Demonstrujte na příkladě!
Co to je líne vyhodnocování (lazy evaluation) programu? Čím se vyznačuje a jaké výhody přináší?
Co znamená, že programovací jazyk je typově bezpečný? Demonstrujte na konkrétním příkladě.

Překladače - obecná otázka - 13 bodů

Popište, jakými formálními prostředky a metodami se popisuje lexikální a syntaktická struktura programovacího jazyka.
Vysvětlete pojem atributová překladová gramatika, uveďte, k čemu slouží, a popište pravidla, jimiž se řídí předávání jednotlivých druhů atributů.
Nakreslete schéma překladače s vyznačením jednotlivých logických fází překladu. Popište jednou větou funkci jednotlivých fází, uveďte formu dat na jejich vstupu a výstupu a u kaľdé z nich určete typické chyby, které v nich můľe překladač hlásit.
Popište činnost a strukturu jak kompilačního tak interpretačního překladače. Popište výhody a nevýhody jednotlivých přístupů.
Popište, co znamená průchod při překladu a čím se liší jednorpůchodové a víceprůchodové překladače. Co musí platit, abychom mohli daný jazyk překládat jednoprůchodovým překladačem?
Popište, co to je Just-In-Time překladač a na jakém principu pracuje. Jaké jsou jeho výhody?
Popište co se provádí ve fázi syntaktické analýzy, co je vstupe a co výstupem v této logické fázi při překladu. Jaké metody se obecně používají pro syntaktickou analýzu?

Překladače - konkrétní otázka - 7 bodů

Pomocí pseudokódu popište algoritmus činnosti lexikálního analyzátoru řízeného tabulkou přechodů deterministického konečného automatu. Předpokládejte, že v koncovém stavu se může provést uživatelem specifikovaná akce se zadaným číslem.
Popište možné způsoby vnitřní reprezentace programu v překladači a ukažte na příkladech.
Vysvětlete princip zotavení po chybě v syntaktické analýze rekurzivním sestupem a jeho implementaci. Uveďte, jakým způsobem obvykle probíhá zotavení v rámci lexikální a sémantické analýzy.
Vysvětlete, k čemu slouží blokově strukturovaná tabulka symbolů, a uveďte příklady její implementace.
Ukažte, jaký tvar má obecně rozkladová tabulka pro LL(1) analyzátor, a popište akce, které se v nich mohou vyskytnout.
Vysvětlete pojem aktivačního záznamu a ukažte, jakým způsobem je zajištěn přístup k parametrům a proměnným funkce na různých úrovních zanoření.
Vysvětlete, co to je tabulka symbolů. K čemu se používá? Na příkladu demonstrujte.
Jaké typy optimalizací znáte (na jakých úrovních mohou být prováděny)? Ukažte konrétní příklad nějaké optimalizace, kterou může překladač provést.

Praktický příklad - 15 bodů

Sestavte LL(1) gramatiku popisující definici strutury. Definice struktury začíná klíčovým slovem struct následuje identifikátor a klíčové slovo begin. Potom je sekvence deklarací. Ty jsou odděleny středníkem. Za poslední deklarací může, ale nemusí být středník. Definice struktury končí klíčovým slovem end. Jednotlivé deklarace začínají typem (jeden z dvojice int, double) a obsahují sekvenci identifikátorů oddělených čárkou. Dobrou definici ukazuje následující příklad:
```
struct X begin
  int a,b,c;
  double x,y
end
```
Výpočtem množin FIRST a FOLLOW ověřte, že vytvořená gramatika je opravdu LL(1)!
Převeďte následující gramatiku na LL(1) gramatiku tak, aby popisovala syntaxi regulárních výrazů. Operátor součtu a konkatenace jsou zleva asociativní, přičemž nejvyšší prioritu má operátor * a konkatenace má větší prioritu než součet. Ověřte, ľe je výsledná gramatika typu LL(1).
```
     E -> E + E  |  E E  |  E *  |  ( E ) | a
```
Vytvořte LL(1) gramatiku pro jazyk, jehož větami jsou bezkontextové gramatiky. Předpokládejte, ľe pravidla gramatiky jsou od sebe oddělena středníkem a jsou tvořena symboly n (neterminální symbol), t (terminální symbol), e (prázdné slovo), operátorem ‘|’ a šipkou ‘->’.
```
Příklad platné věty:     
n -> t n n | e ;    n -> n t | t ;  n ->  t | n | e;
```
Ověřte, že vytvořená gramatika je LL(1)!
Vytvořte LL(1) gramatiku popisující syntaxi deklarace hlavičky funkce s parametry v jazyce C. Typ parametrů nebo výsledku může být vytvořen z typů int, double, ukazatel a pole. Do řešení zahrněte vícerozměrná pole a násobné ukazatele. Ověřte, že vytvořená gramatika je LL(1)!
Vytvořte LL(1) gramatiku jazyka popisujícího jednu deklaraci proměnných v jazyce C. Uvažujte datové typy int, double a vícerozměrná pole těchto typů s uvedeným počtem prvků, např.
```
int x, arr1[10], arr2[4][5];
```
Ověřte, že vytvořená gramatika je LL(1)!
Vypočtěte pro následující gramatiku množiny FIRST všech pravých stran a FOLLOW všech nonterminálů a ukažte, zda je gramatika typu LL(1).
```
   S  -> A B C | C A
   A  -> a A   | C a | e
   B  -> b B   | c
   C  -> A b C | e
```
Převeďte následující gramatiku na ekvivalentní LL(1) gramatiku. Ukažte, že je výsledná gramatika opravdu LL(1).
```
   P  ->  N b | c
   L  ->  L P | a
   N  ->  L | L d P | a
```
Vypočtěte množiny First všech pravých stran a Follow všech nonterminálů pro následující gramatiku a ověřte, zda je tato gramatika typu LL(1).
```
   S  ->  S * E | E
   E  ->  T R
   R  ->  + T R | e
   T  ->  ( S ) | T ? | i
```
Převeďte následující gramatiku na ekvivalentní LL(1) gramatiku. Ukažte, ľe je výsledná gramatika opravdu LL(1).
```
   P  -> i : R L
   L  -> / R L  |  / n | e
   R  -> i S
   S  -> S i   |  e
```

(c) Marek Běhálek, FEI VŠB-TU Ostrava

Desing: Miroslav Beneš, FEI VŠB-TU Ostrava

18. 5. 2024 14:53:46