home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / compiler / 1540 < prev    next >
Encoding:
Internet Message Format  |  1992-09-10  |  1.4 KB
  1. Path: sparky!uunet!europa.asd.contel.com!darwin.sura.net!udel!gvls1!faatcrl!iecc!compilers-sender
  2. From: jarmo@ksvltd.FI (Jarmo Raiha)
  3. Newsgroups: comp.compilers
  4. Subject: Backtracking yacc
  5. Keywords: yacc, parse, question, comment
  6. Message-ID: <92-09-059@comp.compilers>
  7. Date: 10 Sep 92 23:01:10 GMT
  8. Sender: compilers-sender@iecc.cambridge.ma.us
  9. Reply-To: Jarmo Raiha <jarmo@ksvltd.FI>
  10. Organization: Compilers Central
  11. Lines: 18
  12. Approved: compilers@iecc.cambridge.ma.us
  13.  
  14. Has anybody seen such a thing as backtracking yacc?  What I had in mind
  15. was a LALR parser that resolves ambiquity by backtracking to the point
  16. where it had multiple routes to go.  It would parse the input until it
  17. encounters a dead end, and after that it would try an alternative path.
  18.  
  19. I know this would not solve much.  Resolving the the conflicts 'the wrong
  20. way' can still result to an errorless parsing, but I would like to know if
  21. there have been any study about this approach.  Is this a completely dead
  22. idea ?
  23.  
  24. Jarmo Raiha
  25. [That might help for conflicts in an unambiguous grammar that needs more than
  26. one token lookahead, but not for the more common case that a conflict is due
  27. to a truly ambiguous grammar.  Besides, isn't there a theorem that says that
  28. any LR(k) grammar can be rewritten as LR(1)? -John]
  29. -- 
  30. Send compilers articles to compilers@iecc.cambridge.ma.us or
  31. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  32.