Ciele
- Oboznámiť sa s organizáciou cvičení predmetu Formálne jazyky.
- Zopakovať a prehĺbiť poznatky o regulárnych výrazoch.
- Prakticky precvičiť zostavenie vybraných regulárnych výrazov.
Úvod
Na tomto cvičení sa oboznámite s organizáciou cvičení a podmienkami udelenia priebežného hodnotenia (zápočtu). Následne sa oboznámite regulárnymi výrazmi a s konečno-stavovými automatmi akceptujúcimi vstup podľa zadaného regulárneho výrazu. Tieto zručnosti si prakticky overíte na cvičení.
Postup
Krok 1
Oboznámte sa s organizáciou cvičení predmetu Formálne jazyky a prekladače a podmienkami udelenia zápočtu.
Krok 2
Zopakujte si teóriu regulárnych výrazov.
Poznámka
Regulárne výrazy sa môžu zapisovať rôznymi spôsobmi. V tabuľke je v druhom stĺpci uvedený zjednodušený zápis, ktorý sa používa na tomto predmete. V treťom stĺpci je uvedený zápis, s ktorým sa najčastejšie môžete stretnúť v existujúcich implementáciách regulárnych výrazov. Väčšina zápisov regulárnych výrazov tiež ponúka viaceré skrátené zápisy pre celé skupiny znakov.
| Regulárny výraz | Zjednodušený zápis (používaný na tomto predmete) | Zápis bežný v implementáciách |
|---|---|---|
| zoskupenie (postupnosť) | (xy) |
(xy) |
| alternatíva (x alebo y) | x|y |
x|y |
| tranzitívny uzáver (0 alebo viac krát) | {x} |
(x)* |
| opakovanie (1 alebo viac krát) | x{x} |
(x)+ |
| voliteľnosť (0 alebo 1 krát) | [x] |
(x)? |
Poznámka
Postupnosť má vyššiu prioritu ako alternatíva, preto pozor napr. na prípady podobné tomuto:
a | b {c} = a | (b {c})
Najvyššiu prioritu majú zátvorky. Ich používaním môžete zabrániť nejednoznačnosti:
(a | b) {c}
Príklad
Regulárny výraz pre binárne numerály:
0 | 1 {0 | 1}
Aký tvar môžu nadobúdať binárne numerály podľa uvedeného regulárneho výrazu?
Úloha 2.1
Skonštruujte ďalšie výrazy pre binárne numerály.
Regulárne výrazy je možné zobraziť aj graficky pomocou prechodových diagramov. Princíp zostrojenia takéhoto diagramu je znázornený na obrázku.
Krok 3
Úloha 3.1
Skonštruujte regulárny výraz pre overenie zápisu identifikátora.
Zápis identifikátora má nasledujúce vlastnosti:
- identifikátor môže (a nemusí) začínať znakom $,
- následne prvý znak môže byť len malé alebo veľké písmeno latinskej abecedy,
- ďalšie znaky (ak sa v pomenovaní vyskytujú) môžu tvoriť ľubovoľnú kombináciu malých alebo veľkých písmen latinskej abecedy alebo ľubovoľné číslice.
Úloha 3.2
Skonštruujte regulárny výraz pre overenie zápisu reálneho čísla.
Zápis čísla má nasledujúce vlastnosti:
- číslo môže byť kladné alebo záporné,
- číslo môže a nemusí obsahovať desatinnú časť,
- číslo musí mať vyjadrenú celú časť na aspoň jednu platnú číslicu,
- ak číslo obsahuje aj desatinnú časť, aj tá musí byť vyjadrená na aspoň jednu platnú číslicu,
- oddeľovač celej a desatinnej časti môže byť znak desatinnej čiarky ',' alebo desatinnej bodky '.'
Ako zabezpečíte, aby numerál neobsahoval nevýznamné nuly zľava?
Úloha 3.3
Skonštruujte regulárny výraz pre overenie zápisu rodného čísla (podľa slovenskej legislatívy).
V zápise rodného čísla:
- sa môže vyskytovať oddeľovač '/', prípadne zápis neobsahuje žiaden oddeľovač,
- skupina číslic za oddeľovačom môže mať dĺžku 3 alebo 4 znaky,
- sa pri mesiacoch vyskytujú dve možné postupnosti: 01-12, 51-62.
Úloha 3.4
Skonštruujte regulárny výraz pre všetky reťazce pozostávajúce zo znakov a a b, ktorý obsahuje podreťazec abba.
Úloha 3.5
Skonštruujte regulárny výraz pre všetky reťazce pozostávajúce zo znakov x a y, v ktorých je každý výskyt znaku y bezprostredne nasledovaný postupnosťou troch znakov x.
Úloha 3.6
Skonštruujte regulárny výraz pre všetky reťazce pozostávajúce zo znakov p a q, ktoré obsahujú nepárny počet znakov q.
Úloha 3.7
Zostrojte prechodové diagramy pre regulárne výrazy z predchádzajúcich úloh.
Doplňujúce zdroje
Vizualizačné nástroje znázorňujúce proces rozpoznávania textu na základe regulárnych výrazov využívajúce znázornenie na ich prechodových diagramoch.
Poznámka
Obidva nástroje používajú alternatívny zápis regulárnych výrazov, s ktorým ste sa oboznámili na tomto cvičení. Tento zápis sa nebude používať na cvičeniach ani na skúške, zíde sa však pri implementácii programov. Pred použitím oboch vizualizačných nástrojov odporúčame dôkladne sa oboznámiť so vstupným tvarom regulárnych výrazov, ktoré obidva nástroje používajú.