Global Data Flow Analysis Problems Arising in Locally Least-Cost Error Recovery

Abstract

Locally least-cost error recovery is a technique for recovering from syntax errors by editing the input string at the point of error detection.A scheme for its implementation in recursive descent parsers, which in principle embodies a process of passing a parameter to each procedure in the parser for each terminal symbol in the grammar, has been suggested.For this scheme to be practical it is vital that as much parameterization as possible is eliminated from the recursive descent parser.This oPtimization problem and how it may be split into three separate global data flow analysis problems-classifying terminal symbols and the so-called min and max follow cost problems--are discussed.The max follow cost problem is a particularly difficult one to solve.The application of Gaussian elimination to its solution is shown by expressing it as a continuous data flow problem, and it is also related to an "idiosyncratic" data flow problem arising in the optimization of very high level languages.Classifying terminal symbols is also difficult since the problem is unsolvable in general.However, for the class of LL(1) grammars, the problem is shown to be expressible as a distributive data flow problem and so may be solved using, say, Gauss-Seidel iteration.