home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / compiler / 1438 < prev    next >
Encoding:
Internet Message Format  |  1992-08-22  |  2.7 KB
  1. Path: sparky!uunet!ogicse!das-news.harvard.edu!spdcc!iecc!compilers-sender
  2. From: bburshte@pyrps5.eng.pyramid.com (Boris Burshteyn)
  3. Newsgroups: comp.compilers
  4. Subject: Full LR(1) Parser Generator
  5. Keywords: LR(1), comment
  6. Message-ID: <92-08-138@comp.compilers>
  7. Date: 21 Aug 92 22:13:11 GMT
  8. Article-I.D.: comp.92-08-138
  9. Sender: compilers-sender@iecc.cambridge.ma.us
  10. Reply-To: bburshte@pyrps5.eng.pyramid.com (Boris Burshteyn)
  11. Organization: Compilers Central
  12. Lines: 45
  13. Approved: compilers@iecc.cambridge.ma.us
  14.  
  15. USSA (Universal Syntax and Semantics Analyzer) is a minimal state full LR1
  16. parser generator. It uses an optimized version of David Spector's
  17. algorithm published in SIGPLAN NOTICES, V.23 N. 12 1988 ("Efficient Full
  18. LR(1) Parser Generation").
  19.  
  20. USSA is written in C++ and produces tables in the form of C++ objects.
  21. The skeleton parser is also written in C++. USSA has some additional
  22. features such as several grammars in a single source (converted to several
  23. C++ parser objects which can be executed from a single program), multiple
  24. grammar inheritance, regular expressions, real time parsing, generator
  25. (which automatically generates sample sentences of the defined language),
  26. run-time communication between compilers for different grammars, default
  27. lexer... YACC grammar definitions may be easily converted to USSA format.
  28.  
  29. USSA is already a production quality parser generator and is intensively
  30. used in one of Pyramid Technology Corporation's development projects. We
  31. intend to optimize it to run faster and to produce smaller tables.  The
  32. following is a comparison between USSA and YACC on Pyramid S-series
  33. machines (MIPS R3000, UNIX SVR4).
  34.  
  35. In most cases USSA has better or comparable with YACC tables.  Note, that
  36. space is measured in the number of elements.  However, YACC generates
  37. tables from int(s) (on PYRAMID), but USSA - from short(s).  
  38.  
  39. Time is min from several runs of YACC and USSA by UNIX time command.  
  40.  
  41. grammar         yacc      ussa             yacc     ussa
  42.         space     space            time     time
  43. -------         ----      ----             ----     ----
  44.  
  45. ansic           3661      2674             3.0      0.7
  46. ussa(incomplete)2381      1945             0.9      0.6
  47. dBase4          8939      5890             14.8     3.2
  48. f77             4597      4650             3.0      1.3
  49. lex             373       281              1.0      0.0
  50. yacc            563       278              0.0      0.0
  51. pascal          1957      2160             0.9      0.4
  52. prolog          877       784              0.2      0.1
  53.  
  54.  
  55. Sincerely, Boris Burshteyn (bburshte@pyramid.com).
  56. [So can we get a copy?  Sounds great. -John]
  57. -- 
  58. Send compilers articles to compilers@iecc.cambridge.ma.us or
  59. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  60.