Softwar resources - Compilers and Compiler Generators

Software resources for "Compilers and Compiler Generators with C++"

October 1999: It is likely that you wish to obtain the files that accompany this book and install the system from this web site rather than from a diskette! In this case, any references here or in the book to files of the form

       A:SOMEFILE

should be changed to

       X:SOMEFILE

where X: is the path to the directory/folder in which the source files reside.

The page you are reading now describes the layout of the directory structure set up after you have installed the sources for the book onto your system

IMPORTANT:

We shall assume a working knowledge of MS-DOS based systems. If you are working from within MS-Windows in any release, we assume that you will be able to place any commands illustrated here into the context of the File Manager/Explorer, or that you will run within an MS-DOS window where appropriate.
Installation is described here, and in Appendix A of the book.
Remember to install BOTH the common files (decompress A:COMMON.ZIP) and the language specific files (A:xSOURCES.ZIP) before you attempt any case studies.
If you intend using Coco/R, you must also install the version of Coco/R for your language of choice. If this is C++, remember to compile the base class support. Please read the README files for Coco/R to complete the installation.
If you intend using Modula-2, you must also install the FileIO library (decompress A:FILEIO.ZIP).

Directories

Where appropriate, we shall assume in what follows that the software has been installed onto a directory

       C:\SRCES

that you have installed a version of Coco/R onto a directory

       C:\COCO

and that you will be using a working directory for a case study of interest

       C:\WORK

These names are suggestions only; you are free to use different volumes (C:, D:, E: ...) and different directories if you prefer.

In the directory C:\SRCES you should find

       README.SRC  - this file

       CHECK.PAS   - Source of CHECK
       CHECK.EXE   - Executable to assist with the SETUP process
                     (This is invoked automatically by the SETUP process)

       CONVERT.PAS - Source of CONVERT
       CONVERT.EXE - Program to convert text files between operating systems
                     (translating line marks appropriate to the O/S in use)

Typing the command CONVERT with no parameters gives details of use.

       Example:   CONVERT DOS.CPP APPLE.CPP 2

Subdirectories for the case studies of each chapter

There are no source files associated with chapters 1, 2, 3 or 9. Other subdirectories are as follows:

   *   CHAP04      - Machine emulation
       CHAP05      - Language specification
   *   CHAP06      - Simple assemblers
   *   CHAP07      - Advanced assembler features
       CHAP08      - Grammars and their classification
   *   CHAP10      - Parser and scanner construction
   *   CHAP11      - Syntax directed translation
   *   CHAP12      - Using Coco/R - overview
   *   CHAP13      - Using Coco/R - case studies
   *   CHAP14      - A simple compiler - the front end (Clang level 1)
   *   CHAP15      - A simple compiler - the back end  (Clang level 1)
   *   CHAP15.ASM  - A simple compiler - generating assembler code
   *   CHAP16D     - Simple block structure (using a display) (Clang level 2)
   *   CHAP16S     - Simple block structure (using a static link)
   *   CHAP17      - Parameters and functions (Clang level 3)
   *   CHAP18      - Concurrent programming (Clang level 4)

   *   COMMON      - Files that are common to many Clang case studies

       ASMBLER     - A macro assembler with full-screen interpreter

       HASH        - Investigation of minimal perfect hash functions
                     (Chapter 14)

   *   TOPSY       - Suggestions for the Topsy project (Chapters 14, 15)

Those subdirectories marked with an * contain further subdirectories depending on the implementation language. For example, once you have unpacked the sources, you will find that they appear in directories like

       C:\SRCES\CHAP18\CPP     for the C++ versions

or, correspondingly

       C:\SRCES\CHAP18\PASCAL  for the Pascal versions
       C:\SRCES\CHAP18\MODULA  for the Modula-2 versions

Setting up for a case study

In the interests of economy, files that are common to several case studies have been stored once only. Managing these, and navigating through a pile of similarly named files with very similar contents, might prove to be a nightmare. To aid with this, we have arranged that installation of many (but not all) of the case studies requires you simply to

