Archiv závěrečné práce Václav Vacek FI B-IN BcIN

Mgr. Václav Vacek

Generický BNF parser

Generic BNF-driven parser

Abstract: This thesis describes the bnfparser2 C++ library. It is a generic runtime-generated parser capable of parsing any context-free language. The parser is primarily meant for verification and diagnosis of telecommunication protocols, but the usage is not restricted to that. First, the possibility of using tools already available is discussed. The rest of the thesis is then fully devoted to bnfparser2. The architecture of the library is described in detail; all the important steps and algorithms are given. This generally involves tranforming the user input into an internal form, generating the parser and parsing. After that, format of input and output, required settings, restrictions are described. Finally the furher improvements of the library are outlined. …víceméně

Parser, parser generator, context-free languages, ambiguous grammars, Backus-Naur form, LALR, GLR, GSS

Zadání: Úkolem diplomové práce bude vytvoření za běhu generovatelného parseru. Řešení bude realizováno jako C++ knihovna. Hlavní komponentou bude třída Parser, realizující vlastní parser.

Odhalení chyb:
• oznámení chyby při pokusu o vytvoření parseru pro nesprávnou gramatiku a metasyntax • oznámení chyby při parsování nekorektní zprávy a lokalizace chyby

Předpokládané použití:

• Knihovna se přilinkuje. • Vytvoří se instance třídy BnfParser2 pro potřebné gramatiky s příslušnými parametry. • Parsování bude spočívat ve volání metody parse_word a bude vracet instance vhodně definované třídy se strukturálními daty.

Obecné:

• Důraz spíše na robustnost než na rychlost. • Předpokládáme, že parser bude zpracovávat ("míra robustnosti") libovolné CFL gramatiky včetně nejednoznačných. V případě, že gramatika není jednoznačná, nelze hlásit warning, neboť tento problém je nerozhodnutelný. • Parser by měl podporovat načtení konkrétní specifikace syntaxe z několika souborů. • Na vstupu budou pouze BNF gramatiky • Metasyntaxe (ABNF, EBNF, ...) definována pomocí základních pravidel a metaoperátorů. • Gramatiky vkládány read-only. Všechny potřebné změny externě v konfiguračních souborech gramatik. • Konfigurační soubory obsahují úpravy gramatiky a odkazy do externích namespaces. • Namespaces: implicitně má každá gramatika vlastní namespace a odkazuje se pouze interně. Externí odkazy jsou definovány v konfiguračním souboru. • Vzorový popis notace gramatiky v meta notaci by měl být vytvořen pro ABNF definovanou v [RFC2234] a rozšíření ABNF definované v [(http://www.faqs.org/rfcs/rfc2616.html) RFC 2616]. • Parser by měl být otestován pomocí SIP zpráv. V tomto případě bude parser řízen třemi soubory: specifikací ABNF notace, základními pravidly ABNF vykopírovanými z [RFC2234] a syntaxí SIP zpráv vykopírované z [(http://www.faqs.org/rfcs/rfc3261.html) RFC 3261]. • Návrh a implementace parseru by měla být plně dokumentovaná. …víceméně

Jazyk práce: angličtina