Putting algebra to work in compiler construction (structure, editor, syntax)
Eugene J. Rollins · 1984
An algebraic framework for compilers is developed in which a precise relationship is established between the concrete (parsing) syntax and the abstract syntax of a language. An interesting application of this theory is the design of a syntax-analyzer, Syn. Syn is dual purpose; it can be used batch style as the component of a traditional compiler or interactively as a program-structure editor. It is language relative in that it is parameterized by the syntactic structure of a language. The Syn editor exploits the precise relationship between the concrete and abstract syntaxes of a language to provide the best features of both structural and textual editing. Previous attempts to combine structural and textual editing have resulted in an inconsistent treatment of language constructs. Here, all language constructs are treated uniformly. Programs are entered as text with the aid of templates. Templates are invoked through source language program fragments. As a program is entered an abstract-syntax tree for that program is incrementally constructed. Infix operators in expressions cause no problems and are entered in infix notation. Text editing is provided in such a way as to complement structure editing. The user can interactively select structurally significant program fragments to edit as text. An edited fragment is reintegrated into the program by parsing just that fragment. This is accomplished without modification of the parsing technique. SAC, a syntax-analyzer constructor, accepts an annotated grammar, a context-free grammar (CFG) augmented with simple, terse annotations as input and produces the language dependent tables that drive Syn. An annotated grammar defines a mapping from source language programs to abstract-syntax trees (ASTs). Syn implements this mapping. From an annotated grammar, SAC produces an abstract-syntax grammar (ASG) that describes the class of ASTs that comprise the range of this mapping. Since the parsing grammar is often inappropriate for the user interface of the editor, the templates are displayed in terms of the ASG. This thesis does not deal with the engineering issues involved in program editing; it does lay a solid foundation for simultaneously viewing programs via text and structure.