home *** CD-ROM | disk | FTP | other *** search
/ ftp.ee.pdx.edu / 2014.02.ftp.ee.pdx.edu.tar / ftp.ee.pdx.edu / pub / users / Harry / compilers / yapp / readme < prev    next >
Text File  |  2003-05-23  |  3KB  |  94 lines
  1. YAPP - Yet Another PCAT Parser
  2. ==============================
  3.  
  4. by Harry Porter (October, 1998)
  5.  
  6. This directory contains an SLR parser generator written in the PCAT language.  
  7. This program takes, as input, a context-free grammar (the "grammar") and a
  8. sample input string (called the "example").  From the grammar, it builds
  9. parsing LR parsing tables using the "SLR" algorithm.  Then it attempts
  10. to find a parsing of the sample input example string.
  11.  
  12. -----
  13.  
  14. There is also a tst directory containing several sample "grammar"s and
  15. "example"s.
  16.  
  17. grammar1:     A syntax for expressions using + * ( ) id
  18. example1:     A small expression
  19.  
  20. grammar2:     A syntax for expressions using AND OR NOT ( ) true false
  21. example2:     A small boolean expression
  22.  
  23. grammar3:     A small ambiguous (therefore, non-LR) grammar
  24. example3:     An example string from this language
  25.  
  26. grammarPCAT:  A grammar for PCAT
  27. examplePCAT1: A small PCAT program
  28. examplePCAT2: A small PCAT program (The quicksort program)
  29.  
  30. -----
  31.  
  32. To run the YAPP program type something like one of these commands:
  33.   go grammar1 example1
  34.   go grammar2 example2
  35.   go grammar3 example3
  36.   go grammarPCAT examplePCAT1
  37.   go grammarPCAT examplePCAT2
  38.  
  39. You should see a trace of the table building process, followed by an
  40. attempt to parse the given input.
  41.  
  42. In particular, you should see the following:
  43.   1.  The grammar rules as they are read in.
  44.   2.  A list of the terminals and the non-terminals in the grammar.
  45.   3.  A repeat of the grammar, augmented with a dummy start rule.
  46.   4.  The FIRST and FOLLOW sets.
  47.   5.  A trace of the SLR table building process.
  48.   6.  A list of all the sets of items (i.e., the canonical collection
  49.       of LR(0) items).
  50.   7.  A formatted display of the table.  (This will only look good
  51.       for very small grammars, since it will be truncated.)
  52.   8.  A parse of the sample "prog" input string using the table,
  53.       with a trace of which actions were taken.  This should end
  54.       by saying either "parse succeeded" or "parse failed".
  55.  
  56. In the case of grammar3, you will see error messages during table
  57. construction as the shift-reduce and reduce-reduce conflicts are
  58. detected.
  59.  
  60. In the case of grammarPCAT, the trace of the table building is fairly long
  61. and the table is fairly large.  The trace of the parse is also long, but
  62. should succeed.
  63.  
  64. The following files are included in this directory:
  65.  
  66. tst
  67.   A directory containing the test grammars and examples, as described
  68.   above.
  69. go
  70.   A script to run the YAPP program, discussed above.
  71. pre.c
  72.   A program to pre-process the grammar and the input string.  PCAT programs
  73.   cannot read character data; only integers and reals, so the input is
  74.   preprocessed to turn all tokens into integers before being sent to
  75.   the main PCAT program.
  76. lexer.h, lexer.c
  77.   Routines used by pre.c to tokenize the input grammar and the input string.
  78.   Lexer.c may not be present since it is assigned as a programming
  79.   project in CS-301.
  80. post.c
  81.   PCAT programs have limited capability to output newlines, so the
  82.   YAPP program writes a "$" instead of newline.  This program translates
  83.   all "$"s into newlines.
  84. yapp.pcat
  85.   The SLR parser generator and the LR parsing algorithm.  2109 lines of
  86.   PCAT code.
  87. pcat
  88.   An executable version of the PCAT-to-SPARC compiler (C Version).
  89. pc
  90.   A shell script to run the PCAT compiler and follow it with the assembly
  91.   stage, producing a ".o" file.
  92. makefile
  93.   A Makefile to compile the programs: pre.c, yapp.pcat, and post.c.
  94.