-
Bezkontextová gramatika
- G = (N, Σ, P, S)
- P: A → α, A ∈ N, α ∈ (N ∪ Σ)*
-
Derivační strom
- G = (N, Σ, P, S)
- S ⇒ v0 ⇒ v1 ⇒ ... ⇒ vk ⇒ δ, δ ∈ (N ∪ Σ)*
- vrcholově ohodnocený strom s těmito vlastnostmi:
- 1. vrcholy jsou ohodnoceny symboly z (N ∪ Σ)
- 2. kořen je ohodnocen symbolem S
- 3. přímé derivaci, kde i-1 ⇒ vi, i-1 = μAλ, i = μαλ, A → α ∈ P, α = X1X2...Xn, odpovídá n hran (A, Xj) z uzlu A v pořadí (A, X1), (A, X2), ..., (A, Xn) zleva doprava
- 4. ohodnocení vrcholových uzlů vytváří zleva doprava větnou formu δ
-
Levá (pravá) derivace
- G = (N, Σ, P, S)
- derivace větné formy S ⇒ v0 ⇒ v1 ⇒ ... ⇒ vk ⇒ δ, δ ∈ (N ∪ Σ)*
- jestliže byl v každém řetězci v0, v1, ..., vk přepsán nejlevější (nejpravější) neterminál, jedná se o levou (pravou) derivaci
-
Fráze větné formy
- G = (N, Σ, P, S)
- λ = αβγ je větná forma, β je fráze větné formy vzhledem k neterminálu A ⇔
- S ⇒* αAγ ∧ A ⇒+ β
- jednoduchá fráze větné formy: S ⇒* αAγ ∧ A ⇒ β
- l-fráze: nejlevější jednoduchá fráze
-
Víceznačnost gramatik
- věta w je víceznačná, pokud existuje více různých derivačních stromů, jejichž koncové uzly tvoří w
- gramatika je víceznačná, pokud generuje alespoň jednu víceznačnou větu, jinak je jednoznačná
- jazyk s inherentní víceznačností - nelze generovat jednoznačnou gramatikou
- problém víceznačnosti je nerozhodnutelný
- příklad: E → E+E | E-E | E*E | E/E | (E) | i
-
Ekvivalentní gramatiky
generují stejný jazyk
-
Nedostupný symbol
- G = (N, Σ, P, S)
- symbol X ∈ (N ∪ Σ) je nedostupý v G, pokud v G neexistuje derivace S ⇒* αXβ
- nejde vůbec derivovat z S
- výpočet množiny V dostupných symbolů
- 1. začnu z počátečního neterminálu S
- 2. přidám do množiny V všechny neterminály na pravé straně nějakých pravidel, která mají na levé straně už nalezený neterminál z V, ...
-
Zbytečný symbol
- G = (N, Σ, P, S)
- symbol X ∈ (N ∪ Σ) je zbytečný v G, pokud v G neexistuje derivace S ⇒* αXβ ⇒* zxy
- negeneruje větu
- výpočet množiny Nt generující terminální řetězce:
- 1. najdu pravidla, která mají na pravé straně pouze terminály, neterminály na levé straně pravidel přidám do Nt
- 2. najdu pravidla, která mají na pravé straně pouze terminály nebo neterminály z Nt, ...
-
Odstranění zbytečných a nedostupných symbolů
- 1. vyhodím zbytečné symboly, upravím pravidla
- 2. vyhodím nedostupné symboly, upravím pravidla
-
Odstranění ε-pravidel
- 1. nalezení neterminálů, které generují ε, Nε = {A | A ⇒+ ε}
- 2. pravidla tvaru A → αBβDγ, kde B, D ∈ Nε nahradím mrakem pravidel: A → αBβDγ | αβDγ | αBβγ | αβγ
- 3. odstraním ε-pravidla
- 4. pokud S ∈ Nε, pak přidám nový neterminál S' a pravidlo S' → S | ε
-
Jednoduché pravidlo
A → B
-
Odstranění jednoduchých pravidel
- 1. najdu pro každý neterminál A všechny neterminály, které jej derivují (NA = {B | A ⇒* B})
- 2. přidám všechny pravé strany pravidel, které mají na levé straně některý neterminál z NA k pravidlům A → ...
- 3. odstraním jednoduchá pravidla
-
Cyklus
G obsahuje cyklus, jestliže A ⇒+ A
-
Vlastní gramatika
- gramatika bez zbytečných a nedostupných symbolů, ε-pravidel a cyklů
- převod:
- 1. odstranění zbytečných a nedostupných symbolů
- 2. odstranění ε-pravidel
- 3. odstranění jednoduchých pravidel
-
-
Odstranění levé rekurze
- A → Aα | β
- se transformuje na
- A → β | βA'
- A' → α | αA'
-
Odstranění nepřímé levé rekurze
- nejdřív aplikuju A → Bα, B → β | γ ... A → βα | γα (nahrazení neterminálu pravými stranami pravidel)
- pak odstraním levou rekurzi
-
Chomského normální forma
- G = (N, Σ, P, S)
- A → BC
- A → α
- S → ε, S není na pravé straně
- převod:
- 1. ponecháme pravidla tvaru CNF
- 2. A → BCDEF... transformujeme na A → B', kde B' je buď terminál nebo nový neterminál
- 3. A → BC transformuje na A → B'C', B' a C' jsou neterminály (pokud B, C už byly neterminály, pak se ponechají)
- 4. pro nové neterminály tvaru zavedeme pravidla → C'
- 5. doplníme pravidla pro nové neterminály A' → a, pokud to mají být terminály
-
Greibachové normální forma
- G = (N, Σ, P, S)
- A → aα, a ∈ Σ, α ∈ N*
- S → ε, S není na pravé straně
- převod:
- 1. odstranění levé rekurze a ε-pravidel
- 2. nalezení lineárního uspořádání ≺ na N (A ≺ B ⇔ ∃A → Bα ∈ P)
- 3. aplikace substitucí v pořadí opačném k ≺ tak, aby byla pravidla ve tvaru A → aβ, β ∈ (N ∪ Σ)*
- 4. převod pravidel tvaru A → aβ na A → aα, α ∈ N*
|
|