home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / lang / ada / 3346 < prev    next >
Encoding:
Internet Message Format  |  1992-11-24  |  3.6 KB
  1. Path: sparky!uunet!elroy.jpl.nasa.gov!ames!network.ucsd.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: <61990007@acf3.NYU.EDU>
  6. Date: 24 Nov 92 04:03: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: 66
  11. Nntp-Posting-Host: acf3.nyu.edu
  12.  
  13. A few comments on the GNAT progress report.
  14.  
  15. The figure of 1,000,000 lines per minute on a 16 Mhz PC is correct. It
  16. is the the performance of a syntax checker, i.e. the program does not
  17. build a parse tree, but does diagnose syntax errors (and recovers from
  18. them). This performance is due to several ingredients: 
  19.  
  20. a) the program is written in assembly language, with global register 
  21. assignments that code  generators are not able to duplicate. 
  22.  
  23. b) The program to be parsed is fully in  memory, so the lexical scanner 
  24. does not have to check for, nor perform, any I/O. 
  25.  
  26. c) The parser is not table driven.
  27.  
  28. A parser that builds a syntax tree will have a more modest performance
  29. ( currently our Ada-written parser is processing about 20,000
  30. lines/min). At this speed, the bulk of the compilation time is still spent 
  31. on code generation. 
  32.  
  33. The parser is a top-down parser with backtracking. Robert Dewar chose
  34. this model first out of a personal preference, and second in  order to
  35. compare its performance with that of an excellent LALR parser generator,
  36. built by Philippe Charles, and which does substantial table compression
  37. and has excellent error recovery. The top-down parser turns out to be
  38. faster by more than an order of magnitude (even after the relative
  39. speed of the lexical scanner is taken into account) and the error
  40. recovery is of comparable quality (i.e. no cascaded errors, and almost
  41. no spurious errors on the whole ACVC suite).
  42.  
  43. Why are top-down parsers considered inferior? This is probably a result
  44. of the negative remarks made about them by  Aho, Ullman and Sethi, who
  45. are (understandably) very fond of the admitedly elegant algorithms
  46. involved in LALR parsing. It is also due to the fact that top-down
  47. parsers require a closer understanding of the grammar of the language
  48. being parsed (not such a strange requirement if you want to write a
  49. compiler!) while table-driven parsers can be produced mechanically with
  50. a minimum of effort. Hand-written parsers clearly require greater craft.
  51. The Dragon book also shows that in some cases  a TD parser will not even
  52. recognize the language you thought you were parsing, but this pathology 
  53. is of purely theoretical import, and does not apply to existing
  54. programming languages, to the best of my knowledge (and everyone's
  55. experience).
  56.  
  57. It is also not the case that LALR parsers can now be
  58. equipped with obviously superior error recovery: a top-down parser has a 
  59. better idea of the state of the parse, and can find more easily a
  60. resynchronization point. This is certainly our experience. 
  61.  
  62. Finally, for a language such as Ada, with a relatively high density of
  63. keywords, the parse is most of the time deterministic (i.e. requires no
  64. backtracking, or a minimal look-ahead), and a only a handful of instructions 
  65. are performed per token. The recognizing automaton can often be coded
  66. with gotos (a natural programming technique for FSA) with obvious
  67. performance gains. 
  68.  
  69. During language design, when the grammar changes rapidly, parser
  70. generators are of course indispensable. Once the grammar is frozen,
  71. a top-down parser is a reasonable choice. The difficult part is not
  72. parsing anyway, it's code generation and optimization!
  73.  
  74. Ed Schonberg
  75. GNAT project
  76. New York University
  77.  
  78. schonberg@nyu.edu
  79.