| Meno: | Lukáš
|
|---|
| Priezvisko: | Hudcovský
|
|---|
| Názov: | Rozšírenie a implementácia algoritmu pre LR parsovanie permutačných fráz
|
|---|
| Vedúci: | RNDr. Jana Kostičová, PhD.
|
|---|
| Rok: | 2026
|
|---|
| Kľúčové slová: | permutačná fráza, LR parsovanie, stavová zložitosť, voliteľný prvok
|
|---|
| Abstrakt: | Permutačná fráza je zápis reprezentujúci všetky permutácie danej množiny symbolov. V práci sa zaoberáme priestorovo efektívnym LR parsovaním gramatík s permutačnými frázami. Štandardné LR parsovacie algoritmy generujú pre permutačnú frázu dĺžky $n$ položkový automat so stavovou zložitosťou $\Omega(n!)$. V predošlej práci bol navrhnutý efektívnejší algoritmus, ktorý znižuje stavovú zložitosť na $O(2^n)$. Tento základný algoritmus je však značne obmedzený a dokáže spracovať iba veľmi jednoduché permutačné frázy. V práci navrhujeme a formálne opisujeme rozšírenia základného algoritmu, ktoré umožňujú spracovať aj vnorené podfrázy, voliteľné prvky a opakujúce sa prvky. Naše riešenie pokrýva prevažnú väčšinu identifikovaných výskytov permutačných fráz a je teda použiteľné na oveľa širšiu množinu praktických prípadov ako základný algoritmus. Ďalej algoritmus implementujeme a empiricky overujeme jeho korektnosť pomocou testovania. Nakoniec experimentálne demonštrujeme úsporu počtu stavov pri použití nášho algoritmu oproti štandardnému algoritmu.
|
|---|