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 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 Existuje pro libovolnou gramatiku typu 2 algoritmus pro - to je gramaticka bezkontextova (cisluji se od 0) a) převod na ekvivalentní nelevorekurzivní gramatiku? - ano, zname alg. b) � � LL(k) � - muzeme to zkouset, ale neni alg. c) � � LR(k) � - muzeme to zkouset, ale neni alg. d) výpočet množin LR(0) položek? - ano, dojdeme ke konfliktu a pak muzeme pocitat dalsi 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 :) -------------------------------- tucne to, co je v casti prikaldu kdyz nebude LL, tak bude LR k prikladum povolena literatura, bez pocitace (k tomu tucne) k tomunormalne, to bez materialu