home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / compiler / 1497 < prev    next >
Encoding:
Text File  |  1992-09-01  |  2.2 KB  |  49 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!think.com!spdcc!iecc!compilers-sender
  3. From: eifrig@beanworld.cs.jhu.edu (Jonathan Eifrig)
  4. Subject: Re: Parsing wars
  5. Reply-To: eifrig@beanworld.cs.jhu.edu (Jonathan Eifrig)
  6. Organization: The Johns Hopkins University CS Department
  7. Date: Tue, 1 Sep 1992 17:07:19 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <92-09-016@comp.compilers>
  10. References: <92-09-006@comp.compilers>
  11. Keywords: parse, LR(1)
  12. Sender: compilers-sender@iecc.cambridge.ma.us
  13. Lines: 34
  14.  
  15. dww@inf.fu-berlin.de writes:
  16. >The parsing is called shift-reduce parsing, and I thought I had understood
  17. >that. What happens on a reduction though is, instead of pushing the
  18. >nonterminal of the lhs of the reduced production onto a symbol stack and
  19. >digging through the goto table for the appropriate state to push onto the
  20. >state stack, the nonterminal is *prepended* to the input sequence of
  21. >tokens and parsing resumes as normal. The other actions, shift, accept and
  22. >error are as expected, an action shiftreduce combines the normal shift and
  23. >the strange reduce.
  24.  
  25. The Moderator adds:
  26.  
  27. >[It sounds to me like a way to combine the shift and goto tables, since
  28. >pushing the nonterminal and then shifting it would be equivalent to a
  29. >goto.  -John]
  30.  
  31.     It's also a cheesy way of saving the parse tree.  Since nothing is
  32. ever popped off of the parsing stack, the result of parsing is just the
  33. input annotated with special non-terminal symbols.  This is basically the
  34. parse tree written out by either a pre- or post-order traversal, depending
  35. on whether you look at the stack from either the top or the bottom.
  36.  
  37.     There are better ways of making a parse tree, of course, since
  38. this method gives one that is (1) difficult to traverse and (2) reflects
  39. the _concrete_ rather than the _abstract_ syntax of the language, which is
  40. usually more useful.  It is, however, relatively space efficient, the
  41. entire stack being only a (small) constant factor larger than the input.
  42. So it could be useful for some things, like printing error messages
  43. including the offending portion of the input.
  44. --
  45. Jack Eifrig (eifrig@cs.jhu.edu)       The Johns Hopkins University, C.S. Dept.
  46. -- 
  47. Send compilers articles to compilers@iecc.cambridge.ma.us or
  48. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  49.