Úvod do formálnych gramatík.

Krok 1

Prvá časť cvičenia je venovaná absolvovaniu zápočtového testu A. Je potrebné postupovať podľa pokynov vyučujúceho.

Krok 2

Formálne gramatiky (FG) predstavujú poslednú z pokročilých metód špecifikácie jazyka, ktorou sa budeme v rámci tohto predmetu zaoberať. Ide o tzv. generatívny spôsob špecifikácie jazyka, autorom ktorého je americký lingvista Noam Chomsky. Teraz pristúpime k definícii formálnej gramatiky a základných pojmov s ňou spojených.

Formálna gramatika je usporiadaná štvorica $G=(N,T,P,S)$ kde:

• $N$ je konečná neprázdna množina neterminálnych symbolov (neterminálov).
• $T$ je konečná množina terminálnych symbolov (terminálov), pričom $N \cap T = \emptyset$.
• $S$ je začiatočný (alebo štartovací) symbol gramatiky, pričom $S \in N$.
• $P$ je množina (prepisovacích) pravidiel, ktorá je konečnou podmnožinou množiny $(N \cup T)^* N (N \cup T)^* \times (N \cup T)^*$.

Teraz si popíšeme rozdiel medzi slovom resp. vetou a vetnou formou jazyka definovaného formálnou gramatikou.

• Slovo (veta) jazyka $w$ je ľubovoľná postupnosť (reťazec) terminálnych symbolov gramatiky, $w\in T^*$,
• Vetná forma $\alpha$ je reťazec zložený z terminálnych aj neterminálnych symbolov gramatiky, $\alpha\in (N\cup T)^*$.

Na množine vetných foriem $(N \cup T)^*$ definujeme binárnu reláciu krok odvodenia (alebo reláciu derivácie) $\Rightarrow\subseteq(N \cup T)^*$ nasledujúcim spôsobom:

$\alpha \beta \gamma \Rightarrow \alpha \delta \gamma\ $ vtedy a len vtedy, ak v $P$ existuje pravidlo $\beta \rightarrow \delta$, pričom $\alpha, \gamma, \delta \in (N \cup T)^*$ a $\beta \in (N \cup T)^* N (N \cup T)^*$.

Nech $\alpha_i \in (N \cup T)^* \text{ pre } i = 0,1,\ldots,k $. Potom hovoríme, že reťazec $ \alpha_k $ sa dá odvodiť z reťazca $ \alpha_0 $ (na $k$ krokov), ak platí, že $$ \alpha_0 \Rightarrow \alpha_1 \Rightarrow \dots \Rightarrow \alpha_k .$$

Postupnosť reťazcov $ \alpha_0 \Rightarrow \alpha_1 \Rightarrow \dots \Rightarrow \alpha_k $ sa nazýva odvodenie (alebo derivácia) reťazca $ \alpha_k $ z reťazca $ \alpha_0 $
Vyjadrovať ju budeme vo forme mocniny relácie $ \Rightarrow $ v tvare $ \alpha_0 \Rightarrow^k \alpha_k $, kde číslo $k$ predstavuje dĺžku odvodenia.

• tranzitívnym uzáverom relácie krok odvodenia nazývame reláciu $ \Rightarrow^+$, definovanú na množine vetných formiem nasledovne:
  $\alpha \Rightarrow^+ \beta$ práve vtedy, keď existuje $ n \geq 1$ také, že $ \alpha \Rightarrow^n \beta $.
• reflexívnym a tranzitívnym uzáverom relácie krok odvodenia nazývame reláciu $ \Rightarrow^*$, definovanú na množine vetných formiem nasledovne:
  $ \alpha \Rightarrow^* \beta $ práve vtedy, keď existuje $ n \geq 0$ také, že $ \alpha \Rightarrow^n \beta $.

Pričom v obidvoch prípadoch platí $ \alpha, \beta \in (N \cup T)^* $.

Jazyk $L(G)$ generovaný formálnou gramatikou $G$ je množina: $$L(G)=\{w\;|\; S \Rightarrow^* w \land w\in T^*\}.$$

Na základe tvaru prepisovacích pravidiel je možné definovať hierarchiu tried gramatík a jazykov, ktorú označujem pojmom Chomskeho hierarchia.

