| 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. |
Súbory diplomovej práce:
| praca.pdf |
| priloha.zip |
Súbory prezentácie na obhajobe: