Název: Syntaktická analýza řízených gramatik
Překlad názvu: Parsing of Regulated Grammars
Autoři: Šrajer, Roman ; Čermák, Martin (oponent) ; Křivka, Zbyněk (vedoucí práce)
Typ dokumentu: Diplomové práce
Rok: 2011
Jazyk: cze
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [cze] [eng]
Diplomová práce se zabývá řízenými gramatikami, jejich principem a vyjadřovacími schopnostmi vzhledem k Chomského klasi kaci jazyků. Více do detailů je probrána programovaná gramatika z hlediska různých typů nejlevějších derivací. V práci je prezentována varianta deterministické syntaktické analýzy programovaných gramatik, která pracuje podobně jako analýza LL(k) gramatik. Dále jsou představeny algoritmy pro převod maticových gramatik na programované bez změny vyjadřovací síly. Rovněž je prezentován mechanismus syntaktické analýzy regulárně řízených gramatik za pomocí programované gramatiky. Nakonec jsou prezentovány kooperující distribuované gramatiky s levě povolujícími gramatikami jako komponenty. Jejich syntaktická analýza je zajištěna buď deterministicky pomocí prediktivní tabulky nebo prohledáváním stavového prostoru. This thesis studies regulated grammars, their fundamentals and expressing power regarding Chomsky hierarchy of languages. Programmed grammars are investigated in more depth considering a few types of leftmost derivations. A variant of deterministic syntax analysis of programmed grammars is introduced. This analysis works similarly as LL(k) parsing. Transformations of matrix grammars into programmed grammars without changing their expressing power are introduced. The syntax analysis by regularly controlled grammars partly using programmed grammars are presented. In the end, cooperating distributed grammars with left permitting grammars as components are mentioned. Their deterministic syntax analysis uses predictive table or exhaustive exploration of the whole state space.
Klíčová slova: gramatika s nahodilým kontextem; jednoduchá levě povolující kooperující distribuovaná gramatika; jednoduchá maticová gramatika; jednoduchá programovaná gramatika; jednoduchá regulárně řízená gramatika; kanonická derivace; kooperující distribuovaná gramatika; levě povolující gramatika; maticová gramatika; programovaná gramatika; regulárně řízená gramatika; rozšířená jednoduchá maticová gramatika; rozšířená jednoduchá programovaná gramatika; Syntaktická analýza; řízená gramatika; canonical derivation; cooperating distributed grammar; extended simple matrix grammar; extended simple programmed grammar; left permitting grammar; matrix grammar; programmed grammar; random context grammar; regularly controlled grammar; regulated grammar; simple left permitting cooperating distributed grammar; simple matrix grammar; simple programmed grammar; simple regularly controlled grammar; Syntax analysis

Instituce: Vysoké učení technické v Brně (web)
Informace o dostupnosti dokumentu: Plný text je dostupný v Digitální knihovně VUT.
Původní záznam: http://hdl.handle.net/11012/54076

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-236933


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Vysoké učení technické v Brně
Vysokoškolské kvalifikační práce > Diplomové práce