Original title:
Syntaktická analýza založená na gramatikách s nahodilým kontextem
Translated title:
Parsing Based on Random Context Grammars
Authors:
Mikita, Martin ; Solár, Peter (referee) ; Vrábel, Lukáš (advisor) Document type: Bachelor's theses
Year:
2013
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[cze][eng]
Tato bakalářská práce popisuje gramatiku s nahodilým kontextem a implementaci aplikace, která bude konvertovat gramatiku (respektující LL podmínku) na ekvivalentní bezkontextovou gramatiku (také splňující podmínku LL). Výslednou gramatiku je možné použít ve stávajících generátorech parseru, který přijme yacc-kompatibilní formát. Tato práce používá GNU Bison generátor, pro který byl zavedený zapouzdřený skript. Potenciální výhodou gramatiky s nahodilým kontextem je dokázaný úspornější zápis oproti bezkontextové gramatiky pro některé jazyky.
This thesis describes a random context grammar and the implementation of an application which will convert this grammar (respecting the LL condition) to an equivalent context-free grammar (also satisfying the LL condition). The resulting grammar can be used in the existing parser generator that accepts a yacc-compatible format. This thesis uses the GNU Bison generator, for which the encapsulated script was introduced. The potential advantage of random context grammar consists in the proven efficient description compared to context-free grammar for some languages.
Keywords:
context-free grammar; efficient description; GNU Bison front-end in C++; leftmost derivation; LL RCG; LL requirement; parser; parser generator; parsing; Random context grammar; RCG; syntactic analysis; yacc-compatible format; bezkontextová gramatika; generátor parsera; GNK; GNU Bison front-end v C++; Gramatika s nahodilým kontextem; LL GNK; LL podmínka; nejlevější derivace; parser; parsování; syntaktická analýza; yacc-kompatibilní format; úsporný zápis
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/54865