Content area
The automatic production of syntax-organized compilers using a modified pushdown automaton to perform LL(1) parsing instead of recursive descent is investigated. The technique is similar to transition matrices, allowing very fast compilers, but considerably smaller. Unlike traditional LL(1) parsing, strings of input symbols are checked by one state instead of several, thereby reducing the number of states required. An integer value indicating how many input symbols to advance in a state transition is used instead of a Boolean value simply indicating if a symbol is consumed. Multiple error entries are also eliminated.
In addition to generating the syntax analyzer automatically, semantics must be automatically incorporated into the compiler from some formal specification. The programming language PASCAL is investigated as a metalanguage for defining compiler-oriented semantics, including the use of semantic macros in PASCAL to define similar features for a variety of programming languages as a means of automating static semantics and intermediate code expressible in PASCAL to define dynamic semantics. The intermediate language is defined to serve for a variety of source languages and target machines. PASCAL is used to completely define the semantics of itself and considered for defining FORTRAN and ADA. Because PASCAL is a programming language instead of a mathematical formal notation, it is easier to use a semantic metalanguage but its main advantage is that a PASCAL definition of a language constitutes a compiler for that language.
Algorithms were developed and implemented to generate LL(1) compiler tables from language specifications and to use the generated tables to compile source programs and it is shown how the pushdown automaton parsing technique can be extended to LL(k) parsing, for k > 1. A complete specification of PASCAL was used to generate a PASCAL compiler and syntactic specifications of FORTRAN and ADA were developed to generate parsing tables for these languages. These parsing tables are much smaller than parsing tables generated by other methods. The PASCAL compiler generated is comparable to a hand-coded recursive-descent compiler in terms of compilation time and contains significantly less source code. Therefore, an advantage is gained in both time and space in compilers generated by this technique.