home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / std_unix / v21 / 095 < prev    next >
Internet Message Format  |  1990-12-05  |  3KB
  1. From std-unix-request@uunet.uu.net  Sun Sep  9 15:19:07 1990
  2. Received: from cs.utexas.edu by uunet.uu.net (5.61/1.14) with SMTP 
  3.     id AA01995; Sun, 9 Sep 90 15:19:07 -0400
  4. Posted-Date: 9 Sep 90 04:39:29 GMT
  5. Received: by cs.utexas.edu (5.64/1.76) 
  6. From: henry@zoo.toronto.edu (Henry Spencer)
  7. Newsgroups: comp.std.unix
  8. Subject: Re: ambiguous match with multiple-character collating elements
  9. Message-Id: <501@usenix.ORG>
  10. References: <487@usenix.ORG>
  11. Sender: jsq@usenix.ORG
  12. Organization: U of Toronto Zoology
  13. X-Submissions: std-unix@uunet.uu.net
  14. Date: 9 Sep 90 04:39:29 GMT
  15. Reply-To: std-unix@uunet.uu.net
  16. To: std-unix@uunet.uu.net
  17.  
  18. From: henry@zoo.toronto.edu (Henry Spencer)
  19.  
  20. In article <487@usenix.ORG> karl@IMA.ISC.COM (Karl Heuer) writes:
  21. >In an environment where the digraph "ch" collates as a single element, what
  22. >happens if an attempt is made to match the subject string "chi" with the
  23. >pattern "[c[.ch.]]i" or "[c[.ch.]]hi"?  Is the implementation required to
  24. >report a successful match in both cases?  If so, it would seem necessary to
  25. >use a nondeterministic finite automaton or equivalent, thus making simple
  26. >regexp matching and filename globbing as complex as egrep pattern matching.
  27.  
  28. Looking at draft 10, I don't think there is much doubt that they both must
  29. match, assuming those are legal regular expressions.  (If "c" is not a
  30. collating element or noncollating character, they're not.)  If both "c"
  31. and "ch" are valid collating elements, the bracket expression must be
  32. prepared to match either.
  33.  
  34. The wording could stand improving.
  35.  
  36. As for the implementation aspects, yes, this is a pain.  However, there
  37. is basically no such thing as "simple" regexp matching. :-)  The extra
  38. complexity added by multicharacter collating elements, while annoying,
  39. is not that big a deal.  I think Karl is confused.  *Any* non-trivial
  40. regexp matching ends up using either nondeterministic or deterministic
  41. automata, sometimes behind clever plastic disguises.  The very simplest
  42. forms, like globbing, sometimes can get away without having to compile
  43. the regexp string into an internal form, by running a nondeterministic
  44. automaton directly from the regexp string.  That will get a bit harder
  45. because of the greater complexity of 1003.2 regexps.  However, there
  46. is no way that even "simple" regexp matching (I assume Karl is thinking
  47. of things like ed) is viable without a compilation step.
  48.  
  49. Given that 1003.2 defines -- finally! -- library functions for regexp
  50. work of various kinds, including globbing, the complexity will, in any
  51. case, be localized to library functions.  The programmer won't have to
  52. worry about it unless he's actually writing those library functions.
  53. (*That* won't be fun.)
  54. -- 
  55. TCP/IP: handling tomorrow's loads today| Henry Spencer at U of Toronto Zoology
  56. OSI: handling yesterday's loads someday|  henry@zoo.toronto.edu   utzoo!henry
  57.  
  58. Volume-Number: Volume 21, Number 95
  59.  
  60.