home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / compiler / 1544 < prev    next >
Encoding:
Text File  |  1992-09-12  |  2.5 KB  |  52 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!world!iecc!compilers-sender
  3. From: Gary Merrill <sasghm@unx.sas.com>
  4. Subject: Re: Backtracking yacc
  5. Reply-To: Gary Merrill <sasghm@unx.sas.com>
  6. Organization: Compilers Central
  7. Date: Fri, 11 Sep 1992 12:30:46 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <92-09-063@comp.compilers>
  10. References: <92-09-059@comp.compilers>
  11. Keywords: yacc, C++, parse
  12. Sender: compilers-sender@iecc.cambridge.ma.us
  13. Lines: 37
  14.  
  15. > Has anybody seen such a thing as backtracking yacc?  What I had in mind
  16. > was a LALR parser that resolves ambiquity by backtracking to the point
  17. > where it had multiple routes to go.  It would parse the input until it
  18. > encounters a dead end, and after that it would try an alternative path.
  19. > 
  20. > I know this would not solve much.  Resolving the the conflicts 'the wrong
  21. > way' can still result to an errorless parsing, but I would like to know if
  22. > there have been any study about this approach.  Is this a completely dead
  23. > idea ?
  24.  
  25. Our C++ parser uses a yacc-generated parser that is recursively callable
  26. in order to resolve the ambiguities in C++.  I have modified a version of
  27. Berkeley yacc in several (not very complicated) ways to support this
  28. approach.  The underlying yacc parser will of course not correctly parse a
  29. non-LR(k) grammar by itself, but given the added features and using a
  30. technique of "trial parsing" (such as that hinted at in the above
  31. posting), it is possible to parse the desired ambiguities -- and more
  32. generally, it is possible to parse non-LR(k) grammars.  A paper describing
  33. the implementation of the changes to yacc, the technique of trial parsing,
  34. the role of the lexical analyzer, techniques required in constructing the
  35. yacc grammar, and examples of parsing ambiguities in C++ has been
  36. submitted to a journal.  I suppose I could make draft copies of this
  37. available on an individual basis to those interested.
  38.  
  39. Having done all this, I am still rather uncertain as to its value.  (The
  40. paper explains briefly why I went this route, and the reasons pertained
  41. largely to practical concerns, scheduling, etc. rather than to technical
  42. issues.)  The approach certainly seems to work.  It is quite powerful.
  43. But I think if I had it to do over again I would use a recursive descent
  44. parser.
  45. ---
  46. Gary H. Merrill  [Principal Systems Developer, C Compiler Development]
  47. SAS Institute Inc. / SAS Campus Dr. / Cary, NC  27513 / (919) 677-8000
  48. sasghm@theseus.unx.sas.com ... !mcnc!sas!sasghm
  49. -- 
  50. Send compilers articles to compilers@iecc.cambridge.ma.us or
  51. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  52.