Kompletní studijní scripta s vysvětlením, příklady a procvičováním. Vše krok za krokem.
Gramatika je formální způsob, jak popsat (generovat) jazyk — tedy množinu slov. Místo toho, abychom vypisovali každé slovo zvlášť, zapíšeme pravidla, podle nichž se slova sestavují.
Představ si, že máš šablonu: „věta = podmět + přísudek". To je pravidlo. Gramatika v teorii jazyků funguje stejně — máš neterminály (zástupné symboly jako „věta", „podmět") a terminály (skutečná písmena/slova). Pravidla říkají, jak neterminály nahradit.
Chceme popsat jazyk plně uzávorkovaných aritmetických výrazů jako:
Abeceda jazyka: Σ = {0,1,2,...,9, +, -, *, /, (, )}
Induktivní definice pomocí pravidel:
Bezkontextová gramatika je čtveřice G = (Π, Σ, S, P), kde:
| Součást | Co to je | Příklad |
|---|---|---|
| Π | Neterminály — "zástupné" symboly | {A, B, C} nebo {S, E, T} |
| Σ | Terminály — skutečné znaky výsledného slova | {a, b} nebo {0..9, +, -, *, /} |
| S | Startovací neterminál — od něj se začíná | A nebo S nebo E |
| P | Pravidla tvaru A → α (neterminál → řetězec) | A → aBBb, B → ε |
U bezkontextových gramatik může být na pravé straně pravidla cokoliv — libovolný řetězec terminálů a neterminálů. U regulárních gramatik je pravá strana omezena (max. jeden neterminál, vždy na kraji).
„Bezkontextové" = pravidlo A → α lze použít bez ohledu na kontext kolem A.
Více pravidel se stejnou levou stranou:
Místo tří oddělených pravidel A→α₁, A→α₂, A→α₃.
G = (Π, Σ, A, P), kde Π = {A, B, C}, Σ = {a, b}, startovní symbol = A:
Řetězec α lze jedním krokem přepsat na α', tj. α ⇒ α', právě když:
α = β₁Aβ₂ a α' = β₁γβ₂ pro nějaká β₁, β₂, γ ∈ (Π ∪ Σ)* a A ∈ Π, kde (A → γ) ∈ P.
Jinými slovy: vyber jeden neterminál v řetězci, nahraď ho pravou stranou nějakého jeho pravidla.
Máme pravidlo B → bCA. Pak:
Neterminál B byl nahrazen řetězcem bCA.
V každém kroku nahrazujeme nejlevější neterminál.
V každém kroku nahrazujeme nejpravější neterminál.
Každému derivačnímu stromu odpovídá právě jedna levá a právě jedna pravá derivace.
Gramatika: A → aBBb | AaA, B → ε | bCA, C → AB | a | b
Derivace lze znázornit jako strom. Každý derivační strom odpovídá jedné nebo více derivacím (záleží na pořadí nahrazování neterminálů).
Zjednodušená vizualizace — plný strom z přednášky má ještě b jako list pravého B.
L(G) = { w ∈ Σ* | S ⇒* w }
Jazyk gramatiky G je množina všech slov nad terminální abecedou Σ, která lze odvodit z počátečního neterminálu S.
Jazyk L je bezkontextový, jestliže existuje bezkontextová gramatika G taková, že L = L(G).
Řetězce α ∈ (Π ∪ Σ)*, pro které platí S ⇒* α, se nazývají větné formy. Jsou to mezikroky derivace (mohou obsahovat neterminály). Slova v L(G) jsou větné formy obsahující jen terminály.
L = { aⁿbⁿ | n ≥ 0 } — stejný počet a a b za sebou.
Derivace pro aabb:
Jazyk aⁿbⁿ není regulární (dokázáno pumping lemmatem). Bezkontextová gramatika ho ale pěkně zachytí — neterminál S si „pamatuje", kolik a ještě musí přidat b.
L = { w ∈ {a,b}* | w = wᴿ } — všechna palindromy nad {a,b}.
Derivace pro abaaaba:
Pravidlo aSa „obaluje" S písmenem a z obou stran — zaručuje symetrii.
L = všechna dobře uzávorkovaná slova nad {(, )}. Např. (()())(()) ∈ L, ale )()) ∉ L.
L = aritmetické výrazy s operandy a, operátory + a *, závorky.
Derivace pro (a+a)*a+(a*a):
Výraz a*a+a má dva různé derivační stromy (viz sekce o nejednoznačnosti).
Gramatika G je nejednoznačná, jestliže existuje nějaké slovo w ∈ L(G), kterému přísluší dva různé derivační stromy (resp. dvě různé levé nebo dvě různé pravé derivace).
Příklad: Gramatika E → a | E+E | E*E | (E) je nejednoznačná. Pro slovo a*a+a existují dvě různé levé derivace:
Strom: + je kořen, vlevo a*a, vpravo a
Strom: * je kořen, vlevo a, vpravo a+a
Při parsování programovacích jazyků (překladače) chceme přesně jednu interpretaci. Nejednoznačnost = kompilátor neví, jak výraz vyhodnotit!
Místo nejednoznačné gramatiky E → a | E+E | E*E | (E) použijeme:
Tato hierarchie zajišťuje správnou prioritu operátorů (* váže těsněji než +) a gramatika je jednoznačná.
Pokud nelze nejednoznačnou gramatiku nahradit žádnou ekvivalentní jednoznačnou gramatikou, říkáme, že je podstatně nejednoznačná.
Průnik dvou BKJ nemusí být BKJ!
Mějme gramatiky G₁ = (Π₁, Σ, S₁, P₁) a G₂ = (Π₂, Σ, S₂, P₂), kde Π₁ ∩ Π₂ = ∅ a S ∉ Π₁ ∪ Π₂.
Přidáme nový startovní symbol S s pravidlem S → S₁S₂:
Vygeneruje nejdřív slovo z L(G₁) (přes S₁), pak z L(G₂) (přes S₂).
Přidáme nový startovní symbol S s pravidly S → S₁ a S → S₂:
Z S se dostaneme buď do G₁ nebo do G₂ — tedy vygenerujeme slova z jednoho nebo druhého jazyka.
Přidáme nový startovní symbol S s pravidly S → ε a S → S₁S:
S → S₁S umožňuje opakovat libovolněkrát, S → ε skončí.
Regulární gramatiky jsou speciálním případem bezkontextových gramatik — jejich pravidla jsou omezena na jednodušší formu.
Všechna pravidla jsou tvaru:
Neterminál je vždy vpravo.
Všechna pravidla jsou tvaru:
Neterminál je vždy vlevo.
Existují dva způsoby (levá / pravá gramatika). Každý přechod automatu δ(q, a) = p se zapíše jako pravidlo:
Přechod A →a B zapíšeme jako:
Pro přijímající stavy přidáme: A → ε
Přechod A →a B zapíšeme jako:
Pro počáteční stavy přidáme: A → ε
Někdy se povolují obecnější pravidla tvaru A → wB nebo A → w (kde w ∈ Σ*). Lze je rozložit na elementární pravidla:
Pravidlo A → abbB nahradíme:
X₁, X₂ jsou nové neterminály použité jen tady.
Otevři každý příklad a zkus si nejdřív sám odpovědět, pak koukni na řešení.
Slova jsou (případně i prázdné) posloupnosti výrazů E oddělených čárkami:
S generuje buď prázdné slovo (ε) nebo neprázdnou posloupnost přes T. T buď jeden výraz, nebo výraz + čárka + další posloupnost.
S = příkaz, T = blok, U = sekvence příkazů, F = volitelný výraz.
Postup: strom regulárního výrazu, každý uzel dostane neterminál.
G₁ a G₂ jsou ekvivalentní, pokud L(G₁) = L(G₂).
Neexistuje algoritmus, který by pro libovolné dvě BK gramatiky rozhodl, zda jsou ekvivalentní. Dokonce je nerozhodnutelné, zda L(G) = Σ*.