Skip to content

Latest commit

 

History

History
197 lines (112 loc) · 12.7 KB

09_gramatiky.md

File metadata and controls

197 lines (112 loc) · 12.7 KB
Raw

9. - Gramatiky

Gramatiky, Chomského hierarchie, vztah gramatik ke konečným strojům.

Gramatika se skládá z množiny pravidel, pomocí kterých může být každé slovo předepsaným způsobem vygenerováno z předem daného počátečního symbolu. Máme nějakou abecedu symbolů (řekněme třeba a, b), což odpovídá terminálním symbolům. Dále máme nějaké proměnné zvané též neterminální symboly, například X, Y. Pak potřebujeme počáteční proměnnou, ze které je možné odvodit všechna slova, která umí gramatika generovat. Řekněmě, že počáteční symbol bude X. Nakonec k tomu přidáme přepisovací pravidla, pomocí kterých je možné přepisovat terminální a neterminální symboly na jiné. Generování probíhá tak, že vezmeme počáteční symbol, na něj aplikujeme kterékoli z pravidel, na získaný řetězec opět aplikujeme kterékoli z pravidel a tak dále, dokud nevygenerujeme požadované slovo. Pokud je pro každé slovo nejvýše jeden postup generování, gramatika je jednoznačná.

Formální definice:

Gramatika G je uspořádaná čtveřice G = (\Pi, \Sigma, S, P), kde

\Pi je množina neterminálů,

\Sigma je množina terminálů, \Pi \cap \Sigma = \varnothing (terminální a neteminální symboly jsou odlišné),

S \in \Pi je počáteční neterminál,

P je konečná množina přepisovacích pravidel.

Konvence:

  • jednotlivé terminály značíme – a, b, c, …
  • řetězce terminálů značíme – u, v, w, …
  • jednotlivé neterminály – A, B, C … X, Y, Z
  • řetězce neterminálů a terminálů – α, β, γ, …
  • prázdný řetězec značíme symbolem e nebo také ε

Přepisovací pravidla

Pravidla mají tvar \alpha \rightarrow \beta , kde \alpha, \beta \in (\Pi \cup \Sigma)*.

To znamená, že pomocí přepisovacích pravidel můžu změnit řetězec \alpha, který může být složen z terminálních i neterminálních symbolů na řetězec \beta, který zase může obsahovat libovolné terminální a neterminální symboly (nebo prázdné slovo y).

Příklady pravidel

Pravidlo Popis
X \rightarrow a neterminál X se přepíše na a
X \rightarrow Y neterminál X se přepíše na neterminál Y
X \rightarrow a | Y neterminál se X přepíše buď na terminál a nebo na neterminál Y (spojení více pravidel do jednoho)
aX \rightarrow ba terminál a následovaný neterminálem X se přepíše na terminální symboly ba

Příklad gramatiky

G = (\Pi, \Sigma, S, P)

\Pi = {S}

\Sigma = {a, b}

P = { S \rightarrow aSb, S\rightarrow ab }

Taková gramatika generuje jazyk

L(G) = {a^nb^n, n \in \mathbb{N}}

Funguje to tak, že vycházím z počátečního symbolu, zde S. Postupně používám různá pravidla, abych vygeneroval slovo, které chci získat. Třeba pro získání aaabbb by to probíhalo následovně:

\mathbf{S} \Rightarrow a\boldsymbol{S}b \Rightarrow aa\mathbf{S}bb \Rightarrow aaabbb

Což se dá zapsat jako S \Rightarrow^*_G aaabbb (S se přepíše pomocí gramatiky G na aaabbb).

Přepisovací systém

u \Rightarrow v ... u se přímo přepíše na v

u \Rightarrow^* w ... u se přepíše na w (nevypisují se jednotlivé kroky, ale pouze počátek a konec)

\Rightarrow^* je **reflexivní a tranzitivní binární relace (viz níže - vlastnosti relací)

Generativní gramatika

Pro analýzu shora dolů se používají generativní gramatiky. Shora dolů znamená, že mám počáteční symbol S, ze kterého vytvářím nějaké slovo, tedy:

S \Rightarrow \ldots \Rightarrow aabbcc

Generativní gramatiky jsou ty, co byly popsány výše.

Analytické gramatiky

Pro analýzu zdola nahoru se používají analytické gramatiky. Zdola nahoru znamená, že vycházím z nějakého slova a snažím se získat počáteční symbol, tedy:

