Tutorial: Metacompilers Part 1

James M. Neighbors
James.Neighbors@BayfrontTechnologies.com
Bayfront Technologies, Inc.
August 20, 2008 revised August 12, 2016
 Tutorial in PDF (2008 version), see Revisions

META II: A Syntax-Oriented Compiler Writing Language.
Schorre, D. V.
In Proceedings of the 1964 19th ACM National Conference,
ACM Press, New York, NY, 41.301-41.3011, 1964.
available as http://doi.acm.org/10.1145/800257.808896

Abstract:
Meta II is a compiler writing language which consists of syntax equations resembling Backus normal form and into which instructions to output assembly language commands are inserted. Compilers have been written in this language for VALGOL I and VALGOL II. The former is a simple algebraic language designed for the purpose of illustrating META II. The latter contains a fairly large subset of ALGOL 60.

The method of writing compilers which is given in detail in the paper may be explained briefly as follows. Each syntax equation is translated into a recursive subroutine which tests the input string for a particular phrase structure, and deletes it if found. Backup is avoided by the extensive use of factoring in the syntax equations. For each source language, an interpreter is written and programs are compiled into that interpretive language.

META II is not intended as a standard language which everyone will use to write compilers. Rather, it is an example of a simple working language which can give one a good start in designing a compiler-writing compiler suited to his own needs. Indeed, the META II compiler is written in its own language, thus lending itself to modification.

"Many details of those two days (February 4-5, 1967) still remain fresh in my mind. ... Peter [Wegner] asked me what I thought about formal semantics, and I said I liked Iron's idea of synthesizing an overall meaning from submeanings. I also said that I liked the way other people had combined Irons's approach with a top-down or "recursive-descent" parser; Irons had used a more complex parsing scheme. In particular, I was impressed by the metacompiler of Val Schorre [Schorre64] and by the more powerful (though less elegant) "transmogrifier" of Bob McClure [McClure65]."

1. Input provides the text input to the compiler. There is a drop down selection for the texts used in the META II paper and the many extensions on these pages. Feel free to edit the Input window text by keystroke or cut-and-paste.
2. Code provides the pseudo assembly language presented in the META II paper and later JavaScript extensions. We will discuss the meaning of this language later. There is a drop down selection for the codes used in the META II paper and on these pages. You may also edit the Code window text.
3. Output is the output of the last compile. There are two output-related buttons: "Copy to Code" and "Clear". "Copy to Code" is used if the output is a new compiler you wish to test. As with all the other windows you may edit the text of the Output window.

1. Select Input i01. demo, AEXP example assignments
2. Select Code c01. demo, AEXP assignments compiler c[i02,c02]
3. Click the "Compile" button in the lower left corner

fern:=5+6;
ace:=fern*5;
waldo:=fern+alpha/-beta^gamma;

	address fern
	literal 5
	literal 6
	add
	store
	address ace
	load fern
	literal 5
	mpy
	store
	address waldo
	load fern
	load alpha
	load beta
	minus
	load gamma
	exp
	div
	add
	store

1. Select Input "Input Clear"
2. Select Input "i01. demo, AEXP example assignments"
3. Select Code "c01. demo, AEXP assignments compiler c[i02,c02]"
4. Click the "Compile" button in the lower left corner
5. Select Code "c00. demo, compiled assignments c[i01,c01]"
6. Click the "Compare Code and Output" button in the lower left corner

1. Select Input "Input Clear"
2. Select Input "i01. demo, AEXP example assignments"
3. Select Code "c01. demo, AEXP assignments compiler c[i02,c02]"
4. Click the "Compile" button in the lower left corner

1. Change the name of one of the Input variables and click Compile to prove that we are actually compiling the contents of the Input window.
2. Change the name of one of the Code constants (e.g., 'store' into 'save' or something) in the Code window and click Compile. (Yes you can edit the Code window and it is the code we run when Compile is clicked. If you create an infinite loop you will have to close and restart the browser.)
3. Try editing the Input and clicking "Compile" until you receive the error notification alert box. The last line in the alert box tells you where the compiler was scanning when it encountered the error by inserting a <scan> marker into the erroneous input line.

1. Select Input "i02. demo, AEXP example assignment compiler"
2. Click the "Extract Syntax to Output" button in the lower left corner

.SYNTAX AEXP

AEXP = AS $AS .,
AS = .ID .OUT('address ' *) ':=' EX1 .OUT('store') ';' .,
EX1 = EX2 $('+' EX2 .OUT('add') /
            '-' EX2 .OUT('sub') ) .,
EX2 = EX3 $('*' EX3 .OUT('mpy') /
            '/' EX3 .OUT('div') ) .,
EX3 = EX4 $('^' EX3 .OUT('exp')) .,
EX4 = '+' EX5 / '-' EX5 .OUT('minus') / EX5 .,
EX5 = .ID  .OUT('load ' *) /
      .NUMBER .OUT('literal ' *) /
      '(' EX1 ')' .,

.END

.SYNTAX AEXP

AEXP = AS $AS ;

AS = .ID ':=' EX1 ';' ;

EX1 = EX2 $( '+' EX2 / '-' EX2 ) ;

EX2 = EX3 $( '*' EX3 / '/' EX3 ) ;

EX3 = EX4 $( '^' EX3 ) ;

EX4 = '+' EX5 / '-' EX5 / EX5 ;

EX5 = .ID / .NUMBER / '(' EX1 ')' ;

.END

1. Select Input "i02. demo, AEXP example assignment compiler"
2. Select Code "c02. Meta II of fig. 5, c[i03,c02]"
3. Click the "Compile" button in the lower left corner

1. Click the "Copy to Code" button at the top of the Output window
2. Select Input "i01. demo, AEXP example assignments"
3. Click the "Compile" button in the lower left corner
4. Select Code "c00. demo, compiled assignments c[i01,c01]"
5. Click the "Compare Code and Output" button in the lower left corner

1. Select Input "i02. demo, AEXP example assignment compiler"
2. Select Code "c02. Meta II of fig. 5, c[i03,c02]"
3. Click the "Compile" button in the lower left corner
4. Select Code "c01. demo, AEXP assignments compiler c[i02,c02]"
5. Click the "Compare Code and Output" button in the lower left corner

1. Select Input "i03. Meta II syntax (paper fig. 5)"
2. Click the "Extract Syntax to Output" button in the lower left corner

.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

.SYNTAX PROGRAM

OUT1 = '*1' / '*2' / '*' / .STRING ;

OUTPUT = ( '.OUT' '(' $OUT1 ')' /
           '.LABEL' OUT1 ) ;

EX3 = .ID / .STRING / '.ID' /
      '.NUMBER' / '.STRING' /
      '(' EX1 ')' / '.EMPTY' /
      '$' EX3 ;

EX2 = ( EX3 / OUTPUT )
      $( EX3 / OUTPUT ) ;

EX1 = EX2 $( '/' EX2 ) ;

ST = .ID '=' EX1 '.,' ;

PROGRAM = '.SYNTAX' .ID $ST '.END' ;

.END

1. Select Input "i03. Meta II syntax (paper fig. 5)"
2. Select Code "c02. Meta II of fig. 5, m[i03,c02]"
3. Click the "Compile" button in the lower left corner. This may take a while, so wait for the "Done.".
4. Click the "Compare Code and Output" button in the lower left corner

1. Click the Output "Copy to Code" button and Output "Clear" button
2. Click the "Compile" button in the lower left corner. This may take a while, so wait for the "Done.".
3. Click the "Compare Code and Output" button in the lower left corner

1. Select Input "i04. Meta II syntax (i03 reordered)"
2. Click the "Extract Syntax to Output" button in the lower left corner

.SYNTAX PROGRAM

PROGRAM = '.SYNTAX' .ID .OUT('ADR ' *)
          $ ST
          '.END' .OUT('END') .,

ST = .ID .LABEL * '=' EX1 '.,' .OUT('R') .,

EX1 = EX2 $('/' .OUT('BT ' *1) EX2 )
      .LABEL *1 .,

EX2 = (EX3 .OUT('BF ' *1) / OUTPUT)
      $(EX3 .OUT('BE') / OUTPUT)
      .LABEL *1 .,

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') .,

OUTPUT = ('.OUT' '('$OUT1 ')' /
          '.LABEL' .OUT('LB') OUT1)
         .OUT('OUT') .,

OUT1 = '*1'    .OUT('GN1')  /
       '*2'    .OUT('GN2')  /
       '*'     .OUT('CI')   /
       .STRING .OUT('CL '*) .,

.END

.SYNTAX PROGRAM

PROGRAM = '.SYNTAX' .ID $ST '.END' ;

ST = .ID '=' EX1 '.,' ;

EX1 = EX2 $( '/' EX2 ) ;

EX2 = ( EX3 / OUTPUT )
      $( EX3 / OUTPUT ) ;

