Professor Adrian Johnstone
Adrian Johnstone's research interests lie in the theory and practice of programming languages and their translators. Recent work centres on (i) the formal properties and applicability of generalised parsing and (ii) the customisation of processor architectures for embedded applications.
There has been a resurgence of interest in general parsing techniques because modern computer hardware is sufficiently powerful to make such techniques practical. New efficient and correct parsing algorithms have been developed in collaboration with Prof Elizabeth Scott; in particular the GLL top-down parser and the RNGLR family of generalised Tomita-style LR parsers. We are presently investigating their use in compiler generation and reverse compilation as well as for the analysis of biological sequence data.
Earlier research concerned the efficient design and implementation of realtime processors, especially fast image processing systems, both at board and chip level. We have developed new algorithms for finding convex subsets of dataflow graphs that enable us to generate small processor cores which contain only the features necessary to execute a particular embedded application.
As well as developing new algorithms, we have developed the following software tools.
- The asm21toc reverse compiler for ADSP 21xx architectures which generates ANSI-C source code from assembler source. Several companies have used this tool to port their intellectual property from the 16-bit ADSP devices to more modern processors with optimising C compilers. Please note that the tool requires full source code to be available: it is not for reverse-engineering.
- The gtb grammar toolbox which provides implementations of many standard parsing algorithms as well as out locally developed RNGLR, BRNGLR, RIGLR and GLL algorithms.
- The ART GLL parser generator which produces fast generalised top-down parsers, and which also implements our grammar modularity and Tear-Insert-Fold (TIF) tree rewriting formalism.
We welcome expressions of interest from potential industrial clients and from prospective research students.