META II was a simple translator writing system written by V Schorre in 1962. It was used at the Atlas Laboratory both as an educational tool and for a variety of pre-processing tasks. Probably the major use was the FOREST pre-processor for FORTRAN on the Prime systems. The system used at RAL was considerably modified from the original Schorre version. Additional syntax constructs were added and the notation was also changed. It was continually evolving and this is a snapshot taken around 1978. See a modern tutorial on the topic at http://www.bayfronttechnologies.com/mc_tutorial.html.
The basic ideas involved in the META series of compilers were formulated in three early papers:
The first system META I, was not a great success. META II, on the other hand was widely used on a variety of systems.
A third system, META III, was defined in terms of META II and ran on an IBM 7090. Its main addition was putting recognised items on a stack rather than a simple buffer for a single recognised symbol. The implementation at Atlas was really META 2.5 in that it added additional buffers to make things easier but did not go for a stack of recognised items. In some ways it is more flexible than the META III implementation. Between 1964 and 1967, META 4, META 5 and META PI were defined. None of these were very successful but the final system TREE-META, in 1968, was a major contribution. TREE-META was also widely used at Atlas.
In META II, the language for which a translator is required must be specified as a set of syntax rules. These very much resemble the BNF notation except that they contain code generation commands as part of the syntax definition. There is limited memory in META II so there is a need to output information soon after it has been recognised. For this reason, it is usual to translate from a High Level Language into an Assembler and let the Assembler handle the second pass of the translation. Part of the translator is a set of hand-coded routines called by the translator.
A restrictive top-down method of syntax analysis is used in the META II system. The restriction is that it does not allow back tracking. The main goal is to match the complete program with the Syntax Rule whose name follows .META at the head of the program. The name of the Syntax Rule appears at the start of the rule followed by the = symbol. The right-hand side of this Syntax Rule indicates which entities have to be recognised to achieve this goal. The recogniser achieves its main goal by looking for these smaller entities, from left to right, as individual subgoals. These subgoals are themselves defined in terms of other entities, and so the process of recognising a complete program becomes a matter of looking for progressively smaller entities, right down to the level at which basic symbols such as characters and numbers are recognised. For example, a simple META II program is:
.META SIMPLE SIMPLE = 'A' VOWEL / 'B' SIGN ; VOWEL = 'A' / 'E' / 'I' / 'O' / 'U' ; SIGN = '+' | '-' ; .END
The right-hand side of each Syntax Rule consists of a set of alternatives separated by the / symbol (similar to the BNF | symbol). Identifiers define subgoals that need to be recognised while strings indicate that the particular characters making up the string are expected at this point. In the example, a SIMPLE program is defined as consisting of the letter A followed by a vowel, or the letter B followed by a sign. The complete set of SIMPLE programs is:
AA AE AI AO AU B+ B-
META II's method of syntax analysis is a restrictive top-down which does not allow backtracking other than in the first subgoal of an alternative. If non-recognition occurs at a subgoal other than the first, the translator will stop and output an error diagnostic. For example:
. META SMALL SMALL = FIRST SECOND / ONLY ; FIRST = 'AB' ; SECOND = 'C' ; ONLY = 'ABD' ; .END
This translator will only recognise the program consisting of the symbols ABC. It cannot recognise the program ABD. If this program is input, the first alternative of SMALL will be tried which, initially, matches the subgoal FIRST with the input symbols AB. The subgoal SECOND now expects the input to consist of the character C when, in fact, it is D. This failure is not in the first subgoal of an alternative and so the recogniser will stop with an error. This form of syntax analysis is not as restrictive as it may at first seem. By suitable bracketing of subgoals, many languages can be recognised without backtracking.
At any point in the syntax analysis, the recogniser will be attempting to match the current subgoal or stest with the input still to be read. The result of matching the input with a subgoal will always be to move the position reached in the input to a point immediately after the recognised characters. For subgoals and strings preceded by the symbol fullstop, the recognised input will be placed on a stack ready for output.
The possible subgoals, which match the input with a particular entity are given below. In all cases, spaces and newlines are ignored if they appear on the input preceding the entity to be recognised.
Examples of possible rules, with input they can recognise, are:
(1) FRED = 'ABC' 'CDE' / 'GH' 'JK' ; ABC CDE GH JK (2) FRED = .NUMBER .ID ; 39 ABC1D
The right-hand side of a META II statement consists of a set of alternatives separated by /. It is, however, possible to use brackets in much the same way as they are used in arithmetic expressions so that a set of alternatives act as though they were a single alternative. The result of a bracketed alternative list is either true or false depending on whether any alternative is recognised. For example:
A = B '*' C C = D / E
could be written:
A = B '*' ( D / E )
It mainly acts as a compacting of the syntax definition.
Although it is possible to define a sequence of similar items recursively, META provides a specific construction for this case which is both more efficient and easier to read. The special symbol $ is used to signify that the following subgoal will be recognised repeatedly until a failure to match occurs. It is possible for the subgoal not to be matched at all. For example:
SET = 'C' $ 'C' ;
will recognise a sequence of any number of C characters as long as there is at least one. The subgoal following the $ symbol can be a bracketed entity. In this case, one of the alternatives within the brackets is recognised repeatedly until a failure to match occurs. For example:
SET = 'C' $ ( 'D' / 'E' )
recognises any string consisting of the letter C followed by any sequence involving the letters D and E. Thus:
CDDEDDE and CEDDED
would both be recognised.
A recogniser for arithmetic expressions involving addition and multiplication in its simplest form would be defined as:
.SYNTAX EXP
EXP = TERM ( '+' EXP / .EMPTY ) ;
TERM = PRIMARY ( '*' TERM / .EMPTY ) ;
PRIMARY= .ID / .NUMBER / '(' EXP ')' ;
.END
will recognise strings of the form:
ALPHA 1.7 ALPHA + 1.7 ALPHA*BETA *1.7 * GAMMA ALPHA*(BETA+1.7) + GAMMA
The same recogniser can be written using the $ notation as:
.SYNTAX EXP
EXP = TERM $( '+' TERM ) ;
TERM = PRIMARY $( '*' PRIMARY) ;
PRIMARY= .ID / .NUMBER / '(' EXP ')' ;
.END
Each statement or rule in META is conceptually compiled into a section of code which is similar to a recursive subroutine. The appearance of a rule name on the right hand side of a statement is equivalent to a call of that statement. For example, to recognise X+3 the translator first calls the rule EXP. Using the second definition above this will call the rule TERM remembering the position reached in the EXP statement. The rule TERM attempts to recognise a PRIMARY by calling that rule. The PRIMARY rule first checks for an identifier and is successful. An exit from the rule PRIMARY occurs and it returns to the TERM rule ready to attempt to recognise the item within the $ bracket. Initially it is necessary to try and match the input with the string * but the input pointer is pointing at the + symbol following X. There is a failure to match at this point and as it is allowed to have no matches of the $ item, the TERM recognition is complete. The recognition now continues looking for the $ item in the EXP statement and so on.
The constructs defined so far for META statements are capable of generating a recogniser for the language under consideration but that is all. It is capable of deciding whether the programs or files presented to it are free from error but no compilation or transliteration as such takes place. To generate output it is necessary to specify output commands within the META statements. Each alternative in a META statement can consist of a set of items which may be either syntactic recognisers or output commands. As the top down recogniser moves to the next alternative, it will attempt to recognise it if it is a syntactic expression or will output the required information if it is an output command.
The output command can be thought of as similar to .EMPTY in that it returns a success result as far as recognition is concerned. In general, it is unwise to use it as the first item of an alternative unless the alternative is using a construct which is always successful.
Output commands consist of a number of output items enclosed in brackets. The form of the brackets depend on the output stream to be used. They are:
It is possible to direct the Output File Stream to the terminal so that, for example, the two streams could be merged during debugging. All output is sent to an output buffer which is not emptied until either the buffer is full or a newline is output. The set of output items is given below.
There are a number of more complex output commands involved with labels and manipulating the recognition buffer that will be described later. Examples of possible statements with the input they can recognise and the equivalent output are:
FRED = .ID ',' [ 'ID= ' * ] .NUMBER ['-' * % ] ; Input XYZ,27 Output ID= XYZ-27 FRED = .. ':' [ 'TRUNC=' *B ' END' % ] ; Input a string Output TRUNC=a string END
As items are recognised such as .ID and .NUMBER the symbols are put into a recognition buffer which is 90 characters long. Any attempt to recognise another item which puts its result in the recognition buffer will cause the recognition buffer to be emptied. It will no longer be available for use in an output command. For example:
FRED = .ID .NUMBER [ * ] ;
This will output the number recognised and there is no way of subsequently outputting the identifier. Similarly:
FRED = .ID ( .NUMBER / . EMPTY [ * % ] ) ;
This is not a sensible META statement as the identifier recognised initially would be placed in the recognition buffer. However, the attempt to match .NUMBER will cause the recognition buffer to be emptied. If a number does not appear on the input, the second of the bracketed alternatives will be tried which will cause the contents of an empty recognition buffer to be output.
The inability to retain more than one item in the recognition buffer can cause difficulties and, for this reason, two ancillary recognition buffers are provided which can contain copies of the recognition buffer. It is possible to move the current contents of the recognition buffer into an ancillary recognition buffer and to return it to the recognition buffer at some later time for outputting. The relevant commands which can appear in an output statement are:
An example of the way these buffers could be used is as follows:
ASGN = .ID '=' [*->1] .NUMBER
[ 'LOAD' * % *<-1 'STORE ' * % ] ;
Input
XYZ = 27
Output
LOAD 27
STORE XYZ
The recognition buffer and the two ancillary buffers are global and apply to all statements. For example, a user may load the recognition buffer in one statement, move it into an ancillary buffer in another, move it back in a third and output it using a fourth.
To generate code for any conditional or control statement it is necessary to have a system whereby the compiler can generate unique internal labels for the compiled program. The META system can generate labels of the form AA001, AA002, AA003, and BB001, BB002, BB003 and so on.
The output command also allows the following two items:
For each case, the first appearance of *1 or *2 in an output command will cause the next free label to be assigned to this statement. Subsequent appearances of *1 or *2 in this statement will cause the same label to be output.
As there are only two series, there is a maximum of two different labels which can be output for anyone statement used. However, if the same statement is used either recursively or from several different places then new labels will be generated each time it is obeyed. For example, an ALGOL-like IF statement might be defined as:
IFST = '.IF' BOOL '.THEN' [ 'BRFALSE ' *1 % ]
ST '. ELSE' [' BR '*2 % ] [ *1 ':' % ]
ST [*2 ':' % ] ;
The item BOOL would be designed to generate code which set a switch to TRUE or FALSE. The routine BRFALSE will branch to the address given as argument if the switch is set to FALSE. The routine BR is an unconditional branch to the label given as argument. Assuming that IFST is one valid possibility for ST then the following might be a possible IF statement:
.IF B>C .THEN .IF D=E .THEN F:=l .ELSE F:=2
.ELSE .IF G<H .THEN J:=2 .ELSE K:=3
The META program would generate the following code(assuming
no internal labels for the AA or BB series had been
output previously)
Code for B>C
BRFALSE AA001
Code FOR D=E
BRFALSE AA002
Code for F=l
BR BB001
AA002:
Code for F=2
BB001:
BR BB002
AA001:
Code for G<H
BRFALSE AA003
Code for J=2
BR BB003
AA003:
Code for K=3
BB003:
BB002:
Notice how the labels are allocated as they are required during the recognition
so that the outer IF uses AA001 and BB002. The label BB001 had already been assigned
to the first second-level IF statement.
It is possible using the initialisation statements to modify the prefix (AA or BB)
which precedes the label number.
LABEL LISTS
In some applications it is necessary for a set of labels to be output rather than a
single label. To aid this, two additional output commands are provided.
An example of the use of these commands might be:
FRED = .NUMBER [ GOTO (' *1 .. ')' % ] ','
.NUMBER [ 'LABEL=' *1+ % ] ;
Input
5,3
Output
GOTO(AA004,AA005,AA006,AA007,AA008)
LABEL=AA006
Preceding the .SYNTAX statement at the head of a META program it is possible to include an initialisation statement which modifies the initial settings of certain parameters. The initialisation statement consists of a set of statements in any order surrounded by .INIT and .INITEND. The possible statements are given below.
An example of an initialisation statement is:
.INIT ' 2 3' TABSET=6 CRIN=187 .INITEND
This defines the label prefixes as 2 and 3, sets tab positions every 6 spaces and specifies the input carriage return character as semicolon.
All files associated with META are kept in the sub-directory META of directory APPLIC. A particular system is defined by writing a file SYSDF which contains the META program. Any name can be used but the convention is for the program to have DF at the end of the name. The META system can compile such a program and produce an eye-readable version of the compiled SYSDF program. This file is sometimes used for debugging purposes although it need be of no interest to the average user. As mentioned before, META programs are interpreted and it is necessary to provide a mechanism for converting the external form of the program, defined as SYSOU, into the internal machine-readable form which is ready for interpretation. Most META system programs have an input file SYSFR from which input is read and an output file SYSTO to which output is sent. Finally, in order to save time in converting from the external to internal form for every run, it is possible to dump the internal form of a program in a file. Such a file is usually called SYSBN.
As META is itself a META program just like any other it is defined by a META program called METADF which, when executed by the META system produces a file METAOU. The internal form of this program is stored in the file METABN for efficient loading. The main facilities are defined below.
A sensible set of commands for loading the META System and compiling and executing a particular META program then proceeds as follows:
BININ METABN EXECTE SYSDF SYSOU CONVRT SYSOU EXECTE SYSFR SYSTO
Once the particular META program SYSOU has been compiled, subsequent runs need only execute:
CONVRT SYSOU EXECTE SYSFR2 SYST02
Alternatively a more efficient loading mechanism can be provided by dumping the internal form:
CONVRT SYSOU BINOUT SYSBN
Subsequent runs of the program could then be done by:
BININ SYSBN EXECTE SYSFR3 SYST03
The simplest method of accessing the META system is using the SEG file #META which contains an environment which will accept commands in the form defined in the previous section and provide all the necessary file opening automatically. The system is entered by executing the command:
SEG #META
Once the system has been loaded, it will prompt the user with the string:
COMMAND:
Any of the commands EXECTE,CONVRT,BININ,BINOUT,EXEC and FINISH with their relevant arguments can be input in response to the prompt.
The system functions EXECTE,CONVRT,BININ and BINOUT can all be called directly from a FORTRAN program. The relevant FORTRAN subroutines have the names given above and do not have any arguments. Before any META functions can be executed, the system must be initialised by calling INITST. Before calling EXECTE, the routine INITEX must be called. The files associated with particular commands must be open on the relevant streams before the routine is called. The relevant streams are:
EXECTE Input stream 5 Output stream 6 CONVRT Input stream 7 BINOUT Output stream 8 BININ Input stream 9
Suppose, for example, a user wishes to compile a META program SYSDF and store the output form of the compiled program in SYSOU. This could be done by the following run:
SEG #META COMMAND:BININ METABN COMMAND:EXECTE SYSDF SYSOU COMMAND: FINISH
An alternative method would be to define a FORTRAN program:
CALL INITST
CALL BININ
CALL INITEX
CALL EXECTE
STOP
END
If this program is loaded with the META routines into a file #SYS, this would be executed by:
OPEN METABN 11 1 OPEN SYSDF 5 1 OPEN SYSOU 6 2 SEG #SYS CLOSE ALL
Note the rather unfortunate PRIME method of defining stream numbers in octal so that stream 9 is defined as 11!
The META system is currently defined as a set of binary files which need to be loaded with a FORTRAN program that uses them. As the main routines call all the others, there is little to be gained by putting them in a library. The set of files are:
B_MNMTFL B_CVMTFL B_EXMTFL B_EYMTFL B_LBMTFL
The file B_MNMTFL is the main program which accepts commands and gives the relevant prompts. The FORTRAN program defined in the previous section would not need to load the first file defined above but would require to load all the rest.
In most cases, on meeting an error, the META system stops and prints an error message. In only a few cases is it possible for META to continue past an error. This may appear to be a rather catastrophic situation. However, it is frequently possible to formulate META programs so that, to some extent, they can handle their own error recovery. This is done by defining the most likely errors as legal syntax but with the generated output being the appropriate error messages.
The current set of error messages are:
Attempts to continue are only made in the cases marked with the * symbol.
After the error message, the current contents of the input string buffer are output together with a pointer indicating the position reached so far in the recognition process. The illegal text should be to the right of the pointer. This information applies only to those errors encountered during syntax analysis and not those encountered with the CONVRT operation. The ring buffer will usually contain more than one input line. The newline positions are marked by displaying semicolon symbols in their place.
This program is included partly as an example of a META program but also as a useful system for documenting FORTRAN programs. The assumption is that it will be used when a set of FOREST routines (or FORTRAN) are to be input for the first time. A typical routine in its documented form might be:
SUBROUTINE INBF(JCHAR)
C------------------------------------------------------------
C
C PURPOSE
C ENTERS CHARACTER INTO NEXT POSITION IN RECOG BUFFER
C
C METHOD
C CHARACTERS ARE ADDED UP TO A MAX OF JRECTP. AFTER THAT
C THEY ARE IGNORED
C HISTORY
C AUTHOR-FRAH DATE-17.2.77 MACHINE PRIME 400
C
C ARGUMENTS IN
C JCHAR=CHARACTER FROM INPUT TO BE PLACED IN BUFFER
C
C COMMON ACCESSED
C SYSTEM-JRECMX,JRECTP
C
C COMMON ALTERED
C SYSTEM-JRECMX,JRECOG
C
C ROUTINES CALLED
C PACKAGE-MTERR
C
C
C SUBROUTINE INBF(JCHAR)
C************************************************************
C
$INSERT SYSTEM
JRECMX=JRECMX+l
IF(JRECMX .EQ. JRECTP+l) CALL MTERR(-10)
IF(JRECMX .GT. JRECTP) RETURN
JRECOG(JRECMX)=JCHAR
RETURN
END
C
C
The main points are that each routine to be input needs to have the same HISTORY section added to it and so this is defined once at the start of the session and will be included automatically at the specified point in each routine. The initial heading for the routine is repeated as a comment line just before the body of the routine and so this also needs to be stored for future use.
The system runs in an interactive mode with prompts to the user indicating the information to be typed. The user may wish to make comments in which case he types the relevant comment and terminates it by a blank line. Alternatively, he may wish to ignore a particular section as nothing relevant needs to be said in which case, a carriage return will move him on to the next prompt. The necessary indenting and C characters in the first line position will be provided by the system. The user will eventually be asked to type the routine itself and this is concluded by the user typing ***. At this stage the system returns to the start ready to input the documentation for another routine. If no more routines are to be input, the user should type .FINISH.
The META documentation program is defined as DOCDF and the binary version of the program is in the file DOCBN. To generate the commented routine INBF in the file PRINBF would require the following interaction:
SEG #META
-GO
-COMMAND: BININ DOCBN
-COMMAND: EXEC PRINBF
-TYPE HISTORY LINE, AUTHOR-DATE-MACHINE
AUTHOR-FRAH DATE-17.2.77 MACHINE PRIME 400
-TYPE ROUTINE HEADING
SUBROUTINE INBF(JCHAR)
-PURPOSE E
ENTERS CHARACTER INTO NEXT POSITION IN RECOGNITION BUFFER
-METHOD
CHARACTERS ARE ADDED UP TO A MAX OF JRECTP. AFTER THAT
THEY ARE IGNORED
-ARG IN
JCHAR=CHARACTER FROM INPUT TO BE PLACED IN BUFFER
-ARG OUT
-COM IN
SYSTEM-JRECMX,JRECTP
-COM OUT
SYSTEM-JRECMX,JRECOG
-LOCALS
-ROUTINES
PACKAGE-MTERR
-TYPE ROUTINE FINISHING ***
$INSERT SYSTEM
JRECMX=JRECMX+1
IF(JRECMX .EQ. JRECTP+1) CALL MTERR (-10)
IF(JRECMX .GT. JRECTP) RETURN
JRECOG(JRECMX)=JCHAR
RETURN
END
***
-TYPE ANOTHER ROUTINE HEADING
.FINISH
-COMMAND: FINISH
Prompts are indicated by a - symbol preceding the line. The META program, DOCDF, for the documentation system is as follows:
.INIT CRIN=187 TABSET=6 INSTR=l .INITEND
.SYNTAX DOC
DOC = HISTORY [. 'TYPE ROUTINE HEADING' % .]
$ (. NOT '. FINISH' .BUT ROUTINE
[ . 'TYPE ANOTHER ROUTINE HEADING' % .] ) ;
HISTORY = [. 'TYPE HISTORY LINE,AUTHOR-DATE-MACHINE' % .] .. ';' [*->2] ;
ROUTINE = HEADING PROLOG BODY ;
HEADING = ..';' [*->1 *T *B % ]
['C---------------------------------------------------------'
'--------------------' % 'C' % ] ;
PROLOG= [.'PURPOSE' % .] (';' /['C PURPOSE' %] SECTION)
[. 'METHOD' % .] (';' /['C METHOD' %] SECTION)
['C HISTORY' % ] [*<-2 'C' *T ' ' *B % 'C' %]
[. 'ARG IN' % .] (';'/['C ARGUMENTS IN' %] SECTION)
[. 'ARG OUT'% .] (';'/['C ARGUMENTS OUT' %] SECTION)
[. 'COM IN' % .] (';'/['C COMMON ACCESSED' %] SECTION)
[. 'COM OUT'% .] (';' / ['C COMMON ALTERED' %] SECTION)
[. 'LOCALS' % .] (';' / ['C LOCALS' %] SECTION)
[. 'ROUTINES' % .] (';' / ['C ROUTINES CALLED' %] SECTION)
['C' *T *<-1 *B %]
['C**********************************************************'
'*******************' % 'C' % ] ;
BODY = [. 'TYPE ROUTINE FINISHING ***' % .]
$ ( .NOT ,***' . BUT ..';' [ *B %] ) ';' ['C' % 'C' % ]
[' C' % 'C' % ] ;
SECTION $ ( .NOT ';' .BUT ..';' ['C' *T ' , *B %] ) ['C' % ];
. END