The ModulaTor

Book recension

by Günter Dotzel, ModulaWare

The creator of the programming languages Pascal, Modula-2 und Oberon wrote a new book about compiler construction:

Niklaus Wirth: "Grundlagen und Techniken des Compilerbaus", Addison-Wesley, 1996, ISBN 3486243748.

In only 200 pages, Prof. Wirth explains all essential aspects of compiler construction and presents a simple, but complete compiler program for a subset of the programming language Oberon, called Oberon-0.

Wirth also defines an architecture and the instruction set for a hypothetical RISC-machine and presents an interpreter to execute the RISC-instructions, as well as a disassembler.

The Oberon-0 compiler is a compact and fast one-pass compiler written in Oberon, which directly emits machine code. It uses the following library modules of the Oberon Systems: Oberon, Texts, Viewers, MenuViewers and TextFrames.

The compiler consists of only four modules: (OSS, OSP, OSG and RISC).MOD, which represent the scanner, parser, code-generator, interpreter and disassembler. In total only about 35000 characters source text, i.e. about 1100 lines of code.

The Oberon-0 compiler can be compiled and executed on all popular platforms, using the freely available Oberon System V4, which was developed at ETH-Zürich.

The code generated from Oberon-0 programs can directly be loaded and executed. An example Oberon-0 program, the disassembled RISC-code and the result of it's execution is given below:

MODULE sieve;
(* Eratosthenes Sieve prime number generation program written in Oberon-0 *)

CONST Size= 81;
VAR    
  Flags: ARRAY Size+1 OF BOOLEAN;
  i,prime,k: INTEGER;

BEGIN
  i:=0; WHILE i <= Size DO Flags[i]:=TRUE; i:=i+1; END;
  i:=0; WHILE i <= Size DO
    IF Flags[i] THEN
      prime:=i*2+3;
      k:=i+prime;
      WHILE k <= Size DO
        Flags[k]:=FALSE;
        k:=k+prime;
      END;
      Write(prime); 
    END;
    i:=i+1;
  END;
  WriteLn;
END sieve.

Oberon0 Compiler  9.2.95
compiling sieve
code generated    53

entry     0
   0    ADDI      30,   0,    3756 entry code
   4    PSH       31,  30,       4 
   8    STW        0,   0,    -332 i:=0
  12    LDW        1,   0,    -332 i
  16    MODI       1,   1,      81 Size
  20    BGT        1,   0,      10 WHILE i<=Size
  24    LDW        1,   0,    -332 i
  28    CHKI       1,   0,      82
  32    MULI       1,   1,       4 [i]
  36    ADDI       2,   0,       1 TRUE
  40    STW        2,   1,    -328 Flags[i]:=TRUE
  44    LDW        1,   0,    -332 i
  48    ADDI       1,   1,       1 +1
  52    STW        1,   0,    -332 i:=i+1
  56    BEQ        0,   0,     -11 end while
  60    STW        0,   0,    -332 i:=0
  64    LDW        1,   0,    -332 i
  68    MODI       1,   1,      81 Size
  72    BGT        1,   0,      32 WHILE i<=Size
  76    LDW        1,   0,    -332 i
  80    CHKI       1,   0,      82
  84    MULI       1,   1,       4 [i]
  88    LDW        2,   1,    -328 Flags[i]
  92    BEQ        2,   0,      23 IF Flags[i]
  96    LDW        1,   0,    -332 i
 100    MULI       1,   1,       2 *2
 104    ADDI       1,   1,       3 +3
 108    STW        1,   0,    -336 prime:=i*2+3
 112    LDW        1,   0,    -332 i
 116    LDW        2,   0,    -336 prime
 120    ADD        1,   1,       2 +
 124    STW        1,   0,    -340 k:=i+prime
 128    LDW        1,   0,    -340 k
 132    MODI       1,   1,      81 Size
 136    BGT        1,   0,      10 WHILE k<=Size
 140    LDW        1,   0,    -340 k
 144    CHKI       1,   0,      82
 148    MULI       1,   1,       4 [k]
 152    STW        0,   1,    -328 Flags[k]:=FALSE
 156    LDW        1,   0,    -340 k
 160    LDW        2,   0,    -336 prime
 164    ADD        1,   1,       2 +
 168    STW        1,   0,    -340 k:=k+prime
 172    BEQ        0,   0,     -11 end while
 176    LDW        1,   0,    -336 prime
 180    WRD        0,   0,       1 Write(prime)
 184    LDW        1,   0,    -332 i
 188    ADDI       1,   1,       1 +1
 192    STW        1,   0,    -332 i:=i+1
 196    BEQ        0,   0,     -33 end while
 200    WRL        0,   0,       0 WriteLn;
 204    POP       31,  30,       4
 208    RET        0,   0,      31 exit code
