home *** CD-ROM | disk | FTP | other *** search
/ Oakland CPM Archive / oakcpm.iso / sigm / sigmv039.ark / LL1ANL.DOC < prev    next >
Encoding:
Text File  |  1985-02-10  |  5.9 KB  |  148 lines
  1. *****************************************************************
  2. *             LL(1) Language Analyzer            *
  3. *****************************************************************
  4.  
  5. BY:
  6.     ROBERT M. WHITE
  7.     H & W COMPUTER SYSTEMS, INC.
  8.     P.O. BOX 4173
  9.     BOISE, ID  83704
  10.  
  11. DESCRIPTION:
  12.     Thi≤á systeφá read≤á ßá BN╞á descriptioεá oµá aεáá LL(1⌐ 
  13. language¼á analyze≤á i⌠á fo≥ error≤ anΣ generate≤ thσá selectioε 
  14. set≤ fo≥ thσ productions«á  Variou≤ intermediatσ table≤ arσ als∩ 
  15. generated to allow better debugging of the language.
  16.  
  17. SOURCE LANGUAGE:
  18.     PL/I-8░ distributed by DIGITA╠ RESEARCH¼á PACIFI├ GROVE¼ 
  19. CALIFORNIA.  Release developed under was 1.3.
  20.  
  21. SYSTEM REQUIRED:
  22.     1.  8080/Z80 processor w/60k minimum.
  23.     3.  2 disk drives (I used Double-Density w/600k capacity.)
  24.     2.  CP/═áá Releaseá 1.┤á or  aboveá distributedá byá DIGITA╠ 
  25. RESEARCH, PACIFIC GROVE, CALIFORNIA.
  26.     3.  PL/I-8░ distributed by DIGITA╠ RESEARCH¼á PACIFI├ GROVE¼ 
  27. CALIFORNIA.  Release developed under was 1.3.
  28.  
  29. INSTALLATION:
  30.     1⌐á Adjus⌠ LL1ANL.SU┬ t∩ reflec⌠ thσ prope≥ drivσá whicΦ 
  31.             contains the source.
  32.     2)  Submit the file, LL1ANL.SUB.
  33.  
  34. SYSTEM EXECUTION:
  35.     1⌐á  Pu⌠ thσ BN╞ gramma≥ int∩ ß filσ witΦ thσá extensioε 
  36.              oµ GM╥ (i.e«á EXAMPLE.GMR)«á  Thi≤ filσ i≤ expecteΣ 
  37.              t∩ bσ iε standarΣ sourcσ forma⌠ (i.e«á eacΦ linσ i≤ 
  38.              terminateΣ witΦ ß carriage-return¼ line-feed)«  Thσ 
  39.              format of the BNF must be as follows:
  40.         <grammar> -> <rule> '<eof>'
  41.               ;
  42.         <rule> -> '<ident>' <alt> ';' <rule>
  43.                -> 
  44.                ;
  45.         <alt> -> '->' <rp> <alt>
  46.               ->
  47.               ;
  48.         <rp> -> '<string>' <rp>
  49.              -> '<ident>' <rp>
  50.              ->
  51.              ;
  52.          Aεá identifie≥ i≤ an∙ 1-╕ character≤ surroundeΣá b∙ 
  53.              <...╛á (i.e«áá <grammar>«á  ┴á strinτá i≤á an∙á 1-╕ è             character≤áá surrounΣá b∙áá quote≤áá (i.e«áá '->')«  
  54.              Comment≤á ma∙á bσ addeΣ t∩ thσ enΣ oµ an∙á linσá b∙ 
  55.              merel∙á codinτ ß '$ º anΣ theε thσá comments«á  Thσ 
  56.              analyze≥á als∩á ha≤ certaiε switche≤ whicΦá ma∙á bσ 
  57.              turneΣá oε o≥ ofµ b∙ usinτ thσ '$º followeΣ b∙á thσ 
  58.              switcΦá numbers«áá  Revie≈á program¼áá LL1P10¼á fo≥ 
  59.              further information.
  60.     2⌐á  Sincσá thσ  program≤ use≤ overlays¼á thσá currentl∙ 
  61.              loggeΣá disδ mus⌠ bσ thσ onσ containinτ thσá objec⌠ 
  62.              fo≥ LL1ANL.COM«á  T∩ analyzσ ß grammar¼á ente≥á thσ 
  63.              following:
  64.             LL1ANL grammar_file_name<return>
  65.              For example, the example grammar was analyzed with:
  66.             LL1ANL EXAMPLE<return>
  67.              The file extension of GMR is always assumed.
  68. áááááááá3)   Prin⌠á thσá filσá witΦ thσ extensioε oµá PR╬á (i.e« 
  69. áááááááááááááEXAMPLE.PRN)«  Thi≤ wil∞ prin⌠ thσ selectioε se⌠ a≤ 
  70. áááááááááááááwel∞á a≤ thσ intermediatσ table≤ useΣ t∩á calculatσ 
  71. áááááááááááááthσ selectioε set«  Thσ las⌠ repor⌠ wil∞ onl∙ exis⌠ 
  72. áááááááááááááiµá thσ gramma≥ i≤ no⌠ LL(1⌐ anΣ i⌠á wil∞á indicatσ 
  73. áááááááááááááwhicΦ production≤ causeΣ i⌠ no⌠ t∩ be.
  74.  
  75. FILES DONATED:
  76.     EXAMPLE.GMR - First example grammar
  77.     EXAMPLE2.GMR - Second example grammar
  78.     LL1ANL.DOC - The file that you are reading.
  79.     LL1ANL.PLI - Driver program
  80.     LL1ANL.SUB - Command List to Compile and  Link 
  81.                      the language analysis programs.
  82.     LL1CMN.DCL - Common area for all programs
  83.     LL1LNK.SUB - Command List to Link the language analysis
  84.              programs after re-compiling one of them.
  85.     LL1PRC.DCL - Common Procedures Declarations
  86.     LL1PRC.PLI - Common Procedures generated in LL1ANL
  87.     LL1P10.PLI - Language Parser
  88.     LL1P20.PLI - Language Sort and Print
  89.     LL1P30.PL╔ - Languagσ Analysi≤ - FinΣ Nullablσ 
  90.                      Production≤ anΣ Non-terminals
  91.     LL1P40.PL╔ - Languagσ Analysi≤ - Calculate the 
  92.                      Beginning type relationships
  93.     LL1P50.PL╔ - Languagσ Analysi≤ - Calculate the 
  94.                      Ending type relationships
  95.     LL1P60.PL╔ - Languagσ Analysi≤ - Calculate the 
  96.                      Follow Set Relationship
  97.     LL1P70.PL╔ - Languagσ Analysi≤ - Calculate the 
  98.                      Selection Set for all productions
  99.     LL1P80.PL╔ - Languagσ Analysi≤ - Validate that 
  100.                      the language is LL(1)
  101.  
  102. REFERENCES:
  103.     These programs were written from the outline given in:
  104.         'COMPILER DESIGN THEORY' by P.M. Lewis III,
  105.         D.J. Rosenkrantz and R.E. Stearns, Addison-
  106.         Wesley Publishing Company, 1978.
  107.     If you are going to use this system, it is highly re-
  108.     commended that you get this book.
  109.     Other books referenced:
  110.         1. 'Compiler Design and Construction' by
  111.            Arthur Pyster, Van Nostrand Reinhold Co.,
  112.            1980.
  113.         2. 'Structured System Programming' by Jim
  114.            Welsh & Michael McKeag, Prentice-Hall
  115.            International, Inc., 1980.
  116.         3. 'Algorithms + Data = Programs', by N.
  117.            Wirth, Prentice-Hall International, Inc.,
  118.            1976.
  119.  
  120. FUTURE ENHANCEMENTS:
  121.     The following is list of items that I may or may not get
  122.     around to doing.  They represent enhancements or changes
  123.     for the better (I hope!).
  124.         1.  Add the following to the input language:
  125.             a.  Allow sections of terminals to be sur-
  126.             rounded by parentheses followed by a
  127.             '?' for 0 or 1 repetitions, '*' for 0 or
  128.             more repetitions or '+' for 1 or more
  129.             repetitions.
  130.             b.  Allow lists to be defined as <nt> LIST
  131.             ',' which denotes a list of <nt>'s seperated
  132.             by commas.
  133.         2.  Add a phase which checks for left recursion 
  134.             since this is the most deadly sin.
  135.         3.  Add a phase which given the internal language
  136.             tables and the selection set produces the outline
  137.             of the compiler for all the various rules.
  138.  
  139. NOTICE OF PUBLIC DOMAIN:
  140.     The files herein contained and denoted under my controlè    arσá hereb∙á placeΣ int∩ thσ publiπ domaiεá anΣá ma∙á bσ 
  141.         freely distributed for any non-commercial personal use.
  142.  
  143.  
  144.  
  145.             Robert M. White
  146.             July 15, 1981
  147.  
  148.