home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / compiler / 1543 < prev    next >
Encoding:
Internet Message Format  |  1992-09-12  |  2.6 KB
  1. Path: sparky!uunet!cis.ohio-state.edu!zaphod.mps.ohio-state.edu!uwm.edu!ogicse!das-news.harvard.edu!spdcc!iecc!compilers-sender
  2. From: ipser@solomon.technet.sg (Ed Ipser)
  3. Newsgroups: comp.compilers
  4. Subject: Re: Backtracking yacc
  5. Keywords: yacc, parse, LR(1)
  6. Message-ID: <92-09-062@comp.compilers>
  7. Date: 11 Sep 92 07:36:32 GMT
  8. Article-I.D.: comp.92-09-062
  9. References: <92-09-059@comp.compilers>
  10. Sender: compilers-sender@iecc.cambridge.ma.us
  11. Reply-To: ipser@solomon.technet.sg (Ed Ipser)
  12. Organization: TECHNET, Singapore
  13. Lines: 36
  14. Approved: compilers@iecc.cambridge.ma.us
  15.  
  16. The moderator comments:
  17. >[That might help for conflicts in an unambiguous grammar that needs more than
  18. >one token lookahead, but not for the more common case that a conflict is due
  19. >to a truly ambiguous grammar.  Besides, isn't there a theorem that says that
  20. >any LR(k) grammar can be rewritten as LR(1)? -John]
  21.  
  22. Such theorems are rarely of practical value; in practice you will find
  23. that rewriting an LR(k) grammar to be LR(1) (or whatever) will involve
  24. contorting the original syntax in ways that are perverse. While such a
  25. contortion might be acceptable for parsing alone, attempting to add simple
  26. semantic actions or, worse, trying to maintain the grammar for an evolving
  27. language can lead to premature greying. The Roskind C++ grammar is a
  28. notorious example.
  29.  
  30. As for backtracking, there are additional problems: again, what about
  31. semantic processing? If you are merely parsing or constructing a parse
  32. tree, you can get away with throwing away an incorrect guess. But as soon
  33. as you introduce side effects of even the simplest nature, you are left
  34. with the task of figuring out how to undo actions associated with the
  35. wrong guess. Even for a language as simle as Ansi C, you must perform
  36. certain semantic actions just to parse and C++ is even worse.
  37.  
  38. A far better approach is to have available a set of tools which allow the
  39. disambiguation at the point where it is first encountered. LADE, for
  40. example, allows context-sensitive tests to be performed. These can be used
  41. to either a) test arbitrary semantic information to decide on a path to
  42. take, or b) parse ahead in parse-only mode to find some disambiguating
  43. symbol, then return and resume normal, action-associated, parsing. While b
  44. approaches a back-tracking capability, it is not, in fact, backtracking
  45. since it returns to the originating point regardless of what symbols were
  46. found in the scan- ahead.
  47.  
  48. (For information on LADE please contact xorian@solomon.technet.sg)
  49. -- 
  50. Send compilers articles to compilers@iecc.cambridge.ma.us or
  51. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  52.