home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / theory / 1895 < prev    next >
Encoding:
Text File  |  1992-09-09  |  1.7 KB  |  35 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!spool.mu.edu!yale.edu!ira.uka.de!math.fu-berlin.de!weberwu
  3. From: weberwu@inf.fu-berlin.de (Debora Weber-Wulff)
  4. Subject: What kind of an automaton is this?
  5. Message-ID: <4QU69WW@math.fu-berlin.de>
  6. Sender: news@math.fu-berlin.de (Math Department)
  7. Reply-To: dww@inf.fu-berlin.de
  8. Organization: Free University of Berlin
  9. Date: Wed, 9 Sep 1992 13:13:57 GMT
  10. Lines: 23
  11.  
  12. We've been discussing on comp.compilers the kind of parsing automaton that is described in
  13. DeRemer[CACM 71] as being an SLR-Parser. It is not the kind of PDA I
  14. learned about when I studied Automata Theory with the next state and the
  15. output being determined by the current state, the top of the stack, and
  16. the current symbol in the input. In this "strange" automaton the lhs of
  17. the production being reduced is returned to the input after the stack
  18. has been popped. This is not just backing up over input, but non-terminals
  19. can be built up on the input, perhaps with a number of epsilon productions.
  20. Some people have said "oh yes, we like that and have a hack to use it"
  21. but it is unclear what exactly the computational complexity of this
  22. automaton is. LR parsing is clearly a subset of what this automaton can
  23. do - just don't do any of the strange reductions. 
  24.  
  25. Has anyone encountered this type of automaton before? What does it buy
  26. me, i.e. what special problems could be solved with this type of
  27. automaton that we can't do with LR-parsers? Pointers or ideas of
  28. any kind are welcome.
  29.  
  30. -- 
  31. Debora Weber-Wulff                       dww@inf.fu-berlin.de
  32. Institut fuer Informatik                 +49 30 89691 124
  33. Nestorstr. 8-9                           (INCLUDE "standard.disclaimer")
  34. D-W-1000 Berlin 31                       (PRINTN (WITTY-MESSAGE TODAY))
  35.