META II

META II is a compiler writing language (also known as compiler-compiler) first released in 1963 by Dewey Val Schorre. It consists of syntax equations resembling Backus normal form, into which output instructions are inserted. Each syntax equation is translated into a function which tests the input string for a particular phrase structure advancing over matched elements. Backup is avoided by the extensive use of factoring in the syntax equations. Meta II programs are compiled into an interpreted language. Compilers have been written in the META II language for VALGOL and SMALGOL, [1][2] the former is a simple algebraic language designed for the purpose of illustrating META II, the latter is described as a fairly large subset of ALGOL 60.

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 II is a different language than META I.

In the documentation, META II, is described as a language resembling Backus normal form. That is misleading. But most syntax directed compilers of the day were described as BNF like or as using BNF. It would better be defined as a top down syntax analyzer. The meta language of META I and II define the order of testing the input. The difference is more clearly shown with an example. In BNF Backus normal form an arithmetic expression is defined as:

expr:= <expr> | <expr> <addop> <term>

The BNF rule does not tell us how we should parse an expression. Unless you are a computer scientist or Linguist it more than likely looks like Gibberish. In META II, the order of testing is specified by the rule. The META expr is a conditional expression evaluated left to right.

expr = term ('+' expr | '-' expr | .empty);

Above expr is defined as rule by 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 attempted. In META II a rule is a function returning success or failure. The rule can also be expressed using nested grouping as:

expr = term (('+' |'-') expr | .empty);

The production elements were left out to simplify the example. The examples have used a recursive rule to more closely match the bnf rule. But in META II a loop would more than likely be used The '$' 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.

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.

See also

References

  1. ↑ Dewey, Val Schorre (1963). "A Syntax - Directed SMALGOL for the 1401,". ACM Natl. Conf., Denver,Colo.
  2. ↑ Dewey, Val Schorre (1964). "META II a syntax-oriented compiler writing language". Proceedings of the 1964 19th ACM National Conference.
  3. ↑ Dewey. Val Schorre (date 1963). META II A SYNTAX-ORIENTED COMPILER WRITING LANGUAGE. UCLA: UCLA Computing Facility. Check date values in: |date= (help)

External links

Notes

  1. ↑