Krok 1

Formálne gramatiky 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)^*$.

Neterminálne symboly sú pomocné symboly používané v pravidlách gramatiky. Tieto symboly sú postupne nahrádzané (substituované) počas procesu zvaného derivácia alebo odvodzovanie. Štandardne sa označujú veľkými písmenami latinskej abecedy, napríklad A, B, C, alebo sú uzavreté v lomených zátvorkách, napríklad <program>, <term>, <boolen-term> (BNF štandard).

Terminálne symboly, taktiež označované ako lexémy, tvoria abecedu výsledného jazyka. Zvyčajne sa zapisujú malými písmenami latinskej abecedy, napr. a, b, c, alebo sa uvádzajú v úvodzovkách, napríklad "while","if","+" (EBNF štandard).

Prepisovacie pravidlá definujú, ako môžu byť reťazce pozostávajúce z terminálnych a neterminálnych symbolov prepisané na iné reťazce. Tieto reťazce, teda prvky množiny $(N \cup T)^*$, budeme vo všeobecnosti označovať písmenami gréckej abaecedy.

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)^+\times(N \cup T)^*$ nasledujúcim spôsobom:

$\alpha \beta \gamma \Rightarrow \alpha \delta \gamma\ $ vtedy a len vtedy, keď 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.

V odvodení pritom vystupujú dva typy reťazcov, ktoré sa od seba líšia mierou úplnosti odvodenia:

• Slovo alebo tiež veta jazyka $w$ je reťazec zložený výlučne z terminálnych symbolov, $w\in T^*$ odvoditeľný zo začiatočného symbolu gramatiky $S$. Jazyk $L(G)$ generovaný formálnou gramatikou $G$ je množina všetkých takýchto slov, pre ktoré platí: $$L(G)=\{w \mid S \Rightarrow^* w \land w\in T^*\}.$$
• Vetná forma $\alpha$ je reťazec $\alpha \in (N \cup T)^*$ zložený z terminálnych aj neterminálnych symbolov, ktorý je odvoditeľný zo začiatočného symbolu $S$.

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

Nech $\alpha$ patrí množine reťazcov terminálnych a neterminálnych symbolov obsahujúcich aspoň jeden neterminálny symbol $(N \cup T)^* N (N \cup T)^*$; $\alpha_1, \alpha_2, \beta$ patria množine reťazcov terminálnych a neterminálnych symbolov $(N \cup T)^*$; $A,B$ patria množine neterminálnych symbolov $N$ a $b$ patrí množine terminálnych symbolov $T$. Na základe tvaru prepisovacích pravidiel potom rozlišujeme jednotlivé triedy formálnych gramatík a jazykov preyentované v nasledujúcej tabuľke.

Medzi jazykmi generovanými jednotlivými typmi gramatík platí nasledujúci vzťah: $$ L(G_3) \subseteq L(G_2) \subseteq L(G_1) \subseteq L(G_0) .$$

Lineárnu deriváciu slova je možné zapísať taktiež pomocou orientovanej stormovej štruktúry, ktorá sa nazýva strom odvodenia (derivačný strom) (z angl. parse tree) a pre ktorú platia nasledujúce pravidlá:

• každý vrchol stromu je ohodnotený symbolom z množiny $ N\cup T_\varepsilon$,
• 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_\varepsilon$,
• slovo $w \in T^*$ sa dá získať zreťazením ohodnotení listov stromu zľava doprava.

Okrem stromu odvodenia poznáme aj strom abstraktnej syntaxe (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. Pre štruktúru AST platia nasledujúce pravidlá:

• 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),
• vyjadruje hierarchiu operácií a prioritné vzťahy medzi operáciami,
• neobsahuje neterminálne symboly ani pomocné syntaktické prvky (zátvorky, bodkočiarky, atď.),
• 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 prichádzajú len bezkontextový a regulárny typ gramatiky. Napríklad pravidlo $5.$ však nespĺňa obmedzenia pre pravidlá regulárnej gramatiky a daná gramatika je preto bezkontextová.

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.

V tomto príklade môžeme pozorovať nasledujúce vlastnosti stromu odvodenia:

• koreň stromu odvodenia je tvorený začiatočným symbolom gramatiky,
• listy sú tvorené terminálnymi symbolmi,
• aplikácia vybraného pravidla na konkrétny 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.

V porovnaní so stromom odvodenia môžeme pozorovať nasledujúce vlastnosti AST:

