home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / lang / ada / 3334 < prev    next >
Encoding:
Internet Message Format  |  1992-11-22  |  2.3 KB
  1. Path: sparky!uunet!cis.ohio-state.edu!rutgers!cmcl2!acf3!schonber
  2. From: schonber@acf3.NYU.EDU (Ed Schonberg)
  3. Newsgroups: comp.lang.ada
  4. Subject: Re: GNU-NYU Ada project
  5. Message-ID: <61990006@acf3.NYU.EDU>
  6. Date: 23 Nov 92 01:22:00 GMT
  7. References: <1992Nov19.184504.22639@coe.montana.edu>
  8. Sender: notes@cmcl2.nyu.edu (Notes Person)
  9. Organization: New York University
  10. Lines: 39
  11. Nntp-Posting-Host: acf3.nyu.edu
  12.  
  13. A few words of explanation about the figures in the GNAT progress
  14. report.
  15.  
  16. The quoted performance (1,000,000 lines/min on a 16 mhz PC) is correct,
  17. but it is the performance of a syntax checker, not a parser, i.e. the
  18. recognizer does not build a parse tree. Apart from the parsing algorithm
  19. (more of that below) what is critical to this performance is the coding
  20. of the lexical scanner. It seems clear that this performance is not
  21. achievable with a table-driven system.
  22.  
  23. Robert Dewar wrote the syntax checker precisely to compare the
  24. performance of a top-down parser with  that of an LALR parser (in this
  25. case, a highly optimized system written by Philippe Charles, with table
  26. compression, and very effective error recovery). In addition to the
  27. more than order-of-magnitude performance gain, the top-down parser is
  28. much smaller (i.e. the total code is smaller than the LALR tables),
  29. and its error recovery of comparable quality.
  30.  
  31. So why do people insist on the superiority of LALR methods? For one,
  32. because tools allow anyone to produce working parsers with relatively
  33. little effort. For another, because the Aho-Ullman text has been touting
  34. the advantages of LALR for a decade, mostly out of fondness for what are
  35. obviously very elegant algorithms. It is also said that error recovery
  36. methods are easier to build into LALR parsers, but this is obviously not
  37. the case: when parsing top-down you have a much better idea of what you
  38. are looking for, and it is easier to resynchronize. Finally, in the case
  39. of a language such as Ada, with a high density of keywords, it is very 
  40. easy to write a top-down parser, and the actions per token are few,
  41. which explains the overall performance. 
  42.  
  43. Of course, writing a top-down parser by hand still requires reasonable
  44. skill and a close examination of the grammar of the language. but it
  45. nowhere as fraught with peril as the Dragon book makes it sound.
  46.  
  47. Ed Schonberg
  48. GNAT project
  49. New York University
  50.  
  51. schonberg@nyu.edu  
  52.