Programming Research Group Technical Report TR-20-92

P T Breuer and J P Bowen

1992, 25pp

Top-down (LL) parsers are easy to express in functional programming languages, but the elegant functional programming model can also serve as an exact prototype for a "real" implementation of the technology in ANSI C. The result is a compiler-compiler that takes unlimited lookahead and backtracking, the extended BNF notation, and parameterized grammars with (higher order) meta-parameters to the world of C programming. The generated code is standard ANSI C and is "plug compatible" with lex-generated lexical analyzers prepared for the UNIX yacc compiler-compiler. In contrast to yacc, however, the generated code is modular and thus allows parts of scripts to be compiled separately and linked in incrementally, but it remains efficient, as is demonstrated by the example OCCAM parser treated in depth here.