KIV/FJP - Formální jazyky a překladače
V souborech jsou ke stažení přednášky, vč. verze 4na1. Dále jsou k dispozici vypracované otázky, a to několikery.
Obsah |
[editovat] 2016
[editovat] 11. ledna
[editovat] příklady
- 1
Rozhodněte, zda je gramatika LR(0) nebo SLR(1).
S -> 1A | 1B
A -> 1S | 1
B -> 0B | 0
- 2
Upravte na LL(1), napište rozkladovou tabulku.
S -> 1A | 1B
A -> 1S | 1
B -> 0B | 0
[editovat] teorie
3. Stejná G jako v 1 a 2, nakreslete konečný automat.
4. Co je obsahem deskriptoru třídy?
5. Zapište výraz (a+b)*(a+b-c) a) v prefixové b) v postfixové notaci.
6. Jakými vlastnostmi jazyka je podmíněno statické přidělování paměti?
7. Popište význam částí dynamické adresy (adresové dvojice).
[editovat] 2015
[editovat] 20. ledna
[editovat] příklady
- 1
Pro G[Z] s pravidly:
Z -> d | XYZ
Y -> c | e
X -> Y | a
Konstruováním tabulek analyzátoru dokažte, že není SLR(1).
- 2
Pro G[Z] s pravidly:
Z -> d | XYZ
Y -> c | e
X -> Y | a
a) Definujte ekvivalentní nedeterministický zásobníkový automat pracující zdola nahoru. Popište posloupnost konfigurací pro akceptaci věty "ad".
b) Pokuste se najít regulární výraz, který definuje stejný jazyk.
[editovat] teorie
1. Co jsou to generátory překladačů, popiště nějaký.
2. Vysvětlete funkci procedury test(s1, s2:symset, n:integer).
3. Vysvětlete co je prefix, infix a víceadresové instrukce.
4. Co jsou to syntetizované atributy?
5. Popište části dynamické adrey.
6. Napište formální definici LL(1) gramatik.
[editovat] 2013
[editovat] 21. ledna
[editovat] příklady
- 1
Navrhněte SLR(1) analyzátor pro jazyk popsaný gramatikou G[S]:
S -> S = E
S -> E
E -> {S}
E -> a
- 2
Navrhněte LL(1) analyzátor pro gramatiku G[S]. Pozor! Je třeba ji upravit.
S -> S = E
S -> E
E -> {S}
E -> a
[editovat] otázky
1. Zdůvodněte, proč se nepoužívají čistě interpretační překladače.
2. Jaká vlastnost gramatiky podmiňuje nekonečnost generovaného jazyka?
3.Popište princip metody rekurzivního sestupu.
4. Přeložte do postfixových instrukcí příkaz while x < y do x = (x+y)/(x-y); je-li x na adrese 100 a y na adrese 101.
5. Popište význam částí dynamické adresy (adresové dvojce).
6. Kdy překladač vytváří CIR (class instance record) a jaké informace ukládá?
[editovat] 8. ledna
[editovat] příklady
- 1
S -> AS | e
A -> baA | b
- Je gramatika LR(0) nebo SLR(1).
- Pro pozitivní případ vytvořite tabulky akcí a přechodů.
- Akceptujte slovo "bab"
(Pozn. V některých množinách položek se objevil konfilikt redukce-přesun -> tj. tečka na konci a tečka uprostřed, tudiž jsem napsala, že se jedná o SLR ;) )
- 2
A:=(X+Y)*(W-Z)
rozložit do trojic, doplnit tabulku (nemusela se opisovat) o ":=".
(Pozn. Promítal slidy s tabulkou, která je v 7. přednášce, kde je taky úplně na posledním slidu názorný příklad na ty trojice)
[editovat] teorie
- Porovnejte výhody a nevýhody interpretačních a kompilačních překladačů
- Zapište s co nejmenším počtem pravidel gramatiku popisující binární čísla s lichým počtem jedniček
- A -> 1B
- B -> 1B1 | 0B0 | e
- Zapište výraz -2*(x+y)^3 a) v prefixové b) v postfixové notaci (Nejjednoduší je udělat si strom a vypsat ho v post- a preorderu)
- Uveďte, jaké údaje ukládá překladač v aktivačním záznamu
- Uveďte příklad víceznačné gramatiky. Víceznačnost dokažte.
- Popište způsob vytváření a práce s frekvenčně uspořádanou tabulkou symbolů
[editovat] 2012
[editovat] Předtermín 18. 12.
[editovat] příklady
- 1
s -> AS | e
A -> baA | b
- převést na LL(1)
- udělat překladovou tabulku
- akceptujte slovo "bab" podle překladové tabulky
- udělat regulární výraz odpovídající gramatice
- 2
(X+Y)*X-Z
- udělat čtveřice
- převést do cílových instrukcí
[editovat] teorie
- Popiště princip způsobu zotavení ze syntaktické chybyv překladači PL/0
- uveďte obecný tvar překladových pravidel používaných v LEX
- k čemu lsouží mapovací funkce pole a z jakých se skládá částí
- 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
- popište přechodovou funkce zásobníkového automatu akceptujícího s prázdným zásobníkem, který je ekvivalentní grmatice G[S] -> (S) | S() | e
- zdůvodněte proč LR(k) gramatiky popisují obsáhlejší třídu jazyků než LL(k)
[editovat] 2010
[editovat] 22. ledna
[editovat] příklady
- 1
Je dána gramatika, ukažte, že není jednoznačná a dokažte, že je regulární tím, že navrhnete konečný automat který ji klasifikuje.
- 2
Je dán jazyk generovaný gramatikou, navrhněte LL(1) analyzátor, který tuto gramatiku akceptuje.
[editovat] 6. ledna
[editovat] příklady
- 1
Zadaná gramatika(s jednim e pravidlem) zjistit, zda je regulární, pokud ano, tak regulárním výrazem popsat generovaný jazyk a zjistit, zda je SLR gramatika a tabulku
- 2
Řetězec A:=(X+Y)*(W-Z) rozepsat do čtveřic, doplnit := a co se generuje
[editovat] Předtermín ??. prosince
[editovat] příklady
- 1 (15b.)
Zjistěte, zda gramatika G [S] s pravidly: (1),(2): S->AS|e (3),(4): A->baA|b je LR(0) nebo SLR(1). Pro pozitivní případ zkonstruujte rozkladové tabulky akcí i přechodů a použijte je k analýze věty bab.
- 2 (10b.)
Převeďte gramatiku G [S] s pravidly: (1),(2): S->AS|e (3),(4): A->baA|b na LL(1) gramatiku, zkonstruujte pro ní rozkladovou tabulku a analyzujte větu bab.
- 3 (5b.)
Dokažte, že gramatika ze zadání př. 1, resp. 2, popisuje regulární jazyk. (Návod: jakého tvaru jsou generované řetězce?)
[editovat] 2009
[editovat] Předtermín 23. prosince
[editovat] příklady
- 1
Zadana nejaka gramatika a zjistit zda je LL(0), LL(1), LR(0) a udelat rozkladove tabulky.
- 2
Retezec a:=(x+y)*(w-z) rozlozit do trojic. Do tabulky doplnit ":=" a rozepsat co se bude generovat.
(zdroj: http://zcu.arcao.com/kiv/fjp/) - současná zadání jsou pouze kombinace níže uvedených nebo obdobných příkladů
Charakterizujte křížový překladač - preklada se na jinym kompu nez sto bude (pracka) Objasněte pojem silikonový překladač - integrovany obvody Co to jsou formátory textu? Uveďte příklad - tex Charakterizujte kaskádní překladač - z jazyka A do B a mame prekladac z A do C a je snazsi z C do B Porovnejte výhody a nevýhody interpretačních a kompilačních překladačů - :) Jaké jsou důvody pro použití víceprůchodového překladače - snazime se o 1 pruchod, 1 derivacni stroj vsechny atributy ... takovy zavislosti mezi atrinbuty, ze to nejde; prekladani na nekolik casti a jeden mezijazyk a druhy mezijazyk (treba malo pameti, moc tezky na jeden krok) Zdůvodněte, proč se nepoužívají čistě interpretační překladače - vzdy je nejaka cast, udela se mezi jazyk a to se interpretuje (postfixova notace a pak se to zakoduje), dela se to proto, aby se tam nedelali veci zbytecne (smycky) Co to jsou generátory překladačů, uveďte příklad - yacc, na zaklade popisu jazyka gramatikou (a toho, co se ma vygenerovat) Nakreslete schéma překladače kompilačního typu - lexikalni, syntaxticka analyza, sematicke zpracovani, generator vystupniho kodu (nejakej obrazek)
Jaká vlastnost gramatiky podmiňuje nekonečnost generovaného jazyka? - rekurzivita Popište gramatilou reálná čísla s desetinnou částí - nejakej automat, staci bez znaminka Jaký je nejvyšší možný počet stavů deterministického KA, má-li ekvivalentní nederm. KA 5 stavů - az do mohutnosti mnozin vsech podmnozin ... (2^5)-1 Popište tvar identifikátoru levou lineární gramatikou - na pravy strane pravidla na zacatku pravidla neterminalni symbol Zapište pravou lineární gramatiku čísla real v semilogaritmickém tvaru - automat (semilogartimicky 2,3E-6) Zapište s co nejmenším počtem pravidel gramatiku popisující binární čísla s lichým počtem jedniček. - predstavti jako automat a prevest na gramatiku :) Uveďte obecný tvar překladových pravidel používaných v LEX - regexpy Jaký řetězec rozpoznává LEX, je-li překladové pravidlo dáno např. výrazem \+?[0-9][0-9]*$ - cele cislo na konci radku, muze mit znamenko Jaký řetězec rozpoznává LEX, je-li překladové pravidlo dáno výrazem \*[1-9]* - * a retezec cislis vecetne prazdneho Jak řeší lexik. analyzátory problém nalezení symbolu v případě, kdy je jeden symbol prefixem jiného? - hleda ten nejdelsi (cele cislo desetinne cislo) Popište formálně zásobníkový automat a význam jeho částí - ma stavy, ma vstupni symboly, zasobnikove symboly, prechodova fce (jak vypada?), dno zasobniku, pocatecni stav, mnozina koncovych stavu (je jich 7)
Popište přechodovou funkci zásobníkového automatu akceptujícího s prázdným zásobníkem, který je ekvivalentní gramatice G [S]: S -> ( S ) | S ( ) | e - na vrcholu zasobniku S, ma 3 moznosti, jak se nahradi, pro vsechny terminalni symbolky, kdyz je na zasobniku a ve vstupu tentyz, tak se dela srovnani
Jaký jazyk popisuje gramatika např. G [S]: S -> ( S ) | S ( ) | e - popsat ho slovne nebo priklad, co tam patri, nejaka predstava, tady je to: jazyk zavorkovych vyrazu, ktere jsou parovane a mohou byt do sebe vnorovane
Jaký jazyk popisuje gramatika např. G [S]: S -> a S a | b S b | e - retezec 'a' a 'b' a za tim zrcadlovej obraz retezce
Navrhněte gramatiku jazyka (např. jehož věty mají tvar w wreverzní, kde wÎ{0,1}* - to samy jako predtim
Kdy označujeme větu jazyka jako víceznačnou - kdyz pro ni existujou alespon 2 derivacni stromy
Popište princip způsobu zotavení ze syntaktické chyby v překladači PL/0 - fce test(), ktera zpusobi, ze se preskakuje, dokud se nenarazi na mnozinu follow()
Jaké vlastnosti musí splňovat jazyk analyzovatelný rekurzivním sestupem - nemi byt levo-rekurzivni a jednolivy pravy strany by meli bejt odlisitelne
Vysvětlete funkci procedury Test(s1,s2: symset; n: integer); v překladači PL/0 - s1, s2 - mnozny symbolu a fce se vola na zacatku, kdy zjistuje, jaky z tech pravidel se ma pouzit a vola se nakonci pravidla, kdy se overuje, jeslti je to spravne zakoncene; s1, s2 - mnozina tech symbolu, ktery maji bejkt na zacatku pravy strany a to druhy je mnozina symbolu follow toho levostranyho symbolu ... ve druhym pripade je to follow a mnozina symbolu ktery k tomu vyznamove patri a nemely by se prekocit
Zapište gramatiku aritmetického výrazu s operátory + , *, a závorkami (, ). Zapište levou derivaci věty i + i - prej jasny :)
Popište princip metody rekurzivního sestupu - metoda, kdy se rekurzivne volaji procedury/fce, tkere odpovidaji neterminalnim symbolum
Charakterizujte syntetizované atributy - vyhodnocuji se zdola nahoru (mista, kde jsou ulozney jednotlivy promenny (adresy))
Popište způsob vyhodnocování dědičných atributů. - vyhodnocuji se shora dolu (napr - adresa odkud se daji ukladat mezivysledky)
Popište zásady konstrukce postfixového výrazu z infixového - zachovane poradi operandu, operatory nasledyji za operandy
Zapište posloupnost postfixových instrukcí pro např. a10 = - (x20 + y30)/(x20 - y30) - zalezi na priorite -
Zapište např -2*(x + y) ^ 3 pro případ 1) nejvyšší, 2) nejnižší precedence operátoru unárního
minus a) v prefixové, b) v postfixové notaci - zalezi na priorite - a na zaklade toho se to vyhodnocuje
Přeložte do posloupnosti postfix. instrukcí if (A10 < B 20) then C 30 := (A 10 + B 20 ) * ( A10 - B20 ); - vybrat postfixovy instrukce (treba z PL/0 nebo ADD, AMOL, ...) a proste to napsat :) nesmime zapomenout na if-false-jump
Přeložte do postfixových instrukcí příkaz while x<y do x:= (x+y) / (x-y); je-li x na adrese 100 a y na adrese 101 - skok zpatky na while a preskok az za while
Popište význam částí dynamické adresy (adresové dvojice) - uroven vnoreni a offset 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 - statickej ukazuje na staticky nadrazenej zaznam, dynamickej na dynamicky (odkud je to volany) ... podm: podprogram musi bejt deklarovanej v te urovni, kde je volanej ten prikaz (ale muzou bejt v podprogramu i podprogramy) Jaké informace o proměnných jsou uloženy v tabulce symbolů překladače jazyka pascalského typu - druh identifikatoru (promenna, fce, navesti, typ, trida, ...), kdyz je to promenna, tak jakej je to typ (jednoduchej, strukturovanej), atd ... to se vymysli :) adresa promenne, na jakej hladine s jakym offsetem Jaká je časová složitost práce s rozptýleně organizovanou tabulkou symbolů v závislosti na počtu symbolů v programu? - u seznamu je kvadraticka (pouzivaji se vicekrat) a tady vznikaji taky seznamy (hask funkce), obecne taky kvadraticka, ale tabulka ma k-casti a zacinam od urcityho mista a proto je kvadraticka narocnost redukovana cislem 'k' Jaká je závislost časové režie vyhledávání v netříděně uspořádané tabulce symbolů na počtu jmen v tabulce - kvadraticka Popište způsob vytváření a práce s frekvenčně uspořádanou tabulkou symbolů - kdyz se najde polozka, posune se k zacatku, casto pouzivany jsou vic nahore a driv se na ne narazi, tabulka se prohledava od zacatku dolu Jakými vlastnostmi jazyka je podmíněno statické přidělování paměti - nesmi tam bejt nic dynamickyho :) (dynamicke promenne, dynamicke typy, ale ani rekurze!! a ani paralelne provadene aktivity - nevime kdy a kolik se toho spusti) Popište odlišnost zpřístupnění nelokálních proměnných Pascalu a C - v pascalu nasobne vnorovani v C ne, v C pouze globalni a lokalni promenne - 2 hladiny; v Pascalu jich je vic, hladin libovolne mnoho Uveďte, jaké údaje ukládá překladač v aktivačním záznamu - aktivacni zaznam odpovida pridelenemu mistu v pameti pro nejakou jednotku a musi tam bejt navratova adresa, misto pro usporadani aktivacnich zaznamu (jak se ma vypoctovy zasobnik zmenit, az skonci dynamicky ukazatel), musi tam byt staticky ukazatel (v Pascalu), musi byt misto pro parametry, musi byt misto pro lokalni promenne Vysvětlete, jakým mechanismem překladač zajišťuje respektování lokality identifikátorů v blokově strukturovaném jazyce - aby nasel driv, to, oc je lokalni nez to, co je globalni, tak si identifikatory dava do zasobniku
Uveďte datové struktury , které jsou použitelné k přidělování paměti pro a) rekurzivně volané procedury a funkce, - zasobnik, halda b) dynamické proměnné, - halda c) dynamické typy, - zasobnik, halda d) paralelně proveditelné programové jednotky - kaktusovy zasobnik, halda
Popište způsob a důvod použití displeje. - moznost hnizdeni podprogramu a sestupuje po statickem retezci, takze zavedeme display a primo ukazujeme na platnou hladinu Popište význam částí dynamické adresy (adresové dvojice) - hladina a offset Jaká jazyková omezení budou důsledkem přístupu do výpočtového zásobníku pomocí displeje, který je realizován jako tříprvkový vektor adres - omezeni jazyka by byly: uroven vnoreni maximalne 3 K čemu slouží mapovací funkce pole a na jaké části se člení? - slouzi k tomu, abych se dostal na prislusny prvek pole, dve casti - pevna (odnekud umisteny a je to vlastne zacatek pole) a zavisla na konkretnich indexech
Jaké informace jsou předávány při volání podprogramu, je-li formálním parametrem procedura a) v případě statického přidělování paměti, - vse napevno, preda se jako parametr adresa zacatku procedury b) v případě dynamického přidělování paměti - jeste k tomu pridame ukazatel na staticke rpostredi ve kterym je definovana procedura (byl na to priklad)
Co je obsahem deskriptoru třídy u OO jazyků - ukazatel na deskriptor rodice, udaje o offsetech jednotlivych datovych polozek a udaj o virtualnich metodach (zpristupnena tabulka virtualnich metod) Popište mechanismus zpracování statických metod - (v OO prostedi), hleda se metoda v miste, kde se vyskytne jeji volani, kdyz se nenajde, jde se do rodice a porad vejs a vejs az se metoda nekde najde a kdyz ne, tak je to chyba Popište mechanismus zpracování dynamických metod - v pripade, ze se vola nejaka metoda a volani je soucasti prikazu, kde se vyskytuje jmeno referencni promenny a a jmeno objektu vazane k promenne a v okamziku, kdy se provadi vytvoreni objektu konstruktorem, tak se provede navazani na tabulku virtualnich metod a tim padem se bude ten objekt .... bude objekt pouzivat metody, ktere mu prislusi, referecni promenna muze odkazovat na tridy, ktere ji patri i na tridy, ktere jsou jeji potomci, provede se navazani na tabulku visrtulanich metod Popište obecně základní cyklus interpretu - jako zakladni cyklus procesoru :) pracuje se s citacem instrukci, ktery se pri provedeni instrukce inkrementuje a podle instrukce se vyvola ake, ktera se ma delat do instrukce STOP :) S pomocí algoritmu generování z přednášek rozepište zadaný příklad pro generování z čtveřic - ulozeni do strace, zapamatovani pro kumutativni/nekomutativni, vzit se sebou mustr a podle toho to udelat S pomocí algoritmu generování z přednášek rozepište zadaný příklad pro generování z trojic -- jako to nahore :)
Uveďte příklad víceznačné gramatiky. Víceznačnost dokažte. - neco vymyslet, aby mela dva derivacni stromy :) Kdy označujeme větu jazyka jako víceznačnou? - uz tam bylo :) Může pro víceznačnou gramatiku existovat ekvivalentní gramatika jednoznačná? - ano, nekde tu byl priklad Operátor umocnění je ve Fortranu pravorasociativní. Zapište pravidla pro aritmetický výraz respektující tuto vlastnost - uzavorkovat s vyrazem napravo (??) Charakterizujte vztah mezi jazyky s LL(0) gramatikou a regulárními jazyky - LL(0) nemusim koukat na vstup a muzu expandovat - to muzu udelat tehdy, kdyz pro kazdy neterminalni symbol mam jednu pravou stranu a ten jazyk neni rekurzivni a tim padem je konecnej a proto je hloupejsi nez regularni :) je to podmnozina regularnich jazyku Uveďte formální definici LL(1) gramatiky - pro kazde pravidlo a -> alfa nebo beta musi platiti, ze first(alfa) atd.... nekde to je napsamny :) Zdůvodněte, proč je každá LL(1) gramatika silná - protoze ta silna gramatika je definovana timhle vzoreckem a pro k=1 to plati Uveďte nutnou a postačující podmínku pro to, aby gramatika byla silná LL(k) - K čemu slouží úprava gramatiky zvaná "pohlcení terminálu"? Uveďte příklad. -neco nejak pojmenujeme [Ai] - viz cviceni, pridame pravidlo [Ai] se prepise na neco :) Příklady převodu na LL gramatiku, konstrukci rozkladové tabulky a rozklad zadané věty - priklad Uveďte příklady algoritmicky nerozhodnutelných problémů z teorie formálních jazyků - jestli existuje LRk rpo libovolny k, jeslti nejaka gramatike je nebo neni viceznacna
Zdůvodněte proč LR(k) gramatiky popisují obsáhlejší třídu jazyků než LL(k) - nejakej obrazek - kam dohlidneme, ty dnesni trojuhelniky Porovnejte mohutnosti (souboru) množin LR(0), LALR(k), LR(k) položek - LR(0) == LALR(k) <= LR(k) Jaké podmínky musí splňovat množiny LR(0) položek, aby gramatika byla SLR(1)? - kdyz bude '.' na konci, musi byt jedina polozka a kdyz bude '.' nekde jinde, tak je to presun Popište tvar LR(0) položky a význam jejích jednotlivých částí - maji tvar prepisovaciho pravidla, kde je navic tecka a ta to rodeluje na to, co je v zasobniku a to, co je na vstupu Příklady konstrukce LR(0) a SLR(1) tabulek a rozklad zadané věty - LARL tma nebudou :) Jakou metodu syntaktické analýzy používá YACC - pouziva LALR Jakým způsobem řeší YACC konflikty redukce-redukce - moc se s tim nemazli a kdyz tam vznikne konflikt redukce-redukce, tak vezme to mensi a redukce-presun, udela redukci :)