aabbcc \Rightarrow \ldots \Rightarrow S

Analytické gramatiky se od generativních liší tak, že u přepisovacích pravidel (ve formátu \alpha \rightarrow \beta) obsahuje \beta alespoň jeden neterminál.

Jazyk L rozpoznávaný analytickou gramatikou G je potom:

L(G) = {w \in \Sigma^, w \Rightarrow^_G S}

Chomského hierarchie

Gramatiky se dělí na základě omezení přepisovacích pravidel do několika typů podle Chomského hierachie. Ta definuje následující typy gramatik:

Chomskeho hierarchie

Důležité je si uvědomit, že regulární gramatika je zároveň i bezkontextová, kontextová i typu 0. Stejně tak třeba kontexová gramatika je zároveň i typu 0. Všechny gramatiky jsou tím pádem typu 0.

Různé typy gramatik jsou schopné rozpoznávat různé typy jazyků a pro jejich implementaci je potřeba jiný typ konečného stroje. Výhodou gramatik vyšších typů je právě fakt, že jejich implementace je jednodušší. Následující tabulka znázorňuje typy gramatik, jazyků, strojů pro implementaci a omezení pro přepisovací pravidla.

Gramatika Jazyky Konečný stroj Formát přepisovacích pravidel
Typ 0 Rekurzivně spočitatelné TS, PS, KSZ2 \alpha \rightarrow \beta (žádná omezení)
Kontextová (typ 1) Kontextové \alpha A \beta \rightarrow \alpha \gamma \beta
Bezkontextová (typ 2) Bezkontextové nedeterministický KSZ1 A \rightarrow \gamma
Regulární (typ 3) Regulární KA A \rightarrow a, A \rightarrow aB

U přepisovacích pravidel platí konvence:

  • písmena řecké abecedy \in (\Pi \cup \Sigma)*
  • velká písmena představují neterminální symboly
  • malá písmena představují terminální symboly

Vztah ke konečným strojům

Viz předchozí tabulka. Připomenutí:

Turingův stroj (TS)

  • čtecí hlava, nekonečná páska, program
  • na pásce se lze pohybovat doleva/doprava, je možné číst a zapisovat

Postův stroj (PS)

  • pamět je typu fronta (FIFO)
  • z jednoho konce se čte, z druhého se zapisuje

Konečný stroj se zásobníky (KSZn)

  • paměť je typu zásobník (LIFO)
  • zapisuje se i se čte z vrcholu zásobníku
  • pokud má alespoň 2 zásobníky, dokáže to,co TS nebo PS

Zásobníkový automat (KSZ1)

  • jiné označení pro KSZ1
  • konečný stroj s jedním zásobníkem nedokáže to, co TS, PS nebo KSZ2+

Konečný automat (KA)

  • žádná paměť pro zápis
  • pouze si pamatuje (se nachází v) aktuální stav

Vlastnosti binárních relací

Není to úplně součástí otázky, ale mohla by na to přijít řeč. Je to dobré vědět, ale pokud se na to někdo vyložené nezeptá, asi bych to nezmiňoval.

Pro libovolnou binární relaci mohou (a nemusí) platit následující vlasnosti.

Nechť \varrho je binární relace.

  1. Reflexivita

\forall a \in A: a \varrho a

Všechny prvky z A jsou v relaci samy se sebou.

  1. Symetrie

\forall a, b \in A: a \varrho b \leftrightarrow b \varrho a

Pokud a je v relaci s b, potom i b je v relaci s a. (nebo právě tehdy když - zde to lze zaměnit)

  1. Antisymetrie

\forall a, b \in A: a \varrho b \wedge b \varrho a \rightarrow a = b

Pokud a je v relaci s b a zároveň je i b v relaci s a, potom se jedná o totožný prvek.

  1. Tranzitivita

\forall a, b, c \in A: a \varrho b \wedge b \varrho c \rightarrow a \varrho c

Pokud a je v relaci s b a zároveň je b v relaci s c, potom je i a v relaci s c.

Relace ekvivalence

Pro relaci ekvivalence \sim platí:

  • reflexivita
  • symetrie
  • tranzitivita

K libovolné relaci ekvivalence existuje právě jediný rozklad na třídy ekvivalence.

Částečné uspořádání

Pro relaci částečného uspořádání \leq platí:

  • reflexivita
  • antisymetrie
  • tranzitivita

Syntaktická analýza

Příklad syntaktické analýzy

Příklad syntaktické analýzy