home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / lang / ada / 3332 < prev    next >
Encoding:
Internet Message Format  |  1992-11-22  |  2.8 KB
  1. Path: sparky!uunet!munnari.oz.au!yoyo.aarnet.edu.au!news.adelaide.edu.au!cs.adelaide.edu.au!andrewd
  2. From: andrewd@cs.adelaide.edu.au (Andrew Dunstan)
  3. Newsgroups: comp.lang.ada
  4. Subject: Re: GNU-NYU Ada project
  5. Date: 23 Nov 1992 00:12:21 GMT
  6. Organization: The University of Adelaide
  7. Lines: 40
  8. Distribution: world
  9. Message-ID: <1ep7l5INN3kb@huon.itd.adelaide.edu.au>
  10. References: <1992Nov19.184504.22639@coe.montana.edu> <62223@mimsy.umd.edu>
  11. NNTP-Posting-Host: achilles.cs.adelaide.edu.au
  12.  
  13. In article <62223@mimsy.umd.edu>, alex@cs.umd.edu (Alex Blakemore) writes:
  14. |> dpoole@hydrogen.oscs.montana.edu (David Poole) writes:
  15. |> [report about NYU GNU Ada Project]
  16. |> > the parser uses recursive descent.
  17. |>
  18.  
  19. I should be very interested to see the parsing grammar being used. I was under the 
  20. impression that Ada was difficult to do using LL(k) methods. Since I like both
  21. Ada and LL parsing, I am glad to see that the two are getting married :-)
  22.  
  23.  
  24. |> [discussion of relative merits of LL(1) and LALR(1) parsing]
  25. ...
  26. |> 
  27. |> LALR(1) is a very popular class of grammar because it includes a large class
  28. |> of languages and there are efficient techniques/tools for automatically constructing
  29. |> parsers for LALR(1) grammars.  It is not the _best possible_ assuming you mean
  30. |> can parse the largest class of grammars.  I believe there exist languages for which
  31. |> there exist LR(1) grammars but not LALR(1) grammars for example.  Recursive descent
  32. |> works for the class LL(1) which is smaller than LALR(1).
  33.  
  34. This is not quite correct. (This discussion really belongs in comp.compilers.)
  35. The class LL(1) is smaller than the class LALR(1). In fact, the class LL(k) is 
  36. smaller than the class LALR(1) for any k. However. the class LALR(1) = LR(1). This
  37. class actually also includes SLR(1). This class can be shown to be the class of all
  38. determinstically parseable languages. In fact, you can produce an SLR(1) or LALR(1)
  39. grammar which not only derives the same language as any LR(k) grammar, but the parser 
  40. for which emits the same set of parse traces as a parser built from the original grammar.
  41. In effect, this means that it builds an equivalent parse tree. If the language is prefix-free,
  42. you can even build an LR(0) covering grammar for it. The reason for not doing this is 
  43. not that it can't be done, but that it is simply not worth the trouble, normally.
  44.  
  45. -- 
  46. #######################################################################
  47. #  Andrew Dunstan                   #   There's nothing good or bad   #
  48. #  Department of Computer Science   #   but thinking makes it so.     #
  49. #  University of Adelaide           #                                 #
  50. #  South Australia                  #          - Shakespeare          #
  51. #  net: andrewd@cs.adelaide.edu.au  #                                 #
  52. #######################################################################
  53.