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_0.doc next >
Text File  |  1994-02-20  |  12KB  |  257 lines
  1. ** RDP release version 1.00 flyer. Adrian Johnstone 16 February 1994 **
  2.  
  3. RDP - a recursive descent parser generator
  4.  
  5. RDP compiles attributed LL(1) grammars decorated with C-language semantic
  6. actions into recursive descent compilers. RDP is written in strict ANSI C
  7. and produces strict ANSI C. RDP was developed using Borland C 3.1 on a PC
  8. and has also been built with no problems on Alpha/OSF-1, DECstation/Ultrix
  9. and Sun 4/SunOS hosts. The definition of strict ANSI here means compiling
  10. with gcc -Wall -pedantic -ANSI and getting no warning messages.
  11.  
  12. RDP itself and the language processors it generates use standard symbol,
  13. set and scanner modules. The RDP scanner is programmed by loading tokens
  14. into the symbol table at the start of each run.
  15.  
  16. RDP produces complete runnable programs with built-in help information and
  17. command line switches that are specified as part of the EBNF file. In this
  18. sense RDP output is far more shrink-wrapped than the usual parser generators
  19. which helps beginning students. RDP can generate itself which is a nice
  20. demonstration of the bootstrapping technique used for porting compilers to
  21. new architectures.
  22.  
  23. I wrote RDP because in October I start giving a course on compiler design.
  24. I don't think the world needs another course on parsing techniques and am
  25. really interested in code generation for exotic processors, so I tried to
  26. produce a compact parser generator that would enable undergraduates to rip
  27. through the syntax and standard code generation parts of the syllabus in a
  28. few weeks, thus leaving me time to get into the black arts of code
  29. scheduling and optimisation.
  30.  
  31. What you get.
  32.  
  33. - An implementation of Pascal style set-handling in C.
  34.  
  35. - A hash-coded symbol table with support for scoping and arbitrary user data
  36.  
  37. - A programmable high-speed scanner with integrated error handling and
  38.   hooks for macros (RDP is being used to generate assemblers for two novel
  39.   microprocessors in addition to the traditional territory of LL(1) parsers).
  40.  
  41. - The source to a hand-coded version of the RDP translator. RDP checks that
  42.   the source grammar is LL(1) and explains exactly why a non-LL(1) grammar
  43.   is unacceptable. RDP does not attempt to rework a grammar by itself.
  44.  
  45. - A decorated EBNF file describing RDP that may be processed by the
  46.   hand-coded RDP translator to produce a machine generated version of RDP.
  47.   This is good for boggling undergraduate's minds with.
  48.  
  49. - A decorated EBNF file describing an interpreter for a language called TOY.
  50.  
  51. - An EBNF file describing Pascal which can be used to generate parser for
  52.   the Pascal language. This file has not been well tested!
  53.  
  54. - A pre-built executable for MS-DOS.
  55.  
  56. - Sources, makefiles and Borland 3.1 project files for everything which
  57.   you may use freely on condition that you send copies of any modifications,
  58.   enhancements and ill-conceived changes you might make back to me so that
  59.   I can improve RDP.
  60.  
  61. What you don't get.
  62.  
  63. - Decent manuals (coming Real Soon Now).
  64.  
  65. - Tutorial information on parsing and compiling (try Wirth's Algorithms +
  66.   Data Structures = Programs, Chapter 5 or your favourite compiler book).
  67.  
  68. - Warranties. (This code has only just escaped from my personal toolkit.
  69.   I've put a lot of effort into making it fit for others to use, but in
  70.   the very nature of compiler compilers it is hard to test all the angles,
  71.   and the Garbage In - Garbage Out principle holds to the highest degree:
  72.   if you write syntactically ill-formed semantic actions you won't find
  73.   out until you try and compile the parser that RDP wrote for you.)
  74.  
  75. What I'd like.
  76.  
  77. - Guinea pigs: I'm sure there are some bad surprises waiting for me, and I'd
  78.   like to find them before October so that my course doesn't get torpedoed.
  79.  
  80. - A C grammar. The supplied Pascal grammar was produced by retrieving the
  81.   yacc Pascal description floating around on the net and hacking it into RDP
  82.   source form (which shortens it a great deal BTW). An obvious first
  83.   project is to do the same for the C grammar and maybe produce a
  84.   pretty-printer based on it.
  85.  
  86. RDP source language.
  87.  
  88. - The RDP source language is a very conventional EBNF supplemented with:
  89.  
  90.     a few pre-defined tokens such as ID (an alphanumeric identifier),
  91.     NEW_ID (an alphanumeric identifier that has not yet been added to
  92.     the symbol table), EOF and EOLN,
  93.  
  94.     some programmable tokens such as STRING and STRING_ESC which define
  95.     Pascal and C style strings respectively,
  96.  
  97.     a set of directives which are mainly used to programme the scanner
  98.     and the help subsystems
  99.  
  100.     a weird construct < sequence > 'token' which is shorthand for
  101.     sequence {'token' sequence}
  102.  
  103.     attributes of the form :identifier which may be attached to production
  104.     names where they define the type of variable returned on the LHS and
  105.     the name of the receiving variable on the RHS of an ::=
  106.  
  107.     arbitrary C code semantic actions embedded in double quotes. These are
  108.     simply copied into the generated parser.
  109.  
  110. - Here's the RDP grammar written in terms of itself. Tokens are enclosed
  111.   in single quotes, directives and built-in tokens are written in upper case
  112.   and comments are denoted by (* ... *). RDP is case sensitive.
  113.  
  114. (* RDP source grammar *)
  115. unit      ::= { prod | dir} EOF.
  116.  
  117. prod      ::= (ID|NEW_ID) [':'(ID|NEW_ID) {'*'} ] '::=' alt:body '.' .
  118.  
  119. alt       ::= < seq: body > '|' .
  120.  
  121. seq       ::= { (item_ret [':' (ID | NEW_ID) ] | item_inl) }.
  122.  
  123. item_ret  ::= ID | NEW_ID | token |
  124.               'STRING' '(' token ')' |
  125.               'STRING_ESC' '(' token token')' |
  126.               'COMMENT' '(' token token ')' |
  127.               'COMMENT_NEST' '(' token token ')'.
  128.  
  129.  
  130. item_inl: ::= code |                 (* semantic action *)
  131.               '('alt:body')' |       (* do first *)
  132.               '{'alt:body'}' |       (* zero or more *)
  133.               '['alt:body']' |       (* zero or one *)
  134.               '<'alt:body'>' token . (* list: <X>'t' expands to X {'t' X} *)
  135.  
  136. code      ::= STRING_ESC('"' '\\').
  137. token     ::= STRING_ESC('\'' '\\').
  138. comment   ::= COMMENT('(*' '*)').
  139.  
  140. dir::= 'INCLUDE' '(' code ')' |        (* Does for RDP what #include does for C *)
  141.        'HELP' '(' code code  ')' |     (* Add help line and command line switch *)
  142.        'USES' '(' code ')' |           (* Adds a #include to the generated parser *)
  143.        'TITLE' '(' code ')' |          (* Descriptive programme title for help *)
  144.        'SUFFIX' '(' code ')' |         (* Defalt file suffix for scanner input *)
  145.        'OUTPUT_FILE' '(' code ')' |    (* Default output file name *)
  146.        'SET_SIZE' '(' NUMBER ')' |     (* Set maximum set size (must be >= # of tokens *)
  147.        'HASH_SIZE' '(' NUMBER ')' |    (* Number of hash buckets in hash table *)
  148.        'HASH_PRIME' '(' NUMBER ')' |   (* Hash key: see dragon book on hash functions *)
  149.        'TAB_WIDTH' '(' NUMBER ')' |    (* Tab expansion width in listings *)
  150.        'TEXT_SIZE' '(' NUMBER ')' |    (* Default size of text buffer *)
  151.        'MAX_ERRORS' '(' NUMBER ')' |   (* Stop after this many errors *)
  152.        'MAX_WARNINGS' '(' NUMBER ')' | (* Stop after this many warnings *)
  153.        'CASE_INSENSITIVE' |            (* Make scanner case insensitive (cf Pascal) *)
  154.        'SHOW_SKIPS' |                  (* Issue 'Skipping...' informational messges *)
  155.        'NEWLINE_VISIBLE' |             (* Make newlines visisbles (cf Ada comments, assemblers) *)
  156.        'COMMENTS_VISIBLE'.             (* Return comments to parser (cf assemblers) *)
  157.  
  158. (* End of grammar *)
  159.  
  160. How to get RDP.
  161.  
  162. - Use anonymous ftp to cscx.dcs.rhbnc.ac.uk () and download
  163.   pub/rdp/rdp.tar.Z if you are a Unix user or pub/rdp/rdp.zip if you are an
  164.   MS-DOS user. Actually both files contain exactly the same distribution kit,
  165.   so you will find an MS-DOS executable in the tar file.
  166.  
  167. - If you can't manage ftp then I am prepared to send out 3.5in 1.4M disks
  168.   for MS-DOS. If you're really desperate I can supply just any other medium
  169.   that PC's, Amigas, Atari-ST's, Mac's or DEC computers have ever used, but
  170.   I'm very short of time so strange requests may take a while to service.
  171.  
  172. Other machines.
  173.  
  174. - An ex-student of mine is going to try and build RDP for an Amiga. IMHO
  175.   anybody with an ANSI C compiler should have almost no problems building
  176.   from the standard kit. On the other hand K&R compiler users may suffer.
  177.  
  178. Installation.
  179.  
  180. 1 Unpack the distribution kit into a single directory. You should have the
  181.   following files:
  182.  
  183.   crash.c      fatal error handling
  184.   crash.h
  185.   makefile     build instructions
  186.   pascal.bnf   EBNF description of Pascal. Use -F to overcome dangling else
  187.   pascal.prj   Borland C 3.1 project file for machine generated pascal
  188.   rdp.bnf      decorated version of rdp grammar given above
  189.   rdp.c        hand written rdp parser
  190.   rdp.doc      this file
  191.   rdp.exe      MS-DOS executable
  192.   rdp.h
  193.   rdp.prj      Borland C 3.1 project file for hand written RDP
  194.   rdp_aux.c    RDP auxilliary functions
  195.   rdp_aux.h
  196.   rdp_gen.prj  Borland C 3.1 project file for machine generated RDP
  197.   scan.c       the scanner
  198.   scan.h
  199.   set.c        set handling routines
  200.   set.h
  201.   symbol.c     the hash coded symbol table
  202.   symbol.h
  203.   toy.bnf      decorated grammar for a TOY language interpreter
  204.   toy.prj      Borland C 3.1 project file for machine generated TOY
  205.  
  206. 2 The makefile can be used on Unix or on a PC. You should edit the makefile
  207.   to specify the name of your C compiler by changing the first line. Simply
  208.   issuing the command 'make' will build and do an installation test.
  209.  
  210.   In detail, rdp.c and its friends are compiled into the executable rdp(.exe)
  211.   which is the hand coded parser generator. This executable is then run on
  212.   rdp.bnf to produce rdp_gen.c which is the machine generated analogue of
  213.   rdp.c.
  214.  
  215.   rdp_gen(.exe) is then run on rdp.bnf to produce rdp_gen2.c which should
  216.   be the same as rdp_gen.c except for the program title and header file name.
  217.   This is confirmed by running a diff (or fc on MS-DOS) on them. You should
  218.   see something like the following. If other differences appear then
  219.   something is broken and I would appreciate being told.
  220.  
  221. 3 Assuming all has gone well, try 'make toy'. This will run toy.bnf through
  222.   rdp(.exe) and then compile the resulting interpreter. Toy is a small
  223.   language with many of the worst features of both C and Pascal. It is
  224.   closely based on Wirth's PL0 as described in A+D=P but has C-style
  225.   declarations and a Pascal write(ln) statement. Toy.bnf contains all the
  226.   necessary interpreter semantics, although some dirty tricks have been used
  227.   in the implementation of if and while statements. I have deliberately not
  228.   implemented an else clause to postpone  discussion of dangling-else
  229.   problems until after the student has successfully built their first
  230.   language processor.
  231.  
  232. 4 There is a toy test programme in the file test.toy. Try typing 'toy' to
  233.   see the help message and then 'toy test' to interpret the test programme.
  234.   'toy -l test' effectively provides a trace of interpretation by turning
  235.   on the scanner line echoing.
  236.  
  237. 5 You might like to try 'make clean' which deletes all object files along
  238.   with the machine generated rdp sources used produced during the
  239.   installation.
  240.  
  241. Enhancements for the next version
  242.  
  243. - RDP parsers have large numbers of constant first and follow sets embedded
  244.   in them. For some applications, especially assemblers, many of these sets
  245.   are identical. In version 2 identical sets will be collapsed. This is only
  246.   likely to save a few kilobytes in even the most pathological parser.
  247.  
  248. - Macro handling code will be incorporated directly into the scanner. At the
  249.   moment I do macros within my assemblers (which I'm not releasing for
  250.   public consumption just yet).
  251.  
  252. Comments, queries and requests for code to
  253.  
  254. Dr Adrian Johnstone, CS Dept, Royal Holloway, University of London
  255. Email: adrian@dcs.rhbnc.ac.uk
  256.  
  257.