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.
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.
In its documentation, META II is described as resembling BNF, which today is explained as a production grammar.
META II is a stack-based functional parser programming language that includes output directive.
META II like other programming languages would overflow its stack attempting left recursion.
The expr equation can also be expressed using nested grouping as: The code production elements were left out to simplify the example.
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: With the ability to express a sequence with a loop or right ("tail") recursion, the order of evaluation can be controlled.
"—Alan KayThe original paper is not freely available, but was reprinted in Doctor Dobb's Journal (April 1980).
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.
These languages were developed by members of the L.A. ACM SIGPLAN sub-group on Syntax Directed Compilers.