home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / compiler / 1535 < prev    next >
Encoding:
Internet Message Format  |  1992-09-10  |  2.3 KB
  1. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!udel!gvls1!faatcrl!iecc!compilers-sender
  2. From: bruce@harry.ugcs.caltech.edu (Bruce J Bell)
  3. Newsgroups: comp.compilers
  4. Subject: Re: Parsing wars
  5. Keywords: parse, LR(1)
  6. Message-ID: <92-09-054@comp.compilers>
  7. Date: 9 Sep 92 00:46:52 GMT
  8. References: <92-09-006@comp.compilers> <92-09-043@comp.compilers>
  9. Sender: compilers-sender@iecc.cambridge.ma.us
  10. Reply-To: bruce@harry.ugcs.caltech.edu (Bruce J Bell)
  11. Organization: California Institute of Technology, Pasadena
  12. Lines: 37
  13. Approved: compilers@iecc.cambridge.ma.us
  14.  
  15. jar@cheops.HQ.Ileaf.COM (Jim Roskind x5570) writes:
  16.  
  17. ( about a stack-based parser that puts reduced nonterminals back on the input,
  18.   instead of on the stack )
  19.  
  20. >The conseqeunces of this extension are quite significant, and the
  21. >resulting parser engine provides a much larger class of parsers than LR
  22. >parsers.  Clearly all LR parsers are a subset of the above parsers, as
  23. >doing the above "strange reduce" followed by a "shift" is identical to
  24. >doing a classical LR engine "reduce."
  25.  
  26. >To see the weirdness of this extension, it can be noted that you can build
  27. >an N pass parser using the above mechanisms.  Certainly parsing is not
  28. >restricted to Left to right, Right most derivation.  ...
  29.  
  30. If you allow "single-reductions", this parser sounds an awful lot like a
  31. Turing machine, but if you require that all reductions convert more than
  32. one symbol to a nonterminal, you have a parser that is less powerful than
  33. a Turing machine, but still more powerful than an LR parser.  Either way,
  34. I have heard this kind of parser referred to as a "two-stack parser",
  35. since the "strange reduce" treats the input as a stack which is
  36. initialized with the program text on it.
  37.  
  38. Also, if there are no single-reductions, you are guaranteed that the parse
  39. takes time proportional to the length of the input string, while a 2-stack
  40. parser with single-reductions could conceivably take a great deal of time,
  41. or just enter an infinite loop...
  42.  
  43. I have looked into this class of parser as possibly being powerful enough
  44. to integrate lexing into the parser.  I doubt it would improve efficiency
  45. much, but the idea of putting the entire front end into a single
  46. conceptual framework has its appeal.
  47.  
  48. Bruce J. Bell
  49. -- 
  50. Send compilers articles to compilers@iecc.cambridge.ma.us or
  51. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  52.