home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / compiler / 1908 < prev    next >
Encoding:
Text File  |  1992-11-18  |  1.9 KB  |  47 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!think.com!spdcc!iecc!compilers-sender
  3. From: mareb@levels.unisa.edu.au
  4. Subject: re: Grammar Algebras?
  5. Reply-To: mareb@levels.unisa.edu.au
  6. Organization: University of South Australia
  7. Date: Tue, 17 Nov 1992 23:59:47 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <92-11-099@comp.compilers>
  10. Keywords: parse, theory
  11. Sender: compilers-sender@iecc.cambridge.ma.us
  12. Lines: 33
  13.  
  14. Clearly you can't intersect CFGs - since the intersection may not be a
  15. CFG. I have been playing with the intersection of CFGs lately for a couple
  16. of reasons.
  17.  
  18. 1. we wanted to know how to parse a^n b^n c^n d^n ... quickly.  Since we
  19. can parse a^n b^n c^m d^m ... in time O(N) {does anyone have a reference
  20. to a published proof that LR(k) parsing is O(N)?} and a^* b^i c^i d^j e^j
  21. ... we just run two parsers in parallel (or serially) and if they both
  22. succeed, the string is in the above CSL.
  23.  
  24. Perhaps we are lucky that CFLs are not closed under intersection!
  25.  
  26. Another observation is that this method of producing any type of grammar
  27. for the above CSL is probably easier and more intuitive than trying to
  28. produce a CSG. I find that it takes quite a bit of experience to be able
  29. to work effectively with CFGs; I know very few people who can look at a
  30. CSG and have much of a idea what it does and doesn't `say'.
  31.  
  32. 2. a second reason for wanting to parse a^n b^n c^n ... is that people
  33. keep asking me about parsing 2D syntax. Mostly they mean tables. I tell
  34. them to just linearise their language and build a parser. If they have the
  35. above problem, parse a^* b^* c^* and check the lengths with semantic
  36. rules. So far, they've all been happy. The above trick is nice theory but
  37. hasn't proven of much practical significance for me.
  38.  
  39.     regards,
  40.     Bob Buckley
  41.  
  42. School of Computer and Information Science
  43. University of South Australia
  44. -- 
  45. Send compilers articles to compilers@iecc.cambridge.ma.us or
  46. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  47.