home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / lang / ada / 3325 < prev    next >
Encoding:
Internet Message Format  |  1992-11-20  |  2.3 KB
  1. Path: sparky!uunet!haven.umd.edu!mimsy!alex
  2. From: alex@cs.umd.edu (Alex Blakemore)
  3. Newsgroups: comp.lang.ada
  4. Subject: Re: GNU-NYU Ada project
  5. Message-ID: <62223@mimsy.umd.edu>
  6. Date: 20 Nov 92 22:55:41 GMT
  7. References: <1992Nov19.184504.22639@coe.montana.edu>
  8. Sender: news@mimsy.umd.edu
  9. Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
  10. Lines: 40
  11.  
  12. dpoole@hydrogen.oscs.montana.edu (David Poole) writes:
  13. [report about NYU GNU Ada Project]
  14. > the parser uses recursive descent.  Why?  I thought LALR was the best possible.
  15.  
  16. Thoretical answer at the end but in short in choosing between a LALR(1) and
  17. recursive descent approach to a parser - there are tradeoffs on both sides.
  18.  
  19. LALR(1)
  20.   + appropriate for a wide class of languages
  21.   + usually constructed automatically from a grammar
  22.   + easy to handle synthesized attributes
  23.   - harder to handle inherited attributes
  24.   - difficult to get good error messages and recovery
  25.  
  26. recursive descent (works for LL(1))
  27.   + often faster (though parsing is not usually the compilation bottleneck)
  28.   + easier to get good error messages and recover from syntax errors gracefully
  29.   + easy to handle inherited attributes
  30.   - harder to handle synthesized attributes
  31.   - usually requires construction by hand
  32.   - some grammars are not LL(1) but are LALR(1)
  33.  
  34. So we should be happy that the NYU GNAT team (really Robert Dewar in this case I think)
  35. were willing to put in the effort to build a parser by hand so GNU Ada
  36. would be faster and have very good error messages/recovery.
  37.  
  38. The class of language accepted is not as critical as one would think because
  39. all practical compilers parse a language that includes strings (programs)  
  40. that are not in the source language and then prune illegal programs via
  41. semantic checks (conceptually after parsing phase).
  42.  
  43. LALR(1) is a very popular class of grammar because it includes a large class
  44. of languages and there are efficient techniques/tools for automatically constructing
  45. parsers for LALR(1) grammars.  It is not the _best possible_ assuming you mean
  46. can parse the largest class of grammars.  I believe there exist languages for which
  47. there exist LR(1) grammars but not LALR(1) grammars for example.  Recursive descent
  48. works for the class LL(1) which is smaller than LALR(1).
  49. -- 
  50. ---------------------------------------------------
  51. Alex Blakemore alex@cs.umd.edu   NeXT mail accepted
  52.