Některé důležité pojmy ze státnicových otázek z EaI - předmět PJP (snad nikomu nebude vadit, že jsem to sem dal :), pokud by to vadilo, tak to smáznu )

• abeceda = konečná množina symbolů
• řetězec (řetěz, slovo) nad abecedou T:
  • konečná posloupnost symbolů z T
  • ε je prázdný řetězec
  • T* je množina všech řetězců nad T (včetně prázdného řetězce)
• operace zřetězení
  • xy je řetězec, který vznikne připojením řetězce y za řetězec x
  • je asociativní, není komutativní
  • ε je jednotkový prvek
  • |x| je délka řetězce x (počet symbolů)
• formální jazyk L je libovolná podmnožina množiny všech řetězců nad abecedou T: L ⊂ T*
• operace nad formálními jazyky:
  • obvyklé množinové operace
  • součin (zřetězení) jazyků L1 · L2 = {xy: x ∈ L1, y ∈ L2}
  • n-tá mocnina Ln = L · Ln-1, L0 = {ε}, L1 = L
  • iterace L* = ∪Ln pro n = 0 .. ∞
  • pozitivní iterace L+ = ∪Ln pro n = 1 .. ∞

• bezkontextová gramatika G:
  • G = (N, T, P, S)
    • N je konečná množina neterminálních symbolů
    • T je konečná množina terminálních symbolů (N ∩ T = ø)
    • P je konečná množina pravidel zapisovaných ve tvaru A → α, kde A ∈ N, α ∈ (N ∪ T)*
    • S je počáteční (startovací) symbol gramatiky
  • levou stranou pravidla A → α rozumíme neterminál A, pravou stranou řetězec α
  • několik pravidel se stejnou levou stranou zapisujeme též zkráceně ve tvaru A → α1 | α2 | … | αn
• regulární gramatika G:
  • je bezkontextová gramatika, ve které každé pravidlo má tvar A → aB nebo A → a, kde A,B ∈ N, a ∈ T
  • vyjímku tvoří pravidlo S → ε v případě, že S se neobjeví na pravé straně žádného pravidla

• přímá derivace
  • x ⇒ y (x přímo derivuje y), jestliže x = αAβ, y = αχβ, A ∈ N, α, β, χ ∈ (N ∪ T)* a v P existuje pravidlo A → χ
  • k-tá mocnina relace ⇒ se označuje ⇒k
  • tranzitivní uzávěr relace ⇒ se označuje ⇒+
  • reflexivně tranzitivní uzávěr relace ⇒ se označuje ⇒*
• derivací řetězce β z řetězce α délky k v gramatice G = (N, T, P, S) se nazývá posloupnost řetězců α0, α1, …, αk takových, že α = α0, αi-1 ⇒ αi pro 1 ≤ i ≤ k a αk = β
• větnou formou v gramatice G = (N, T, P, S) se nazývá řetězec α, pro který platí S ⇒* α, α ∈ (N ∪ T)*. Větná forma neobsahující neterminální symboly se nazývá věta generovaná gramatikou G
• jazyk generovaný gramatikou G je množina všech vět generovaných gramatikou G a označuje se L(G)
• gramatiky G1 a G2 jsou ekvivalentní, když generují stejný jazyk: L(G1) = L(G2)

• derivační strom v gramatice G = (N, T, P, S) má tyto vlastnosti:
  • uzly derivačního stromu jsou ohodnoceny terminálními a neterminálními symboly
  • kořen stromu je ohodnocem počátečním symbolem gramatiky
  • jestliže má uzel alespoň jednoho následníka, pak je ohodnocen neterminálním symbolem
  • jestliže n1, n2, …, nk jsou bezprostřední následnovníci uzlu n, který je ohodnocen symbolem A, a tyto uzly jsou ohodnoceny symboly A1, A2, …, Ak, pak A → A1A2…Ak je pravidlo v P
  • listy derivačního stromu tvoří zleva doprava větnou formu nebo větu v gramatice G
• gramatika G je jednoznačná, pokud pro každou větu existuje právě jeden derivační strom
• věta w se nazývá víceznačná, jestliže pro ni existují alespoň dva různé derivační stromy
• gramatika G je víceznačná, když generuje alespoň jednu víceznačnou větu

napr. věta: a+a+a (pro tuto větu lze vyvořit 2 derivační stromy → tato gramatika je víceznačná) soubor: derivacnistrom.jpg

(deterministický) Konečný automat (DKA, DFA) je pětice A = (Q, T, δ, q0, F), kde

• Q je konečná neprázdná množina stavů,
• T je vstupní abeceda,
• δ je přechodová funkce, která pro každou dvojici (stav, vstupní symbol) určuje následující stav,
• q0 z Q je počátečním stavem,
• F částí Q je množinou koncových stavů.

• konečný automat je dán:
  • konečnou množinou vnitřních stavů Q
  • konečnou vstupní abecedou T
  • přechodovou funkcí δ, což je zobrazení:
    • z Q × T do Q pro deterministický konečný automat
    • z Q × T do 2Q pro nedeterministický konečný automat
  • počátečním stavem q0
  • množinou koncových stavů F ⊆ Q