Log onto to an appropriate source drive (for a chapter) and subdirectory (for a language), for example
```
       C:
       CD C:\SRCES\CHAP15\CPP
```
Issue the command
```
      SETUP
```
with no parameters. This will indicate what parameters might be added to the command to provide a variant appropriate for the case studies of that chapter.
For example, follow this by obeying a SETUP command like
```
      SETUP C:\WORK 5
```
where C:\WORK is a directory that will be created if necessary, and into which the appropriate components for SETUP option 5 will be copied.
Once you have copied all the files, you may start to experiment by logging onto the working directory
```
       CD C:\WORK
```
and issuing the MAKE command (C++) or equivalent compiler commands (Pascal or Modula-2) to compile the selected case study.
IMPORTANT
The SETUP process copies source code files, and also specimen code (data) that the application generated by the case study can compile, assemble or process.
The "makefiles" and TURBOC.CFG files supplied are intended for almost immediate use with Borland C++ release 3.1; they may need slight alteration for use with other systems, or editing to suit your directory structure.
If you use one C:\WORK directory and simply keep copying new case studies to this without due attention to disk house-keeping, you may well find that applications do not compile or link properly. The simplest procedure to follow is to clear the work directory before you copy files to it.
```
       C:
       CD C:\SRCES\CHAP15\CPP
       DEL C:\WORK\*.*     or RD C:\WORK\ /S
       SETUP C:\WORK 5
```
Please be careful about deleting files! Please also keep the original distribution files safe, and write-protected. In that way you can always reinstall the sources and other components if accidents occur.

Some of the simpler case studies - typically those consisting of only one source file - are not managed by a SETUP process.

In cases of difficulty, please contact the author

Pat Terry
Computer Science Department
Rhodes University
MAKHANDA / GRAHAMSTOWN 6140
South Africa
email: p.terry@ru.ac.za>

Directory contents

The following notes will help you explore the sources further. In these notes, \x\ stands for \CPP\, \MODULA\ or \PASCAL\ according to the chosen implementation language, and an * denotes that there may be several files with names related to those shown (usually with differing extensions).

CHAP04 - Machine emulation

This chapter contains case studies of two pseudo-machines, with their interpreters and rudimentary assemblers.

    CHAP04\x\SETUP.BAT    - Execute CHAP04\x\SETUP.BAT to piece together a
                            complete case study

The following files pertain to the single-accumulator machine (section 4.3)

    CHAP04\BITS.ASM       - Count the bits in a number (simple code)
    CHAP04\BITS.MC        - Count the bits in a number (core image)
    CHAP04\SIEVE.MC       - Sieve of Eratosthenes (core image)

    CHAP04\x\AS.*         - Assembler (using mnemonics)
    CHAP04\x\AS0.*        - Loader (from core image)
    CHAP04\x\ASM.MK       - Makefile for Borland C++
    CHAP04\x\ASSEMBLE.*   - Main routine
    CHAP04\x\MC.*         - Single-accumulator machine interpreter
    CHAP04\x\MISC.H       - Miscellaneous routines

The following files pertain to the stack based machine (section 4.4)

    CHAP04\LSMALL.STK     - Find largest and smallest in a sequence

    CHAP04\x\STACKASM.*   - Main routine
    CHAP04\x\STACKASM.MK  - Makefile for Borland C++
    CHAP04\x\STKASM.*     - Rudimentary assembler
    CHAP04\x\STKMC.*      - Stack machine interpreter

CHAP05 - Language specification

This directory contains some simple examples of the use of Cocol to express grammars in EBNF. There is no SETUP system for this directory.

    CHAP05\*.ATG          - Various sample Coco/R grammars
    CHAP05\COCOL.ATG      - Cocol/R expressed in Cocol/R (section 5.9.5)

CHAP06 - Simple assemblers

This directory contains the source code for simple one-pass and two-pass assemblers for the single-accumulator machine of Chapter 4.

    CHAP06\x\SETUP.BAT    - Execute CHAP06\x\SETUP.BAT to piece together a
                            complete case study

    CHAP06\ASM*.ATG       - Grammars for the ASSEMBLER language
    CHAP06\*.ASM          - Simple source examples

    CHAP06\x\AS1.*        - One-pass assembler
    CHAP06\x\AS2.*        - Two-pass assembler
    CHAP06\x\ASM.MK       - Makefile for Borland C++
    CHAP06\x\ASSEMBLE.*   - Main routine
    CHAP06\x\LA.*         - Lexical analyzer
    CHAP06\x\MISC.H       - Miscellaneous routines
    CHAP06\x\SA.*         - Syntax analyzer
    CHAP06\x\SH.*         - Source handler
    CHAP06\x\ST1.*        - Symbol table handler - One-pass assembler
    CHAP06\x\ST2.*        - Symbol table handler - Two-pass assembler
    CHAP06\x\TP.*         - Definitions of special types

