Úvod do lexikálnej analýzy.

Krok 1

Gramatika je usporiadaná štvorica G = (N, T, P, S), kde:

• N je množina neterminálnych symbolov,
• T je množina terminálnych symbolov,
• P je množina pravidiel,
• S je počiatočný (štartovací) symbol gramatiky.

Krok 2

Na vyjadrenie gramatiky jazyka sa väčšinou používa Backusova-Naurova forma (BNF), prípadne niektoré jej rozšírenia. Na tomto predmete to bude rozšírená Backusova-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

Pri zápisoch budeme používať tie isté operátory, aké boli použité v zápisoch regulárnych výrazov a v regulárnych jazykoch.

Ako príklad uveďme 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 naseldujúcim spôsobom ( 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"

[window]
maximized = no
width = 420
height = 300
 
[history]
store = yes
limit = 120

Krok 3

Spolu s pedagógom prediskutuje riešenia vybraných úloh z predošlého cvičenia.