home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / modula2 / alexcoco / readme.wrd < prev    next >
Text File  |  1987-07-16  |  13KB  |  309 lines
  1.              Automatic Compiler Generation with Alex and Coco
  2.                              H. Mössenböck
  3.                University of Linz, Institut für Informatik
  4.                      Altenbergerstr. 69, A-4040 Linz
  5.  
  6.  
  7. Compiler construction is a well understood programming discipline which makes
  8. use of various standard techniques. It is therefore possible to write
  9. programs that apply those techniques to the automatic generation of a
  10. compiler from a formal compiler description.
  11.  
  12. What has compiler construction to do with your own programming tasks?
  13. Don't be confused by the term "compiler construction techniques". In practice
  14. there are a lot of situations where the same techniques can also be applied
  15. to problems which are not in the typical domain of compiler construction.
  16. Consider for example a command language for an interactive user interface or
  17. the processing of a file with variable length records each having its own
  18. structure.
  19.  
  20. In fact every time a structured input has to be processed it is possible to
  21. specify its syntax and its translation by means of a so called attributed
  22. grammar. This description is nothing else than a program in a very high level
  23. language specifically suited for problems of this kind. It can be
  24. automatically translated into the specified "compiler" by a tool called a
  25. compiler generator. The advantage of high level compiler descriptions
  26. compared to compilers written in a general purpose language like Modula-2 is,
  27. that they are usually much shorter and easier to read, because no coding
  28. effort has to be spent for syntax analysis, error handling and attribute
  29. propagation. These actions are included automaticall by the generator,
  30. helping the programmer to focus his attention on the crucial parts of the
  31. translation.
  32.  
  33.  
  34. Contents of the Demo Disk
  35. -------------------------
  36. The demo disk contains two compiler generating tools: Alex is a scanner
  37. generator which builds a lexical analyzer from a description of the terminal
  38. symbols of a language. Coco is a compiler generator which builds a topdown
  39. parser and a semantic evaluator from an attributed grammar. To give you
  40. an impression of how Alex and Coco work we have used them to write a compiler
  41. for a small programming language which we have called Taste (because it gives
  42. a taste of how to generate a compiler). The disk includes the source code
  43. of the Taste compiler. Play with it, add some new features and learn how to
  44. construct your own compiler.
  45.  
  46. Alex and Coco come in demo versions which allow generation of compilers for
  47. languages with at most 32 terminal symbols. This is enough to realize the
  48. benefits of the tools over conventional hand coding. Real languages are of
  49. much bigger size. So if you like Alex and Coco, you should order the full
  50. version of the programs (for sfr 1200.-) from
  51.  
  52.   A.+L. Meier-Vogt
  53.   Im Späten 23
  54.   CH-8906 Bonstetten / ZH
  55.   Tel.: (+41)  1/700 30 37
  56.  
  57. Further material regarding the input languages and the implementation of
  58. Alex and Coco can be found in:
  59.  
  60.   Mössenböck H.: Alex - A Simple and Efficient Scanner Generator.
  61.   SIGPLAN-Notices, Vol 21, Nr.5, May 1986.
  62.  
  63.   Rechenberg P., Mössenböck H.: Ein Compiler-Generator für Mikrocomputer.
  64.   Hanser-Verlag, 1985 (in German).
  65.  
  66.  
  67. Files on the Disk
  68. -----------------
  69. Alex
  70.   alex.EXE         scanner generator Alex
  71.   alextab          tables which are needed by Alex
  72.   alexframe        scanner frame needed by Alex
  73.  
  74. Coco
  75.   coco.EXE         compiler generator Coco
  76.   cocotab          tables which are needed by Coco
  77.   cocosynf         syntax analyzer frame needed by Coco
  78.   cocosemf         semantic evaluator frame needed by Coco
  79.  
  80. Library
  81.   CocoAlex.DIR     This M2SDS-Library contains the following files
  82.   CocoAlex.LIB     in a ready-to-link form
  83.  
  84. Standard Modules
  85.   FileIO.DEF+IMP   IO Module (InOut for multiple Files)
  86.   Errors.DEF+IMP   standard error message module
  87.   Keywords.DEF+IMP recognizes abbreviated program parameters
  88.  
  89. Taste (an example of a generated compiler)
  90.   taste.LEX        scanner description of Taste (to be processed by Alex)
  91.   taste.ATG        attributed grammar of Taste (to be processed by Coco)
  92.   taste.MOD        main program of the Taste compiler
  93.   tastelex.DEF+IMP scanner (generated by Alex from taste.LEX)
  94.   tastesyn.DEF+IMP parser (generated by Coco from taste.ATG)
  95.   tastesem.DEF+IMP semantic evaluator (generated by Coco from taste.ATG)
  96.   tastetab         parser tables (generated by Coco from taste.ATG; they are
  97.                    read by the module tastesyn at run time)
  98.   tastesym.DEF+IMP symbol list module
  99.   tastecod.DEF+IMP code generator
  100.   Test.TAS         example main program written in Taste
  101.  
  102.  
  103. The Taste Language
  104. ------------------
  105. Taste is a very simple programming language which is derived from Modula-2.
  106. It has variables of type INTEGER and BOOLEAN and non-recursive procedures
  107. without parameters. It allows assignments, procedure calls, IF- and WHILE-
  108. statements. Integers may be read from the keyboard and written to the screen,
  109. each of them in a single line. It has arithmetic expressions (+,-,*,/) and
  110. relational expressions (=,<,>). For a full grammar see the file taste.ATG.
  111. A Taste program may look like this:
  112.  
  113.   MODULE Example;
  114.   VAR n: INTEGER;
  115.  
  116.     PROCEDURE SumUp; (*build the sum of all integers from 1 to n*)
  117.     VAR sum: INTEGER;
  118.     BEGIN
  119.       sum:=0;
  120.       WHILE n>0 DO sum:=sum+n; n:=n-1 END;
  121.       WRITE sum
  122.       END SumUp;
  123.  
  124.   BEGIN
  125.     READ n;
  126.     WHILE n>0 DO SumUp; READ n END
  127.     END Example.
  128.  
  129. Of course Taste is too restrictive to be used as a real programming language.
  130. It was our purpose to give just a taste of how to write a compiler with Alex
  131. and Coco.
  132.  
  133.  
  134. Modules of the Taste Compiler
  135. -----------------------------
  136. The Taste compiler is a compile-and-go compiler, which means that it reads a
  137. source program and translates it into a target language which is executed
  138. (i.e. interpreted) immediately after the compilation. The following figure
  139. shows the structure of the compiler (arrows denote procedure call dependencies).
  140.  
  141.                           taste
  142.                             |
  143.          ...................|........
  144.          .               tastesyn   .
  145.          .                  |       .
  146.          .     +------------+------------+
  147.          .     |            |       .    |
  148.          .  tastelex <-- tastesem ---> Errors
  149.          ...................|........
  150.                   +---------+---------+
  151.                   |                   |
  152.                tastesym            tastecod
  153.  
  154. The modules in the dotted rectangle are generated by Alex and Coco, the
  155. other modules are written by hand. Errors is a standard module. The
  156. modules have the following tasks:
  157.  
  158. taste
  159.   Main program. It reads the name of the source file from the keyboard and
  160.   calls the parser and the interpreter.
  161.  
  162. tastesyn
  163.   Parser. It is generated by Coco from the attributed grammar taste.ATG.
  164.   The parser contains a language independent error recovery mechanism
  165.   which is derived by Coco from the attributed grammar.
  166.  
  167. tastesem
  168.   Semantic evaluator. It is generated by Coco from the attributed grammar
  169.   taste.ATG. It contains all the semantic actions of the grammar. The actions
  170.   are called and executed during parsing and do the actual compilation work.
  171.  
  172. tastelex
  173.   Scanner. It is generated by Alex from the scanner description taste.LEX.
  174.  
  175. tastesym
  176.   Symbol list module. This module contains procedures to handle scopes and
  177.   to store and retrieve object information.
  178.  
  179. tastecod
  180.   Code generator. This module contains procedures to emit instructions
  181.   as well as the interpreter and its data structures
  182.  
  183. Errors
  184.   General module for error messages. It is a standard module in compilers
  185.   generated by Coco.
  186.  
  187.  
  188.  
  189. The Target Code
  190. ---------------
  191. We define an abstract stack machine for the interpretation of Taste programs.
  192. The compiler translates a source program into instructions of that machine
  193. which are interpreted later on. The machine uses the following data
  194. structures (code and data are filled by the compiler):
  195.  
  196.   data:  array of integer data memory
  197.   code:  array of byte    code memory
  198.   stack: array of integer expression stack of the stack machine
  199.   pc:    integer          program counter
  200.  
  201. The instructions have variable length. They consist of an operation code
  202. (one byte) and of an operand if necessary (two bytes). The instructions
  203. are described by the following table:
  204.  
  205. LOAD  adr  Load value
  206.            Push(data[adr]);
  207. LIT   val  Load literal constant (or address)
  208.            Push(val);
  209. STO        Store
  210.            Pop(val); Pop(adr); data[adr]:=val;
  211. ADD        Add
  212.            Pop(val2); Pop(val1); Push(val1+val2);
  213. SUB        Subtract
  214.            Pop(val2); Pop(val1); Push(val1-val2);
  215. DIV        Divide
  216.            Pop(val2); Pop(val1); Push(val1/val2);
  217. MUL        Multiply
  218.            Pop(val2); Pop(val1); Push(val1*val2);
  219. EQU        Compare if equal
  220.            Pop(val2); Pop(val1); if val1=val2 then Push(1) else Push(0) end;
  221. LSS        Compare if less
  222.            Pop(val2); Pop(val1); if val1<val2 then Push(1) else Push(0) end;
  223. GTR        Compare if greater
  224.            Pop(val2); Pop(val1); if val1>val2 then Push(1) else Push(0) end;
  225. CALL  adr  Call procedure
  226.            Push(pc); pc:=adr;
  227. RET        Return from procedure
  228.            Pop(pc);
  229. JMP   adr  Jump
  230.            pc:=adr;
  231. FJMP  adr  False jump
  232.            Pop(val); if val=1 then pc:=adr end;
  233. HALT       End of the program
  234.            Halt;
  235. NEG        Negation
  236.            Pop(val); Push(-val);
  237. READ  adr  Read integer
  238.            Write("?"); Read(val); data[adr]:=val; WriteLn;
  239. WRITE      Write integer
  240.            Pop(val); Write(val); WriteLn;
  241.  
  242.  
  243.  
  244. How to use Alex and Coco
  245. ------------------------
  246. If you want to build a compiler for a source language of your own,
  247. proceed as follows:
  248.  
  249. 1. Write a scanner description (i.e. the syntax of the terminal symbols).
  250.    The scanner description of Taste is on the file taste.LEX. Feed the
  251.    scanner description to Alex to get the scanner as a Modula-2 module.
  252.  
  253. 2. Write an attributed grammar of the compiler's source language. An
  254.    attributed grammar consists of a context free grammar and of attributes
  255.    and semantic actions in Modula-2. Attributes may be regarded as parameters
  256.    of the terminals and nonterminals. Semantic actions may be regarded
  257.    as translation actions. They are placed at those points in the grammar
  258.    where a computation with the attributes or with arbitrary Modula-2
  259.    variables are necessary. The attributed grammar of Taste is on the file
  260.    taste.ATG. Feed the attributed grammar to Coco to get the parser and
  261.    the semantic evaluator of the compiler as Modula-2 modules. Coco also
  262.    produces grammar tables which are read by the generated compiler at run
  263.    time.
  264.  
  265. 3. Write a main program. It has to initialize the compiler and to call
  266.    the parser. The main program of the Taste compiler is on the file
  267.    taste.MOD.
  268.  
  269. 4. Write semantic modules as needed. These modules contain procedures that
  270.    are called in the semantic actions of the attributed grammar. For
  271.    example, the Taste compiler has a symbol list module (tastesym.IMP) and
  272.    a code generator (tastecod.IMP). A standard module which prints error
  273.    messages can be found in the file Errors.IMP.
  274.  
  275. 5. Put the pieces together to get a running compiler.
  276.  
  277.  
  278. Examples for the Use of Alex and Coco
  279. -------------------------------------
  280. At our university we have used Alex and Coco for various tasks. The following
  281. list should give you some ideas about what might be useful applications of
  282. the generators:
  283.  
  284. - An analyzer for the static complexity of programs. The analyzer evaluates
  285.   the kind of operators and statements, the program nesting and the use
  286.   of local and global variables to obtain a measure of the program complexity
  287.   and an indication if the program is well structured.
  288.  
  289. - A cross reference generator which lists all occurences of the objects in
  290.   a program according to their scope together with information where the
  291.   objects have been assigned a value and where they have been referenced.
  292.  
  293. - An "intelligent" pretty printer which uses the structure and the length
  294.   of statements for proper indentation.
  295.  
  296. - A program which generates an index for books and reports. The index is
  297.   generated from relations between page numbers and keywords entered in an
  298.   appropriate way.
  299.  
  300. - The front end of a syntax oriented editor. A Modula-2 program is translated
  301.   into a tree representation which is the internal data structure of the
  302.   editor.
  303. MBlock1wor
  304. F
  305. 
  306. (2<FPZdnxéîûP MKapitel1rB
  307. (2<FPZdnxéîûP  b&!B
  308. (2<FPZdnxéîûP ddd
  309. WP¬1²