Nech $\alpha$ patrí množine vetných foriem obsahujúcich aspoň jeden neterminál $(N \cup T)^* N (N \cup T)^*$; $\alpha_1, \alpha_2, \beta$ patria množine vetných foriem $(N \cup T)^*$; $A,B$ patria množine neterminálov $N$ a $b$ patrí množine terminálov $T$. Na základe tvaru prepisovacích pravidiel potom rozlišujeme nasledujúce triedy formálnych gramatík a jazykov.

Lineárnu deriváciu (odvodenie) slova možno zapísať taktiež pomocou orientovanej stormovej štruktúry tzv. strom odvodenia (derivačný strom) (z angl. parse tree) pre ktorý platí:

• Každý vrchol stromu je ohodnotený symbolom z množiny $ N\cup T_\epsilon$ .
• Koreň stromu je ohodnotený začiatočným symbolom $S$.
• Ak má nejaký vrchol stromu potomkov, potom je ohodnotený symbolom z množiny $N$.
• Ak $X_1,X_2,\dots,X_k$​ sú ohodnotenia priamych potomkov vrcholu $A$, potom v $P$ musí existovať pravidlo $ A \to X_1,X_2,\dots,X_k $
• Listy stromu sú ohodnotené symbolmi z množiny $T_\epsilon$.
• Slovo $w \in T^*$ sa dá získať zreťazením ohodnotení listov stromu zľava doprava.

Okrem stromu odvodenia poznáme aj abstraktný syntaktický strom (AST) (z angl. abstract syntax tree), ktorý predstavuje štruktúrovanú reprezentáciu syntaxe programovacieho jazyka alebo výrazu, zachytávajúcu podstatnú sémantickú štruktúru bez zachovania všetkých syntaktických detailov. Abstraktný syntaktický strom spĺňa nasledujúce podmienky:

• Každý vrchol stromu reprezentuje operáciu, príkaz alebo konštrukciu jazyka.
• Koreň stromu reprezentuje hlavnú operáciu alebo konštrukciu programu.
• Vnútorné uzly predstavujú operácie alebo štruktúry (napríklad +, *, if, while).
• Listy stromu sú tvorené operandmi - terminálnymi symbolmi (napríklad číselné literály, identifikátory premenných).
• Strom zachytáva hierarchiu operácií a prioritné vzťahy medzi operáciami.
• AST neobsahuje neterminálne symboly ani pomocné syntaktické prvky (zátvorky, bodkočiarky, atď.).
• AST je jazykovo špecifický a závisí od sémantiky cieľového jazyka.

Riešenie

Ako je možné vidieť gramatika $G$ patrí do triedy bezkontextových gramatík. Vysvetlenie: Keďže všetky prepisovacie pravidlá majú na ľavej strane len jeden neterminál do úvahy pripadali len bezkontextový a regulárny typ gramatiky, keďže napríklad pravidlo $5.$ nespĺňa obmedzenia pre pravidlá regulárnej gramatiky, musí sa jednať o bezkontextový typ gramatiky.

Teraz pristúpme k odvodeniu slova. Každé odvodenie slova začína zo štartovacieho symbolu, v tomto prípade ide o neterminálny symbol E.

${}$	${}$
$\phantom{\overset{(2)}{\Rightarrow}}$E	$\overset{(2)}{\Rightarrow}$ T
${}$	$\overset{(3)}{\Rightarrow}$ T * F
${}$	$\overset{(4)}{\Rightarrow}$ F * F
${}$	$\overset{(6)}{\Rightarrow}$ id * F
${}$	$\overset{(5)}{\Rightarrow}$ id * (E)
${}$	$\overset{(1)}{\Rightarrow}$ id * (E + T)
${}$	$\overset{(2)}{\Rightarrow}$ id * (T + T)
${}$	$\overset{(4)}{\Rightarrow}$ id * (F + T)
${}$	$\overset{(6)}{\Rightarrow}$ id * (id + T)
${}$	$\overset{(4)}{\Rightarrow}$ id * (id + F)
${}$	$\overset{(6)}{\Rightarrow}$ id * (id + id)

Podľa tohto postupu odvodenia vieme zostrojiť derivačný strom.