• koreň stromu reprezentuje hlavnú operáciu alebo konštrukciu programu,
• listy sú tvorené operandmi (numerály 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 2

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

Autorom pôvodnej formy je John Backus (Obrázok 4 vľavo), ktorý ju prvýkrát použil na opis syntaxe programovacieho jazyka ALGOL 60. Následne ju Peter Naur (Obrázok 4 vpravo) rozšíril a zdokonalil, čím získala dnešnú podobu.

BNF má nasledujúce vlastnosti.

• Neterminálne symboly, v BNF označované ako metajazykové premenné alebo taktiež syntaktické triedy/kategórie 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ázdny reťazec $\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 tak použitiu týchto znakov v syntaxi jazykov v nej definovaných. Rozšírená Backusova-Naurova forma (EBNF) sa vysporadúva s týmto problémom striktným uzavretím všetkých terminá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ť reťazca symbolov $\alpha$ využívame zápis [$\alpha$],
• pre nula alebo viac opakovaní reťazca symbolov $\alpha$ využívame zápis {$\alpha$},
• pre zoskupenie reťazcov symbolov $\alpha, \beta$ využívame zápis ($\alpha\beta$).

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 voliteľnosti – nech A $\in N$; $R_1,R,R_2$ sú regulárne výrazy nad $N\cup T$ a nech
  

je pravidlo v EBNF. Pri transformácii tohto pravidla do BNF máme niekoľko možností. Jenou z nich je nahradiť voliteľný výraz [$R$] novým neternimálom X a zaviesť preň nasledujúce nerekurzívne pravidlá:

Druhou množnosťou je pridanie novej alternatívy pravidla, ktorá vznikne vynechaním voliteľnosti [$R$] z už existujúcej alternatívy a odstránenie označenia voliteľnosti nasledujúcim spôsobom:

• Odstránenie Kleeneho uzáveru – nech A $\in N$; $R_1,R,R_2$ sú regulárne výrazy nad $N\cup T$ a nech
  

je pravidlo v EBNF. Pri transformácii tohto pravidla do BNF je Kleeneho uzáver { $R$ } potrebné nahradiť novým neterminálom X a vytvoriť jemu zodpovedajúce ľavo alebo pravo rekurzívne pravidlo:

• Odstránenie zoskupenia – nech A $\in N$; a nech $R_1,R,R_2$ sú regulárne výrazy nad $N\cup T$. Uvažujme pravidlo v EBNF v tvare

Pri transformácii tohto pravidla do BNF zoskupenie ( $R$ ) nahradíme novým neternimálnym symbolom X spolu s jemu zodpovedajúcim pravidlom:

Krok 3

V tomto kroku pristúpime ku konštrukcii 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.

Krok 4

Pri návrhu programovacích jazykov a vyhodnocovaní výrazov zohrávajú dôležitú úlohu dva základné koncepty, ktoré určujú spôsob, akým sa výrazy analyzujú a vyhodnocujú. Sú to

• priorita a
• asociativita operátorov.

Tieto vlastnosti možno vyjadriť už na úrovni syntaktického modelu jazyka (gramatiky),, čo vysvetlíme podrobnejšie v nasledujúcom kroku.

Špecifikácia priority operátorov

Priorita operátorov určuje, ktoré operácie majú prednosť pri vyhodnocovaní výrazov. Štandardne má napríklad operácia násobenia vyššiu prioritu ako operácia sčítania. Preto sa výraz 1+2*3 vyhodnotí na hodnotu $7$ a nie $9$. Pri syntaktickej špecifikácii priority operátorov v gramatike sa budeme riadiť nasledujúcimi pravidlami:

1. Pre každú úroveň priority operácii definujeme samostatný neterminálny symbol.
2. Pravidlá sa pre jednotlivé úrovne (neterminálne symboly) zreťazia tak, že smerom dovnútra (vnáranie k operandom) sa zvyšuje priorita.

Demonštrujme tento postup na nasledujúcom príklade gramatiky aritmetických výrazov.

Nech $G$ je gramatika $(\{$E, T, F$\},\{$+, *, (, )$\}$,$P$,E$)$, kde množina prepisovacích pravidiel v EBNF $P$ je daná nasledovne:

1. najvyššia úroveň priority: zátvorky (spracovávané v F),
2. stredná úroveň priority: násobenie (spracovávané v T),
3. najnižšia úroveň priority: sčítanie (spracovávané v E).

Porovnajme vplyv tvaru gramatiky na prioritu operátorov prostredníctvom zostrojenia stromov odvodenia pre ten istý syntaktický zápis aritmetického výrazu 1+2*3.

Špecifikácia asociativity operátorov

Asociativita operátorov zohráva dôležitú úlohu v prípadoch, keď sa v sekvencii vyskytne viacero operátorov s rovnakou prioritou. Určuje totiž, v akom poradí sa tieto operácie budú vyhodnocovať. Napríklad v aritmetických výrazoch:

• Ľavá asociativita: výraz 5−3−2 sa vyhodnotí ako (5−3)−2=0.
• Pravá asociativita: výraz 2^2^3 sa vyhodnotí ako 2^(2^3)=256. Doplníme, že ľavá asociativita by nebola pri umocňovaní užitočná – rovnaký výsledok sa dá dosiahnúť vďaka pravidlám pre mocniny pomocou súčinu exponentov (2^2)^3=2^(2*3).
• Neasociatívne operátory: operátory porovnania.

Pri implementácii syntaktického analyzátora pomocou rekurzívnych funkcií sa asociativita vyjadruje tvarom pravidiel gramatiky, a to nasledovne:

Porovnajme vplyv tvaru gramatiky na asociativitu operátorov prostredníctvom zostrojenia stromov odvodenia pre ten istý syntaktický zápis aritmetického výrazu 2^2^3.