An algebra for program fragments

摘要

Program fragments are described either by strings in the concrete syntax or by constructor applications in the abstract syntax. By defining conversions between these forms, both may be intermixed. Program fragments are constructed by terminal and nonterminal symbols from the grammar and by variables having program fragments as values. Basic operations such as valuetransfer, composition and decomposition are defined for program fragments allowing more complicated operations to be implemented. Usual operations such as testing for equality are defined, and in addition more specialized operations such as testing that a program fragment is derivable from another and converting program fragments in concrete form to abstract form are defined. By introducing regular expressions in the grammar these may be used in program fragments in concrete form. By defining constructors for regular expressions these may also be used in program fragments in abstract form.