EX3 = .ID / .STRING / '.ID' /
      '.NUMBER' / '.STRING' /
      '(' EX1 ')' / '.EMPTY' /
      '$' EX3 ;

OUTPUT = ( '.OUT' '(' $OUT1 ')' /
           '.LABEL' OUT1 ) ;

OUT1 = '*1' / '*2' / '*' / .STRING ;

.END

1. Select the Input "i04. Meta II syntax (i03 reordered)"
2. Select Code "c02. Meta II of fig. 5, m[i03,c02]"
3. Click the "Compile" button in the lower left corner and wait for the "Done.".
4. Check your guesses for the second and third output lines using the Output window

.SYNTAX PROGRAM

PROGRAM = '.SYNTAX' .ID .OUT('ADR ' *)
          $ ST
          '.END' .OUT('END') .,

	ADR PROGRAM
PROGRAM
	TST '.SYNTAX'
	BF L1
	ID
	BE
	CL 'ADR '
	CI
	OUT
L2
	CLL ST
	BT L2
	SET
	BE
	TST '.END'
	BE
	CL 'END'
	OUT
L1
L3
	R

1. Define a compiler description that ejects your favorite language code
2. Paste it into the Input window
3. Have one of the compilers on these web pages generate the translation to your favorite language
4. Cut the code generated in your favorite language from the Output window
5. Continue compiler and metacompiler development in your favorite language

1. Select the Input "i04. Meta II syntax (i03 reordered)"
2. Select Code "c02. Meta II of fig. 5, m[i03,c02]"
3. Click the "Compile" button in the lower left corner and wait for the "Done.".
4. Click the "Compare Code and Output" button in the lower left corner. The Code and Output do not compare - so c[i04,c02] generated above is not a metacompiler by our textual comparison definition. The Code and Output do not compare because the syntax rules are generated into the output in order - and the rule order between the bottom-up i03 description which generated c02 and the top-down i04 description is different.
5. Click the Output "Copy to Code" button and Output "Clear" button
6. Click the "Compile" button in the lower left corner and wait for the "Done.".
7. Click the "Compare Code and Output" button in the lower left corner. It does compare - so it is a metacompiler.
8. Select Code "c03. Meta II reordered, c[i04,c02], m[i04,c03]"
9. Click the "Compare Code and Output" button in the lower left corner. It does compare - proving our new metacompiler has been named c03

1. c03 = m[i04,c03] = c[i04,c02] = c[i04,m[i03,c02]]
2. c02 = m[i03,c02] = c[i03,c03] = c[i03,m[i04,c03]]

1. Select the Input "i05. add semicolon line end"
2. Select Code "c03. Meta II reordered, c[i04,c02], m[i04,c03]"
3. Click the "Compile" button in the lower left corner and wait for the "Done.".

1. Click the "Compare Code and Output" button in the lower left corner. The Code and Output do not compare - so c[i05,c03] generated above is not a metacompiler. The Code and Output do not compare because the Output c[i05,c03] compiler from i05 is looking for ; terminated syntax rules while the c03 compiler is looking for ., terminated syntax rules.

1. Click the Output "Copy to Code" button and Output "Clear" button
2. Click the "Compile" button in the lower left corner and wait for the "Done.".
3. The above compile of c[i05,c[i05,c03]] fails with a syntax error where the error <scan> marker points to the ., at the end of the initial PROGRAM rule because this new compiler only accepts semicolons at the end of rule descriptions. c[i05,c03] is looking for ; terminated syntax rules while the i05 input contains ., terminated syntax rules.

1. Select the Input "i06. use semicolon line end"
2. Click the "Compile" button in the lower left corner and wait for the "Done.".
3. Click the "Compare Code and Output" button in the lower left corner. It does compare - so it is a metacompiler.
4. Select Code "c04. Meta II semicolons, c[i05,c03], m[i06,c04]"
5. Click the "Compare Code and Output" button in the lower left corner. It does compare - proving our new metacompiler has been named c04

1. Making i05 from i04 that recognizes the new syntax for the existing c03 metacompiler.
2. Creating the plain compiler c[i05,c03] as a stepping stone.
3. Making i06 from i05 that uses the defined syntax.
4. Validating that c04 is new expanded metacompiler made as c04 = c[i06,c[i05,c03]]

1. c04 = m[i06,c04] = c[i05,c03] = c[i05,m[i04,c03]]

OUT1 = '*1'    .OUT('GN1') /
       '*2'    .OUT('GN2') /
       '*'     .OUT('CI')  /
       .STRING .OUT('CL '*) .,

OUT1 = '*1'    .OUT('GN1') /
       '*2'    .OUT('GN2') /
       '*'     .OUT('CI') /
       .STRING .OUT('CL '*) /
       '#'     .OUT('GN') /
       '.NL'   .OUT('NL') /
       '.LB'   .OUT('LB') /
       '.TB'   .OUT('TB') /
       '.LM+'  .OUT('LMI') /
       '.LM-'  .OUT('LMD') .,

1. Select Input "i07. add new output control"
2. Select Code "c04. Meta II semicolons, c[i05,c03], m[i06,c04]"
3. Click "Compile"
4. Click "Compare Code and Output" It does not compare because c[i07,c04] recognizes the extended syntax.
5. Click the Output "Copy to Code" button and Output "Clear" button
6. Click "Compile"
7. Click "Compare Code and Output" It does compare so c[i07,c[i07,c04]] is a metacompiler.
8. Select Code "c05. accept new output, c[i07,c04], m[i07,c05]"
9. Click "Compare Code and Output" It does compare so c05 is the name of the new metacompiler.

1. c05 = m[i07,c05] = c[i07,c[i07,c04]]
2. c04 = m[i06,c04] = c[i06,c[i06,c05]]

.SYNTAX PROGRAM

PROGRAM = '.SYNTAX' .ID .OUT('ADR ' *)
          $ ST 
          '.END' .OUT('END') ;

ST = .ID .LABEL * '=' EX1 ';' .OUT('R') ;

EX1 = EX2 $('/' .OUT('BT ' *1) EX2 )
      .LABEL *1 ;

EX2 = (EX3 .OUT('BF ' *1) / OUTPUT)
      $(EX3 .OUT('BE') / OUTPUT)
      .LABEL *1 ;

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') ;

OUTPUT = '.OUT' '('$OUT1 ')' ;

OUT1 = '*'     .OUT('CI')   / 
       .STRING .OUT('CL '*) /
       '#'     .OUT('GN')   /
       '.NL'   .OUT('NL')   /
       '.LB'   .OUT('LB')   /
       '.TB'   .OUT('TB')   /
       '.LM+'  .OUT('LMI')  /
       '.LM-'  .OUT('LMD')  ;

.END

1. Select Input "i08. delete old output control"
2. Select Code "c05. accept new output, c[i07,c04], m[i07,c05]"
3. Click "Compile"
4. Select Code "c06. reject old output, c[i08,c05]"
5. Click "Compare Code and Output" It does compare so c06 is the name of the stepping stone.

EX1 = EX2 $('/' .OUT('BT ' *1) EX2 )
      .LABEL *1 ;

