home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / compiler / 1541 < prev    next >
Encoding:
Internet Message Format  |  1992-09-12  |  3.2 KB
  1. Path: sparky!uunet!cis.ohio-state.edu!zaphod.mps.ohio-state.edu!rpi!uwm.edu!ogicse!das-news.harvard.edu!spdcc!iecc!compilers-sender
  2. From: mickunas@m.cs.uiuc.edu (Dennis Mickunas)
  3. Newsgroups: comp.compilers
  4. Subject: Re: Parsing wars
  5. Keywords: parse, LR(1), bibliography
  6. Message-ID: <92-09-060@comp.compilers>
  7. Date: 10 Sep 92 20:40:14 GMT
  8. Article-I.D.: comp.92-09-060
  9. References: <92-09-006@comp.compilers> <92-09-051@comp.compilers>
  10. Sender: compilers-sender@iecc.cambridge.ma.us
  11. Reply-To: mickunas@m.cs.uiuc.edu (Dennis Mickunas)
  12. Organization: University of Illinois, Dept. of Comp. Sci., Urbana, IL
  13. Lines: 57
  14. Approved: compilers@iecc.cambridge.ma.us
  15.  
  16. dww@inf.fu-berlin.de writes:
  17.  
  18. >jar@cheops.HQ.Ileaf.COM (Jim Roskind x5570) writes [about "strange parsing"]
  19.  
  20. >>The conseqeunces of this extension are quite significant, and the
  21. >>resulting parser engine provides a much larger class of parsers than LR
  22. >>parsers.  ...
  23.  
  24. >Oh yes, with backing up it seems you could parse a lot more languages
  25. >like a^n b^n c^n ...
  26.  
  27. You can't quite get a^n b^n c^n with the straightforward 2-stack technique
  28. that is suggested here.  It *is* possible to get a proper subset of the
  29. non-deterministic cfl's.  For example, it is quite easy to obtain {a^n
  30. b^n} U {a^n b^2n c}.  Non-canonical techniques for parsing such languages
  31. have been around for some time.  Virtually all of them can be cast in the
  32. form of a two-stack parser.  These non-canonical techniques include
  33. Colmerauer's total precedence method [1], Williams' Bounded-Context
  34. Parsable (BCP) method [2], Culik & Cohen's LR-Regular method [3],
  35. Szymanski's LR(k,infinity) and Finite Phrase Finding Automaton Parsable
  36. (FPFAP(k)) methods [4], Fischer's Synchronous Parsing Machines (SPM)
  37. method [5], Tai's Noncanonical SLR (NSLR) and Leftmost Noncanonical SLR
  38. (LSLR) methods [6], and finally, Schell's Generalized Piecewise LR (GPLR)
  39. method [7].  In particular, Tai's TOPLAS paper provides a very readable
  40. presentation of the technique.
  41.  
  42. [1] Colmerauer, A., "Total precedence relations," _JACM 17_, 1 (1970).
  43.  
  44. [2] Williams, J. H., "Bounded context parsable grammars," _Information
  45.     Control_, 28 (1975).
  46.  
  47. [3] Culik, K. and R. Cohen, "LR - regular grammars - an extension of
  48.     LR(k) grammars," _JCSS 7_, 1 (1973).
  49.  
  50. [4] Szymanski, T. G., "Generalized bottom-up parsing," PhD Thesis,
  51.     Computer Science Department, Cornell University, Technical
  52.     Report TR 73-168, Ithaca, New York (1973).
  53.  
  54. [5] Fischer, C. N., "On parsing context-free languages in a parallel
  55.     environment," PhD Thesis, Computer Science Department, Cornell
  56.     Universiy, echnical Report TR 75-237, Ithaca, New York (1975).
  57.  
  58. [6] Tai, K. C., "Noncanonical SLR(1) grammars," _TOPLAS 1_, 2 (1979).
  59.  
  60. [7] Schell, R. M., "Methods for constructing parallel compilers for use
  61.     in a multiprocessor environment," PhD Thesis, Department of
  62.     Computer Science, University of Illinois at Urbana-Champaign,
  63.     Technical Report UIUCDCS-79-958, Urbana, Illinois (1979).
  64.  
  65. -- 
  66.  
  67. M. Dennis Mickunas                     
  68. Department of Computer Science          1304 W. Springfield Ave.
  69. University of Illinois             Urbana, Illinois 61801
  70. -- 
  71. Send compilers articles to compilers@iecc.cambridge.ma.us or
  72. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  73.