University of Twente Student Theses

Login
As of Friday, 8 August 2025, the current Student Theses repository is no longer available for thesis uploads. A new Student Theses repository will be available starting Friday, 15 August 2025.

A Derivative-based, Colored-edged Parser Generator for Nested Words

Marcelis, Bas (2023) A Derivative-based, Colored-edged Parser Generator for Nested Words.

[img] PDF
193kB
Abstract:The language class of nested words lies between regular- and context-free languages on the Chomsky hierarchy. It combines the expressiveness of hierarchy from context-free languages with the robustness of regular languages. An optimised parser generator for this language would be promising, as the nesting of words can be seen in multiple popular programming languages, such as HTML, JSON, and XML, proving the popularity of its applications. This research combines a derivative-based parser with colored nested words to provide a parser generator for well-matched VPGs that accepts ambiguity and returns all possible parse trees, while also having proper error handling by accepting pending calls. The performance of a prototype based on these findings is linear complexity for unambiguous grammars and linear complexity for every possible parse tree for ambiguous grammars, which is proven in both theory and practice.
Item Type:Essay (Bachelor)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Programme:Computer Science BSc (56964)
Awards:Best Paper Award
Link to this item:https://purl.utwente.nl/essays/94400
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page