EX1 = EX2 $('/' .OUT('BT L'# ) EX2 )
      .OUT(.LB 'L'# ) ;

.SYNTAX PROGRAM

PROGRAM = '.SYNTAX' .ID .OUT(.LB .TB 'ADR ' * .NL)
          $ ST
          '.END' .OUT(.TB 'END' .NL) ;

ST = .ID .OUT(.LB * .NL) '=' EX1 ';' .OUT(.TB 'R' .NL) ;

EX1 = EX2 $('/' .OUT(.TB 'BT L'# .NL) EX2 )
      .OUT(.LB 'L'# .NL) ;

EX2 = (EX3 .OUT(.TB 'BF L'# .NL) / OUTPUT)
      $(EX3 .OUT(.TB 'BE' .NL) / OUTPUT)
      .OUT(.LB 'L'# .NL) ;

EX3 = .ID       .OUT(.TB 'CLL '* .NL) /
      .STRING   .OUT(.TB 'TST '* .NL) /
      '.ID'     .OUT(.TB 'ID' .NL)    /
      '.NUMBER' .OUT(.TB 'NUM' .NL)   /
      '.STRING' .OUT(.TB 'SR' .NL)    /
      '(' EX1 ')'                     /
      '.EMPTY'  .OUT(.TB 'SET' .NL)   /
      '$' .OUT(.LB 'L'# .NL) EX3 .OUT(.TB 'BT L'# .NL) .OUT(.TB 'SET' .NL) ;

OUTPUT = '.OUT' '('$OUT1 ')' ;

OUT1 = '*'     .OUT(.TB 'CI' .NL)   /
       .STRING .OUT(.TB 'CL '* .NL) /
       '#'     .OUT(.TB 'GN' .NL)   /
       '.NL'   .OUT(.TB 'NL' .NL)   /
       '.LB'   .OUT(.TB 'LB' .NL)   /
       '.TB'   .OUT(.TB 'TB' .NL)   /
       '.LM+'  .OUT(.TB 'LMI' .NL)  /
       '.LM-'  .OUT(.TB 'LMD' .NL)  ;

.END

1. Select Input "i09. use new output control"
2. Select Code "c06. reject old output, c[i08,c05]"
3. Click "Compile"
4. Click the Output "Copy to Code" button and Output "Clear" button
5. Click "Compile"
6. Click "Compare Code and Output" It does compare so c[i09,c[i09,c06]] is a metacompiler.
7. Select Code "c07. use new output, c[i09,c06], m[i09,c07]"
8. Click "Compare Code and Output" It does compare so c07 is the name of the new metacompiler.

1. c07 = m[i09,c07] = c[i09,c[i08,c05]]

1. Select Input "i09. use new output control"
2. Click "Extract Syntax to Output" button in the lower left corner
3. Click the Output "Copy to Code" button and Output "Clear" button
4. Select Input "i10. convert i09 to js functions"
5. Click "Extract Syntax to Output" button in the lower left corner
6. Click "Compare Code and Output" The two syntax specifications compare.

.SYNTAX PROGRAM

PROGRAM = '.SYNTAX' .ID
            .OUT(.LB '// '*' compiler' .NL)
            .OUT('function compiler (input) {' .LM+ .NL)
            .OUT('inbuf = input ;' .NL)
            .OUT('inp = 0 ;' .NL)
            .OUT('outbuf = "" ;' .NL)
            .OUT('margin = 0 ;' .NL)
            .OUT('gnlabel = 1 ;' .NL)
            .OUT('rule'*'() ;' .NL)
            .OUT('return outbuf ;' .NL)
            .OUT(.LM- '} ;' .NL .NL)
          $ ST
          '.END' ;

ST = .ID .OUT(.LB 'function rule'*' () {' .LM+ .NL)
     .OUT('var rname = "'*'" ;' .NL)
     .OUT('var rlabel = 0 ;' .NL)
     '=' EX1 ';'
     .OUT(.LM- '} ;' .NL .NL) ;

EX1 = EX2 $('/' .OUT('if (!flag) {' .LM+ .NL) EX2 .OUT(.LM- '} ;' .NL) ) ;

EX2 = (EX3 .OUT('if (flag) {' .LM+ .NL) / OUTPUT .OUT('if (true) {' .LM+ .NL) )
      $(EX3 .OUT('if (!flag) runBEjsfn(rname);' .NL) / OUTPUT)
      .OUT(.LM- '} ;' .NL) ;

EX3 = .ID       .OUT('rule'*'();' .NL) /
      .STRING   .OUT('runTST('*');' .NL) /
      '.ID'     .OUT('runID();' .NL)     /
      '.NUMBER' .OUT('runNUM();' .NL)    /
      '.STRING' .OUT('runSR();' .NL)     /
      '(' EX1 ')'                        /
      '.EMPTY'  .OUT('runSET();' .NL)    /
      '$' .OUT('runSET();' .NL)
          .OUT('while (flag) {' .LM+ .NL)
           EX3 
          .OUT('};' .LM- .NL) 
          .OUT('runSET();' .NL) ;

OUTPUT = '.OUT' '('$OUT1 ')' ;

OUT1 = '*'     .OUT('runCI();' .NL)    /
       .STRING .OUT('runCL('*');' .NL) /
       '#'     .OUT('if (rlabel == 0) { rlabel = gnlabel; gnlabel++ ; } ;' .NL)
               .OUT('runCL(rlabel.toString());' .NL) /
       '.NL'   .OUT('runextNL();' .NL)    /
       '.LB'   .OUT('runLB();' .NL)    /
       '.TB'   .OUT('runextTB();' .NL)    /
       '.LM+'  .OUT('runextLMI();' .NL)   /
       '.LM-'  .OUT('runextLMD();' .NL)   ;

.END

1. Select Input "i10. convert i09 to js functions"
2. Select Code "c07. use new output, c[i09,c06], m[i09,c07]"
3. Click "Compile"
4. Select Code "c08. compile to js functions, c[i10,c07]"
5. Click "Compare Code and Output" It does compare so c08 = c[i10,c07] is the stepping stone.
6. Click the Output "Copy to Code" button and Output "Clear" button
7. Click "Compile"
8. Select Code "c07jf. compile to js functions, c[i10,c08], m[i10,c07jf]"
9. Click "Compare Code and Output" It does compare so c07jf = c[i10,c[i10,c07]].
10. Click "Compile"
11. Click "Compare Code and Output" It does compare so c07jf = m[i10,c07jf] is the new metacompiler.

1. Select Input "i09. use new output control"
2. Select Code "c07jf. compile to js functions, c[i10,c08], m[i10,c07jf]"
3. Click "Compile"
4. Click the Output "Copy to Code" button and Output "Clear" button
5. Click "Compile"
6. Select Code "c07. use new output, c[i09,c06], m[i09,c07]"
7. Click "Compare Code and Output" It does compare so c07 is the built compiler.

.SYNTAX PROGRAM

PROGRAM = '.SYNTAX' .ID $ST '.END' ;
ST = .ID '=' EX1 ';' ;
EX1 = EX2 $( '/' EX2 ) ;
EX2 = (EX3 / OUTPUT)
      $(EX3 / OUTPUT) ;
EX3 = .ID / .STRING /
      '.ID' / '.NUMBER' / '.STRING' /
      '(' EX1 ')' / '.EMPTY' / '$' EX3 ;
OUTPUT = '.OUT' '(' $OUT1 ')' ;
OUT1 = '*' / .STRING / '#' / '.NL' /
       '.LB' / '.TB' / '.LM+' / '.LM-' ;

.END

EX2 = (EX3 .OUT(.TB 'BF L'# .NL) /
       OUTPUT)
      $(EX3 .OUT(.TB 'BE' .NL) /
        OUTPUT)
      .OUT(.LB 'L'# .NL) ;

EX2 = (EX3 .OUT('if (flag) {' .LM+ .NL) /
       OUTPUT .OUT('if (true) {' .LM+ .NL) )
      $(EX3 .OUT('if (!flag) runBEjsfn(rname);' .NL) /
        OUTPUT)
      .OUT(.LM- '} ;' .NL) ;

EX2
	CLL EX3
	BF L11
	TB
	CL 'BF L'
	GN
	NL
L11
	BT L12
	CLL OUTPUT
	BF L13
L13
L12
	BF L14
L15
	CLL EX3
	BF L16
	TB
	CL 'BE'
	NL
L16
	BT L17
	CLL OUTPUT
	BF L18
L18
L17
	BT L15
	SET
	BE
	LB
	CL 'L'
	GN
	NL
L14
L19
	R

function ruleEX2 () {
  var rname = "EX2" ;
  var rlabel = 0 ;
  ruleEX3();
  if (flag) {
    runCL('if (flag) {');
    runextLMI();
    runextNL();
  } ;
  if (!flag) {
    ruleOUTPUT();
    if (flag) {
      runCL('if (true) {');
      runextLMI();
      runextNL();
    } ;
  } ;
  if (flag) {
    runSET();
    while (flag) {
      ruleEX3();
      if (flag) {
        runCL('if (!flag) runBEjsfn(rname);');
        runextNL();
      } ;
      if (!flag) {
        ruleOUTPUT();
        if (flag) {
        } ;
      } ;
      };
    runSET();
    if (!flag) runBEjsfn(rname);
    runextLMD();
    runCL('} ;');
    runextNL();
  } ;
} ;

TR = .ID ':' TX1 ';' ;
TX1 = TX2 $('/' TX2 ) ;
TX2 = TX3 $ TX3 ;
TX3 = '.TOKEN' / '.DELTOK' / '$' TX3 /
      '.ANYBUT(' CX1 ')' / '.ANY(' CX1 ')' / .ID / '(' TX1 ')' ;
CX1 = CX2 $( '!' CX2 ) ;
CX2 = CX3 ( ':' CX3 / .EMPTY ) ;
CX3 = .NUMBER ;

ID     : .TOKEN ALPHA $(ALPHA / DIGIT) .DELTOK ;
NUMBER : .TOKEN DIGIT $DIGIT .DELTOK ;
ALPHA  : .ANY(65:90!97:122) ;
DIGIT  : .ANY(48:57) ;

.SYNTAX PROGRAM

PROGRAM = '.SYNTAX' .ID .OUT(.LB .TB 'ADR ' * .NL)
          $ PR  
          '.TOKENS'
          $ TR
          '.END' .OUT(.TB 'END' .NL) ;

PR = .ID .OUT(.LB * .NL) '=' EX1 ';' .OUT(.TB 'R' .NL) ; 

TR = .ID .OUT(.LB * .NL) ':' TX1 ';' .OUT(.TB 'R' .NL) ;

EX1 = EX2 $('/' .OUT(.TB 'BT L'# .NL) EX2 )
      .OUT(.LB 'L'# .NL) ;

EX2 = (EX3 .OUT(.TB 'BF L'# .NL) / OUTPUT)
      $(EX3 .OUT(.TB 'BE' .NL) / OUTPUT)
      .OUT(.LB 'L'# .NL) ;

EX3 = .ID       .OUT(.TB 'CLL '* .NL) /
      .STRING   .OUT(.TB 'TST '* .NL) /
      '.ID'     .OUT(.TB 'ID' .NL)    /
      '.NUMBER' .OUT(.TB 'NUM' .NL)   /
      '.STRING' .OUT(.TB 'SR' .NL)    /
      '(' EX1 ')'                     /
      '.EMPTY'  .OUT(.TB 'SET' .NL)   /
      '$' .OUT(.LB 'L'# .NL) EX3 .OUT(.TB 'BT L'# .NL) .OUT(.TB 'SET' .NL) ;

OUTPUT = '.OUT' '('$OUT1 ')' ;

OUT1 = '*'     .OUT(.TB 'CI' .NL)   /
       .STRING .OUT(.TB 'CL '* .NL) /
       .NUMBER .OUT(.TB 'CC '* .NL) /
       '#'     .OUT(.TB 'GN' .NL)   /
       '.NL'   .OUT(.TB 'NL' .NL)   /
       '.LB'   .OUT(.TB 'LB' .NL)   /
       '.TB'   .OUT(.TB 'TB' .NL)   /
       '.LM+'  .OUT(.TB 'LMI' .NL)  /
       '.LM-'  .OUT(.TB 'LMD' .NL)  ;

TX1 = TX2 $('/' .OUT(.TB 'BT T'# .NL) TX2) 
      .OUT(.LB 'T'# .NL) ;

TX2 = TX3 .OUT(.TB 'BF T'# .NL)
      $(TX3 .OUT(.TB 'RF' .NL) )
      .OUT(.LB 'T'# .NL) ;

TX3 = ( '.TOKEN'         .OUT(.TB 'TFT' .NL) /
        '.DELTOK'        .OUT(.TB 'TFF' .NL) /
        '$' .OUT(.LB 'T'# .NL) TX3 .OUT(.TB 'BT T'# .NL) ) 
                         .OUT(.TB 'SET' .NL)               /
      '.ANYBUT(' CX1 ')' .OUT(.TB 'NOT' .NL .TB 'SCN' .NL) /
      '.ANY(' CX1 ')'    .OUT(.TB 'SCN' .NL)               /
      .ID                .OUT(.TB 'CLL ' * .NL)            /
      '(' TX1 ')'                                          ;
            
CX1 = CX2 $('!' .OUT(.TB 'BT C'# .NL) CX2) .OUT(.LB 'C'# .NL) ;
CX2 = CX3 (':' .OUT(.TB 'CGE ' * .NL) .OUT(.TB 'BF D'# .NL) 
               CX3
               .OUT(.TB 'CLE ' * .NL) .OUT(.LB 'D' # .NL) /
           .EMPTY .OUT(.TB 'CE ' * .NL)                   ) ;
CX3 = .NUMBER ;

.END

1. Select Input "i11. add token rules to i09"
2. Select Code "c07. use new output, c[i09,c06], m[i09,c07]"
3. Click "Compile"
4. Select Code "c09. accept tokens, c[i11,c07]"
5. Click "Compare Code and Output" It does compare so c09 is the name of the stepping stone.

1. c09 = c[i11,c07]

.TOKENS

PREFIX : $.ANY(32!9!13!10) ;
ID     : PREFIX .TOKEN ALPHA $(ALPHA/DIGIT) .DELTOK ;
NUMBER : PREFIX .TOKEN DIGIT $DIGIT .DELTOK ;
STRING : PREFIX .ANY(39) .TOKEN $.ANYBUT(13!10!39) .DELTOK .ANY(39) ;
ALPHA  : .ANY(65:90!97:122) ;
DIGIT  : .ANY(48:57) ;

.END

.SYNTAX PROGRAM

PROGRAM = '.SYNTAX' ID .OUT(.LB .TB 'ADR ' * .NL)
          $ PR  
          '.TOKENS'
          $ TR
          '.END' .OUT(.TB 'END' .NL) ;

PR = ID .OUT(.LB * .NL) '=' EX1 ';' .OUT(.TB 'R' .NL) ; 

TR = ID .OUT(.LB * .NL) ':' TX1 ';' .OUT(.TB 'R' .NL) ;

EX1 = EX2 $('/' .OUT(.TB 'BT L'# .NL) EX2 )
      .OUT(.LB 'L'# .NL) ;

EX2 = (EX3 .OUT(.TB 'BF L'# .NL) / OUTPUT)
      $(EX3 .OUT(.TB 'BE' .NL) / OUTPUT)
      .OUT(.LB 'L'# .NL) ;

EX3 = ID        .OUT(.TB 'CLL '* .NL)        /
      STRING    .OUT(.TB 'TST ' 39 * 39 .NL) /
      '(' EX1 ')'                            /
      '.EMPTY'  .OUT(.TB 'SET' .NL)          /
      '.LITCHR' .OUT(.TB 'LCH' .NL)          /
      '$' .OUT(.LB 'L'# .NL) EX3 .OUT(.TB 'BT L'# .NL) .OUT(.TB 'SET' .NL) ;

OUTPUT = '.OUT' '('$OUT1 ')' ;

OUT1 = '*'     .OUT(.TB 'CI' .NL)          /
       STRING  .OUT(.TB 'CL ' 39 * 39 .NL) /
       NUMBER  .OUT(.TB 'CC '* .NL)        /
       '#'     .OUT(.TB 'GN' .NL)          /
       '.NL'   .OUT(.TB 'NL' .NL)          /
       '.LB'   .OUT(.TB 'LB' .NL)          /
       '.TB'   .OUT(.TB 'TB' .NL)          /
       '.LM+'  .OUT(.TB 'LMI' .NL)         /
       '.LM-'  .OUT(.TB 'LMD' .NL)         ;

TX1 = TX2 $('/' .OUT(.TB 'BT T'# .NL) TX2) 
      .OUT(.LB 'T'# .NL) ;

TX2 = TX3 .OUT(.TB 'BF T'# .NL)
      $(TX3 .OUT(.TB 'RF' .NL) )
      .OUT(.LB 'T'# .NL) ;

TX3 = ( '.TOKEN'         .OUT(.TB 'TFT' .NL) /
        '.DELTOK'        .OUT(.TB 'TFF' .NL) /
        '$' .OUT(.LB 'T'# .NL) TX3 .OUT(.TB 'BT T'# .NL) ) 
                         .OUT(.TB 'SET' .NL)               /
      '.ANYBUT(' CX1 ')' .OUT(.TB 'NOT' .NL .TB 'SCN' .NL) /
      '.ANY(' CX1 ')'    .OUT(.TB 'SCN' .NL)               /
      ID                 .OUT(.TB 'CLL ' * .NL)            /
      '(' TX1 ')'                                          ;
            
CX1 = CX2 $('!' .OUT(.TB 'BT C'# .NL) CX2) .OUT(.LB 'C'# .NL) ;
CX2 = CX3 (':' .OUT(.TB 'CGE ' * .NL) .OUT(.TB 'BF D'# .NL) 
               CX3
               .OUT(.TB 'CLE ' * .NL) .OUT(.LB 'D' # .NL) /
           .EMPTY .OUT(.TB 'CE ' * .NL)                   ) ;
CX3 = NUMBER ;

.TOKENS

PREFIX : $.ANY(32!9!13!10) ;
ID     : PREFIX .TOKEN ALPHA $(ALPHA/DIGIT) .DELTOK ;
NUMBER : PREFIX .TOKEN DIGIT $DIGIT .DELTOK ;
STRING : PREFIX .ANY(39) .TOKEN $.ANYBUT(13!10!39) .DELTOK .ANY(39) ;
ALPHA  : .ANY(65:90!97:122) ;
DIGIT  : .ANY(48:57) ;

.END

1. Select Input "i12. use token rules"
2. Select Code "c09. accept tokens, c[i11,c07]"
3. Click "Compile"
4. Click the Output "Copy to Code" button and Output "Clear" button
5. Click "Compile"
6. Click "Compare Code and Output" It does compare so c[i12,c09] is a metacompiler.
7. Select Code "c10. use tokens, c[i12,c09], m[i12,c10]"
8. Click "Compare Code and Output" It does compare so c10 is the built metacompiler.

1. c10 = m[i12,c10] = c[i12,c09] = c[i12,c[i11,c07]]
2. c10jf = m[i12jf,c10jf] = c[i12jf,c09jf] = c[i12jf,c[i11jf,c07jf]]

1. Select Input "i12. use token rules"
2. Click "Extract Syntax to Output" button in the lower left corner
3. Click the Output "Copy to Code" button and Output "Clear" button
4. Select Input "i12jf. use token rules"
5. Click "Extract Syntax to Output" button in the lower left corner
6. Click "Compare Code and Output" The two syntax specifications compare.

1. c10 = m[i12,c10] = c[i12,c[i12,c10jf]
2. c10jf = m[i12jf,c10jf] = c[i12jf,c[i12jf,c10]]

.SYNTAX
PROGRAM = '.SYNTAX' ID $(PR / COMMENT) '.TOKENS' $(TR / COMMENT) '.END' ;
COMMENT = '[' CMLINE ']' ;
CX3 = NUMBER / SQUOTE .LITCHR ;
.TOKENS
SQUOTE : PREFIX .ANY(39) ;
CMLINE : .TOKEN $.ANYBUT(10!13!93) .DELTOK ;
.END

[ alphabetic characters ]
ALPHA  : .ANY('A:'Z!'a:'z) ;
[ numeral characters ]
DIGIT  : .ANY('0:'9) ;

1. Select Input "i13. add comments and litchr to i12"
2. Select Code "c10. use tokens, c[i12,c09], m[i12,c10]"
3. Click "Compile"
4. Select Code "c11. accept comments, c[i13,c10]"
5. Click "Compare Code and Output" It does compare so c11 is the name of the stepping stone.

1. c11 = c[i13,c10]

1. Select Input "i14. use comments and litchr"
2. Select Code "c11. accept comments, c[i13,c10]"
3. Click "Compile"
4. Click the Output "Copy to Code" button and Output "Clear" button
5. Click "Compile"
6. Click "Compare Code and Output" It does compare so c[i14,c11] is a metacompiler.
7. Select Code "c12. use comments, c[i14,c11], m[i14,c12]"
8. Click "Compare Code and Output" It does compare so c12 is the built metacompiler.

1. c12 = m[i14,c12] = c[i14,c11] = c[i14,c[i13,c10]]
2. c12jf = m[i14jf,c12jf] = c[i14jf,c11jf] = c[i14jf,c[i13jf,c10jf]]

1. Select Input "i14. use comments and litchr"
2. Click "Extract Syntax to Output" button in the lower left corner
3. Click the Output "Copy to Code" button and Output "Clear" button
4. Select Input "i14jf. use comments and litchr"
5. Click "Extract Syntax to Output" button in the lower left corner
6. Click "Compare Code and Output" The two syntax specifications compare.

1. c12 = m[i14,c12] = c[i14,c[i14,c12jf]
2. c12jf = m[i14jf,c12jf] = c[i14jf,c[i14jf,c12]]

1. c12 = m[i14,c12] = c[i14,c[i14,c12*]
2. c12jf = m[i14jf,c12jf] = c[i14jf,c[i14jf,c12*]]

1. erule - string, the name of the parse or token rule that failed
2. einput - number, the index into the input that failed
3. token - string, the last token successfully recognized
4. outbuf - string, the collected output before the failure

1. Select Input "i14jf. use token rules"
2. Click "Extract Syntax to Output" button in the lower left corner
3. Click the Output "Copy to Code" button and Output "Clear" button
4. Select Input "i14js. convert i14jf to js object"
5. Click "Extract Syntax to Output" button in the lower left corner
6. Manually delete PROGRAM rule references to rules PREAMBLE and POSTAMBLE.
7. Manually delete rules PREAMBLE and POSTAMBLE
8. Click "Compare Code and Output" The two syntax specifications compare.

1. Select Input "i14js. convert i14jf to js object"
2. Select Code "c12jf. use comments, c[i14jf,c11jf], m[i14jf,c12jf]"
3. Click "Compile" (create stepping stone)
4. Click the Output "Copy to Code" button and Output "Clear" button
5. Click "Compile" (use stepping stone, create c12js metacompiler)
6. Click the Output "Copy to Code" button and Output "Clear" button
7. Click "Compile" (use c12js metacompiler)
8. Click "Compare Code and Output" It does compare so c[i14js,c[i14js,c12jf] is a metacompiler.
9. Select Code "c12js. use comments, c[i14js,c[i14js,c12jf]] m[i14js,c12js]"
10. Click "Compare Code and Output" It does compare so c12js is the built metacompiler.

1. c12 = m[i14,c12] = c[i14,c[i14,c12*]
2. c12jf = m[i14jf,c12jf] = c[i14jf,c[i14jf,c12*]]
3. c12js = m[i14js,c12js] = c[i14js,c[i14js,c12*]]

'.PASS'   .OUT('this.inp = 0 ;' .NL)  /

.SYNTAX AEXP

AEXP = AS $AS ;
AS = ID .OUT(.TB 'address ' * .NL) ':=' EX1 .OUT(.TB 'store' .NL) ';' ;
RX1 = RX2 ('='  RX2 .OUT(.TB 'eq' .NL) /
           '<'  RX2 .OUT(.TB 'lt' .NL) /
           '>'  RX2 .OUT(.TB 'gt' .NL) /
           '<=' RX2 .OUT(.TB 'le' .NL) /
           '>=' RX2 .OUT(.TB 'ge' .NL) /
           .EMPTY) ;
RX2 = '~' EX0 .OUT(.TB 'not' .NL) / EX0 ;
EX0 = EX1 ('<-' EX1 .OUT(.TB 'shl' .NL) /
           '->' EX2 .OUT(.TB 'shr' .NL) /
           .EMPTY) ;
EX1 = EX2 $('+' EX2 .OUT(.TB 'add' .NL) /
            '-' EX2 .OUT(.TB 'sub' .NL) ) ;
EX2 = EX3 $('*' EX3 .OUT(.TB 'mpy' .NL) /
            '/' EX3 .OUT(.TB 'div' .NL) ) ;
EX3 = EX4 $('^' EX3 .OUT(.TB 'exp' .NL)) ;
EX4 = '+' EX5 / '-' EX5 .OUT(.TB 'minus' .NL) / EX5 ;
EX5 = ID  .OUT(.TB 'load ' * .NL) /
      NUMBER .OUT(.TB 'literal ' * .NL) /
      '(' EX1 ')' ;

.TOKENS

PREFIX : $.ANY(32!9!13!10) ;
ID     : PREFIX .TOKEN .ANY('A:'Z!'a:'z) $(.ANY('A:'Z!'a:'z) / .ANY('0:'9)) .DELTOK ;
NUMBER : PREFIX .TOKEN .ANY('0:'9) $.ANY('0:'9) .DELTOK ;

.END

1. Select Input "i02a. demo, AEXP example assignment compiler"
2. Select Code "c12js. use comments, c[i14js,c[i14js,c12jf]] m[i14js,c12js]"
3. Click "Compile" (create AEXP compiler)
4. Select Code "c01ajs. demo, AEXP compile assignments c[i02a,c12js]"
5. Click "Compare Code and Output" It does compare, so c01ajs = c[i02a,c12js].
6. Click the Output "Copy to Code" button and Output "Clear" button
7. Select Input "i01. demo, AEXP example assignments"
8. Click "Compile" (use AEXP on demo assignments)
9. Select Code "c00. demo, compiled assignments c[i01,c01]"
10. Click "Compare Code and Output" It does compare, so i02a can do the old demo.

fern:=5+6;
ace:=fern*5;
waldo:=fern+alpha/-beta^gamma;
fern:=5<=6;
ace:=fern*5>=bob;
waldo:=fern<-alpha<=beta->gamma;

1. Select Input "i01a. demo, AEXP2 backup value assignments"
2. Select Code "c01ajs. demo, AEXP compile assignments c[i02a,c12js]"
3. Click "Compile" (use AEXP on demo assignments)

RX1 = RX2 ('='  RX2 .OUT(.TB 'eq' .NL) /
           '<=' RX2 .OUT(.TB 'le' .NL) /
           '>=' RX2 .OUT(.TB 'ge' .NL) /
           '<'  RX2 .OUT(.TB 'lt' .NL) /
           '>'  RX2 .OUT(.TB 'gt' .NL) /
           .EMPTY) ;

RX1 = RX2 ('='         RX2 .OUT(.TB 'eq' .NL) /
           '<' ('='    RX2 .OUT(.TB 'le' .NL) /
                .EMPTY RX2 .OUT(.TB 'lt' .NL) ) /
           '>' ('='    RX2 .OUT(.TB 'ge' .NL) /
                .EMPTY RX2 .OUT(.TB 'gt' .NL) ) /
           .EMPTY) ;

1. Select Input "i02a. demo, AEXP example assignment compiler"
2. Copy one of the above RX1 definitions and paste it over the i02a RX1 definition
3. Select Code "c12js. use comments, c[i14js,c[i14js,c12jf]] m[i14js,c12js]"
4. Click "Compile" (create AEXP compiler)
5. Click the Output "Copy to Code" button and Output "Clear" button
6. Select Input "i01a. demo, AEXP2 backup value assignments"
7. Click "Compile" (use AEXP on demo assignments)

EX3 = ID / STRING / '(' EX1 ')' / '.EMPTY' / '.LITCHR' / '$' EX3 ;

EX3 = ID / STRING / '(' EX1 ')' / '.EMPTY' / '.LITCHR' /
      '.PASS' / '$' EX3 / '[' EX1 $( '|' EX1 ) ']' ;

1. If A succeeds, then the syntax construct succeeds.
2. If A fails, then B | ... | Z is the value of the syntax construct.
3. If A causes a syntax error, then
   1. the input position backs up to the point where A started
   2. the output position backs up to the point where A started
   3. the token buffer backs up to the value it had when A started
   4. the margin backs up to the value it had when A started
   5. B | ... | Z is attempted to be recognized
4. If all of the alternatives fail or cause a syntax error, then everything is backed up to when A started and the construct fails.

RX1 = RX2 ['='  RX2 .OUT(.TB 'eq' .NL) |
           '<'  RX2 .OUT(.TB 'lt' .NL) |
           '>'  RX2 .OUT(.TB 'gt' .NL) |
           '<=' RX2 .OUT(.TB 'le' .NL) |
           '>=' RX2 .OUT(.TB 'ge' .NL) |
           .EMPTY] ;

EX1 = EX2 $['+' EX2 .OUT(.TB 'add' .NL) |
            '-' EX2 .OUT(.TB 'sub' .NL) ] ;

[ parsing expressions ]
EX1 = EX2 $('/' .OUT('if ((!this.pflag) && (!this.eflag)) {' .LM+ .NL)
                EX2
                .OUT(.LM- '} ;' .NL) ) ;

EX2 = (EX3 .OUT('if (this.pflag) {' .LM+ .NL) /
       OUTPUT .OUT('if (true) {' .LM+ .NL) )
      .OUT('while (!this.eflag) {' .LM+ .NL)
      $(EX3 .OUT('if (!this.pflag) this.bkerr();' .NL)
            .OUT('if (this.eflag) break ;' .NL) /
        OUTPUT)
      .OUT(.LM- 'break }' .NL)
      .OUT(.LM- '} ;' .NL) ;

EX3 = ID        .OUT('this.ctxpush(' 39 * 39 ') ;' .NL)
                .OUT('this.rule' * '() ;' .NL)
                .OUT('this.ctxpop() ;' .NL) /
      STRING    .OUT('this.test(' 39 * 39 ');' .NL) /
      '(' EX1 ')'                            /
      '.EMPTY'  .OUT('this.pflag = true ;' .NL)    /
      '.LITCHR' .OUT('this.token = this.inbuf.charCodeAt(this.inp) ;' .NL)
                .OUT('this.inp++ ;' .NL)  /
      '.PASS'   .OUT('this.inp = 0 ;' .NL)  /
      '$' .OUT('this.pflag = true ;' .NL)
          .OUT('while (this.pflag & !this.eflag) {' .LM+ .NL)
           EX3 
          .OUT('};' .LM- .NL) 
          .OUT('this.pflag = !this.eflag ;' .NL) /
      '[' .OUT('this.bkset() ;' .NL)
          EX1
          $('|' .OUT('if (!this.pflag) {' .LM+ .NL)
                .OUT('if (this.eflag) this.bkrestore() ;' .NL)
                EX1
                .OUT(.LM- '} ;' .NL) )
      ']' .OUT('if (this.eflag) this.bkrestore() ;' .NL)
          .OUT('this.bkclear() ;' .NL) ;

1. Select Input "i15js. js metacompiler with backup"
2. Select Code "c12js. use comments, c[i14js,c[i14js,c12jf]] m[i14js,c12js]"
3. Click "Compile" (create stepping stone compiler)
4. Click the Output "Copy to Code" button and Output "Clear" button
5. Click "Compile" (create new metacompiler)
6. Select Code "c13js. accept backup c[i15js,c[i15js,c12js]], m[i15js,c13js]"
7. Click "Compare Code and Output" It does compare, so c13js = c[i15js,c[i15js,c12js]].
8. Select Input "i02b. demo, AEXP2 backup assignment compiler"
9. Click "Compile" (create AEXP2 compiler)
10. Select Code "c01bjs. demo, AEXP2 assignments compiler c[i02b,c13js]"
11. Click "Compare Code and Output" It does compare, so c01bjs = c[i02b,c13js].
12. Select Input "i01a. demo, AEXP2 backup value assignments"
13. Click "Compile" (use AEXP2 on demo assignments)

<HTML><HEAD><TITLE>Running Your Compiler on a Web Page</TITLE></HEAD>
<BODY BGCOLOR="#FFFFFF" TEXT="#000000">
<SCRIPT LANGUAGE="JavaScript" TYPE="text/javascript">

// paste your generated compiler here

function StartJsObjCompile()
{
  // assumes "compiler" defined above is a js object
  // clear the output textbox
  document.CompileForm.OutputText.value = '' ;
  // run the compiler on the input textbox
  compiler.compile(document.CompileForm.InputText.value) ;
  // set the output even if there is an error
  document.CompileForm.OutputText.value = compiler.outbuf ;
  // if there was a compiler error, then report it
  if (compiler.eflag > 0) window.alert(JsObjCompileErrorReport(compiler)) ;
  window.confirm('Done.');
} ;

function JsObjCompileErrorReport (compiler) {
var i ; var j ; var h ; var ctx ; var error;
  // compilation error, provide error context
  error = 'ERROR:\n' +
          'RULE:' + compiler.erule + '\n' +
          'TOKEN:' + compiler.token + '\n' ;
  // provide input scan context
  i = compiler.einput - 20 ;  if (i < 0) i = 0 ;
  j = compiler.einput + 20 ;  if (j > compiler.inbuf.length) j = compiler.inbuf.length ;
  ctx = compiler.inbuf.substring(i,compiler.einput) +
        '<scan>' +
        compiler.inbuf.substring(compiler.einput,j) ;
  error += 'INPUT TEXT:\n' + ctx + '\n' +
           'INPUT CHAR CODES:\n' + CharCodeString(ctx) + '\n' ;
  // provide output context
  i = compiler.outbuf.length - 30 ;  if (i < 0) i = 0 ;
  j = compiler.outbuf.length ;
  ctx = compiler.outbuf.substring(i,j) ;
  error += 'OUTPUT TEXT:\n' + ctx + '\n' +
           'OUTPUT CHAR CODES:\n' + CharCodeString(ctx) + '\n' ;
  return error ;
} ;

function CharCodeString (s) {
var ccs ; var h ;
  // ensure nonprinting character codes are visible in error messages
  ccs = '' ;
  for (var h = 0 ; h < s.length ; h++)
    { if (s.charCodeAt(h) <= 32)
        { ccs += '<' + s.charCodeAt(h) + '>' ; }
      else
        { ccs += s.charAt(h) ; } ;
    } ;
  return ccs ;
} ;

function ClearOutput() {document.CompileForm.OutputText.value = "" ; } ;

</SCRIPT>
<FORM NAME="CompileForm" ACTION="none">
<INPUT TYPE="button" NAME="CompileButton" VALUE="Compile"
  onClick="StartJsObjCompile();">
<INPUT TYPE="button" NAME="OutputClearButton" VALUE="Clear"
  onClick="ClearOutput();">
<BR>
<TEXTAREA NAME="InputText" COLS=80 ROWS=2000>
Input text shows here.
</TEXTAREA>
<TEXTAREA NAME="OutputText" COLS=80 ROWS=2000>
On compile output appears here.
</TEXTAREA>
</FORM>
</BODY>
</HTML>

.SYNTAX PROGRAM

PROGRAM = '.SYNTAX' ID .OUT(.LB .TB 'ADR ' * .NL)
          $ ST
          '.END' .OUT(.TB 'END' .NL) ;

ST = ID .OUT(.LB * .NL) '=' EX1 '.,' .OUT(.TB 'R' .NL) ;

EX1 = EX2 $('/' .OUT(.TB 'BT L' # .NL) EX2 )
      .OUT(.LB 'L'# .NL) ;

EX2 = (EX3 .OUT(.TB 'BF L' # .NL) / OUTPUT)
      $(EX3 .OUT(.TB 'BE' .NL) / OUTPUT)
      .OUT(.LB 'L'# .NL) ;

EX3 = ID        .OUT(.TB 'CLL '* .NL) /
      STRING    .OUT(.TB 'TST '* .NL) /
      '.ID'     .OUT(.TB 'ID' .NL)    /
      '.NUMBER' .OUT(.TB 'NUM' .NL)   /
      '.STRING' .OUT(.TB 'SR' .NL)    /
      '(' EX1 ')'             /
      '.EMPTY'  .OUT(.TB 'SET' .NL)   /
      '$' .OUT(.LB 'L'# .NL) EX3 .OUT(.TB 'BT L' # .NL) .OUT(.TB 'SET' .NL) ;

OUTPUT = ('.OUT' '('$OUT1 ')' /
          '.LABEL' .OUT(.TB 'LB' .NL) OUT1)
         .OUT(.TB 'OUT' .NL) ;

OUT1 = '*1'    .OUT(.TB 'GN1' .NL)  /
       '*2'    .OUT(.TB 'GN2' .NL)  /
       '*'     .OUT(.TB 'CI' .NL)   /
       STRING  .OUT(.TB 'CL '* .NL) ;

.TOKENS

PREFIX : $.ANY(32!9!13!10) ;
ID     : PREFIX .TOKEN ALPHA $(ALPHA/DIGIT) .DELTOK ;
NUMBER : PREFIX .TOKEN DIGIT $DIGIT .DELTOK ;
STRING : PREFIX .TOKEN .ANY(39) $.ANYBUT(13!10!39) .ANY(39) .DELTOK ;
ALPHA  : .ANY('A:'Z!'a:'z) ;
DIGIT  : .ANY('0:'9) ;

.END

1. Select Input "i04a. Meta II syntax (i03 reordered and tokens)"
2. Select Code "c12js. use comments, c[i14js,c[i14js,c12jf]] m[i14js,c12js]"
3. Click "Compile"
4. Click the Output "Copy to Code" button and Output "Clear" button
5. Select Input "i03. Meta II syntax (paper fig. 5)"
6. Click "Compile"
7. Select Code "c02. Meta II of fig. 5, c[i03,c02]"
8. Click "Compare Code and Output" It does compare

1. c02 = m[i03,c02] = c[i03,c03] = c[i03,c[i04a,c12*]]

1. left-recursive grammar - "A left-recursive grammar can cause a top-down parser to go into an infinite loop."
   Below we show the left recursive grammar of example 5.13 from [Aho77, pg. 178]. (The letters used in (5.8) below are from the Algol 60 report standing for Expression, Term, and Factor.) It implements addition +, multiplication *, and precedence () over an identifier. The equivalent input in the Meta II language is also shown.

   (5.8) of example 5.13	(5.8) in Meta II
   E -> E + T | T T -> T * F | F F -> ( E ) | id	E = E '+' T / T ., T = T '*' F / F ., F = '(' E ')' / .ID .,

   Yes Meta II will generate an infinite recursion for this syntax. (You can check this by cutting the Meta II above and pasting it into the rules for i02 and compiling with c02.) The simple symptom of left recursion (ignoring backtracking) is a parse rule being invoked at the same input position where it was last invoked. The example eliminates immediate left recursion (recursion from a rule to itself) to arrive at the solution (5.9) below. Where "ε" in (5.9) is the Greek epsilon meaning empty.

   (5.9) of example 5.13	(5.9) in Meta II	Meta II
   E -> T E' E' -> + T E' | ε T -> F T' T' -> * F T' | ε F -> ( E ) | id	E = T E1 ., E1 = '+' T E1 / .EMPTY ., T = F T1 ., T1 = '*' F T1 / .EMPTY ., F = '(' E ')' / .ID .,	E = T $('+' T) ., T = F $('*' F) ., F = '(' E ')' / .ID .,

   In the third column above we also show the usual way this grammar would be implemented in Meta II using iteration with recursion rather than just recursion. Notice that Meta II "$('+' T)" notation is a compact iterative version of the "E1 = '+' T E1 / .EMPTY .," recursive version. Recognizing left-recursion in the above examples is easy. It becomes more difficult when multiple rules are involved (e.g., rule A calls B calls C calls A). However [Aho77, pg. 179] informs us that "It is possible, although difficult, to eliminate all left-recursion from any grammar."
2. backtracking - "If we make a sequence of erroneous expansions and subsequently discover a mismatch, we may have to undo the semantic effects ... undoing semantic actions requires substantial overhead."
   We saw this in step 13 where the context had to be expanded to save the state of the compiler. In particular all the information saved by the bkset and restored by the bkrestore JavaScript function (i.e., input position, output position, and token buffer).
3. language definition - "with top-down backtracking parsers the order in which alternatives are tried can affect the language accepted."
   We saw this in step 13 where the relational operator "<" was tested before the "<=" operator.
4. error reporting - "when failure is reported, we have very little idea where the error actually occurred."
   The idea here is that if a backtracking parser just keeps backtracking, then on an input containing a syntax error the parser just keeps backtracking through all parse rules until it returns to the top rule where with all alternatives tried it just says "syntax error" pointing to the beginning of the input string.

1. left-recursive grammar - The symptom of a left-recursion infinite loop is that a rule is called twice on the same input position. This is detectable. In fact semantics could be created to fail the rule if left-recursion is detected. Under these semantics even (5.8) above will work with Meta II. Most of the time this just isn't necessary.
2. backtracking - This drawback is in essence an efficiency argument on parsing ("requires substantial overhead"). Further as discussed in the "error reporting" section below the authors may be viewing backtracking as the implementation of all alternatives (i.e., all alternatives backtrack or all do not). In step 13 we implemented backtracking alternation in addition to non-backtracking alternation. This way it only need be used where the language designer deems necessary. Where it isn't necessary no context need be saved. We showed an example where backtracking was necessary in the form of i02b with the rather poor syntax choice of <- and -> for the shift operators. These definitions not only required backtracking but also introduced an ambiguous syntax.
3. language definition - "with top-down backtracking parsers the order in which alternatives are tried can affect the language accepted."
   We saw this in step 13 where the relational operator "<" was tested before the "<=" operator. The usual solution to this problem is to just order the alternatives with the longest literal string first. It doesn't seem to be much of a problem in practice. In the relational operator example we really didn't need to add backtracking to the RX1 rule of i02b because of the "<=" issue as either version in the table below works without backtracking. We needed to add the backtracking to the RX1 rule of i02b because a higher precedence "<-" shift operator conflicted with the "<" relational operator.

   ordered alternatives rule	left-factored rule
   RX1 = RX2 ('=' RX2 .OUT(.TB 'eq' .NL) / '<=' RX2 .OUT(.TB 'le' .NL) / '>=' RX2 .OUT(.TB 'ge' .NL) / '<' RX2 .OUT(.TB 'lt' .NL) / '>' RX2 .OUT(.TB 'gt' .NL) / .EMPTY) ;	RX1 = RX2 ('=' RX2 .OUT(.TB 'eq' .NL) / '<' ('=' RX2 .OUT(.TB 'le' .NL) / .EMPTY RX2 .OUT(.TB 'lt' .NL) ) / '>' ('=' RX2 .OUT(.TB 'ge' .NL) / .EMPTY RX2 .OUT(.TB 'gt' .NL) ) / .EMPTY) ;

   We also pointed out that one of the left-factored rule allows a space between the characters of the "<=" operator and the ordered alternatives rule does not. Aho & Ullman [Aho77, pg. 177] seem to be concerned that the commutative property of EBNF alternatives is not somehow represented in the implementation of the parser because the alternatives are tried in order. I believe it's more of a concern that each parser for a language parses the language the the same way. As parser generators generate tables based on tokens described by a separate lexer the real question is do all of these table parsing schemes provide the same parse? How would we know? Look at the configuration and version space: 1)lexer 2)table generator 3)table interpreter. Each of which are contained in separate specification.
4. error reporting - "when failure is reported, we have very little idea where the error actually occurred."
   The idea here is that if a backtracking parser just keeps backtracking, then on an input containing a syntax error the parser just keeps backtracking through all parse rules until it returns to the top rule where will all alternatives tried it just says "syntax error" pointing to the beginning of the input string. As stated this seems to presume a single alternation implementation with full backtracking. In step 13 this is not what we implemented. In fact it's rather ironic that backtracking would be cited as a problem in error recovery when in practice a form of it is used to implement error reporting. As an example the following replacement and additions to i15js would print out the name of all parse and token rules containing a syntax error. The two token rules PBODY and TBODY are defined to skip over the body of a parse rule or token rule. This is a very primitive error reporting based on backtracking. Usually error reporting is implemented using a different construct similar to backtracking which taps into the syntax error reporting routine (e.g., c13js bkerr function) to find the furthest parse position and rule calling the error to format a detailed error message.

   PROGRAM = '.SYNTAX' ID 
             .OUT(.LB '// ' * ' compiler' .NL)
             .OUT('compiler = {' .LM+ .NL .NL)
             PREAMBLE
             $([PR | ID .OUT('error: ' * .NL) PBODY] / COMMENT)
             '.TOKENS'
             $([TR | ID .OUT('error: ' * .NL) TBODY] / COMMENT)
             '.END' 
             POSTAMBLE 
             .OUT(.LM- '}' .NL) ;
   
   PBODY  : .TOKEN $(STRING / .ANYBUT(''!';)) .ANY(';) .DELTOK;
   TBODY  : .TOKEN $(.ANYBUT(''!';) / .ANY('') .ANY(0:127)) .ANY(';) .DELTOK;
   

1. reserved words - A construct such as .RESERVED('if' 'then' 'repeat' 'while') added to parse rule TX3 of i15js that fails if the token buffer contains any of the reserved words in the construct. Useful to prevent reserved words being used as identifiers if that is desired.
2. iteration limits - A modification to the interation constructs of parse rules EX3 and TX3 of i15js such as $<1:10> that fails if the iterator is successful too few or too many times. Useful to prevent identifiers from being too long or control constructs too empty such as a block with no statements. Usually augmented with an upper limit ability to allow unlimited (e.g.,$<1:*>.)
3. error recovery - A construct such as [[ rule1 ] rule2 ] added to rule EX3 of i15js that is an error trap. If any errors occur in rule1 then the compiler backtracks to the entry state of the construct and rule2 is invoked to skip over a logical section containg the syntax error. The square brackets are used to indicate its similarity to parser backtracking. Error recovery is differentiated from backtracking in order to provide better error messages and error counts.
4. named counters - A construct such as #Name added to rule EX3 of i15js that implements named integer counters. The counters need operations to change them ranging from simple increment and decrement to an implentation along the lines of the AEXP arithmetic assignments example of Step 3. Also these counters can be used in the OUT1 rule just as the # generated unique numbers are accepted. As an example the above error recovery extension rule2 might increment a counter named #ERRORS.
5. string buffers - Similar to named counters, string buffers are a construct such as *Name added to rule EX3 of i15js. Buffers are strings and as with the counters may be assigned values from the token buffer and other buffers. Also as with counters they may be used in the OUT1 rule just as the token buffer * string is accepted. As an example the above error recovery mechanism might set a buffer named *ERRORTOKEN to indicate the token buffer at the point of error and *ERRORLINE to provide the furthest progress into a source line.
6. input redirection - A construct such as .INCLUDE(filename) that redirects the input to the given file until it is exhausted. The filename is specified using OUT1 rule constructs. The file and position may have to be restored on a backtrack depending on where this construct is allowed.
7. output redirection - A construct such as .CON or .FILE that is similar to the OUTPUT rule construct .OUT that directs output messages to the user console or a file.
8. symbol table - Constructs for keeping and finding information during a compilation that uses and sets string buffers, named counters, and literal string constants to keep track of and query information. As mentioned in Step 15. Benefits and drawbacks backtracks may have to roll back this information. The easiest way to start is just use a linear list of entries in memory. The roll back then just needs to restore the maximum index into the symbol table.
9. database connection - Constructs for cross-module compilation that contains the symbol table information from other compilations or interfaces that will be linked with this compilation. As an example many of the resources used by compilers are from operating system shared files. Under MS Windows these are Dynamic Link Library (.DLL) files or under Unix/Linux Shared Object (.so) files. On a successful compile the information can be updated with the public information for the compiled module. The easiest way to start is just use a sorted file of fields indexed by the module name and load it into memory.
10. tree generation - Rather than generate text output directly as we have done in this tutorial we could have generated trees for futher processing [Carr69]. As an example we could write a tree oriented AEXP compiler as

    .SYNTAX AEXP
    
    AEXP = .LIST(stmts AS $AS) ;
    AS = .ID ::address ':=' EX1 :store[2] ';' ;
    EX1 = EX2 $('+' EX2 :add[2] /
                '-' EX2 :sub[2] ) ;
    EX2 = EX3 $('*' EX3 :mpy[2] /
                '/' EX3 :div[2] ) ;
    EX3 = EX4 $('^' EX3 :exp[2]) ;
    EX4 = '+' EX5 / '-' EX5 :minus[1] / EX5 ;
    EX5 = .ID ::value /
          .NUMBER ::number /
          '(' EX1 ')' :parens[1] ;
    
    .END
    

    The easiest way to start is keep a tree node stack in memory where nodes are pushed onto the stack. Each tree node has a name and data. The three node forms used above are:
    1. token nodes - such as ::address above which pushes a node named "address" containing the token buffer string data on the node stack.
    2. tree nodes - such as :store[2] above which pushes a node named "store" on the stack containing two pointers to the second node on node stack and top of node stack in that order.
    3. list nodes - a construct such as .LIST(stmts AS $AS) above which
       1. pushes a special list marker node containing the stmts node name
       2. evaluates the AS $AS which push other nodes
       3. pushes a single node with the node name stmts found in the list marker with data array containing pointers to all the nodes down to the list marker, removes the nodes down to the list marker, and removes the list marker
    The use of pointers above is stressed as they provide an efficient way for tree construction to interact with the needs of backtracking. On backtracking tree constructions need to be rolled back. Two major reasons for generating trees are optimization and separating code generation from the parser. Notice the above AEXP description works for all implementations because the code generation has been removed. Once the code generation has been removed the same generated tree can be the source for generating code for various platforms (including hardware and software mixes), simulations, diagrams, and reports.

1. mc_title.html is the top frame and is just text.
2. mc_input.html is the left input frame. It is computer generated and contains just quoted versions of the various inputs of the input selection drop down box.
3. mc_code.html is the center code frame. Also computer generated it is similar to the input frame and contains just quoted versions of the various codes of the code selection drop down box.
4. mc_output.html is the right output frame. It implements the "Copy to Code" and "Clear" buttons.
5. mc_semantics.html is the bottom frame. It is where all the real work happens. It implements the "Compile", "Compare Code and Output" and "Extract Syntax to Output" buttons. In this frame
   • input text is parent.frames[1].document.InputForm.InputText.value
   • code text is parent.frames[2].document.CodeForm.CodeText.value
   • output text is parent.frames[3].document.OutputForm.OutputText.value
   • The "Extract Syntax to Output" button simply invokes the fully contained JavaScript compiler c[i16,c13js] saved as syntax_extract through the StartExtractSyntax on the input and places the result in the output.
   • The "Compare Code and Output" button calls the hand written function StartCompare to compare the code and output text.
   • The "Compile" button calls the hand written function StartCompile that determines which of the three compiler implementation models (i.e., Meta II interpreter, JavaScript functions, or JavaScript object) is contained in the code text.
     • Meta II interpreter model calls StartIntCompile.
     • JavaScript function model evaluates the code text to define the functions and calls StartJsFnCompile which presumes a function named compiler was defined.
     • JavaScript object model evaluates the code text to define the object and calls StartJsObjCompile which presumes an object named compiler was defined and it defines a compile method.

mc_workshop

mc_title

mc_input

mc_code

mc_output

mc_semantics

1. interpreter (Meta II interpreter model) where the text or a code representation (bytecode) of the text is interpreted by an interpreter loop to create a series of calls to a runtime library.
2. threaded code (JavaScript function model) where the compiler primarily outputs calls to a language runtime library that is linked with the code.
3. compiled code (JavaScript object model) where the compiler primarily outputs executable code with minimal calls to a linked runtime library.

1. A lot of the parsing issues we discussed might be interlinked with the character set. If there is a Unicode character code for each of a language's operators so that the operators are not strings drawn from a limited set of symbols, how much of a problem is this parsing? As an example we might use the actual Unicode symbol for "≤" rather than the low-level string combination "<=". The ambiguous grammar problem we had using "<-" and "->" for left and right shift could easily be solved by using the single symbols "«" and "»". The mathematicians are completely un-shy about using single symbols for meaning. Perhaps the computer scientists should join them in this view. Programming languages at this level have been around for over fifty years. Perhaps it's time we advanced from making "puzzle book" general-purpose languages.
2. Compiler theory started as graph analysis driven by the Chomsky hierarchy. In particular most computer languages are Type-2 context free grammars consisting of:
   1. terminal symbols (scanned input)
   2. nonterminal symbols (rule names)
   3. productions (rules) of the form nonterminal goes to a string consisting of terminals and nonterminals
   You can see this in the input definitions we've used. However the concept of a metacompiler as a compiler generator that is capable of reproducing itself from a high-level domain specific description really never fit well into this original defining framework of recognition systems. Even if we adopt simplistic definitions of "high-level" as the input being smaller than the output and "domain-specific" as the input syntax and output concepts being wholly contained independent of implementation, then we are still dealing with concepts outside of the scope of this defining framework. Did failing to fit into the prevailing framework of the day cause these concepts not to be investigated well during the rise of compiler theory?
3. Many modern computer languages seem to bloat up, become a syntatic mess of low-level symbols, and then die. Is this because of the magnificent job the formal compiler theorists did in creating table driven context-free parsers? Could this be just a variant of the old addage "Any knife sharp enough to help you is sharp enough to cut you?"

Copyright © 2006, 2008, 2014, 2015, 2016 Bayfront Technologies, Inc.
http://www.BayfrontTechnologies.com/mc_tutorial.html
Permission to use, copy, and distribute this document for any purpose with or without fee is hereby granted, provided that the document is unmodified and the above copyright notice, URL, and this permission notice appear in all copies.
THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.