home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / compiler / 2244 < prev    next >
Encoding:
Internet Message Format  |  1993-01-25  |  1.9 KB
  1. Path: sparky!uunet!spool.mu.edu!uwm.edu!ogicse!decwrl!world!iecc!compilers-sender
  2. From: tchannon@black.demon.co.uk (Tim Channon)
  3. Newsgroups: comp.compilers
  4. Subject: Re: Recursive descent parsing is better than LL(1)
  5. Keywords: LL(1), parse
  6. Message-ID: <93-01-172@comp.compilers>
  7. Date: 23 Jan 93 22:43:00 GMT
  8. Article-I.D.: comp.93-01-172
  9. References: <93-01-122@comp.compilers> <93-01-160@comp.compilers>
  10. Sender: compilers-sender@iecc.cambridge.ma.us
  11. Reply-To: tchannon@black.demon.co.uk (Tim Channon)
  12. Organization: Compilers Central
  13. Lines: 61
  14. Approved: compilers@iecc.cambridge.ma.us
  15.  
  16. > I present a simple contra-example:
  17. > 
  18. > Consider the language defined by the next CFG:
  19. > 
  20. > S -> A
  21. > S -> B
  22. > A -> `x' A `y'
  23. > A -> `a'
  24. > B -> `x' B `z'
  25. > B -> `b'
  26. > 
  27. > SID uses elimination of left recursion, factorisation and substitution to
  28. > search for a better grammar.
  29.  
  30. I assume it is a matter of what you ask SID and by the time you are at S
  31. it is too late to branch or is it.
  32.  
  33. Is this a valid LL(1) solution? (diagnostics are too large to post but all
  34.                 is well)
  35.  
  36. S    =  'x' {   'x'
  37.               | 'a'
  38.               | 'b'
  39.             }
  40.             ('y' | 'z')
  41.       | 'a'
  42.       | 'b'.
  43.       
  44. producing this exact output
  45.  
  46.     IF (sym = XSym) THEN
  47.       Get;
  48.       WHILE (sym = XSym) OR
  49.             (sym = ASym) OR
  50.             (sym = BSym) DO
  51.         IF (sym = XSym) THEN
  52.           Get;
  53.         ELSIF (sym = ASym) THEN
  54.           Get;
  55.         ELSE
  56.           Get;
  57.         END;
  58.       END;
  59.       IF (sym = YSym) THEN
  60.         Get;
  61.       ELSIF (sym = ZSym) THEN
  62.         Get;
  63.       ELSE Error(11);
  64.       END;
  65.     ELSIF (sym = ASym) THEN
  66.       Get;
  67.     ELSIF (sym = BSym) THEN
  68.       Get;
  69.     ELSE Error(12);
  70.     END;
  71.  
  72.   TC. 
  73.     E-mail: tchannon@black.demon.co.uk or tchannon@cix.compulink.co.uk
  74. -- 
  75. Send compilers articles to compilers@iecc.cambridge.ma.us or
  76. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  77.