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