Principled procedural parsing

Laurent, Nicolas [UCL]

Parsing is the process of analysing an input string in order to extract a structured representation of its content (a syntax tree) with respect to a specific language. In the thesis, we focus on parsing formal languages, such as programming or markup languages — as opposed to natural spoken languages. Unlike natural languages, formal languages are never ambiguous: there is only a single correct interpretation of the input. Parsing is a pervasive activity: every time a source file must be turned into executable code, a parser is required. Similarly, parsers are used to convert input files into relevant data structures. It is fair to say that most programs include a parser — sometimes many. As such, making parsers easier to write, use, and modify is a broadly beneficial endeavour. This thesis is concerned with the limitations of currently available parsing systems, and how to overcome them. In particular, we show how to develop a simple yet expressive notation that can be easily extended, and build upon this basis to add context-sensitive parsing to the parsing system, robust support for infix expression (avoiding expressiveness and performance issues relating to associativity selection) as well as many more expressiveness and usability features — such as permissive parsing and debugging tools.