glorified left-fold (mine was about 66
lines of Python).
1. Hand-translate the META II productions to the machine language (211
lines of m2vm opcodes).
follow in Schorre’s footsteps directly,
using the traditional bootstrap:
0. Hand-code the META II ma-
chine—this is basically an assembler-
like virtual machine: in other words, a
product4), you might call this monad-
ic composition. In the days of small
memories and essentially linear card
decks, the flattened sequence was the
norm rather than the exception, and in
our times Rick Hehner’s bunches5 are
a good example of a case where flatten-
ing can make the formulae of “formal
methods” more easily manipulable
than normally nestable sets.
Note that it has taken only two
pages for Schorre to describe what we
need for META II. The remainder of
the article focuses on a description of
VALGOL, which might make a suitable
destination for another day. Let us take
a brief pause, however, to examine a
couple of points:
˲ “The omission of statement labels
from the VALGOL I and VALGOL II
seems strange to most programmers.
This was not done because of any difficulty in their implementation, but
because of a dislike for statement labels on the part of the author. I have
programmed for several years without
using a single label, so I know they
are superfluous from a practical, as
well as from a theoretical, standpoint.
Nevertheless it would be too much of
a digression to try to justify this point
here.” History agrees the digression
would have been superfluous; indeed,
now it seems strange that it then
seemed strange. Tempora mutantur,
nos et mutamur in illis (times change,
and we change with them).
˲Finally, Schorre discusses the
problem of backup vs. no backup,
which is still a current topic, as the
recent popularity of the parsing expression grammar (PEG) and other
parsers will attest. In our times, however, we are not so interested in avoiding backup, but in avoiding the need
to start at the beginning and process
linearly until we reach the end. Luckily for compiler writers, whether or not
a production can be matched by an
empty string is a property that can be
determined by divide and conquer...
but it is one of the few1 that are tackled
so simply.
The heart of the matter comes in
figures 5 and 6 in the original article,
“The META II Compiler Written in its
Own Language” (Figure 1 in this article) and “Order List of the META II
Machine” (figures 2 through 4 here).
Now, it would certainly be possible to
Figure 1. The META II compiler written in its own language (Figure 5 from Schorre’s
original paper).
.SYNTAX PROGRAM
OUT1 = '* 1' .OUT('GN1') / '* 2' .OUT('GN2') /
'*' .OUT ('CI') / .STRING .OUT('CL ' *).,
OUTPUT = ('.OUT' '('
OUT1 ')' / '.LABEL' .OUT ('LB') OUT1) .OUT('OUT').,
EX3 = .ID .OUT ('CLL' *) / .STRING
.OUT('TST' *) / '.ID' .OUT('ID') /
'.NUMBER' .OUT('NUM') /
'.STRING' .OUT('SR') / '(' EX1 ')' /
'.EMPTY' .OUT('SET') /
'$' .LABEL 1 EX3
.OUT ('BT ' 1) .OUT('SET').,
EX2 = (EX3 .OUT('BF ' 1) / OUTPUT)
$(EX3 .OUT('BE') / OUTPUT)
.LABEL 1 .,
EX1 = EX2 $('/' .OUT('BT' 1) EX2 )
.LABEL 1 .,
ST = .ID .LABEL '=' EX1
'.,' .OUT('R').,
PROGRAM = '.SYNTAX' .ID .OUT ('ADR' *)
ST '.END' .OUT ('END').,
.END
Figure 2. Order list of the META II machine (Figure 6. 1 in Schorre’s original paper).
Machine Codes
TST STRING TEST After deleting initial blanks in the input string, compare it to the string
given as argument. If the comparison is met, delete the matched
portion from the input and set switch. If not met, reset switch.
ID IDEN TIFIER After deleting initial blanks in the input string, test if it begins with
an identifier; that is, a letter followed by a sequence of letters and/or
digits. If so, delete the identifier and set switch. If not, reset switch.
NUM NUMBER After deleting initial blanks in the input string, test if it begins with
a number. A number is a string of digits which may contain imbeded
periods, but may not begin or end with a period. Moreover, no two
periods may be next to one another. If a number is found, delete it
and set switch. If not, reset switch.
SR STRING After deleting initial blanks in the input string, test if it begins with a
string; that is, single quote followed by a sequence of any characters
other than a single quote followed by another single quote. If a string
is found, delete it and set switch. If not, reset switch.
CLL AAA CALL Enter the subroutine beginning in location AAA. If the top two terms
of the stack are blank, push the stack down by one cell. Otherwise,
push it down by three cells. Set a flag in the stack to indicate
whether it has been pushed by one or three cells. This flag and the
exit address go into the third cell. Clear the top two cells to blanks to
indicate they can accept addresses which may be generated within
the subroutine.