Content area
Abstract
Most programming languages are defined using English, with its attendant ambiguities. This thesis introduces the semantic grammar, a formal, unambiguous notation for syntax and semantics. Appendix D is a semantic grammar for Pascal; I have also written one for Fortran. Semantic grammars evolved from denotational semantics and attribute grammars. A grammar contains domain definitions, expression definitions, and attribute grammar rules. Attributes express semantic dependencies and constraints. A semantic grammar may express static semantics, such as type-checking and symbol table management, as well as dynamic semantics. A grammar can define axiomatic or operational semantics, as well as denotational.
Developing a compiler still requires a major effort, in spite of all the design tools available. Most generate only part of a compiler, and require the user to code the rest. This thesis describes a compiler generator that translates semantic grammars into compilers. It has generated Pascal and Fortran compilers, and run numerous programs, including an LR(0) parser constructor. The compiler generator consists of a grammar analyzer, universal translator, and stack machine. The grammar analyzer converts a semantic grammar into a language description file that includes LALR(1) parse tables and attribute semantics. The universal translator reads the file and parses a program, producing a graph of attribute dependencies. It simplifies the graph into a single formula, while reporting semantic errors in the program. It compiles the formula into stack machine instructions for execution. The stack machine uses Landin's SECD architecture to execute lambda-calculus formulas.
The compiler generator was designed to be as general and complete as possible, to provide language designers with immediate implementations of their ideas. It accommodates applicative languages and novel control structures. It can perform the complex static checking that modern languages require. The compilers are not efficient enough to replace hand-written ones, but can execute test programs several pages long, to evaluate an experimental language.
