DESIGN OF INCREMENTAL TOOLS FOR INTERACTIVE PROGRAMMING ENVIRONMENTS WITH APPLICATION TO COMPILER GENERATORS

An interactive programming environment allows the programmer to construct programs in parts, correct the program as errors are detected, and minimizes the amount of recomputation by re-analysis of the modified parts alone. This thesis focuses on the development of tools for designing incremental language processors. To build an incremental language processor, an incremental parser and an incremental translator are needed. In this work, an incremental LR(1) parser, and an incremental attribute evaluator (suitable for code generation) are presented. The incremental LR(1) parser constructs the parse tree of a modified input by using some of the subtrees constructed in parsing the old input. Reparsing of the input substrings corresponding to the yield of such subtrees is therefore avoided. The parser can be supplemented with error recovery routines to allow interactive user controlled recovery as well as automatic error recovery by the recovery routines. Translation (in particular, code generation) is defined via attribute evaluation. In this work, new algorithms for attribute evaluation are presented and analyzed. The evaluator follows the strategy of evaluation by need , is table-driven and is applicable to any grammar in normal form , circular or non-circular. The incremental version of the evaluator only computes those attributes whose values have been affected by the modifications. Hence, recomputation of unaffected attributes is avoided. The evaluator has time complexity linear in the number of attributes needed to define the meaning of a given input, and has space complexity linear in the size of the input