home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / theory / 1909 < prev    next >
Encoding:
Text File  |  1992-09-10  |  2.1 KB  |  47 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!mcsun!sun4nl!wn1.sci.kun.nl!cs.kun.nl!markjan
  3. From: markjan@cs.kun.nl (Mark-Jan Nederhof)
  4. Subject: Re: What kind of an automaton is this?
  5. Message-ID: <1992Sep10.160404.21612@sci.kun.nl>
  6. Sender: news@sci.kun.nl (NUnet News Owner)
  7. Organization: University of Nijmegen, The Netherlands
  8. References: <4QU69WW@math.fu-berlin.de>
  9. Date: Thu, 10 Sep 1992 16:04:04 GMT
  10. Lines: 35
  11.  
  12. In <4QU69WW@math.fu-berlin.de> weberwu@inf.fu-berlin.de (Debora Weber-Wulff) writes:
  13.  
  14.   >We've been discussing on comp.compilers the kind of parsing automaton that 
  15.   >is described in
  16.   >DeRemer[CACM 71] as being an SLR-Parser. It is not the kind of PDA I
  17.   >learned about when I studied Automata Theory with the next state and the
  18.   >output being determined by the current state, the top of the stack, and
  19.   >the current symbol in the input. In this "strange" automaton the lhs of
  20.   >the production being reduced is returned to the input after the stack
  21.   >has been popped. This is not just backing up over input, but non-terminals
  22.   >can be built up on the input, perhaps with a number of epsilon productions.
  23.   >Some people have said "oh yes, we like that and have a hack to use it"
  24.   >but it is unclear what exactly the computational complexity of this
  25.   >automaton is. LR parsing is clearly a subset of what this automaton can
  26.   >do - just don't do any of the strange reductions. 
  27.  
  28. Being allowed to push symbols onto the input is similar to having two 
  29. stacks. Having two stacks is again similar to having a tape on which you 
  30. can read, write and move both ways; in other words, to having a Turing machine.
  31.  
  32.   >Has anyone encountered this type of automaton before? What does it buy
  33.   >me, i.e. what special problems could be solved with this type of
  34.   >automaton that we can't do with LR-parsers? Pointers or ideas of
  35.   >any kind are welcome.
  36.  
  37. The class of Turing-decidable languages is the largest class of
  38. decidable languages that we know. It subsumes the class of LR(k) languages 
  39. and many others.
  40.  
  41. References: e.g. A.V. Aho, J.D. Ullman: The theory of parsing,
  42. translation, and compiling.
  43.  
  44. Mark-Jan Nederhof
  45. University of Nijmegen
  46.  
  47.