Meta II(ID:202/met011)


Val Schorre 1962

Syntax-directed metacompiler.


Related languages
Meta => Meta II   Evolution of
Meta II => META 4   Implementation
Meta II => META III   Implementation
Meta II => METAPI   Based on
Meta II => Metcalfe syntax language   Strong Influence
Meta II => VALGOL   Written using

References:
  • Schorre, V. "A Syntax - Directed SMALGOL for the 1401" view details
          in ACM 18th National Conference, Denver, Colorado, Aug. 1963 view details
  • Metcalfe, Howard H. "A Parameterised Compiler Based on Mechanised Linguistics" pp125-183 view details
          in Goodman, Richard (ed) "Annual Review in Automatic Programming" (4) 1964 Pergamon Press, Oxford view details
  • Schorre, V. "Meta II: a Syntax Oriented Compiler Writing Language" view details Abstract: META II is a compiler writing language which consists of syntax equations resembling Backus normal form and into which instructions to output assembly language commands are inserted. Compilers have been written in this language for VALGOL I and VALGOL II. The former is a simple algebraic language designed for the purpose of illustrating META II. The latter contains a fairly large subset of ALGOL 60. The method of writing compilers which is given in detail in the paper may be explained briefly as follows. Each syntax equation is translated into a recursive subroutine which tests the input string for a particular phrase structure, and deletes it if found. Backup is avoided by the extensive use of factoring in the syntax equations. For each source language, an interpreter is written and programs are compiled into that interpretive language.
    Extract: Introduction
    META II is not intended as a standard language which everyone will use to write compilers. Rather, it is an example of a simple working language which can give one a good start in designing a compiler-writing compiler suited to his own needs. Indeed, the META II compiler is written in its own language, thus lending itself to modification.
    Extract: History
    History
    The basic ideas behind META II were described in a series of three papers by Schmidt, Metcalf, and Schorre. These papers were presented at the 1963 National A.C.M. Convention in Denver, and represented the activity of the Working Group on Syntax-Directed Compilers of the Los Angeles SIGPLAN. The methods used by that group are similar to those of Glennie and Conway, but differ in one important respect. Both of these researchers expressed syntax in the form of diagrams, which they subsequently coded for use on a computer. In the case of META II, the syntax is input to the cemputer in a notation resembling Backus normal fore. The method of syntax analysis discussed in this paper is entirely different frem the one used by Irons and Bastian. All of these methods can be traced back to the mathematical study of natural languages, as described by Chomsky.
    Extract: How the META II Compiler Was Written
    How the META II Compiler Was Written

    Now we come to the most interesting part of this project, and consider how the META II compiler was written in its own language. [...]

    The META II compiler, which is an interpretive program for the META II machine, takes the syntax equations given in figure 5 and produces an assembly language version of this same interpretive program. Of course, to get this started, I had to write the first compiler-writing compiler by hand. After the program was running it could produce the same program as written by hand. Someone always asks if the compiler really produced exactly the program I had written by hand and I have to say that it was "almost" the same program. I followed the syntax equations and tried to write Just what the compiler was going to produce. Unfortunately I forgot one of the redundant instructions, so the results were not quite the same. Of course, when the first machine-produced compiler compiled itself the second time3 it reproduced itself exactly.

    The compiler originally written by hand was for a language called METAI. This was used to implement the improved compiler for META II. Sometimes, when I wanted to change the metalanguage, I could not describe the new metalanguage directly in the current metalanguage. Then an  intermediate language was created -- one which could be described in the current language and in which the new language could be described . I thought that it might sometimes be necessary to modify the assembly language output, but it seems that it is always possible to avoid this with the intermediate language. [...]

    All subroutines in META II programs are recursive. When the program enters a subroutine a stack is pushed down by three cells. One cell is for the exit address and the other two are for labels which may be generated during the execution of the subroutine. There is a switch which may be set or reset by the instructions which refer to the input string, and this is the switch referred to by the conditional branch commands. The first thing in any META II machine program is the address of the first instruction. During the initialization for the interpreter, this address is placed into the instruction counter. Extract: Further Development of META Languages
    Further Development of META Languages
    As mentioned earlier, META II is not presented as a standard language, but as a point of departure frum which a user may develop his own META language. The term "META Language," with "META"
    in capital letters, is used to denote any compiler-writing language so developed.
    The language which Schmidt implemented on
    the PDP-1 was based on META I. He has now implemented an improved version of this language for a Beckman machine.
    Rutman has implemented LOGIK, a compiler for bit-time simulation, on the 7090. He uses a META language to compile Boolean expressions into
    efficient machine code. Schneider and Johnson have implemented META 3 on the IBM 7094, with the goal of producing an ALGOL compiler which generates efficient machine code. They are planning a META language which will be suitable for any block structured language. To this compiler-writing language they give the name META 4 (pronounced
    metaphor). Extract: META 4
    Schneider and Johnson have implemented META 3 on the IBM 7094, with the goal of producing an ALGOL compiler which generates efficient machine code. They are planning a META language which will be suitable for any block structured language. To this compiler-writing language they give the name META 4 (pronounced metaphor).
          in Proceedings of the 19th ACM national conference January 1964 view details
  • Brown, J. H. review of Schorre 1964 (VALGOL etc) view details
          in ACM Computing Reviews 6(01) January-February 1965 view details
  • Ball, William E. "A Macromodular Meta Machine" view details External link: Online proceedings list Abstract: A MACROMODULAR META MACHINE

    WILLIAM E. BALL

    Washington University, St. Louis, Missouri

    The macromodular concept makes it possible to realize alternative computer designs with ease. However, a change in computer design usually implies that existing programs will no longer function correctly. It appears, then, that a flexibility in software equivalent to that of hardware must be maintained. This can be achieved by defining a very small (fixed) macromodular computer dedicated to compiling a high level language compiler for a target (variable) machine.

    The operation of the compiler computer is based on the compiler-compiler syntax-directed approach proposed by Schorre in his Meta II language. The design of a machine to implement the Meta II concept is described in terms of the MS2 simulation language and connection diagrams.

          in [AFIPS] Proceedings of the 1967 Spring Joint Computer Conference, April 18-20, Atlantic City, N. J. SJCC 30 view details
  • Feldman, Jerome and Gries, David "Translator writing systems" p77-113 view details Extract: META
    The META SYSTEMS (Schorre, [Schor 64], Schneider and Johnson [Seh 64])
    The META systems are the product of the Los Angeles SIGPLAN working group on syntax-directed compilers.
    Although the original work was diversified, the current systems are generally based on a model known as META-II, developed by Sehorre [Schor 64]. Within this model the parsing and translation processes for a language are all stated in a set of BNF-like rules. These rules become reeursive recognizers with embedded code generators when implemented. The rules do not allow left reeursion, using instead the prefix iteration operator $. Terminal symbols are quoted; system symbols are preceded by "."; and all unmarked symbols are user's nonterminals. Parentheses are used to group alternates within right parts. The following rules are used in translating Boolean expressions:
    1. UNION = INTER ('OR' .OUT('BT' *1) UNION .LABEL
    *I].EMPTY) ;
    2. INTER = BPRIMARY ('AND' .OUT('BF' *1) INTER
    .LABEL "1 I .EMPTY) ;
    3. BPRIMARY = .ID .OUT('LD' *) I '('UNION')';
    The last rule defines a procedure for recognizing a Boolean primary in an algebraic language. The word BPRIMAR Y followed by "=" defines the name of the rule, while the right part of the rule is both an algorithm for testing an input stream for the occurrence of a union and a code generator in ease an identifier (.ID) is found. The above rules contain examples of the three basic entities used in most META compilers. The mention of the name of another rule, in this ease UNION, causes a reeursive call on that recognizer to be invoked. The occurrence of a literal string "(" states that the input stream is to be tested for a left duces a line of text, where "*" always refers to the last item recognized by the primitive nonterminal .ID.
    The first mention of a *1 within a rule (as in Rule 1 above) causes both the generation of a label and the output of that label. Subsequent references within the same rule output the same label. That is, when a rule is entered new labels may be generated. These labels exist only while the rule is active. If a call is made to another rule, the labels are pushed onto a stack. Upon return from the called rule, the previous labels are restored. The action .LABEL *1 indicates that the label corresponding to *1 is to be written out..EMPTY is a primitive nonterminal which has no effect on the input but is always satisfied or true.
    For the input stream "(A OR B) AND (C OR D)" the following code would be produced where LD, BT, BF are mnemonics for Load, Branch True, and Branch False respectively.
    LD A
    BT L1
    LD B
    L1
    BF L2
    LD C
    BT L3
    LD D
    L3
    L2
    The usefulness of META-II was severely limited by the lack of facilities for backup or for reordering the output.
    There have been several attempts to extend the META techniques to a complete TWS. META-3 [Schor 64] was an attempt to extend the basic META-II concept so that ALGOI, 60 could be compiled for a 7090. It added some ability for semantic tests and register manipulation, but the additions never proved adequate. META-5 has been used in a number of format conversion and source-tosource language translations, but has not been used for compilers. The most recent development is TREE META, a multipass system using complex processing of intermediate syntax trees. The slowness and inefficiency of META compilers is recognized by their authors, but the ease of implementation, the boot-strapping capabilities, and the large class of languages they can handle are used to justify the work that has gone into their development.
    Abstract: A critical review of recent efforts to automate the writing of translators of programming languages is presented. The formal study of syntax and its application to translator writing are discussed in Section II. Various approaches to automating the postsyntactic (semantic) aspects of translator writing are discussed in Section III, and several related topics in Section IV.
          in [ACM] CACM 11(02) (February 1968) view details
  • META2, Version: l, December 1973 Author: Michael Green, Digital Equipment Corp., Maynard, MA view details Abstract: META2 is a compiler writer. It was used to write ALGOLW (DECUS No. 10-133) but is sufficiently general purpose to write other languages for the DECsystem-10. The compiler is defined by a series of specifications input to META2. META2 is written in itself, and is easily modified. External link: Online at DECUS
          in [ACM] CACM 11(02) (February 1968) view details