Algebraic construction of compilers (Q1183579): Difference between revisions

The algebraic construction of compilers is treated. After discussing fundamental concepts of universal algebras languages are defined as triples consisting of a semantic algebra, a syntactic algebra (word algebra) and a language learning function mapping the semantic algebra into the syntactic algebra and depending on a homomorphism between the syntactic and semantic algebras. First, the simplest case is considered, that means both --- the source language and the target language --- are defined by homogeneous universal algebras of the same signature. Then, the case of different signatures is solved by embedding the source language into the target language using the concept of derived operations and subalgebras. Finally, to define real programming languages and their compilation heterogeneous universal algebras are exploited. Here, a heterogeneous algebra is a hierarchy of two layers. The first layer (specification basis) is a homogeneous algebra defining the operation schemes of the operations of the second layer which are operations on a family of sets. For the compilers explicit algorithms are given. The correctness of the constructed compilers is guaranteed by construction. Parallelization of compilers is possible. The idea of algebraic compiler construction is implemented in the TICS system.