Professor Elizabeth Scott
My current research interests lie in computer language design and compiler construction. My recent work centres on the formal properties of, and applicability of, generalised parsing. We have developed correct, efficient algorithms for parsing general context free languages and modern computer hardware is sufficiently powerful to enable such techniques to be used.
- GLL parsers: recursive descent like parsers which are worst case cubic and can be given for all context free grammars including those with left recursion.
- RNGLR and BRNGLR parsers: based on Tomita's generalisation of LR parsers.
- RIGLR parsers: the extension of Aycock and Horspool's algorithm to grammars with hidden left recursion.
I am interested in the application of these ideas to compiler code generation, specification of embedded systems, reverse compilation, natural language parsing and bioinformatics.This work covers a broad spectrum, from graph theoretic algorithms for target code selection to meta-modelling of embedded systems.
Tools which implement the algorithms have been built and the work is brought together under Royal Holloway's Centre for Software Language Engineering, whose mission is to enhance research in, and the application of, software technologies that employ grammar based techniques. The centre brings together academics and industrial users and aims to develop technologies which are both practical and correct.
I am centrally involved in the PLanCompS project whose goal is to establish and test the practicality of a component-based framework for the design, specification and implementation of programming languages. This is a large project, run jointly with Swansea University and with Microsoft Reseach as project partner, and it is a significant part of my current research focus.
My early research in Computer Science was in the area of formal methods and automated theorem proving, working on the general theory of well founded orderings in order to address the problem of proving process termination. I have given a classification for the case of strings on two letters in terms of the order type of the ordering, and an automated proof of the correctness of a compiler as part of the ESPRIT PROCOS initiative. My mathematical background is in infinite group theory, I constructed an example of a finitely presented simple group with unsolvable conjugacy problem. I also published, jointly with Graham Higman, an OUP monograph on Existentially Closed Groups, which addresses an area on the borders between algebra and logic and uses algebraic techniques to prove results which could not be derived using a purely logic based approach.
Studied at Manchester and then at Oxford, completed a D.Phil under the supervision of Professor Graham Higman. Worked as a researcher at Oxford, and then at the Australian National University in Canberra. Then joined Ursula Martin's group at Royal Holloway. After a brief period at St Andrew's University, returned to Royal Holloway in 1993 and was appointed Professor in 2009.