Recursion Engineering for Reduction Incorporated Parsers

Reduction Incorporated (RI) recognisers and parsers deliver high performance by suppressing the stack activity except for those rules that generate fully embedded recursion. Automaton constructions for RI parsing have been presented by Aycock and Horspool [John Aycock and Nigel Horspool. Faster generalised LR parsing. In Compiler Construction, 8th Intnl. Conf, CC'99, volume 1575 of Lecture Notes in Computer Science, pages 32 - 46. Springer-Verlag, 1999] and by Scott and Johnstone [Adrian Johnstone and Elizabeth Scott. Generalised regular parsers. In Gorel Hedin, editor, Compiler Construction, 12th Intnl. Conf, CC'03, volume 2622 of Lecture Notes in Computer Science, pages 232-246. Springer-Verlag, Berlin, 2003] but both can yield very large tables. An unusual aspect of the RI automaton is that the degree of stack activity suppression can be varied in a fine-grained way, and this provides a large family of potential RI automata for real programming languages, some of which have manageable table size but still show high performance. We give examples drawn from ANSI-C, Cobol and Pascal; discuss some heuristics for guiding manual specification of stack activity suppression; and describe work in progress on the automatic construction of RI automata using profiling information gathered from running parsers: in this way we propose to optimise our parsers' table size against performance on actual parsing tasks.