META II
META II is a domain-specific programming language for writing compilers. It was created in 1963-1964 by Dewey Val Schorre at UCLA. META II uses what Schorre called syntax equations. Its operation is simply explained as:
Each syntax equation is translated into a recursive subroutine which tests the input string for a particular phrase structure, and deletes it if found.[1]
Meta II programs are compiled into an interpreted byte code language. VALGOL and SMALGOL compilers illustrating its capabilities were written in the META II language, [1][2] VALGOL is a simple algebraic language designed for the purpose of illustrating META II. SMALGOL was a fairly large subset of ALGOL 60.
Notation
META II was first written in META I.[3] META I was a hand-compiled version of META II. The history is unclear as to whether META I and META II are different languages.
In the documentation, META II is described as a language resembling Backus normal form (BNF). Most syntax directed compilers of the day were described as BNF-like or as using BNF. There are differences between META II and BNF; for example, in BNF, an arithmetic expression is defined as:
<expr> := <term> | <expr> <addop> <term>
The BNF rule does not tell us how we should parse an expression, while in META II, the order of testing is specified by the equation. The expr parsing equation written in META II is a conditional expression evaluated left to right:
expr = term ('+' expr / '-' expr / .EMPTY);
Above the expr equation is defined by expression to the right of the '='. Evaluating left to right from the '=', term is the first thing that must be tested. If term fails expr fails. If a term is recognized we then look for a '+' if that fails the alternate '-' is tried and finally if a '-' were not recognized the alternate .EMPTY always succeeds and expr returns success recognizing a single term. If a '+' or '-' were matched then expr would be recursively attempted. In META II an equation is a function returning success or failure. The expr equation can also be expressed using nested grouping as:
expr = term (('+' / '-') expr / .EMPTY);
The code production elements were left out to simplify the example. Due to the limited character set of early computers the character / was used as the alternative, or, operator. The examples have used a recursive rule to more closely match the BNF rule. However the evaluation order is a right most first order. That is 5-2+1 would be evaluated as 5-(2+1) A loop would be used to make the implied grouping: (5-2)+1. The $, loop operator, is used to match zero or more of something:
expr = term $(('+' / '-') term);
The above can be expressed in English: An expr is a term followed by zero or more plus or minus terms. Schorre describes this as being an aid to efficiency, but unlike a naive recursive descent compiler it will also ensure that the associativity of arithmetic operations is correct: in modern terms the parsing expression defines a tail recursive parsing function.
Operation
META II outputs assemble code for a stack machine, evaluating this is like using an RPN calculator.
expr = term $('+' term .OUT('ADD') / '-' term .OUT('SUB');
term = factor $('*' factor .OUT('MPY') / '/' factor .OUT('DIV'));
factor = .ID .OUT('LD ' *) / .NUM .OUT('LDL ' *) / '(' expr ')';
In the above .ID and .NUM are built-in token recognizers. * in the .OUT code production references the last token recognized. On recognizing a number with .NUM .OUT('LDL' *) outputs the load literal instruction followed the number. An expression:
- (3*a+5)/b
will generate:
LDL 3
LD a
MPY
LDL 5
ADD
LD b
DIV
META II is the first documented version of a metacompiler,[notes 1] as it compiles to machine code for one of the earliest instances of a virtual machine.
The paper itself is a wonderful gem which includes a number of excellent examples, including the bootstrapping of Meta II in itself (all this was done on an 8K (six bit byte) 1401!)."—Alan Kay
The original paper is not freely available, but was reprinted in Doctor Dobb's Journal (April 1980). Transcribed source code has at various times been made available (possibly by the CP/M User Group). The paper included a listing of the description of Meta II, this could in principle be processed manually to yield an interpretable program in virtual machine opcodes; if this ran and produced identical output then the implementation was correct.
META II was basically a proof of concept. A base from which to work.
META II is not presented as a standard language, but as a point of departure from which a user may develop his own META "language".[1]
Many META "languages" followed. Shorre went to work for System Development Corporation where he was a member of the Compiler for Writing and Implementing Compilers (CWIC) project. CWIC's SYNTAX language built on META II adding a backtrack alternative operator positive and negative look ahead operators and programed token equations. The .OUT and .LABEL operations removed and stack transforming operations :node and !number added. The GENERATOR language based on LISP 2 processed the trees produced by the SYNTAX parsing language. To generate code a call to a generator function was placed in a SYNTAX language equation. These languages were developed by members of the L.A. ACM SEGPLAN sub-group on Syntax Directed Compilers. It is notable how Schorre thought of the META II language:
The term META "language" with META in capital letters is used to denote any compiler-writing language so developed.[1]
Schorre explains META II as a base from which other META "languages" may be developed.
See also
Notes
- ↑ Ignoring META I which is only mentioned in passing in the META II document.
References
- 1 2 3 4 META II A SYNTAX-ORIENTED COMPILER WRITING LANGUAGE (Dewey Val Schorre UCLA Computing Facility 1964)
- ↑ Dewey, Val Schorre (1963). "A Syntax - Directed SMALGOL for the 1401,". ACM Natl. Conf., Denver,Colo.
- ↑ Dewey, Val Schorre (1963). META II: a syntax-oriented compiler writing language (PDF). UCLA: UCLA Computing Facility.