home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / theory / 1910 < prev    next >
Encoding:
Internet Message Format  |  1992-09-11  |  3.2 KB
  1. Path: sparky!uunet!utcsri!neat.cs.toronto.edu!mdhutton
  2. Newsgroups: comp.theory
  3. From: mdhutton@cs.toronto.edu (Mike Hutton)
  4. Subject: Re: What kind of an automaton is this?
  5. Message-ID: <92Sep11.123701edt.47914@neat.cs.toronto.edu>
  6. Organization: Department of Computer Science, University of Toronto
  7. References: <4QU69WW@math.fu-berlin.de>
  8. Date: 11 Sep 92 16:37:11 GMT
  9. Lines: 53
  10.  
  11. In article <4QU69WW@math.fu-berlin.de> dww@inf.fu-berlin.de writes:
  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. You state SLR differently than I have seen it before; are you thinking
  32. of noncanonical SLR [Tai 1979]?  
  33.  
  34. Fischer and LeBlanc (Crafting a Compiler) defines the SLR(1) machine as
  35. an extension of the LR(0) machine to include one symbol of (canonical,
  36. i.e. temrminal symbols only) lookahead (but no new states); LALR(1) is
  37. a reduction of the full LR(1) machine to merge redundant states.  Both
  38. are attempting to gain the expressiveness of the LR(1) machine with
  39. cost closer to the LR(0) machine, just from different directions.
  40.  
  41. SLR parsers are still canonical parsers though; I don't see how the
  42. description given above matches with the definition in Fischer and
  43. LeBlanc or with my memory.  
  44.  
  45. To disagree with the previous two responses, even if you extend to allow
  46. noncanonical lookahead (i.e. allow 2 stacks to go through the
  47. input and put nonterminals back on the input stack), you still have a
  48. context-free-like grammar (just with a more powerful lookahead 
  49. ability) defining the language.  That the noncanonical parser *uses* two 
  50. stacks doesn't imply that any language acceptable by an arbitrary
  51. 2-stack automaton (i.e. Turing Machine) can be expressed with an appropriate 
  52. NLR(k) or NSLR(k) grammar---you still have k-bounded lookahead, even if 
  53. it can also include nonterminals.
  54.  
  55. The point of noncanonical extensions was firstly to allow grammars to
  56. be written more "naturally" (no contortions to make them LALR(1) parsable)
  57. not really to extend the class of recognizable languages.  However, you
  58. can get some non-LR(k) (non DCFL) languages with noncanonical parsers, and
  59. this would be useful for some language constructions.
  60.  
  61. I wrote a grad-course paper surveying this about 3 years ago which
  62. has most of the relevant references; if still interested send email.  
  63.  
  64.