home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / compiler / 1504 < prev    next >
Encoding:
Internet Message Format  |  1992-09-02  |  2.4 KB
  1. Path: sparky!uunet!paladin.american.edu!darwin.sura.net!udel!gvls1!faatcrl!iecc!compilers-sender
  2. From: horst@techfak.uni-bielefeld.de (Horst Hogenkamp)
  3. Newsgroups: comp.compilers
  4. Subject: Re: Parsing wars
  5. Keywords: parse, LR(1)
  6. Message-ID: <92-09-026@comp.compilers>
  7. Date: 2 Sep 92 13:58:53 GMT
  8. References: <92-09-006@comp.compilers>
  9. Sender: compilers-sender@iecc.cambridge.ma.us
  10. Reply-To: horst@techfak.uni-bielefeld.de (Horst Hogenkamp)
  11. Organization: Universitaet Bielefeld, Technische Fakultaet.
  12. Lines: 42
  13. Approved: compilers@iecc.cambridge.ma.us
  14.  
  15. In article <92-09-006@comp.compilers>, 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.  
  26. In the traditional Aho-Sethi-Ullman-parser (p.219) there is an implicit
  27. shift appended to every reduce.  This is some kind of partial evaluation
  28. because it is not always possible to write things back to your input.
  29.  
  30.  
  31. > [It sounds to me like a way to combine the shift and goto tables, since
  32. > pushing the nonterminal and then shifting it would be equivalent to a
  33. > goto.  -John]
  34.  
  35.  
  36. Exactly this is the case.  Terminal symbols and nonterminal symbols are
  37. not distinguished.  The goto table is merged into the action table such
  38. that "goto[s,A]=i" becomes "action[s,A]=shift i".  This can make things
  39. easier.
  40.  
  41. Now you can have terminal symbols as well as nonterminals in the input,
  42. which is needed for example in program transformation systems.
  43. Consider the rule:
  44.     EVAL(E:expr "+" "0") => EVAL(E)
  45. The the parser's input for the lhs would be:
  46.     expr "+" "0"
  47. This would be impossible to parse with a traditional shift-reduce parser.
  48.  
  49. I have done this (as well as other things) in my masters thesis in 1988/89
  50. and it works very well but I reinvented the wheel.  I once saw an article
  51. on exactly this topic but I forgot the reference.
  52.  
  53. Horst Hogenkamp
  54. -- 
  55. Send compilers articles to compilers@iecc.cambridge.ma.us or
  56. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  57.