home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / compiler / 1487 < prev    next >
Encoding:
Internet Message Format  |  1992-08-31  |  1.8 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!darwin.sura.net!udel!gvls1!faatcrl!iecc!compilers-sender
  2. From: dww@inf.fu-berlin.de
  3. Newsgroups: comp.compilers
  4. Subject: Parsing wars
  5. Keywords: parse, LR(1), question, comment
  6. Message-ID: <92-09-006@comp.compilers>
  7. Date: 31 Aug 92 16:13:40 GMT
  8. Sender: compilers-sender@iecc.cambridge.ma.us
  9. Reply-To: dww@inf.fu-berlin.de
  10. Organization: Free University of Berlin
  11. Lines: 28
  12. Approved: compilers@iecc.cambridge.ma.us
  13.  
  14. I have encountered a parsing method that I do not understand. Perhaps it's
  15. just some sort of fancy technique, maybe I overlooked something.  If
  16. someone can either tell me how this works or else state <rtfm,book,topic>
  17. I would be grateful.
  18.  
  19. The parsing is called shift-reduce parsing, and I thought I had understood
  20. that. What happens on a reduction though is, instead of pushing the
  21. nonterminal of the lhs of the reduced production onto a symbol stack and
  22. digging through the goto table for the appropriate state to push onto the
  23. state stack, the nonterminal is *prepended* to the input sequence of
  24. tokens and parsing resumes as normal. The other actions, shift, accept and
  25. error are as expected, an action shiftreduce combines the normal shift and
  26. the strange reduce.
  27.  
  28. My question: how and why does this work? What does it buy me? (Is it
  29. extremely efficient? Use compact tables? Wrong?)
  30.  
  31. Thanks for any clues!
  32. -- 
  33. Debora Weber-Wulff                       dww@inf.fu-berlin.de
  34. Institut fuer Informatik                 +49 30 89691 124
  35. Nestorstr. 8-9, D-W-1000 Berlin 31
  36. [It sounds to me like a way to combine the shift and goto tables, since
  37. pushing the nonterminal and then shifting it would be equivalent to a
  38. goto.  -John]
  39. -- 
  40. Send compilers articles to compilers@iecc.cambridge.ma.us or
  41. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  42.