Accelerating the parsing process with an Application Specific VLSI RISC processor

Abstract

This thesis investigates the topic of the design, implementation and potential use of specialised hardware used to accelerate the recognition and translation of computer programs expressed in a range of computer languages. This investigation focuses specifically on the twin processes of parsing and lexical analysis.

The research described was carried out in two areas namely, the feasibility of designing a specialised instruction set for a RISC like processor able to accelerate the parsing and lexical analysis process, and the physical implementation of a RISC processor in CMOS VLSI technology able to execute the designed instruction set.

The feasibility of mapping the process of language recognition onto the instruction set of a RISC processor is investigated. This involves an assessment of the suitability of the LL(1) and LALR(1) algorithms, both of which are used for parsing, and other associated algorithms, used for lexical analysis, as a basis for an appropriate instruction set architecture. The feasibility of an instruction set design which uses fixed size instructions with variable size data fields to ensure scaleable operation is also investigated. The appropriate software mechanisms used to validate the instruction set architecture are outlined.

The practical implementation using CMOS technology of a RISC processor able to execute the new instruction set is investigated. In particular the feasibility of using bit-slice technology to implement the processor having fixed size instructions with variable size data-paths and address ranges is investigated.

The combination of novel instruction set with variable data-widths and the fabricated devices able to activate semantic actions directly from hardware together form an original contribution to the field of parsing and lexical analysis.