home *** CD-ROM | disk | FTP | other *** search
/ cs.rhul.ac.uk / www.cs.rhul.ac.uk.zip / www.cs.rhul.ac.uk / pub / rdp / old_versions / rdp1_3.doc < prev    next >
Text File  |  1994-12-29  |  14KB  |  290 lines

  1. The third maintenance release of RDP (version 1.3) is now available via ftp
  2. from cscx.cs.rhbnc.ac.uk (134.219.200.45) in directory /pub/rdp. Get
  3. rdp1_3.zip if you are an MS-DOS user or rdp1_3.tar if you are a Unix user.
  4.  
  5. RDP compiles attributed LL(1) grammars decorated with C-language semantic
  6. actions into recursive descent compilers. You will find more details in the
  7. last section of this message. If you would like your name added to a mailing
  8. list which will keep you up to date with RDP developments please mail me at
  9. the address given at the end of this message.
  10.  
  11. ** RDP release version 1.30 flyer. Adrian Johnstone 21 December 1994 **
  12.                                                       ________________________
  13. This is the RDP V1.30 release distribution. To       |
  14. install RDP look in the makefile and ensure that the |           *
  15. blocks of options at the top are commented out       |           |
  16. correctly for your compiler and operating system.    |          / \ 
  17. Then type 'make' (or 'nmake' if you are a Microsoft  |          / \
  18. compiler user) and stand well back.                  |         //o\\
  19.                                                      |         // \\
  20. If you use an ANSI compiler then you should be       |        /o/ \o\
  21. able to build RDP after you have defined suitable    |        /// \\\
  22. compiler switch options in the makefile. I'd really  |       //o  \\
  23. like to hear about any problems you have with other  |       o/// \\\\
  24. MS-DOS or Unix C compilerc.                          |      //  / \ o\\
  25.                                                      |      /o/o/|\o\ \
  26. If you have a non-ANSI compiler, then the following  |     //////|\\\\o\
  27. parts of the code might cause you problems:          |         __|__
  28.                                                      |         |   |
  29.  1. Several of the data structures use bit fields to |         \___/
  30.     store flags. You can rework the code to use      |
  31.     #define'd masks in the traditional way.          |
  32.                                                      |    A MERRY CHRISTMAS
  33.  2. As of version 1.3, I am using the ANSI CPU time  |
  34.     routines to generate usage statistics at the     |         TO ALL
  35.     end of each run. I know that some early versions |        
  36.     of Turbo-C use a non-ANSI macro to specify the   |      READERS AND
  37.     number of clock ticks per second. You could      |
  38.     comment out the relevant printf statement if you |     AND RDP USERS 
  39.     can't figure out a fix.                          |________________________
  40.       
  41. Further documentation may be found in Postscript form in subdirectory 'rdp_doc'.
  42.  
  43. I'd like to thank the many people who have tried RDP and sent me encouraging
  44. messages, suggestions for improvements and bug reports, in particular Andy
  45. Betts (previously of UCL, now at Inmos) and my students on course CS347 
  46. (Compilers and code generation) at RHUL.
  47.  
  48. *** Important note ***
  49.  
  50. I have made the following non-backwards compatible changes at this release: 
  51.  
  52. a) the PRE_PROCESS and POST_PROCESS directives have been renamed PRE_PARSE and
  53.    POST_PARSE respectively, 
  54.  
  55. b) the EOF scanner primitive has been removed. EOF is automatically appended
  56.    to the start production (as in fact it always was) and
  57.  
  58. c) the undocumented TEXT_MODE directive has been renamed INTERPRETER 
  59.    (as threatened in the version 1.2 documentation) although it remains 
  60.    undocumented and will probably be replaced by a new mechanism in a future
  61.    release.
  62.  
  63. ** Improvements in this version include **
  64.  
  65. NEW FEATURES AND CHANGES
  66.  
  67. 1. The hand written rdp parser has now been removed. The production rdp
  68. executable is built from an rdp generated C source file. 
  69.  
  70. 2. Semantic actions may have a `pass expression' appended to them of the form
  71. @n where n is an integer. Such actions will only be executed on pass n.
  72. Actions that do not have a pass expression will be executed on every pass.
  73.  
  74. 3. Inherited attributes are now supported. See the user manual, and examples
  75. of their use in the Toy parser. 
  76.  
  77. 4. A new RDP only option -E causes the name of the production detecting an
  78. error to be inserted into generated error messages. This is useful for 
  79. debugging error handlers.
  80.  
  81. 5. PRE_PROCESS and POST_PROCESS are now called PRE_PARSE and POST_PARSE
  82. respectively.
  83.  
  84. 6. Scanner primitive EOF has now been removed. EOF is automatically appended
  85. to the start production (as indeed it always was...)
  86.  
  87. 7. In verbose mode, rdp generated parsers now report the amount of CPU time
  88. used.
  89.  
  90. 8. Call counts are now maintained for all tokens and productions and are
  91. reported along with the first and follow sets in the expanded production
  92. listing switched on by the -e option. Productions that have a call count of
  93. zero generate warning messages, and are not instantiated into the generated
  94. parser.
  95.  
  96. 9. The new global variable 'int rdp__error_return' is used to pass an error
  97. value back to the operating system. By default it is zero, but can of course
  98. be set to any other value within your semantic actions.
  99.  
  100. 10. Calls to undeclared productions are now detected syntactically (RDP is now
  101. a 2 pass parser, so as to cope with forward references) rather than during the
  102. grammar checking phase.
  103.  
  104. 11. Doubly declared productions are now detected syntactically.
  105.  
  106. 12. The Toy interpreter has been replaced by an extened Mini interpreter
  107. called MPL. This language illustrates the use of inherited attributes and is
  108. described in a new chapter of the user manual.
  109.  
  110. 13. In the makefile, macro definitions have been added to support
  111. SUN's acc version 2.0 (thanks to Curtis Bartley), GNU C on MS-DOS
  112. (thanks to Mark Simmons) and Microsoft C++ version 7 (thanks to Paul
  113. Margetts).
  114.  
  115. 14. Several parts of the makefile have been tidied up: in particular the 
  116. support library object files are now only remade when necessary.
  117.  
  118. CORRECTED MISTAKES
  119.  
  120. 15. Subproductions are reported in null production errors. At version 1.2 I
  121. hid subproduction names, but got a little carried away so that null errors
  122. were always reported against the parent production.
  123.  
  124. 16. The rdp.bnf grammar file actually allowed empty sequences (productions of 
  125. the form adrian ::= 'a' | | 'z'. The grammar checking phase would crash as a
  126. result of dereferencing through null pointers generated by these illegal
  127. productions. Empty sequences are now detected syntactically.
  128.  
  129. 17. The new (at version 1.2) error message facility omitted to quote ', " and
  130. \ characters, which caused compile time errors. Thanks to Geoff Lane for
  131. reporting this one. 
  132.  
  133. 18. The new (at version 1.2) error message facility incorrectly reported the
  134. contents of the follow set (as opposed to the first set) when an error was
  135. detected during a scan__test_set() call.
  136.  
  137. 19. RDP parsers reported the compilation time of the parent rdp executable
  138. rather than the generation time of the parser.
  139.  
  140. 20. Due to a pointer arithmetic error, RDP was not previously picking up empty
  141. tokens in normal productions, although it did correctly detect empty tokens in
  142. list iterators.
  143.  
  144. 21. Extended keywords such as STRING which only used one extension field were
  145. written out incorrectly in the load_extended_keywords part of the parser. I
  146. don't understand why this has only just come to light: anyway it's fixed now.
  147.  
  148. 22. The comment at the top of the generated header and parser files reported
  149. the name of the output file instead of the name of the source BNF file.
  150.  
  151. 23. A large number of minor changes have been made to the manual, mainly
  152. to correct typos and document new features.
  153.  
  154. **** Features for future versions
  155.  
  156. Version 2.00 will support scanner productions which supersede the various
  157. programmable tokens used at the moment. RDP will then write out a customised
  158. scanner for each language in exactly the same way that it currently writes out
  159. parsers. These generated scanners will look just like the existing scanner
  160. (i.e. they will NOT be DFA based) so that they can be debugged easily. A set
  161. of scanner productions roughly equivalent to the current scanner will be
  162. supplied.
  163.  
  164. Version 2.00 will also offer some new grammar writing tools. In particular, I
  165. intend to enhance the < > construct so as to allow specification of maximum
  166. and minimum iteration counts, and redefine all other constructs in terms of
  167. this  new mechanism, I also hope to support permutation phrases, as described
  168. in a recent edition of LOPLAS.  
  169.  
  170. The set package will be enhanced to support sets which dynamically grow. At
  171. the moment, all sets allocate the same amount of memory, which can be very
  172. wasteful if your application needs large sets. 
  173.  
  174. Perhaps at V2.00, you will be able to selectively allow backtracking so
  175. allowing LL(k) grammars to be parsed. If you need this a lot you should be
  176. looking at PCCTS or PRECC not RDP.
  177.  
  178. Other suggestions for improvements are welcome.
  179.  
  180. As you may have gathered, RDP V2.00 will be a major rewrite, so don't expect
  181. much until the Spring of 1995.
  182.  
  183. Finally (surprise, surprise) a textbook on code generation for modern
  184. processors, using RDP to construct the compiler front ends, will appear
  185. eventually. Anybody interested in beta-testing the book might like to get in
  186. touch, but we're not expecting to make much progress on it until early Summer
  187. 1995.
  188.  
  189. **** Here follows a thumbnail sketch of RDP ****
  190.  
  191. RDP - a recursive descent parser generator
  192.  
  193. RDP compiles attributed LL(1) grammars decorated with C-language semantic
  194. actions into recursive descent compilers. RDP is written in strict ANSI C and
  195. produces strict ANSI C. RDP was developed using Borland C 3.1 on a PC and has
  196. also been built with no problems on Alpha/OSF-1, DECstation/Ultrix Sun 4/SunOS
  197. and NetBSD 0.9 hosts all using GCC. The definition of strict ANSI here means 
  198. compiling with 
  199.  
  200. gcc -Wmissing-prototypes -Wstrict-prototypes -fno-common -Wall -ansi -pedantic
  201.  
  202. and getting no warning messages. 
  203.  
  204. RDP also compiles with Borland Turbo-C and Microsoft C.
  205.  
  206. RDP is C++ `clean' i.e. there are no identifiers used that clash with C++
  207. reserved words. RDP generated code has been used with g++ applications, and
  208. compiles with g++ and the Borland C++ (as opposed to ANSI) compiler.
  209.  
  210. RDP itself and the language processors it generates use standard symbol, set
  211. and scanner modules. The RDP scanner is programmed by loading tokens into the
  212. symbol table at the start of each run. In principle, the RDP scanner can be
  213. used to support runtime extensible languages, such as user defined operators
  214. in Algol-68, although nobody has had the nerve to try this yet.
  215.  
  216. RDP produces complete runnable programs with built-in help information and
  217. command line switches that are specified as part of the EBNF file. In this
  218. sense RDP output is far more shrink-wrapped than the usual parser generators
  219. which helps beginning students. RDP generates itself (you mean you use a 
  220. parser generator which _isn't_ written in itself?) which is a nice
  221. demonstration of the bootstrapping technique used for porting compilers to new
  222. architectures.
  223.  
  224. I wrote RDP because in October '94 I started giving a course on compiler
  225. design. I don't think the world needs another course on parsing techniques and
  226. am really interested in code generation for exotic processors, so I tried to
  227. produce a compact parser generator that would enable undergraduates to rip
  228. through the syntax and standard code generation parts of the syllabus in a few
  229. weeks, thus leaving me time to get into the black arts of code scheduling and
  230. optimisation.
  231.  
  232. What you get.
  233.  
  234. o An implementation of Pascal style set-handling in C.
  235.  
  236. o A hash-coded symbol table with support for scoping and arbitrary user data.
  237.  
  238. o A programmable high-speed scanner with integrated error handling and
  239.   hooks for macros (RDP is being used to generate assemblers for two novel
  240.   microprocessors in addition to the usual applications of LL(1) parsers).
  241.  
  242. o The machine generated source for the RDP translator. RDP checks that
  243.   the source grammar is LL(1) and explains exactly why a non-LL(1) grammar
  244.   is unacceptable. RDP does not attempt to rework a grammar by itself.
  245.  
  246. o The decorated EBNF file describing RDP that was processed by the RDP 
  247.   executable to produce its own source code. This is good for boggling 
  248.   undergraduate's minds with.
  249.  
  250. o A decorated EBNF file describing an interpreter for a language called TOY.
  251.  
  252. o An EBNF file describing Pascal which generates a parser for the Pascal 
  253.   language. 
  254.  
  255. o A pre-built RDP executable for MS-DOS.
  256.  
  257. o Sources, makefiles and Borland 3.1 project files for everything which
  258.   you may use freely on condition that you send copies of any modifications,
  259.   enhancements and ill-conceived changes you might make back to me so that
  260.   I can improve RDP.
  261.  
  262. o Manuals
  263.  
  264. What you don't get.
  265.  
  266. o Tutorial information on parsing and compiling (try Wirth's Algorithms +
  267.   Data Structures = Programs, Chapter 5 or your favourite compiler book).
  268.   Maybe one day there'll be a book by me. In a future release I will include
  269.   the slides and notes from my compilers course.
  270.  
  271. o Warranties. This code has only just escaped from my personal toolkit.
  272.   I've put a lot of effort into making it fit for others to use, but in
  273.   the very nature of compiler compilers it is hard to test all the angles,
  274.   and the Garbage In - Garbage Out principle holds to the highest degree:
  275.   if you write ill-formed semantic actions you won't find out until you try
  276.   and compile the parser that RDP wrote for you. On the plus side, RDP has
  277.   now been used pretty ferociously by lots of people and has stood up very 
  278.   well. It does seem to be pretty stable, and I will continue to respond to 
  279.   bug reports.
  280.  
  281.                                      Adrian
  282.  
  283. ***
  284. Comments, queries and requests for code to
  285.  
  286. Smail: Dr Adrian Johnstone, Dean of Science, Computer Science Department, 
  287.        Royal Holloway, University of London, Egham, Surrey, TW20 0EX, UK.
  288.  
  289. Email: adrian@dcs.rhbnc.ac.uk  Tel: +44 (0)1784 443425  Fax: +44 (0)1784 443420
  290.