Compiler Research at NRL

I worked at Nelson Research Laboratories from September 1967 to April 1969. I was recruited into a new group intended to do research on Compilers and Compiler Compilers, but was also drawn into work on a suite of programs for the analysis of electrical power transmission networks, so not all my time was spent with Compilers.

The group was starting from scratch and lacked strong leadership. So we spent plenty of time familiarising ourselved with what had been done elsewhere.

Despite my own limited knowledge and competence I was allowed to find my own way forward, which I did by putting together some very elementary building blocks. But what I did, was the kind of thing which a youngster with no education in computer science and not even much experience with computers could do. A computer science undergraduate would today be expected to know a lot more about parsing before considering the sort of project I undertook.

Data Driven Parsers

Compiler Compilers were phase in the development of Compiler technology. They hung around general purpose parsers but aspired to a more general competence. The parser technologies evolved into todays parser generators such as lex.

I started by coding up a very simple data driven parser for context free grammars. This just did the naive thing with recursive descent and backtracking, and would loop if the grammar was left recursive. The only thing which stopped this from being utterly trivial was that it was written in Fortran which did not support recursion, and so had to manage its own stack. It was neat, about 50 lines of FORTRAN if my memory is correct.

Nevertheless, it impressed, and I was permitted then to plot a course forward. We didn't have good languages for this kind of programming in those days, though Algol was used on the KDF9, we were expected to work on English Electric Sysem-4, a clone of the IBM 360, designed for commercial rather than scientific computing. The choice of language was FORTRAN or System-4 Usercode (an assembler). So I went for assembler. I coded up a simple dynamic storage management system (for the RAM), and a table driven recursive descent parser. So far as I recall all I did with it was use it to translate grammers written in Backus-Naur form into the kind of table required for the parser.

up quick index © RBJ

privacy policy


$Id: rbjcv009.xml,v 1.1 2010/02/01 11:34:11 rbj Exp $