home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / compiler / 1479 < prev    next >
Encoding:
Internet Message Format  |  1992-08-30  |  4.1 KB
  1. Path: sparky!uunet!centerline!noc.near.net!news.Brown.EDU!qt.cs.utexas.edu!cs.utexas.edu!sun-barr!ames!agate!stanford.edu!rutgers!faatcrl!iecc!compilers-sender
  2. From: eifrig@beanworld.cs.jhu.edu (Jonathan Eifrig)
  3. Newsgroups: comp.compilers
  4. Subject: LR(0) vs. LALR, and the Great Parsing War
  5. Keywords: parse, bibliography
  6. Message-ID: <92-08-179@comp.compilers>
  7. Date: 30 Aug 92 02:40:50 GMT
  8. Sender: compilers-sender@iecc.cambridge.ma.us
  9. Reply-To: eifrig@beanworld.cs.jhu.edu (Jonathan Eifrig)
  10. Organization: Johns Hopkins Computer Science Department, Baltimore, MD
  11. Lines: 78
  12. Approved: compilers@iecc.cambridge.ma.us
  13.  
  14.  
  15.     It being near the start of the new school year and all, it seems
  16. appropriate to start the (N+1)th Annual Comp.Compilers Parsing Argument.
  17. Let's see if we can finish it up before Thanksgiving this year!  :-)
  18.  
  19.     Seriously, I came across a _hint_ of a surprising result that I
  20. was hoping someone could either confirm or refute:
  21.  
  22.     In a paper in this year's ACM SIGPLAN Workshop on ML and its
  23. Applications, Pettersson and Fritzson [1] claim that using Tomita's
  24. pseudo-parallel LR(0) parsing scheme [2] "in practice" only takes about
  25. 10% longer than using an SLR or LALR parser.  They reference a result by
  26. Lankhorst [3] as justification for this claim, which I simply _cannot_ get
  27. my hands on.  (Read the reference; you'll understand my difficulty.)
  28.  
  29.     This seems quite surprising to me, given that Tomita's algorithm
  30. basically has to spin off on the fly new parsing automatons to follow each
  31. possible path in a derivation.  Now, while I can see that this might be
  32. true if you're implementing in a language with a nice GC-ed heap like
  33. Lisp, it's not so clear if you have to keep cloning stacks all the time.
  34.  
  35.     Can someone who's read the paper post or mail me some sort of
  36. synopsis?
  37.  
  38. ObRefs:
  39.  
  40. @string{mlwork92 = "Proceedings of the 1992 ACM SIGPLAN Workshop on ML and
  41.     Its Applications"}
  42. @string{ijcai85 = "Proceedings of the 1985 International Joint Conference
  43.     on Artificial Intelligence"}
  44.  
  45. @inproceedings{pettersson92,
  46. author = "Mikael Pettersson and Peter Fritzon",
  47. title = "A General and Practical Approach to Concrete Syntax Objects
  48.     within ML",
  49. booktitle = mlwork92,
  50. year = 1992,
  51. pages = "17--27",
  52. abstract = "In this paper we present an approach to concrete syntax
  53. objects within ML, which is both general and efficiently implementable.
  54. These language enhancements add BNF rules for abstract syntax declarations
  55. and ``{\em semantic brackets}'' with inline concrete syntax and pattern
  56. matching for readability and conciseness.  This approach has several
  57. improvements integrated together which either do not appear in previous
  58. works, or appear in forms which are very restrictive or have very
  59. inefficient implementations.  Our improvements are: (1) inline concrete
  60. syntax within ``semantic brackets'' has been integrated bot with the ML
  61. type system and the ML scope rules, (2) concrete syntax can appear both as
  62. {\em syntactic patterns} for pattern matching and as {\em syntactic
  63. expressions} for building objects, (3) patterns can be nested to arbitrary
  64. depth, (4) concrete syntax and ML objects can be mixed; so-called {\em
  65. anti-quotations} are supported directly, (5) patterns and parts of
  66. patterns can be augmented with type information, (6) efficient integration
  67. with a general incremental LR(1) parsing mechanism.
  68.     These extentions have been efficiently implemented within our DML
  69. system.  DML, the Denotational Meta-Language, is a dialect of Standard ML
  70. with extentions aimed at making it (even more) useful for implementing
  71. denotational specifications of programming languages."  }
  72.  
  73. @inproceedings{tomita85,
  74. author = "Masaru Tomita",
  75. title = "An Efficient Context-Free Parsing Algorithm for Natural Languages",
  76. booktitle = ijcai85,
  77. year = 1985
  78. }
  79.  
  80. @inproceedings{lankhorst91,
  81. author = "M. M. Lankhorst",
  82. title = "An Empirical Comparison of Generalized LR Tables",
  83. booktitle = "Proceedings of the Workshop on Tomita's Algorithm - Extensions
  84.     and Applications",
  85. year = 1991
  86. }
  87. --
  88. Jack Eifrig (eifrig@cs.jhu.edu)       The Johns Hopkins University, C.S. Dept.
  89. -- 
  90. Send compilers articles to compilers@iecc.cambridge.ma.us or
  91. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  92.