Konstrukce překladačů (SWI002)

Tento předmět byl zrušen a rozdělen na Principy překladačů SWI098 a Konstrukce překladačů SWI109.

Schéma překladače

      Práce překladače připomíná studenta, když se učí z ručně psaných (typicky vlastních) poznámek. Začíná to lexikální analýzou, kdy student zkoumá, co jsou ty čmáranice vlastně za písmenka, kde jsou hranice slov a podobně. Syntaktická analýza probíhá většinou paralelně s lexikální. Student ověřuje, zda jsou jeho poznámky vůbec česky (případně slovensky, anglicky, ...) a zda to nejsou čiré nesmysly.

      Následuje sémantická analýza, kdy student bádá, co tím chtěl básník (tedy on) vlastně říct, pídí se po nějakém hlubším smyslu poznámek a snaží se odhalit nějaké souvislosti mezi jednotlivými odstavci, sekcemi a kapitolami. Jednotlivým elementům textu jsou přiřazeny atributy, které postupně (v k průchodech, kde k je často mnohem větší než 1) doplňuje hodnoty těchto atributů. Příkladem atributů mohou být odkazy na související oblasti učiva nebo různé pomůcky a analogie pro snadnější pochopení a zapamatování jednotlivých elementů. Fáze sémantické analýzy bývá obvykle kritická a většinou se neobejde bez potíží (minimálně warningů). Student kleje, že poznámky nedávají smysl, a lamentuje nad tím, že si to nepoznačil lépe a nenapsal si toho víc. Nedostatky poznámek, způsobené obvykle nepozorností nebo dokonce absencí na přednášce, obvykle končí chybami při překladu, méně často učení proběhne bez větších potíží a výsledkem je pouze několik (desítek) varování. O jiných případech asi nemá cenu mluvit, jsou příliš vzácné.

      Do back-endu už tolik nevidíme, je však nutné poznamenat, že choulostivou fází jsou optimalizace. Je potřeba se vyhnout přeoptimalizování. High-level optimalizace často způsobují nepřesnosti zásadního rozsahu ve znalostech studenta. Low-level optimalizace můžou v jeho mysli zastínit některé důležité detaily.

Syntaktická analýza

Síla gramatik

...navyše zjednotenie všetkých LR(n) dáva DBKJ (deterministické bezkontextové jazyky).

---

Analýza zhora-nadol

• aká je definícia gramatiky LL(1)
• ako sú nadefinované operátory FIRST a FOLLOW, a čo to predstavuje
• pri LL(1) je potrebné vedieť, akým spôsobom skonštruujeme jednoduchý automat.

Operátor FIRST

Je to funkcia, ktorá dostane terminály alebo neterminál a vráti množinu terminálov. Yaghob sa vás určite spýta, čo vlastne tento operátor predstavuje. Je potrebné vedieť, že FIRST(X) je množina terminálov takých, ktoré sa môžu vyskytnúť na začiatku slova, zderivovateľného z X.

Túto množinu potrebujeme pre vytvorenie FOLLOW(X) a pre definíciu gramatiky LL(1).

Definice

Pro množinu slov $ L \subseteq P(V^*) \,\! $ je $ FIRST_k^G(L)= \{x \in V_T^* | (\exists y \in L)((y\Rightarrow_G^* x \ \and\ |x| \leq k) \ \or\ (\exists z \in V_T^*)(y\Rightarrow_G^* xz \ \and\ |x| = k)) \}. $

Konstrukce

Ako vytvoríme FIRST(X)?

1. ak je X terminál, potom FIRST(X)={X}
2. ak je X neterminál, potom:
   • Ďalej nás zaujímajú len pravidlá z gramatiky, ktoré majú na ľavej strane neterminál X.</li>
   • Ak je v gramatike pravidlo X -> λ, potom do FIRST(X) pridáme λ.</li>
   • Ak je pravidlo v tvare: X -> Y₁Y₂Y₃Y_... a všetky FIRST(Y_i) obsahujú λ, potom do FIRST(X) znova pridáme λ.</li>
   • Ak je pravidlo v tvare: X -> Y₁Y₂Y₃Y_... ale existuje FIRST(Y_i), ktoré neobsahuje λ, potom nájdeme zľava prvé také Y_k, aby FIRST(Y_k) obsahovalo λ ale FIRST(Y_k+1) neobsahovalo λ Potom do FIRST(X) dáme všetko z FIRST(Y₁) ... FIRST(Y_k+1)

Navyše môžeme celý postup zobecniť na reťazce. V tom prípade ak je (S_i)_i=1..n postupnosť terminálov a neterminálov, pre ktoré už FIRST máme spočítané, potom FIRST(S) vytvoríme z FIRST(S₁)..FIRST(S_k), ktoré obsahujú λ a FIRST(S_k+1), ktoré už λ neobsahuje.

Operátor FOLLOW

Je to funkcia, ktorá dostane neterminál a vráti množinu terminálov. Znova sa vás Yaghob spýta, čo vlastne tento operátor v skutočnosti predstavuje.

FOLLOW neterminálu vrací množinu terminálů, které se mohou (např. ve větné formě) vyskytovat bezprostředně za tímto neterminálem.

Túto množinu potrebujeme pre definíciu gramatiky LL(1) a hlavne pre konštrukciu SLR(1) parseru (podľa toho zistíme, kam patria redukcie).

POZNÁMKA k SLR(1) parseru: Pokiaľ sa niekde vyskytne kolizia v redukcii, znamena to, že nejake neterminaly X,Y mali neprazdny prienik vo svojich množinách FOLLOW, čo sa dá zapísať takto:

FOLLOW(X) ∩ FOLLOW(Y) ≠ ∅

Back in school, I'm doing so much lerainng.

QishPB <a href="http://zksvatnwittz.com/">zksvatnwittz</a>

H4Dyi9 , [url=http://mfjcfelxckdf.com/]mfjcfelxckdf[/url], [link=http://axbsnbjxfmjg.com/]axbsnbjxfmjg[/link], http://gogfhkbgmwxa.com/

cy6Czb <a href="http://vdzconratrwv.com/">vdzconratrwv</a>

hSheqc , [url=http://egzwdtdthzgo.com/]egzwdtdthzgo[/url], [link=http://cfmcyylfucuf.com/]cfmcyylfucuf[/link], http://ozbattpabrzg.com/

Zkouška

• maily o zkoušce z mff-info: 1 2 3 4 5 6 7
• novější zadání