CHAP07 - Advanced assembler features

This directory contains the source code for a one-pass macro assembler for the single-accumulator machine of Chapter 4.

    CHAP07\x\SETUP.BAT    - Execute CHAP07\x\SETUP.BAT to piece together a
                            complete case study

    CHAP07\*.ASM          - Simple source examples

    CHAP07\x\AS.*         - One-pass assembler
    CHAP07\x\ASMBASE.H    - One-pass assembler base class
    CHAP07\x\ASSEMBLE.*   - Main routine
    CHAP07\x\LA.*         - Lexical analyzer
    CHAP07\x\MAKEFILE     - Make file for Borland C++
    CHAP07\x\MH.*         - Macro handler
    CHAP07\x\MISC.H       - Miscellaneous routines
    CHAP07\x\SA.*         - Syntax analyzer
    CHAP07\x\SET.H        - Template set class (C++)
    CHAP07\x\SH.*         - Source handler
    CHAP07\x\ST.*         - Symbol table handler (hashed)
    CHAP07\x\ST2.*        - Symbol table handler (simple linked list)
    CHAP07\x\TP.*         - Definitions of special types

CHAP08 - Grammars and their classification

This directory contains some simple demonstrations of grammars and programs for the first levels of the Clang and Topsy languages. There is no SETUP system for this directory.

    CHAP08\CLANG1.ATG     - Clang grammar in BNF  (section 8.7.1)
    CHAP08\CLANG2.ATG     - Clang grammar in EBNF (section 8.7.2)
    CHAP08\QUERY.CLN      - Sample Clang program with unclear semantics
    CHAP08\VOTE.CLN       - Sample Clang program
    CHAP08\VOTE.TOP       - Sample Topsy program

CHAP10 - Parser and scanner construction

This directory contains some simple hand-crafted recursive descent parsers and a simple LR parser demonstration. There is no SETUP system for this directory. The programs are all self-contained. Copy their source code to a work directory, and then compile them.

    CHAP10\x\LRDATA       - Data for LR Parser demonstration
    CHAP10\x\LRPARSER.*   - Toy LR parser program
    CHAP10\x\PARSER1.*    - Parser from section 10.2 (no nested routines)
    CHAP10\x\PARSER2.*    - Parser from section 10.2 (equivalent grammar)
    CHAP10\x\PARSER3.*    - Parser from section 10.2 (Pascal/Modula with
                            nested routines)

CHAP11 - Syntax directed translation

This directory contains some hand-crafted parsers and a simple Coco/R case study from section 11.5. There is no SETUP system for this directory. The parsers are self-contained. Copy the files to a work directory and experiment with them.

    CHAP11\x\CLASS.DTA    - Data for Coco/R case study
    CHAP11\x\CLASSL.FRM   - Coco/R compiler frame file
    CHAP11\x\CLASSLIS.ATG - Cocol grammar for case study of section 11.5
    CHAP11\x\DBASEMAN.*   - Dummy data base handler module
    CHAP11\x\MAKE.BAT     - Batch file to make the C++ case study of 11.5
    CHAP11\x\PARSER4.*    - Parse infix expressions (section 11.1)
    CHAP11\x\PARSER5.*    - Convert infix to reverse Polish (section 11.1)
    CHAP11\x\PARSER6.*    - Evaluate infix expressions (section 11.3)
    CHAP11\x\TURBOC.CFG   - Sample Borland C++ configuration file

CHAP12 - Using Coco/R - overview

