# Rychlý přehled (cheat sheet) – FJP > Kondenzovaná verze celého předmětu na jeden průchod. Detaily v `tema_pXX.md`. --- ## 1. Základní pojmy (p01) ``` Abeceda Σ neprázdná konečná množina symbolů Řetězec x konečná posloupnost ze Σ, |x| = délka ε prázdný řetězec, |ε| = 0 x·y konkatenace: ASOC, NE komutativní xⁿ x⁰ = ε, xⁿ = x·xⁿ⁻¹ xᴿ reverze: (xᴿ)ᴿ = x, (xy)ᴿ = yᴿxᴿ Σ* = všechny řetězce nad Σ (vč. ε) Σ⁺ = Σ* \ {ε} Jazyk L ⊆ Σ* Operace nad jazyky množinové: L₁ ∪ L₂, L₁ ∩ L₂, L₁ \ L₂, L̄ = Σ* \ L řetězcové: L₁·L₂, Lⁿ, L* = ⋃ Lⁿ (n≥0), L⁺ = L·L*, Lᴿ identity: L·{ε}=L, L·∅=∅, L⁰={ε}, ∅*={ε} (L₁L₂)ᴿ = L₂ᴿL₁ᴿ ``` ⚠️ **Vždy si pamatuj rozdíl:** `ε` (řetězec) × `{ε}` (jazyk s 1 prvkem) × `∅` (prázdný jazyk). --- ## 2. Chomského hierarchie (p02) ★★★ | Typ | Název | Tvar pravidel α → β | Gramatika | Automat | |---|---|---|---|---| | 0 | obecná / rekurzivně vyčíslitelný jazyk | α ∈ (N∪Σ)⁺, β ∈ (N∪Σ)* | gramatika typu 0 | **Turingův stroj** | | 1 | kontextová / rekurzivní jazyk | α = α₁Aα₂, β = α₁γα₂, γ ≠ ε | kontextová gramatika | **lineárně omezený TS** | | 2 | bezkontextová (CFG) | A → β, A ∈ N, β ∈ (N∪Σ)* | bezkontextová gramatika | **zásobníkový automat (PDA)** | | 3 | regulární | A → aB nebo A → a nebo A → ε (pravá lineární) | regulární / lineární gramatika | **konečný automat (KA)** | ``` L₃ ⊊ L₂ ⊊ L₁ ⊊ L₀ ⊊ všechny formální jazyky ``` **Gramatika** G = (N, Σ, P, S): - N = neterminály, Σ = terminály, P = pravidla, S ∈ N = startovní - **Derivace**: λ ⇒ μ pokud λ = γαδ, μ = γβδ, α→β ∈ P - **Jazyk**: L(G) = { w ∈ Σ* | S ⇒* w } **Ekvivalence:** G₁ ≡ G₂ ⇔ L(G₁) = L(G₂). Rozhodnutelnost ekvivalence závisí na třídě (typ 3 ANO, typ 2 obecně NE). --- ## 3. Regulární jazyky (p03) ★★★ ### Reprezentace (4 ekvivalentní) ``` regulární gramatika ↔ konečný automat ↔ regulární výraz ↔ regulární množina ``` ### Regulární výraz (RV) ``` ∅, ε, a (a∈Σ), (α+β), (αβ), (α*) sémantika: h(∅) = ∅, h(ε) = {ε}, h(a) = {a} h(α+β) = h(α) ∪ h(β) h(αβ) = h(α) · h(β) h(α*) = h(α)* ``` Priorita: `*` > `·` > `+`. Identity Kleeneho algebry: α+α=α, α+β=β+α, α(βγ)=(αβ)γ, ε·α=α, ∅·α=∅, α*=ε+αα*, … ### Úpravy gramatiky (algoritmy) - **Redukce** = plodnost (N_t) + dosažitelnost (V): odstraň pravidla s neplodnými nebo nedosažitelnými symboly - **Odstranění ε-pravidel**: spočítej N_ε = množinu symbolů, ze kterých lze derivovat ε. Pak pro každé pravidlo A → α₁α₂…αₙ generuj všechny varianty bez podmnožin αᵢ ∈ N_ε. - **Vlastní gramatika** = redukovaná + bez ε-pravidel + bez cyklu (A ⇒⁺ A). --- ## 4. Konečné automaty (p04) ★★★ ### Definice DKA ``` M = (Q, Σ, δ, q₀, F) Q konečná množina stavů Σ vstupní abeceda δ:Q×Σ→Q deterministická přechodová funkce q₀ ∈ Q počáteční stav F ⊆ Q koncové (přijímající) stavy NKA má δ: Q×Σ → 2^Q (množina stavů) NKA s ε má δ: Q×(Σ∪{ε}) → 2^Q ``` **Jazyk přijímaný:** L(M) = { w ∈ Σ* | δ*(q₀, w) ∈ F }. Pokud F = ∅, pak L(M) = ∅. **Kleeneho věta:** L je regulární ⇔ existuje KA M, který L přijímá. ### Klíčové algoritmy | Algoritmus | Výsledek | |---|---| | Odstranění ε-přechodů | NKA bez ε | | Podmnožinová konstrukce (subset construction) | NKA → DKA | | Odstranění nedosažitelných stavů | KA bez zbytečných stavů | | Úplnost (doplnění past stavu) | úplný DKA | | **Minimalizace** (Myhill–Nerode, ekvivalence stavů) | minimální DKA | **Subset construction (NKA → DKA):** 1. Počáteční stav DKA = `ε-closure({q₀})` 2. Pro každý množinový stav S a symbol a ∈ Σ: nový stav = `ε-closure(δ(S, a))` 3. Koncové stavy: ty množinové stavy, které obsahují alespoň jeden koncový stav původního NKA. ### Převody ``` RG ──── alg 5.19 ────► KA ──── alg 5.22 ────► RG RV ──── alg 5.23 ────► KA ──── alg 5.24 ────► RV (eliminace stavů) ``` --- ## 5. Lexikální analyzátor (p05) ### Struktura překladače ``` ZDROJOVÝ KÓD ▼ [ Lexikální analyzátor ] ── tokeny ──► [ Syntaktický analyzátor ] ── strom ──► [ Sémantický analyzátor ] ── AST + tab.symbolů ──► [ Generátor mezikódu ] ──► [ Optimalizace ] ──► [ Generátor cílového kódu ] ▼ CÍLOVÝ KÓD ◄── Tabulka symbolů, hlášení chyb ``` **Kompilátor** = překlad ZK → CK (jednou, pak běží CK). **Interpret** = vstup ZK, výstup hodnoty (každé spuštění analyzuje). ### Token - **Význmový** = identifikátor, klíčové slovo, konstanta, operátor, oddělovač - **Nevýznamový** = mezera, komentář, EOL (ignorovány po rozpoznání) **Lexer** typicky implementován jako KA. Postupně čte vstup, ve stavu shoda → emituje token, jinak chybový stav. 🌐 **Longest match rule**: ze dvou možných tokenů (např. `<` vs. `<=`) emituj ten delší. --- ## 6. Bezkontextové jazyky (p07) ★★★ ### Derivační strom (parse tree) - Kořen = startovní symbol S - Vnitřní uzly = neterminály - Listy zleva doprava = výsledná věta - Synové uzlu A = pravá strana použitého pravidla A → β **Levá derivace** = vždy nahrazuj nejlevější neterminál. **Pravá derivace** = nejpravější. ### Nejednoznačnost **Gramatika G je nejednoznačná** ⇔ existuje věta z L(G) se 2 různými derivačními stromy (= 2 různé levé/pravé derivace). **Vnitřně nejednoznačný jazyk** = nemá žádnou jednoznačnou gramatiku. Příklad: L = { aⁱbʲcᵏ | i = j ∨ j = k }. **Dangling-else** klasický příklad nejednoznačnosti: ``` S → if E then S | if E then S else S | ... ``` ### Normální formy **Chomského NF (CNF):** všechna pravidla tvaru A → BC nebo A → a (případně S → ε). - Algoritmus: 1) odstraň ε-pravidla, 2) odstraň jednoduchá pravidla (A → B), 3) zaveď neterminály pro terminály, 4) rozštěp dlouhé pravé strany. - Délka derivace věty w v CNF: `2|w| − 1` kroků. **Greibachové NF (GNF):** všechna pravidla tvaru A → aα, kde a ∈ Σ, α ∈ N*. - Vhodná pro PDA — každý krok generuje jeden terminál. ### Levá rekurze Pravidlo `A → Aα | β`: ``` A → A α | β ⟹ A → β A' A' → α A' | ε ``` --- ## 7. Zásobníkový automat (p08) ★★★ ### Definice PDA ``` M = (Q, Σ, Γ, δ, q₀, Z₀, F) Q stavy Σ vstupní abeceda Γ zásobníková abeceda δ: Q × (Σ∪{ε}) × Γ → 2^(Q × Γ*) nedeterministický q₀ počáteční stav Z₀ ∈ Γ počáteční symbol na zásobníku (dno) F ⊆ Q koncové stavy (jen pro 1 typ akceptace) Konfigurace: (q, w, α) ∈ Q × Σ* × Γ* q = stav, w = nepřečtený zbytek vstupu, α = obsah zásobníku (vrchol vlevo) ``` ### Tři typy akceptace 1. **Koncovým stavem** (F): `(q₀, w, Z₀) ⊢* (qf, ε, α)`, qf ∈ F 2. **Prázdným zásobníkem**: `(q₀, w, Z₀) ⊢* (q, ε, ε)` 3. **Kombinací** (koncový stav + prázdný zásobník) **Pro NPDA:** všechny tři typy jsou ekvivalentní (jdou navzájem převést). **Pro DPDA:** akceptace prázdným zásobníkem je slabší (vyžaduje prefix-free jazyk). ### CFG → PDA (standardní konstrukce, akceptace prázdným zásobníkem) ``` M = ({q}, Σ, Γ, δ, q, S, ∅) kde Γ = N ∪ Σ δ(q, ε, A) = { (q, β) | A → β ∈ P } expanze (pro každé pravidlo A → β) δ(q, a, a) = { (q, ε) } porovnání (terminál odpovídá) ``` ### Hierarchie ``` DCFL (deterministické bezkontextové) ⊊ CFL (bezkontextové) KA s 1 zásobníkem = PDA 2 zásobníky = Turingův stroj (silnější) ``` --- ## 8. LL syntaktická analýza (p09) ★★★ ### LL(k) gramatika - **L**eft-to-right read, **L**eftmost derivation, *k* = počet symbolů lookaheadu. - **LL(1)** = stačí jeden symbol vpřed pro rozhodnutí, které pravidlo aplikovat. ### FIRST a FOLLOW **FIRST(α)** = množina terminálů, které mohou stát na začátku řetězce derivovaného z α. ``` FIRST(ε) = {ε} FIRST(a) = {a} pro a ∈ Σ FIRST(Xα): zahrň FIRST(X) \ {ε}; pokud ε ∈ FIRST(X), zahrň také FIRST(α) ``` **FOLLOW(A)** = množina terminálů, které mohou bezprostředně následovat za A v nějaké větné formě (plus `$` pokud A může být na konci). ``` $ ∈ FOLLOW(S) startovní symbol A → αBβ: FIRST(β) \ {ε} ⊆ FOLLOW(B) za B se může vyskytnout cokoliv z FIRST(β) A → αB nebo A → αBβ s ε ∈ FIRST(β): FOLLOW(A) ⊆ FOLLOW(B) ``` **PREDICT(A → α)** = množina lookaheadů, pro které toto pravidlo lze použít. ``` PREDICT(A → α) = FIRST(α) \ {ε} pokud ε ∈ FIRST(α): také ∪ FOLLOW(A) ``` ### LL(1) kritérium Gramatika je LL(1) ⇔ pro každou dvojici pravidel `A → α | β` platí: `PREDICT(A→α) ∩ PREDICT(A→β) = ∅`. ### Rozkladová tabulka M[A, a] = pravidlo, které expandovat, když vrchol zásobníku je A a lookahead je a. Konstrukce: pro každé `A → α` zařaď `A → α` do M[A, t] pro všechna `t ∈ PREDICT(A→α)`. ### Transformace na LL(1) 1. **Odstranění levé rekurze** (viz p07). 2. **Levá faktorizace**: `A → αβ | αγ → A → αA′; A′ → β | γ`. ### Hierarchie ``` jednoduché LL(1) ⊊ q-gramatika ⊊ LL(1) ⊊ LL(2) ⊊ … ⊊ LL(k) ⊊ LR(k) = DCFL ⊊ CFL ``` --- ## 9. Sémantická analýza (p10) ### Implementace LL(1) analyzátoru - **Překladový automat** = zásobníkový automat (rozšířený o výstupní pásku); na vrcholu zásobníku neterminál ⇒ použij M[A, a]; terminál ⇒ porovnej se vstupem. - **Metoda přepisu rozkladové tabulky**: hlavní smyčka čte tabulku M; obecnější (data-driven). - **Metoda rekurzivního sestupu**: pro každý neterminál procedura; volání = expanze. Kód překladače je přímo psaný; rychlejší, ale méně flexibilní. ### Formální překlad ``` Vstupní jazyk D, výstupní jazyk H, překlad Z ⊆ D × H. Syntaxí řízený překlad: Z = Z₁ ∘ Z₂, kde Z₁: D → AST, Z₂: AST → H. Překladová gramatika PG = (N, Σ, D, P, S): Σ = vstupní terminály, D = výstupní akce (action symbols). homomorfismy h_v (extrakce vstupu) a h_d (extrakce výstupu). ``` Příklad infix → postfix: ``` E → E +ᴬ T | T ⟹ E → T E' T → T *ᴬ F | F E' → +ᴬ T E' | ε (akční symbol +ᴬ vystupuje) F → ( E ) | id ... ``` ### Tabulka symbolů | Pole | Význam | |---|---| | jméno | identifikátor (klíč) | | typ | int / float / pole / record / fn / … | | adresa / offset | umístění v paměti | | oblast platnosti (scope) | hloubka vnoření bloku | | další | const/var, počáteční hodnota, … | Operace: `insert(name, info)`, `lookup(name) → info | nil`. Pro bloky: **zásobník tabulek** (push při vstupu do bloku, pop při výstupu) → **shadowing** vnořenými deklaracemi. ### Sémantické kontroly - **Typová kontrola**: u operátorů kontrola, že operandy mají kompatibilní typy. - **Přetypování (coercion)**: implicitní konverze podle priority typů (např. `int + float → float + float`). - **L-value vs R-value**: levá strana přiřazení musí být l-value (paměťové místo); pravá strana může být r-value (hodnota). - **Kontrola deklarace před použitím**, **rozlišení procedury vs. funkce**, **aktivační záznam** (parametry, lokální proměnné, návratová adresa). ### Příkazové konstrukce - **Podmíněný příkaz** `if E then S₁ else S₂`: dangling-else řeší gramatika. - **Cyklus**: `for`/`repeat` → transformace na `while`. - **Podprogramy**: aktivační záznam na zásobníku; rekurze = více záznamů. --- ## 10. „Mapa převodů" pro zkoušku ★★★ ``` Regulární výraz / \ alg 5.23 alg 5.24 / \ RG ─── alg 5.19 ───► KA (NKA, DKA) ◄─── alg 5.22 ─── RG ▲ │ │ │ minimalizace, determinizace, úplnost │ │ Bezkontextová gramatika (CFG) │ / \ │ CNF, GNF levá rekurze, faktorizace │ \ / │ PDA (NPDA, DPDA) ─── deterministicky ───► LL(k)/LR(k) parser │ └─────────────── KONTEXTOVÁ → linearně omezený TS OBECNÁ → Turingův stroj ``` --- ## 11. „Top-20 chytáků" k zopakování v autobuse 1. `ε` × `{ε}` × `∅` – rozdíl ano/ne otázka. 2. Konkatenace je **asociativní, NE komutativní**. 3. `L · ∅ = ∅`, ale `L · {ε} = L`. 4. `L⁰ = {ε}` (NE `∅`, NE `L`). 5. `∅* = {ε}`, `{ε}* = {ε}` – výjimky, kde iterace dává konečný jazyk. 6. **Abeceda je vždy konečná.** 7. Kontextová gramatika typu 1 *vyžaduje* `|α| ≤ |β|` – proto se ε-pravidla řeší zvlášť (S → ε povoleno jen pro startovní S, který se nikde nevyskytuje na pravé straně). 8. CFL je **NE uzavřená na průnik a doplněk**; uzavřená na sjednocení, konkatenaci, iteraci. 9. Regulární jazyky **JSOU** uzavřené na vše (∪, ∩, doplněk, ·, *, ᴿ). 10. NKA a DKA **mají stejnou vyjadřovací sílu**, ale DKA může mít exponenciálně víc stavů (subset construction). 11. DPDA **má menší sílu** než NPDA (DCFL ⊊ CFL); NPDA pro 1 zásobník = ekvivalence s CFG. 12. **2 zásobníky = Turingův stroj.** 13. Levá rekurze blokuje LL parsery; **LR parsery ji zvládají**. 14. Každá LL(k) gramatika je LR(k), ale **NE naopak**. 15. **Nejednoznačnost** je vlastnost gramatiky, nerozhodnutelná obecně. **Vnitřně nejednoznačný jazyk** = nemá jednoznačnou gramatiku. 16. CNF: každá derivace věty délky n má **přesně 2n−1 kroků**. 17. **FIRST(ε) = {ε}**, ale ε se rozlišuje od „regulárního" terminálu při LL(1) výpočtu. 18. **$ ∈ FOLLOW(S)** vždy. 19. Minimalizace DKA: dva stavy ekvivalentní ⇔ pro každý vstup vedou do ekvivalentní třídy a oba jsou (nejsou) koncové. 20. **Sémantická analýza** = vše, co syntax neřeší: deklarace, typy, scope, l-value/r-value. --- 🎓 Hodně štěstí u zkoušky!