Original title: Syntaktická analýza řízených gramatik
Translated title: Parsing of Regulated Grammars
Authors: Šrajer, Roman ; Čermák, Martin (referee) ; Křivka, Zbyněk (advisor)
Document type: Master’s theses
Year: 2011
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [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.
Keywords: 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; 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

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/54076

Permalink: http://www.nusl.cz/ntk/nusl-567086


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Master’s theses