home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / compiler / 1532 < prev    next >
Encoding:
Internet Message Format  |  1992-09-10  |  2.8 KB
  1. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!udel!gvls1!faatcrl!iecc!compilers-sender
  2. From: dww@inf.fu-berlin.de
  3. Newsgroups: comp.compilers
  4. Subject: Re: Parsing wars
  5. Keywords: parse, LR(1)
  6. Message-ID: <92-09-051@comp.compilers>
  7. Date: 8 Sep 92 09:17:20 GMT
  8. References: <92-09-006@comp.compilers> <92-09-043@comp.compilers>
  9. Sender: compilers-sender@iecc.cambridge.ma.us
  10. Reply-To: dww@inf.fu-berlin.de
  11. Organization: Free University of Berlin
  12. Lines: 43
  13. Approved: compilers@iecc.cambridge.ma.us
  14.  
  15. jar@cheops.HQ.Ileaf.COM (Jim Roskind x5570) writes [about "strange parsing"]
  16.  
  17. >The conseqeunces of this extension are quite significant, and the
  18. >resulting parser engine provides a much larger class of parsers than LR
  19. >parsers.  Clearly all LR parsers are a subset of the above parsers, as
  20. >doing the above "strange reduce" followed by a "shift" is identical to
  21. >doing a classical LR engine "reduce."
  22.  
  23. >To see the weirdness of this extension, it can be noted that you can build
  24. >an N pass parser using the above mechanisms.  Certainly parsing is not
  25. >restricted to Left to right, Right most derivation.  To see how to make an
  26. >N pass (trivial) parser using the above engine, you simply have to note
  27. >that a series of "strange reduces" (re: which put stuff back into the
  28. >input queue) can be used at any point to "back up" into the current stack.
  29. >To be fair about this, you have to provide trivial reductions that have a
  30. >right hand side of length 1, and provided new non-terminal names for the
  31. >"popped" entries on the stack.
  32.  
  33. Oh yes, with backing up it seems you could parse a lot more languages
  34. like a^n b^n c^n (rough sketch: shift all the "a"'s over, then all the
  35. "b"'s. When we reach a "c", delete it, shovel the "b"'s - or a non-terminal
  36. representing them - back into the input, when an "a" or a non-terminal
  37. representing it turns up on the input, delete it and the "b" that should now
  38. be the first element of the "input". Now shovel the "b"'s back on the stack
  39. until we find another "c" and repeat. If they all are gone, we've recognized
  40. the word. Only a^n b^n c^n will be accepted, because we manage to delete an
  41. "a", a "b" and a "c" together.). You might need productions like
  42. ? -> ? to strange-reduce whatever is on the top of the stack to the input,
  43. or you could even have terminal symbols on the left hand side of a production.
  44. The trick would be how to specify all this and produce an appropriate table.
  45.  
  46. It might be rather difficult :-) to prove the termination of this parsing
  47. algorithm, but it seems to be an interesting idea. Has anyone ever seen
  48. something like this described? Pointers, please!
  49.  
  50. -- 
  51. Debora Weber-Wulff                       dww@inf.fu-berlin.de
  52. Institut fuer Informatik                 +49 30 89691 124
  53. Nestorstr. 8-9
  54. D-W-1000 Berlin 31
  55. -- 
  56. Send compilers articles to compilers@iecc.cambridge.ma.us or
  57. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  58.