• přechodový diagram konečného automatu:
  • orientovaný graf, ve které jsou uzly ohodnoceny stavy a hrany vstupními symboly
  • z uzlu q vede hrana ohodnocená symbolem a do uzlu p, jestliže
    • p = δ(q, a) pro deterministický automat
    • p ∈ δ(q, a) pro nedeterministický automat
  • počáteční stav označíme šipkou START
  • uzly ohodnocené koncovými stavy označíme dvojitým kroužkem

Regulární gramatika generuje věty regulárního jazyka, konečný automat tyto věty přijímá (rozpoznává) - je formálním modelem procedury, jejímž vstupem je posloupnost symbolů a výstupem je odpověď, zda je vstup větou daného jazyka.

• k regulární gramatice lze vytvořit (nedeterministický) konečný automat
• nedeterministický automat lze převést na deterministický

Pozn:

Jazyk přijímaný DFA je množina všech slov, která po přečtení uvedou DFA z počátečního do nějakého koncového stavu. POZOR: Konečný automat skončí činnost po přečtení posledního vstupního symbolu a přijme tehdy, pokud se v tomto okamžiku nachází v koncovém stavu. Představa, že DFA skončí čtení po dosažení koncového stavu je NESPRÁVNÁ. Konečné automaty jsou schopné rozpoznat regulární jazyky.

Lexikální analyzátor je aplikací konečného automatu. Používá se jako první blok překladače, který čte vstupní text (program) a přemění jej na tok lexikálních elementů (tokens). Při tom vynechává nevýznamné mezery, konce řádků a komentáře. Jeho výstupem není boolská hodnota přijato/nepřijato, ale (většinou) hodnota typu integer nebo enum, která udává jaký lexikální element byl načten. Přikladem lexikálního elementu je číslo, identifikátor, if, =, := a pod. Základní rozdíly mezi konečným automatem (KA) a lexikálním analyzátorem (LA) jsou:

1. KA přečte celý zadaný vstupní řetězec a na jeho konci rozhodne (svým stavem), zda řetězec patří do daného jazyku. LA přečte pouze část řetězce (tj. LA je volán pro zadaný řetězec opakovaně nějakou vyšší vrstvou překladače) a vrací jaký jeden načtený lexikální element nalezl, případně chybu, pokud nenalezl (nerozpoznal) žádný.
2. KA končí poté, co přečte celý svůj vstup. LA naproti tomu skončí čtení vstupu, pokud již nemůže provést žádný další přechod. Pokud byl LA v okamžiku, kdy již nemohl provést následující přechod v koncovém stavu, vrací „nalezen lexikalni element xxx“ (kde xxx zaleží na tom, ve kterém z koncových stavů se LA nacházel), pokud v koncovém stavu nebyl, vrací chybu (nerozpoznaný žádný lexikální element, obvykle se to projeví chybou překladače „syntax error“ nebo „unrecognized statement“).
3. LA přeskakuje komentáře a nevýznamné mezery.
4. LA může provádět sémantické akce, počítat hodnoty atributů. Příkladem je lexikální element cislo, který míva atribut hodnota.
5. LA může být spojen s preprocesorem, rozpoznávat bloky podmíněného překladu (#ifdef … #endif ) a expandovat makra.

Podobně jako KA, i LA můžeme realizovat pomocí tabulky přechodů nebo řídící struktury.

• vstup = pravá regulární gramatika G = (N, T, P, S)
• výstup = nedeterministický konečný automat M = (Q, T, δ, q0, F), pro který platí L(M) = L(G)

1. množina stavů Q = N ∪ {K}, K ∉ N
2. vstupní abeceda automatu M je rovna množině terminálních symbolů T gramatiky G
3. zobrazení δ sestrojíme takto:
   1. je-li v P pravidlo A → aB, pak δ(A, a) obsahuje B
   2. je-li v P pravidlo A → a, pak δ(A, a) obsahuje K
4. q0 = S
5. jestliže je v P pravidlo S → ε, pak F = {S, K}, jinak F = {K}

• vstup = nedeterministický konečný automat M = (Q, T, δ, q0, F)
• výstup = ekvivalentní deterministický konečný automat M' = (Q', T, δ', q0', F')

1. definujeme Q' = q0, stav {q0} považujeme za neoznačený
2. jestliže v Q' jsou již všechny stavy označeny, pokračujeme krokem 4
3. vybereme z Q' neoznačený stav q' a provedeme tyto operace:
   1. definujeme přechodovou funkci δ'(q', a) pro všechna a ∈ T takto: δ'(q', a) = ∪δ(p, a) pro každý stav p ∈ q'
   2. přidáme do Q' každý stav δ'(q', a), který v ní ještě není, a stav q' označíme
   3. pokračujeme krokem 2
4. počáteční stav q0' je {q0}
5. množina koncových stavů F' je tvořena všemi stavy q', které obsahují alespoň jeden koncový stav q ∈ F