home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / compiler / 1508 < prev    next >
Encoding:
Internet Message Format  |  1992-09-02  |  2.1 KB
  1. Path: sparky!uunet!paladin.american.edu!darwin.sura.net!udel!gvls1!faatcrl!iecc!compilers-sender
  2. From: bromage@mullauna.cs.mu.OZ.AU (Andrew Bromage)
  3. Newsgroups: comp.compilers
  4. Subject: Re: Parsing wars
  5. Keywords: parse, LR(1)
  6. Message-ID: <92-09-027@comp.compilers>
  7. Date: 2 Sep 92 23:37:24 GMT
  8. References: <92-09-006@comp.compilers>
  9. Sender: compilers-sender@iecc.cambridge.ma.us
  10. Reply-To: bromage@mullauna.cs.mu.OZ.AU (Andrew Bromage)
  11. Organization: Computer Science, University of Melbourne, Australia
  12. Lines: 30
  13. Approved: compilers@iecc.cambridge.ma.us
  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 action "shiftreduce" has been used for years to optimise LR(0) states
  26. in LALR(1) parsers. The idea is to first create default actions, and then
  27. for any state in which the default action is to reduce, change this to a
  28. "shiftreduce". The benefit of this is that the LALR lookahead set is only
  29. really used in the final parser when a shift-reduce conflict would
  30. otherwise arise. It also helps in the removal of unit productions.
  31. (Apparently. I've never seen it used this way - someone told me about
  32. this). However, the size of the tables are reduced considerably - as most
  33. grammars which people write produce parsers which largely consist of LR(0)
  34. states.
  35.  
  36. Pushing nonterminals onto the token stream, however, is a new one to me.
  37. I suppose that this would optimise the GOTO tables a bit, but there are
  38. better ways of doing this, like creating distinct reduce and lookahead
  39. states (IMHO).
  40.  
  41. bromage@mullauna.cs.mu.oz.au
  42. -- 
  43. Send compilers articles to compilers@iecc.cambridge.ma.us or
  44. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  45.