This directory contains the material for the simple case study used in the description of Coco/R. There is no SETUP system for this directory. Copy the files to a work directory and experiment with them - the case study itself is fairly trivial.

    CHAP12\x\CALC.ATG     - Attributed grammar for simple adding machine
    CHAP12\x\CALC.FRM     - Coco/R compiler frame file
    CHAP12\x\CALC0.ATG    - Unattributed grammar for addin machine (12.2)
    CHAP12\x\DATA         - Specimen data for adding machine
    CHAP12\x\MAKE.BAT     - Batch file to make the system with Borland C++
    CHAP12\x\TURBOC.CFG   - Sample Borland C++ configuration file

CHAP13 - Using Coco/R - case studies

This directory contains the files for four Coco/R case studies, ranging from a trivial one to a fairly extensive one.

    CHAP13\x\SETUP.BAT    - Execute CHAP13\x\SETUP.BAT to piece together a
                            complete case study

    CHAP13\x\MISC.H       - Miscellaneous routines

The following files refer to various exercises

    CHAP13\x\EXPR1.ATG    - Grammar for parsing expressions
    CHAP13\x\EXPR2.ATG    - Grammar for converting infix expressions to Polish
    CHAP13\x\EXPR3.ATG    - Grammar for evaluating expressions

The following files refer to case study 13.1 - C declarations

    CHAP13\DECL.DTA       - Specimen declarations
    CHAP13\x\CDECL.MK     - Makefile for Borland C++
    CHAP13\x\CDECL.ATG    - Attributed grammar for parsing declarations

The following files refer to case study 13.2 - one address code generation

    CHAP13\EXPR.DTA       - Specimen data
    CHAP13\x\EXPR.FRM     - Coco/R compiler frame file
    CHAP13\x\EXPR.MK      - Makefile for Borland C++
    CHAP13\x\EXPR4.ATG    - Attributed grammar for parsing expressions
                            and generating one-address code on the fly

The following files refer to case study 13.3 - code generation via an AST

    CHAP13\EXPR.DTA       - Specimen data
    CHAP13\x\EXPR.FRM     - Coco/R compiler frame file
    CHAP13\x\EXPR2.MK     - Makefile for Borland C++
    CHAP13\x\EXPR5.ATG    - Attributed grammar for parsing expressions
                            and generate code from an AST

The following are the AST tree handlers using variant records/unions

    CHAP13\x\ASTREES0.*   - Simple AST
    CHAP13\x\ASTREES1.*   - AST with constant folding
    CHAP13\x\ASTREES2.*   - AST for fairly optimal one-address code
    CHAP13\x\ASTREES3.*   - AST for fairly optimal single-accumulator code

The following are the AST tree handlers using FST Modula-2 OOP

    CHAP13\x\FSTTREE0.*   - Simple AST
    CHAP13\x\FSTTREE1.*   - AST with constant folding
    CHAP13\x\FSTTREE2.*   - AST for fairly optimal one-address code
    CHAP13\x\FSTTREE3.*   - AST for fairly optimal single-accumulator code

The following are the AST tree handlers using C++ or Turbo Pascal OOP

    CHAP13\x\TREES0.*     - Simple AST
    CHAP13\x\TREES1.*     - AST with constant folding
    CHAP13\x\TREES2.*     - AST for fairly optimal one-address code
    CHAP13\x\TREES3.*     - AST for fairly optimal single-accumulator code

The following are the AST tree handlers using TopSpeed Modula-2 OOP

    CHAP13\x\JPITREE0.*   - Simple AST
    CHAP13\x\JPITREE1.*   - AST with constant folding
    CHAP13\x\JPITREE2.*   - AST for fairly optimal one-address code
    CHAP13\x\JPITREE3.*   - AST for fairly optimal single-accumulator code

The following files refer to case study 13.4 - parser generators

    CHAP13\EBNF.ATG       - Unattributed grammar
    CHAP13\GRAM*.*        - Specimen simple grammars
    CHAP13\PROG1*.*       - Specimen simple programs

    CHAP13\x\EBNF.ATG     - Attributed grammar
    CHAP13\x\EBNF.FRM     - Coco/R compiler frame file
    CHAP13\x\EBNF.MK      - Makefile for Borland C++

    CHAP13\x\GP.*         - Graph parser support
    CHAP13\x\GS.*         - Graph scanner support
    CHAP13\x\SRC.*        - Program source handler

CHAP14 - A simple compiler - the front end

