The Saga Editor: A Language-Oriented Editor Based on an Incremental Lr(1) Parser

Abstract

The research described in this dissertation supports the thesis that a language-oriented editor for full programming languages, and other languages specifiable with context-free LR(1) grammars, can be based upon an incremental LR(1) parser employing incremental analysis techniques. The resulting editor is flexible, supporting a higher-level command interface which includes structure-oriented commands involving tokens and sub-trees, while retaining common text editing commands which operate on arbitrary groups of characters and lines. This editor can be used to develop practical programs which incorporate software engineering principles concerning the design and construction of software systems. In this dissertation, an incremental parsing algorithm suitable for use with an interactive editor is developed. A new solution to the handling of comments in syntax trees is proposed, and an error-recovery algorithm which permits editing of the parse tree in the midst of syntax errors is presented. The resulting editor, its commands, and environment are described. The editor can be retargeted to other languages, and can use any parser-generating system which can meet its interface. A prototype editor which employs these algorithms has been implemented as a part of the SAGA project as a demonstration of the practicality and flexibility of the approach; this editor has been in experimental use during the past couple of years at the University of Illinois at Urbana-Champaign.