Interpretátor

Ciele

Zopakovať si teóriu regulárnych výrazov a gramatík a osvojiť si teoretické základy syntaxou riadeného interpetátora.
Naučiť sa definovať gramatiku jazyka pomocou BNF.
Oboznámiť sa s príkladom implementácie syntaxou riadeného interpretátora pre aritmetické výrazy.
Naučiť sa implementovať syntaxou riadený interpretátor na základe definovanej gramatiky.

Úvod

Syntaxou riadený interpretátor

význam (sémantiku)

dostane na vstupe

Postup

Na vyjadrenie gramatiky jazyka sa väčšinou používa Backus-Naurova forma (BNF), prípadne niektoré jej rozšírenie. Na tomto predmete to bude rozšírená Backus-Naurova forma (Extended BNF).

Základnými prvkami gramatiky sú pravidla a symboly. Pričom symboly môžu byť terminálne (také, ktoré môžu byť prítomné na vstupe), alebo neterminálne. Pravidla budeme zapisovať v takomto tvare:

neterminal → postupnosť symbolov a operátorov

Pritom budeme používať tie isté operátory aké boli použité v regulárnych jazykoch.

`\|`	alternatíva
`{}`	opakovanie 0 alebo viac krát
`[]`	voliteľnosť

Majme napríklad jazyk pre vyjadrenie štruktúr údajov (entít), s ktorými pracuje aplikácia. Pre každú štruktúru, je uvedený jej názov a zoznam vlastností spolu s ich typmi. Napríklad firemná aplikácia môže pracovať s údajmi o oddeleniach a osobách. Na vyjadrenie toho, že niektoré vlastností sú povinné, je možné použiť kľúčové slovo "required". Veta v tomto jazyku môže teda vyzerať napríklad takto:


entity Person
    name : string required
    age : int
    salary : real
end
entity Department
    name : string required
    description : string
end

Gramatiku tohto jazyka môžeme vyjadriť napríklad tak (id a reťazce v úvodzovkách predstavujú terminálne symboly):


Entities → { Entity }
Entity   → "entity" id { Property } "end"
Property → id ":" Type [ "required" ]
Type     → "int" | "real" | "string"

Príklad: Definujte sytnax jazyka konfiguračných parametrov. Parametre majú tvar " názov = hodnota", pričom hodnota môže byť celé číslo, alebo pravdivostná hodnota označená kľučovým slovom yes alebo no. Parametre sú zaradené do sekcií a každá sekcia musí začínať názvom uvedeným v hranatých zátvorkach. Príklad:


[window]
maximized = no
width = 420
height = 300

[history]
store = yes
limit = 120

Na základe gramatiky jazyka je možné implementovať jeho syntaktický analyzátor. Jedným zo spôsobov ako to realizovať je vytvorenie rekurzívneho analyzátora pracujúceho metódou zhora-nadol. Hlavným princípom jeho implementácie je vytvorenie funkcie pre každé pravidlo gramatiky, kde postupnosť krokov v tele funkcie zodpovedá postupnosti symbolov na pravej strane pravidla. Preštudujte si schému implementácie takéhoto syntaktického analyzátora v tabuľke dole.

Tab.: : Schéma implementácie syntaktického analyzátora

EBNF	Implementácia
`A → ...`	Definícia `A() { ... }`
Neterminal A	Volánie `A()`
Terminal `a`	`if (symbol == a) next_symbol();`
`{ X }`	`while (symbol == first(X)) { ... }`
`[ X ]`	`if (symbol == first(X)) { ... }`
`X \| Y \| Z`	`switch (symbol) { case first(X): ... }`

Následne sa proces analýzy spustí prečítaním prvého lexikálneho symbolu a zavolaním funkcie štartovacieho symbolu gramatiky.

Preštudujte si kód realizujúci syntaxou riadený interpretátor, spustíte ho a otestujte rôzne príklady.
Gramatika priloženého príkladu interpretátora vyzerá nasledovne (terminálne symboly sú v úvodzovkách):
```
Expr → Term {("+" | "-") Term}
Term → value | "(" Expr ")"
```
Každé pravidlo gramatiky je reprezentované jednou funkciou v programe.
Úloha: Upravte gramatiku tak, aby bolo nutné zadať kľúčové slovo print pred výrazom. Dá sa to dosiahnuť pridaním nového pravidla, ktoré sa zároveň stane štartovacím:
```
Print → "print" Expr
```
Upravte interpretátor tak, aby odzrkadľoval túto zmenu.
Je potrebné vytvoriť interpretátor programov v tvare:
```
read a, b  print a - b + 10
```
Tento výraz sa musí interpretovať tak, že program vyžiada hodnoty premenných a a b od používateľa a vypíše výsledok vypočítaného výrazu. Jeho výstup teda bude nasledovný (tučným je vyznačený vstup používateľa):
```
a = 10
b = 5
Vysledok: 15
```
Úloha: Upravte gramatiku tak, aby zodpovedala očakávanému tvaru programu: jeden príkaz read nasledovaný jedným príkazom print.

Úloha: Doplňte kód syntaktického analyzátora a interpretátora tak, aby zodpovedal novej gramatike.
Pre ukladanie hodnôt premenných a ich načítanie od používateľa môžete použiť nasledovný kód:
```
/* Tabulka premennych:
 * index -- index identifikatora, hodnota -- hodnota premennej */
int variables[LEX_IDS_MAX];

void read_variable(int id_idx)
{
    int value;
    printf("%s = ", lex_ids[id_idx]);
    scanf("%d", &value);
    variables[id_idx] = value;
}
```