home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / compiler / 2270 < prev    next >
Encoding:
Text File  |  1993-01-28  |  3.0 KB  |  73 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!scifi!acheron!philabs!linus!think.com!spdcc!iecc!compilers-sender
  3. From: Pete Jinks <pjj@cs.man.ac.uk>
  4. Subject: Re: Recursive descent parsing is better than LL(1)
  5. Reply-To: Pete Jinks <pjj@cs.man.ac.uk>
  6. Organization: Compilers Central
  7. Date: Wed, 27 Jan 1993 17:42:25 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <93-01-204@comp.compilers>
  10. Keywords: LL(1), parse
  11. References: <93-01-122@comp.compilers> <93-01-172@comp.compilers>
  12. Sender: compilers-sender@iecc.cambridge.ma.us
  13. Lines: 58
  14.  
  15. Barton Christopher Massey <bart@cs.uoregon.edu> writes:
  16. >I would like to prove or disprove the following conjectures:
  17. > LL(1) Transformability: There exists an algorithm which, given any grammar G
  18. > which is unambiguous and describes an LL(1) language L(G), produces an LL(1)
  19. > grammar G' for the language L(G).
  20. > LL(1) Decidability: There exists an algorithm which, given any grammar G
  21. > which is unambiguous and describes a language L(G), decides whether L(G) is
  22. > an LL(1) language.
  23. >it seems most likely to me that LL1T is true, but I'm skeptical about LL1D.
  24.  
  25. Bill Purvis <W.Purvis@daresbury.ac.uk> writes:
  26. >... SID... accepts a fairly arbitrary BNF description... produce an LL(1)
  27. >grammar (assuming that the language is LL(1). - the first conjecture.
  28. >...I suspect that in practical terms it probably covers the second conjecture.
  29.  
  30. jan@klikspaan.si.hhs.nl writes:
  31. >I present a simple contra-example:
  32. >    S -> A | B
  33. >    A -> `x' A `y' | `a'
  34. >    B -> `x' B `z' | `b'
  35. >...`SID may also report failure because
  36. >its attempt to transform the grammar causes it to loop.'
  37.  
  38. tchannon@black.demon.co.uk (Tim Channon) writes:
  39. >Is this a valid LL(1) solution? S = 'x' {'x'|'a'|'b'} ('y'|'z') | 'a' | 'b'.
  40.  
  41. Jan's example causes SID problems, so SID may establish LL1T but can't
  42. establish LL1D. I believe this is because his example is not LL(1), but
  43. no-one has said so explicitly so far and I can't find the example in the
  44. Dragon book - is it a well-known example?
  45.  
  46. To shorten the grammars/languages, I am using the following notation:
  47.     x^n means x repeated n times, [ab] or a|b means a or b
  48. Thus Jan's original language is:
  49.     x^n a y^n | x^n b z^n      for n>=0
  50. Tim's version is:
  51.     x [xab]^n [yz] | a | b
  52. which is not the same at all. Maybe he meant:
  53.     x^n [ab] [yz]^m | a | b    for n,m>=1
  54.     i.e. x^n [ab] [yz]^m       for n,m>=0
  55. which is closer but still not right.
  56.  
  57. A slightly simpler example, with (I think) the same characteristics as the
  58. original is:
  59.     x^n y^n | x^n z^n i.e. x^n ( y^n | z^n )     for n>=0
  60. This and Jan's original are LR(1), but I believe that they are not LL(n) for
  61. any finite n, as we have to negotiate an indefinitely long string of x-s
  62. before we can chose whether to accept y-s or z-s, but we also have to have
  63. been counting the x-s (i.e. selecting/stacking the "correct" non-terminal
  64. symbol) to be able to accept the right number of y-s or z-s. By contrast:
  65.     x^n [yz]^n
  66. and:
  67.     x^n (y^m | z^m).
  68. are both LL(1).
  69.  
  70. -- 
  71. Send compilers articles to compilers@iecc.cambridge.ma.us or
  72. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  73.