21 - Bezkontextové jazyky a jejich modely

Bezkontextové gramatiky
Zásobníkové automaty

1. Bezkontextová gramatika

Bezkontextová gramatika (BKG) je čtveřice G = (N, T, P, S), kde:

N je abeceda neterminálů
T je abeceda terminálů, přičemž N ∩ T = ∅
P je konečná množina pravidel tvaru A → x, kde A ∈ N, x ∈ (N ∪ T)*
S ∈ N je počáteční neterminál

Derivační krok

Nechť G = (N, T, P, S) je BKG. … Máme nějakou bezkontextovou gramatiku
Nechť u, v ∈ (N ∪ T)* … Dále máme 2 řetězce u a v, které se skládají z terminálů a neterminálů naší gramatiky
a p = A → x ∈ P. a ještě máme jedno pravidlo p, které říká, že neterminál A se dá přepsat terminálem x

Potom, uAv přímo derivuje uxv za použití p v G, zapsáno uAv ⇒ uxv [p] nebo zjednodušeně uAv ⇒ uxv.
Jednoduše řečeno - posloupnost uAv můžeme přepsat na uxv díky pravidlu p

Pokud bude derivačních kroků více za sebou, budeme jim říkat Sekvence derivačních kroků a značit ⇒ⁿ, kde n nám bude říkat, v kolika derivačních krocích přeměníme jednu posloupnost terminálů/neterminálů na druhou

Nechť:
aAb ⇒ aaBbb [1: A → aBb]
aaBbb ⇒ aacbb [2: B → c]
Potom:
aAb ⇒² aacbb [1 2]
aAb ⇒⁺ aacbb [1 2]
aAb ⇒^* aacbb [1 2]

Generovaný jazyk, BK jazyk

Nechť G = (N, T, P, S) je BKG. Jazyk generovaný BKG G, L(G), je definován: L(G) = {w: w ∈ T*, S ⇒* w}
Máme nějakou posloupnost terminálů w. Pokud dokážeme v nějaké sekvenci derivačních kroků přepsat startovací neterminál naší BKG do této posloupnosti terminálů, je tento jazyk generovaný naší BKG.

Bezkontextový jazyk je jazyk, pro který existuje bezkontextová gramatika, která tento jazyk generuje.

Pravidlový strom

grafické znázornění jednotlivých pravidel
použití jednotlivých pravidel znázorníme derivačním stromem (skládá se z pravidlových stromů)
k sestavení derivačního stromu nás může dovést více řešení - my se budeme zajímat o následující dvě:
1. Nejlevější derivace ⇒_lm - přepisujeme vždy nejlevější neterminál
2. Nejpravější derivace ⇒_rm - přepisjeme vždy nejpravější neterminál
- všimněte si, že jsme došli ke stejnému řešení

Nejlevější derivace	Nejpravější derivace

Nechť G = (N, T, P, S) je BKG. Následující 3 jazyky jsou totožné:

{w: w ∈ T*, S ⇒_lm^* w}
{w: w ∈ T*, S ⇒_rm^* w}
{w: w ∈ T*, S ⇒* w} = L(G)^*

Nejednoznačnost BKG

Nechť G = (N, T, P, S) je BKG. Pokud existuje řetězec x ∈ L(G) s více jak jedním derivačním stromem, potom G je nejednoznačná. Jinak G je jednoznačná.

2. Zásobníkový automat

je to Konečný automat rozšířený o zásobník

Zásobníkový automat (ZA) je sedmice: M = (Q, Σ, Γ, R, s, S, F), kde:

Q je konečná množina stavů
Σ je vstupní abeceda
Γ je zásobníková abeceda
R je konečná množina pravidel tvaru Apa → wq, kde A ∈ Γ, p, q ∈ Q, a ∈ Σ ∪ {ε}, w ∈ Γ*
s ∈ Q je počáteční stav
S ∈ Γ je počáteční symbol na zásobníku
F ⊆ Q je množina koncových stavů

Grafický popis	Výpočet

Přechod ZA

jeden výpočetní krok ZA
značíme |- … např. xApay |– xwqy [r]
více přechodů za sebou - sekvence přechodů

Přijímaný jazyk

Nechť M = (Q, Σ, Γ, R, s, S, F) je ZA.
1.) Jazyk přijímaný ZA M přechodem do koncového stavu, značen jako L(M)_f, je definován:
L(M)_f = {w: w ∈ Σ*, Ssw |–* zf, z ∈ Γ*, f ∈ F}
2.) Jazyk přijímaný ZA M vyprázdněním zásobníku, značen jako L(M)_ε, je definován:
L(M)_ε = {w: w ∈ Σ*, Ssw |–* zf, z = ε, f ∈ Q}
3.) Jazyk přijímaný ZA M přechodem do koncového stavu a vyprázdněním zásobníku, značen jako L(M)_fε, je definován:
L(M)_fε = {w: w ∈ Σ*, Ssw |–* zf, z = ε, f ∈ F}

Všechny tři jazyky jsou ekvivalentní:

L = L(M_f)_f pro ZA M_f ⇔ L = L(M_fε)_fε pro ZA M_fε
L = L(M_ε)_ε pro ZA M_ε ⇔ L = L(Mf_ε)_fε pro ZA M_fε
L = L(M_f)_f pro ZA M_f ⇔ L = L(M_ε)_ε pro ZA M_ε

Deterministický zásobníkový automat

z každé konfigurace lze provést pouze 1 přechod
ZA jsou silnější než DZA (DZA přijímá podmnožinu jazyků přijímaných ZA)

Rozšířený zásobníkový automat

zásobníkový automat, který se od obyčejného ZA liší v definici přechodu R
- konečná množina pravidel tvaru: vpa → wq, kde v, w ∈ Γ* , p, q ∈ Q, a ∈ Σ ∪ {ε}
- ze zásobníku můžeme přečíst celý řetězec a ne pouze znak

Pro každý RZA M existuje takový ZA M’, pro který platí: L(M)_f = L(M’)_f.

RZA a modely pro syntaktickou analýzu

existují dva základní přístupy:
1. SA shora dolů - z S směrem ke vstupnímu řetězci
  - porovnávací pravidlo - pro každé a ∈ Σ: přidej asa → s do R
  - expanzivní pravidlo - pro každé A → a₁…a_n ∈ P v G, přidej As → a_n…a₁s do R
2. SA zdola nahoru - ze vstupního řetězce směrem k S
  - shiftovací pravidlo - pro každé a ∈ Σ: přidej sa → as do R
  - redukční pravidlo - pro každé A → x ∈ P v G: přidej xs → As do R
  - finishovací pravidlo - #Ss → f