This directory contains parsers (only) for Clang level 1, that is, for the front end of a compiler, with no code generation

    CHAP14\x\SETUP.BAT    - Execute CHAP14\x\SETUP.BAT to piece together a
                            complete case study

    CHAP14\CLANG.ATG      - Unattributed grammar
    CHAP14\*.CLN          - Simple programs to parse

    CHAP14\x\CLANG.ATG    - Attributed grammar
    CHAP14\x\CLANG.FRM    - Coco/R compiler frame file
    CHAP14\x\CLANG.MK     - Coco/R makefile for Borland C++
    CHAP14\x\CLN.*        - Main routine (Modula/Pascal versions)
    CHAP14\x\CLN0.CPP     - Main routine - no error recovery
    CHAP14\x\CLN0.MK      - Hand-crafted makefile for Borland C++
    CHAP14\x\CLN1.CPP     - Main routine - with error recovery
    CHAP14\x\CLN1.MK      - Hand-crafted makefile for Borland C++
    CHAP14\x\PARSER0.*    - Hand-crafted parser, no error recovery
    CHAP14\x\PARSER1.*    - Hand crafted parser, follower set error recovery
    CHAP14\x\PARSER2.*    - Hand crafted parser, ordered token error recovery
    CHAP14\x\TABLE.*      - Symbol table handler

CHAP15 - A simple compiler - the back end (Clang level 1)
CHAP16D - Simple block structure (using a display) (Clang level 2)
CHAP16S - Simple block structure (using a static link)
CHAP17 - Parameters and functions (Clang level 3)
CHAP18 - Concurrent programming (Clang level 4)

The case studies in these chapters are supported in very similar directory structures. They contain the sources for a variety of implementation strategies for Clang compilers at a variety of levels, using both hand-crafted and Coco/R generated compilers.

    CHAPnn\x\SETUP.BAT    - Execute CHAPnn\x\SETUP.BAT to piece together a
                            complete case study

    CHAPnn\*.CLN          - Simple programs to compile.  Note that
                            the programs for one "level" of Clang can
                            also be compiled by higher levels.  For
                            example, the examples in CHAP15 can be
                            compiled by the Clang compilers in chapters
                            15, 16, 17 and 18.

    CHAPnn\CLANG.ATG      - Unattributed grammar for Clang

    CHAP18\CLANG.RPT      - Language definition for Clang level 4.
                            Others could be derived from this by the
                            removal of features.

    CHAPnn\x\CGEN1.*      - On-the-fly code generators
    CHAPnn\x\CGEN2.*      - AST code generators (Variant record/Union)
    CHAPnn\x\CGEN3.*      - AST code generators (OOP)
    CHAPnn\x\CLANG.ATG    - Attributed grammar for on-the-fly generation
    CHAPnn\x\CLANGAST.ATG - Attributed grammar for AST generation
    CHAPnn\x\PARSER1.*    - Hand crafted parser, follower set error
                            recovery, on the fly code generator
    CHAPnn\x\PARSER2.*    - Hand crafted parser, ordered token error
                            recovery, on the fly code generator
    CHAPnn\x\PARSER3.*    - Hand crafted parser, follower set error
                            recovery, AST code generator
    CHAPnn\x\PARSER4.*    - Hand crafted parser, ordered token error
                            recovery, AST code generator
    CHAPnn\x\PSEUDORA.*   - Random number generators (Modula-2, Clang 4)
    CHAPnn\x\STKMC.*      - Interpreter
    CHAPnn\x\TABLE.*      - Symbol table handler
    CHAPnn\x\TESTRAND.MOD - Test random number generation (Modula)

COMMON - Files that are common to many Clang case studies

Many of the case studies in Chapters 14 through 18 require that some of these files be compiled and linked into the Clang compilers. The SETUP system in the files for Chapters 14 through 18 will do the appropriate selection of these files for you.

    COMMON\x\SETUP.BAT    - Called from CHAPnn\x\SETUP.BAT to piece
                            together complete case studies.
                            (Do NOT run this batch file on its own.)

    COMMON\READ.ME        - Notes on some of these programs

    COMMON\x\CLANG.FRM    - Coco/R compiler frame file
    COMMON\x\CLANG.MK     - Coco/R makefile for Borland C++
    COMMON\x\CLN.*        - Hand-crafted main routine
    COMMON\x\CLN.MK       - Hand-crafted makefile for Borland C++
    COMMON\x\MISC.H       - Various types and declarations (C++)
    COMMON\x\PARSER.DEF   - Parser definition (Modula)
    COMMON\x\REPORT.*     - Error reporting module/class/unit
    COMMON\x\SCAN.*       - Hand-crafted scanner
    COMMON\x\SET.H        - Template set class (C++)
    COMMON\x\SRCE.*       - Hand-crafted source handler
    COMMON\x\TURBOC.CFG   - Sample Borland C++ configuration file