reloc
    8   12   24   40   44   52   60   64   76   88   96  108  112  116
  124  128  140  152  156  160  168  176  184  192

code loaded

3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 
101 103 107 109 113 127 131 137 139 149 151 157 163
 

The source code of the Oberon-0 compilers is listed in Wirth's book. The source code is also available at ftp://ftp.inf.ethz.ch/pub/software/Oberon/Tools/Compilerbau

The source code on the ftp-server was updated recently to correct some minor errors, which couldn't be considered in the German edition of the book. An English edition is in preparation.

Here are the corrections for module OSG as received by Wirth. The text is in German:

Prozedur Relation:

Das EXCL(regs, x.r) sollte entfernt werden, da das Register im später erzeugten Jump noch gebraucht wird.

Prozedur Store:

Im Falle "y.mode = Cond" muss noch der Jump generiert werden:

        IF y.mode = Cond THEN
          Put(BEQ + negated(y.c), y.r, 0, y.a); EXCL(regs, y.r); y.a := pc;
          FixLink(y.b); ...

Die Rücksprungadresse im R31 muss auf den Stack gespeichert werden, sonst wird sie überschrieben, wenn im Body eine Prozedur aufgerufen wird:

        PROCEDURE Header*(size: LONGINT);
        BEGIN
          entry := pc; Put(ADDI, SP, 0, RISC.MemSize - size);  (*init SP*)
          Put(PSH, LNK, SP, 4)
        END Header;
 

Symetrisch zu Header:

        PROCEDURE Close*(VAR S: Texts.Scanner; globals: LONGINT);
        BEGIN
          Put(POP, LNK, SP, 4);
          Put(RET, 0, 0, LNK)
        END Close;
 

The ModulaTor Forum

Book recommendation:

Jean-Francois Revel: "Democracy against itself", Free Press, Macmillan, New York, 1993. ISBN 0-02-926387-5. Translated by Roger Kaplan from the French edition (1992). Includes index.

Illuminating facts about democracy, history and post-communism. Some quotes: "...taking for granted an imaginated future" (p10), "....there was never anything democratic about communist regimes."(p23), "The more state, the less law... 'democratorship.'"(p25), "Communism cannot be reformed; it can only be replaced by something else."(p27), "Politics is not a deductive science"(p40), "...to be a revolutionary is always to be a totalitarian...anarchy leads to despotism... despotism leads to anarchy..."(p40).

IMPRESSUM: The ModulaTor is an unrefereed journal. Technical papers are to be taken as working papers and personal rather than organizational statements. Items are printed at the discretion of the Editor based upon his judgement on the interest and relevancy to the readership. Letters, announcements, and other items of professional interest are selected on the same basis. Office of publication: The Editor of The ModulaTor is Günter Dotzel; he can be reached by tel/fax: [removed due to abuse] or by mailto:[email deleted due to spam]

Most of the ModulaTor back-issues can be downloaded from http://www.modulaware.com/ in plain-ascii text and GNUzip-compressed PostScript format.

Home Site_index Contact Legal Buy_products OpenVMS_compiler Alpha_Oberon_System ModulaTor Bibliography Oberon[-2]_links Modula-2_links

Webdesign by www.otolo.com/webworx, 13-Jul-1999