• Koreň stromu odvodenia je tvorený začiatočným symbolom gramatiky.
• Listy sú tvorené terminálnymi symbolmi.
• Aplikácia nejakého pravidla na nejaký neterminál sa prejaví tým, že symboly na pravej strane použitého pravidla tvoria priamych potomkov prepísaného neterminálu (ľavej strany pravidla).

Abstraktný syntaktický strom je zjednodušená verzia derivačného stromu, ktorá odstraňuje neterminálne symboly a zachováva iba štruktúru výrazu.

• Koreň stromu reprezentuje hlavnú operáciu alebo konštrukciu programu.
• Listy sú tvorené operandmi (napr. 1, 2 alebo premenné).
• Vnútorné uzly reprezentujú operácie alebo štruktúry (napr. +, *, if, while).
• Je jazykovo špecifický a závisí na sémantike cieľového jazyka (napr. priorita operátorov už nie je explicitne vyjadrená).

Krok 3

Backusova-Naurova forma (BNF) predstavuje kompaktnejší spôsob zápisu pravidiel bezkontextových gramatík v nasledujúcom tvare:

$\quad\quad\quad\quad\quad\quad$<neterminal> ::= vetna-forma-1 $\;|\;\ldots \;|\;$ vetna-forma-n.

• Neterminálne symboly sú uzavreté v lomených zátvorkách, napr. <expr>.
• Terminálne symboly sú zapísané ako samostatné znaky alebo reťazce, napr. + alebo 123.
• Ľavá a pravá časť pravidla je oddelená symbolom ::= (alternatíva k symbolu $\to$).
• Pravá strana pravidla môže predstavovať taktiež prázdne slovo $\varepsilon$.
• Symbol | označuje alternatívu, pomocou ktorej zoskupujeme pravidlá s rovnakou ľavou stranou.

BNF je teda formálny spôsob zápisu syntaxe programovacích a iných formálnych jazykov.

Keďže BNF využíva symboly <, >, |, ::= vo svojej vlastnej syntaxi, zabraňuje použitiu týchto znakov v syntaxi jazykov v nej definovaných. Rozšírená Backusova-Naurova forma (EBNF) sa vysporiadava s týmto problémom striktným uzavretím všetkých neterminálov do úvodzoviek ("..." alebo '...'), na základe čoho možno lomené zátvorky pre neterminály vynechať. EBNF naviac implementuje aj štandardnú notáciu využívanú pri regulárnych výrazoch umožňujúcu ešte kompaktnejší zápis prepisovacích pravidiel:

• Pre voliteľnosť vetnej formy $\varphi$ využívame zápis [$\varphi$].
• Pre nula alebo viac opakovaní vetnej formy $\varphi$ využívame zápis {$\varphi$}.
• Pre zoskupenie vetných formiem $\varphi, \psi$ využívame zápis ($\varphi\psi$).

Teraz sa bližšie pozrieme na postup ako transformovať (rozvinúť) gramatiku z kompaktnejšej EBNF do BNF. Tento postup rozvinutia gramatiky bude zohrávať, kľučovú úlohu pri potlačení (eliminovaní) využitia iteračných konštrukcií jazyka (ako while) pri implementácii syntaxou riadeného interpretátora.

• odstránenie opakovania
  Nech A $\in N$; $R_1,R,R_2$ sú reguláry nad $N\cup T$ a
  

je pravidlo v EBNF. Na transformáciu tohto pravidla do BNF je opakovanie { $\beta$ } potrebné nahradiť novým neterminálom X a vytvoriť jemu odpovedajúce rekurzívne pravidlo:

• odstránenie voliteľnosti
  Nech A $\in N$; $R_1,R,R_2$ sú reguláry nad $N\cup T$ a
  

je pravidlo v EBNF. Pri transformácii tohto pravidla do BNF máme niekoľko možností:

• Nahradenie voliteľnosti [ $R$ ] novým neternimálom X spolu s jemu odpovedajúcim nerekurzívnym pravidlom:
  

• Pridanie novej alternatívy pravidla, ktorá vznikne vynechaním voliteľnosti [ $R$ ] z už existujúcej alternatívy a následné odstránenie označenia voliteľnosti:
  

Krok 4

Teraz si precvičíme konštrukciu formálnej gramatiky jazyka.

Niekedy nemáme presnú špecifikáciu jazyka, ale máme k dispozícii len fragment jazyka. Na základe týchto fragmetov sa následne snažíme odvodiť gramatiku.