Automatic recursion engineering of reduction incorporated parsers

AbstractReduction Incorporated (RI) parsers deliver high performance by suppressing the stack activity except for those rules that generate embedded recursion. Automaton constructions for RI parsing have been presented by Aycock and Horspool [J. Aycock, N. Horspool, Faster generalised LR parsing, in: Compiler Construction, 8th Intnl. Conf, CC’99, in: Lecture Notes in Computer Science, vol. 1575, Springer-Verlag, 1999, pp. 32–46] and by Scott and Johnstone [A. Johnstone, E. Scott, Generalised regular parsers, in: G. Hedin (Ed.), Compiler Construction, 12th Intnl. Conf, CC’03, in: Lecture Notes in Computer Science, vol. 2622, Springer-Verlag, Berlin, 2003, pp. 232–246] 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 by choosing different grammar terminalisation sets, 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. In this paper we describe automatic construction of minimal grammar terminalisation sets, giving examples drawn from ANSI-C, Cobol and Pascal; we describe the use of profiling to inform the choice of RI automaton; we investigate the use of RI parsers for scannerless parsing; and we explain some of the phenomena that influence the time/space trade-off for RI parsers