CHAP15.ASM - A simple compiler - generating assembler code

This directory contains components of a Clang level 1 compiler like that discussed in Chapter 15, but which generates assembler code for the simple single-accumulator machine of chapters 4. See section 15.3.5. The assembler code that is generated can be assembled with the assembler found in the ASMBLER directory.

    CHAP15.ASM\x\SETUP.BAT    - Execute CHAP15.ASM\x\SETUP.BAT to piece
                                together a complete case study

    CHAP15.ASM\x\CGEN*.*      - Code generators
    CHAP15.ASM\x\CLANG.FRM    - Coco/R compiler frame file
    CHAP15.ASM\x\CLANG.MK     - Coco/R makefile for Borland C++
    CHAP15.ASM\x\CLANGAST.ATG - Coco/R attributed grammar
    CHAP15.ASM\x\CLN.*        - Hand-crafted main routine
    CHAP15.ASM\x\CLN.MK       - Hand-crafted makefile for Borland C++
    CHAP15.ASM\x\COMPILE.BAT  - Compile/assemble from hand-crafted version
    CHAP15.ASM\x\COMPILE1.BAT - Compile/assemble from Coco/R version
    CHAP15.ASM\x\PARSER*.*    - Hand-crafted parser

ASMBLER - A macro assembler with full-screen interpreter

This directory contains the executable for a version of the macro-assembler described in chapter 7, but which has the option of performing the machine emulation in a full-screen display mode. Study the READ.ME file for details. There is no SETUP system for this directory.

    ASMBLER\ASM.EXE       - Executable of the assembler/interpreter
    ASMBLER\*.ASM         - Simple source examples
    ASMBLER\READ.ME       - Instructions for executing ASM

HASH - Investigation of minimal perfect hash functions (Chapter 14)

This directory contains source code for supporting the exercises discussed in section 14.4.3. There is no SETUP system for this directory. Copy the files to a work directory and compile the source.

    HASH\*.KEY            - Lists of keywords for some languages
    HASH\FINDHASH.*       - Cichelli's algorithm for finding minimal
                            perfect hash functions.
    HASH\READ.ME          - Instructions for running FINDHASH

TOPSY - Suggestions for the Topsy project (Chapters 14, 15)

This directory contains a Topsy level 1 language report and some other material for use in the Topsy project suggested in many of the exercises in chapters 15 through 18. Further extensions are left as exercises.

    TOPSY\x\SETUP.BAT     - Execute TOPSY\x\SETUP.BAT to piece together the
                            complete case study

    TOPSY\*.TOP           - Sample Topsy source files
    TOPSY\TOPSY.RPT       - Topsy language definition
    TOPSY\TOPSY0.ATG      - Basic Topsy level 1 grammar

    TOPSY\x\CGEN.*        - Code generator
    TOPSY\x\STKMC.*       - Interpreter
    TOPSY\x\TABLE.*       - Symbol table manager
    TOPSY\x\TOPSY.ATG     - Attributed grammar
    TOPSY\x\TOPSY.FRM     - Coco/R compiler frame file
    TOPSY\x\MAKEFILE      - Makefile for Borland C++

Copyrights and Trade Marks

Borland C++, Turbo C++, Delphi and Turbo Pascal are trademarks of Borland International Corporation.
IBM and IBM PC are trademarks of International Business Machines Corporation.
Microsoft, MS and MS-DOS are registered trademarks, and Windows is a trademark of Microsoft Corporation.
Stony Brook Software and QuickMod are trademarks of Gogesch Micro Systems, Inc.
TopSpeed is a registered trademark of Jensen and Partners, International.

Any other trademarks inadvertently used here are also duly acknowledged.