home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / gnurx.zip / doc / rx.info (.txt) < prev    next >
GNU Info File  |  1995-12-31  |  37KB  |  707 lines
  1. This is Info file rx.info, produced by Makeinfo-1.63 from the input
  2. file rx.texi.
  3. File: rx.info,  Node: Top,  Next: Posix Entry Points,  Prev: (dir),  Up: (dir)
  4.    This document describes Rx.
  5.    This document applies to version "Rx-diSpencer" of the library named
  6. librx.a
  7. * Menu:
  8. * Posix Entry Points::
  9. * Performance Considerations::  Special considerations when using Rx.
  10. * Semantic Tests::              A test-suite for Posix matcher semantics.
  11. * General Functions::           Rx's native entry points.
  12. * Rx Theory::                   A quick tour of the implementation.
  13. * Improvements to Make::        The Rx TODO list.
  14. File: rx.info,  Node: Posix Entry Points,  Next: Performance Considerations,  Prev: Top,  Up: Top
  15. Regular Expression Matching
  16. ===========================
  17.    This section is excerpted from *The GNU C Library* reference manual
  18. by Sandra Loosemore with Richard M. Stallman, Roland McGrath, and Andrew
  19. Oram.
  20.    The GNU C library supports the standard POSIX.2 interface.  Programs
  21. using this interface should include the header file `rx.h'.
  22. * Menu:
  23. * POSIX Regexp Compilation::    Using `regcomp' to prepare to match.
  24. * Flags for POSIX Regexps::     Syntax variations for `regcomp'.
  25. * Matching POSIX Regexps::      Using `regexec' to match the compiled
  26.                    pattern that you get from `regcomp'.
  27. * Regexp Subexpressions::       Finding which parts of the string were matched.
  28. * Subexpression Complications:: Find points of which parts were matched.
  29. * Regexp Cleanup::        Freeing storage; reporting errors.
  30. File: rx.info,  Node: POSIX Regexp Compilation,  Next: Flags for POSIX Regexps,  Up: Posix Entry Points
  31. POSIX Regular Expression Compilation
  32. ------------------------------------
  33.    Before you can actually match a regular expression, you must
  34. "compile" it.  This is not true compilation--it produces a special data
  35. structure, not machine instructions.  But it is like ordinary
  36. compilation in that its purpose is to enable you to "execute" the
  37. pattern fast.  (*Note Matching POSIX Regexps::, for how to use the
  38. compiled regular expression for matching.)
  39.    There is a special data type for compiled regular expressions:
  40.  - Data Type: regex_t
  41.      This type of object holds a compiled regular expression.  It is
  42.      actually a structure.  It has just one field that your programs
  43.      should look at:
  44.     `re_nsub'
  45.           This field holds the number of parenthetical subexpressions
  46.           in the regular expression that was compiled.
  47.      There are several other fields, but we don't describe them here,
  48.      because only the functions in the library should use them.
  49.    After you create a `regex_t' object, you can compile a regular
  50. expression into it by calling `regcomp'.
  51.  - Function: int regcomp (regex_t *COMPILED, const char *PATTERN, int
  52.           CFLAGS)
  53.      The function `regcomp' "compiles" a regular expression into a data
  54.      structure that you can use with `regexec' to match against a
  55.      string.  The compiled regular expression format is designed for
  56.      efficient matching.  `regcomp' stores it into `*COMPILED'.
  57.      It's up to you to allocate an object of type `regex_t' and pass its
  58.      address to `regcomp'.
  59.      The argument CFLAGS lets you specify various options that control
  60.      the syntax and semantics of regular expressions.  *Note Flags for
  61.      POSIX Regexps::.
  62.      If you use the flag `REG_NOSUB', then `regcomp' omits from the
  63.      compiled regular expression the information necessary to record
  64.      how subexpressions actually match.  In this case, you might as well
  65.      pass `0' for the MATCHPTR and NMATCH arguments when you call
  66.      `regexec'.
  67.      If you don't use `REG_NOSUB', then the compiled regular expression
  68.      does have the capacity to record how subexpressions match.  Also,
  69.      `regcomp' tells you how many subexpressions PATTERN has, by
  70.      storing the number in `COMPILED->re_nsub'.  You can use that value
  71.      to decide how long an array to allocate to hold information about
  72.      subexpression matches.
  73.      `regcomp' returns `0' if it succeeds in compiling the regular
  74.      expression; otherwise, it returns a nonzero error code (see the
  75.      table below).  You can use `regerror' to produce an error message
  76.      string describing the reason for a nonzero value; see *Note Regexp
  77.      Cleanup::.
  78.    Here are the possible nonzero values that `regcomp' can return:
  79. `REG_BADBR'
  80.      There was an invalid `\{...\}' construct in the regular
  81.      expression.  A valid `\{...\}' construct must contain either a
  82.      single number, or two numbers in increasing order separated by a
  83.      comma.
  84. `REG_BADPAT'
  85.      There was a syntax error in the regular expression.
  86. `REG_BADRPT'
  87.      A repetition operator such as `?' or `*' appeared in a bad
  88.      position (with no preceding subexpression to act on).
  89. `REG_ECOLLATE'
  90.      The regular expression referred to an invalid collating element
  91.      (one not defined in the current locale for string collation).
  92. `REG_ECTYPE'
  93.      The regular expression referred to an invalid character class name.
  94. `REG_EESCAPE'
  95.      The regular expression ended with `\'.
  96. `REG_ESUBREG'
  97.      There was an invalid number in the `\DIGIT' construct.
  98. `REG_EBRACK'
  99.      There were unbalanced square brackets in the regular expression.
  100. `REG_EPAREN'
  101.      An extended regular expression had unbalanced parentheses, or a
  102.      basic regular expression had unbalanced `\(' and `\)'.
  103. `REG_EBRACE'
  104.      The regular expression had unbalanced `\{' and `\}'.
  105. `REG_ERANGE'
  106.      One of the endpoints in a range expression was invalid.
  107. `REG_ESPACE'
  108.      `regcomp' ran out of memory.
  109. File: rx.info,  Node: Flags for POSIX Regexps,  Next: Matching POSIX Regexps,  Prev: POSIX Regexp Compilation,  Up: Posix Entry Points
  110. Flags for POSIX Regular Expressions
  111. -----------------------------------
  112.    These are the bit flags that you can use in the CFLAGS operand when
  113. compiling a regular expression with `regcomp'.
  114. `REG_EXTENDED'
  115.      Treat the pattern as an extended regular expression, rather than
  116.      as a basic regular expression.
  117. `REG_ICASE'
  118.      Ignore case when matching letters.
  119. `REG_NOSUB'
  120.      Don't bother storing the contents of the MATCHES-PTR array.
  121. `REG_NEWLINE'
  122.      Treat a newline in STRING as dividing STRING into multiple lines,
  123.      so that `$' can match before the newline and `^' can match after.
  124.      Also, don't permit `.' to match a newline, and don't permit
  125.      `[^...]' to match a newline.
  126.      Otherwise, newline acts like any other ordinary character.
  127. File: rx.info,  Node: Matching POSIX Regexps,  Next: Regexp Subexpressions,  Prev: Flags for POSIX Regexps,  Up: Posix Entry Points
  128. Matching a Compiled POSIX Regular Expression
  129. --------------------------------------------
  130.    Once you have compiled a regular expression, as described in *Note
  131. POSIX Regexp Compilation::, you can match it against strings using
  132. `regexec'.  A match anywhere inside the string counts as success,
  133. unless the regular expression contains anchor characters (`^' or `$').
  134.  - Function: int regexec (regex_t *COMPILED, char *STRING, size_t
  135.           NMATCH, regmatch_t MATCHPTR [], int EFLAGS)
  136.      This function tries to match the compiled regular expression
  137.      `*COMPILED' against STRING.
  138.      `regexec' returns `0' if the regular expression matches;
  139.      otherwise, it returns a nonzero value.  See the table below for
  140.      what nonzero values mean.  You can use `regerror' to produce an
  141.      error message string describing the reason for a nonzero value;
  142.      see *Note Regexp Cleanup::.
  143.      The argument EFLAGS is a word of bit flags that enable various
  144.      options.
  145.      If you want to get information about what part of STRING actually
  146.      matched the regular expression or its subexpressions, use the
  147.      arguments MATCHPTR and NMATCH.  Otherwise, pass `0' for NMATCH,
  148.      and `NULL' for MATCHPTR.  *Note Regexp Subexpressions::.
  149.    You must match the regular expression with the same set of current
  150. locales that were in effect when you compiled the regular expression.
  151.    The function `regexec' accepts the following flags in the EFLAGS
  152. argument:
  153. `REG_NOTBOL'
  154.      Do not regard the beginning of the specified string as the
  155.      beginning of a line; more generally, don't make any assumptions
  156.      about what text might precede it.
  157. `REG_NOTEOL'
  158.      Do not regard the end of the specified string as the end of a
  159.      line; more generally, don't make any assumptions about what text
  160.      might follow it.
  161.    Here are the possible nonzero values that `regexec' can return:
  162. `REG_NOMATCH'
  163.      The pattern didn't match the string.  This isn't really an error.
  164. `REG_ESPACE'
  165.      `regexec' ran out of memory.
  166. File: rx.info,  Node: Regexp Subexpressions,  Next: Subexpression Complications,  Prev: Matching POSIX Regexps,  Up: Posix Entry Points
  167. Match Results with Subexpressions
  168. ---------------------------------
  169.    When `regexec' matches parenthetical subexpressions of PATTERN, it
  170. records which parts of STRING they match.  It returns that information
  171. by storing the offsets into an array whose elements are structures of
  172. type `regmatch_t'.  The first element of the array (index `0') records
  173. the part of the string that matched the entire regular expression.
  174. Each other element of the array records the beginning and end of the
  175. part that matched a single parenthetical subexpression.
  176.  - Data Type: regmatch_t
  177.      This is the data type of the MATCHARRAY array that you pass to
  178.      `regexec'.  It containes two structure fields, as follows:
  179.     `rm_so'
  180.           The offset in STRING of the beginning of a substring.  Add
  181.           this value to STRING to get the address of that part.
  182.     `rm_eo'
  183.           The offset in STRING of the end of the substring.
  184.  - Data Type: regoff_t
  185.      `regoff_t' is an alias for another signed integer type.  The
  186.      fields of `regmatch_t' have type `regoff_t'.
  187.    The `regmatch_t' elements correspond to subexpressions positionally;
  188. the first element (index `1') records where the first subexpression
  189. matched, the second element records the second subexpression, and so
  190. on.  The order of the subexpressions is the order in which they begin.
  191.    When you call `regexec', you specify how long the MATCHPTR array is,
  192. with the NMATCH argument.  This tells `regexec' how many elements to
  193. store.  If the actual regular expression has more than NMATCH
  194. subexpressions, then you won't get offset information about the rest of
  195. them.  But this doesn't alter whether the pattern matches a particular
  196. string or not.
  197.    If you don't want `regexec' to return any information about where
  198. the subexpressions matched, you can either supply `0' for NMATCH, or
  199. use the flag `REG_NOSUB' when you compile the pattern with `regcomp'.
  200. File: rx.info,  Node: Subexpression Complications,  Next: Regexp Cleanup,  Prev: Regexp Subexpressions,  Up: Posix Entry Points
  201. Complications in Subexpression Matching
  202. ---------------------------------------
  203.    Sometimes a subexpression matches a substring of no characters.  This
  204. happens when `f\(o*\)' matches the string `fum'.  (It really matches
  205. just the `f'.)  In this case, both of the offsets identify the point in
  206. the string where the null substring was found.  In this example, the
  207. offsets are both `1'.
  208.    Sometimes the entire regular expression can match without using some
  209. of its subexpressions at all--for example, when `ba\(na\)*' matches the
  210. string `ba', the parenthetical subexpression is not used.  When this
  211. happens, `regexec' stores `-1' in both fields of the element for that
  212. subexpression.
  213.    Sometimes matching the entire regular expression can match a
  214. particular subexpression more than once--for example, when `ba\(na\)*'
  215. matches the string `bananana', the parenthetical subexpression matches
  216. three times.  When this happens, `regexec' usually stores the offsets
  217. of the last part of the string that matched the subexpression.  In the
  218. case of `bananana', these offsets are `6' and `8'.
  219.    But the last match is not always the one that is chosen.  It's more
  220. accurate to say that the last *opportunity* to match is the one that
  221. takes precedence.  What this means is that when one subexpression
  222. appears within another, then the results reported for the inner
  223. subexpression reflect whatever happened on the last match of the outer
  224. subexpression.  For an example, consider `\(ba\(na\)*s \)*' matching
  225. the string `bananas bas '.  The last time the inner expression actually
  226. matches is near the end of the first word.  But it is *considered*
  227. again in the second word, and fails to match there.  `regexec' reports
  228. nonuse of the "na" subexpression.
  229.    Another place where this rule applies is when the regular expression
  230. `\(ba\(na\)*s \|nefer\(ti\)* \)*' matches `bananas nefertiti'.  The
  231. "na" subexpression does match in the first word, but it doesn't match
  232. in the second word because the other alternative is used there.  Once
  233. again, the second repetition of the outer subexpression overrides the
  234. first, and within that second repetition, the "na" subexpression is not
  235. used.  So `regexec' reports nonuse of the "na" subexpression.
  236. File: rx.info,  Node: Regexp Cleanup,  Prev: Subexpression Complications,  Up: Posix Entry Points
  237. POSIX Regexp Matching Cleanup
  238. -----------------------------
  239.    When you are finished using a compiled regular expression, you can
  240. free the storage it uses by calling `regfree'.
  241.  - Function: void regfree (regex_t *COMPILED)
  242.      Calling `regfree' frees all the storage that `*COMPILED' points
  243.      to.  This includes various internal fields of the `regex_t'
  244.      structure that aren't documented in this manual.
  245.      `regfree' does not free the object `*COMPILED' itself.
  246.    You should always free the space in a `regex_t' structure with
  247. `regfree' before using the structure to compile another regular
  248. expression.
  249.    When `regcomp' or `regexec' reports an error, you can use the
  250. function `regerror' to turn it into an error message string.
  251.  - Function: size_t regerror (int ERRCODE, regex_t *COMPILED, char
  252.           *BUFFER, size_t LENGTH)
  253.      This function produces an error message string for the error code
  254.      ERRCODE, and stores the string in LENGTH bytes of memory starting
  255.      at BUFFER.  For the COMPILED argument, supply the same compiled
  256.      regular expression structure that `regcomp' or `regexec' was
  257.      working with when it got the error.  Alternatively, you can supply
  258.      `NULL' for COMPILED; you will still get a meaningful error
  259.      message, but it might not be as detailed.
  260.      If the error message can't fit in LENGTH bytes (including a
  261.      terminating null character), then `regerror' truncates it.  The
  262.      string that `regerror' stores is always null-terminated even if it
  263.      has been truncated.
  264.      The return value of `regerror' is the minimum length needed to
  265.      store the entire error message.  If this is less than LENGTH, then
  266.      the error message was not truncated, and you can use it.
  267.      Otherwise, you should call `regerror' again with a larger buffer.
  268.      Here is a function which uses `regerror', but always dynamically
  269.      allocates a buffer for the error message:
  270.           char *get_regerror (int errcode, regex_t *compiled)
  271.           {
  272.             size_t length = regerror (errcode, compiled, NULL, 0);
  273.             char *buffer = xmalloc (length);
  274.             (void) regerror (errcode, compiled, buffer, length);
  275.             return buffer;
  276.           }
  277. File: rx.info,  Node: Performance Considerations,  Next: Semantic Tests,  Prev: Posix Entry Points,  Up: Top
  278. Performance Considerations
  279. ==========================
  280.    In order to use the Rx implementation of Posix regexp functions, you
  281. should include `<rxposix.h>' in your program.
  282.    In order to use the Rx implementation of Posix regexp functions most
  283. effectively, it may help to know a bit about performance tuning in Rx.
  284. * Menu:
  285. * Avoiding Redundant Compilations ::  Compiling Regexps is costly.
  286. * Controlling Memory Use::      You can limit Rx's memory use.
  287. File: rx.info,  Node: Avoiding Redundant Compilations,  Next: Controlling Memory Use,  Prev: Performance Considerations,  Up: Performance Considerations
  288. Avoiding Redundant Compilations
  289. -------------------------------
  290.    Rx implements the Posix regexp entry points `regcomp', `regerror',
  291. `regexec', and `regfree'.  Some special considerations apply when using
  292. the Rx versions.
  293.    First, `regcomp' is a comparatively expensive operation.
  294. Addiitonally, `regexec' tends to perform better when a compiled
  295. expression is compiled once and used twice than when the pattern is
  296. compiled twice and used twice.  Internally, Rx caches that information
  297. about a pattern which is constructed dynamicly by regexec.  You can save
  298. on compilation costs and maximize the effectiveness of the Rx cache by
  299. re-using compiled expressions when it is convenient.
  300.    For example, for reasons unrelated to Rx, it has long been the
  301. practice in GNU emacs to always save one compiled regular expression
  302. (the most recent).  Before compiling a new expression, Emacs checks to
  303. see if the new pattern is the same as the one that is already compiled.
  304. This is the sort of optimization that Rx likes.  (It may even win, in
  305. some cases, to cache more than a single compiled regexp.)
  306.    In the long-run, Rx should be modified to cache compilations on its
  307. own.  (*Note Improvements to Make::.)
  308.    Sometimes programmers write programs with many regexps, all known
  309. staticly at compile time.  This can be a problem with Rx because when
  310. the program starts up, or as it runs, all of those staticly known
  311. regexps have to be compiled, which may be too time consuming.
  312.    One easy fix for programs with many static regexps is to use `flex'
  313. or another lexical-analyzer generator program instead.  Lexer-generators
  314. are optimized for the case of compiling staticly known regexps.
  315.    There are still reasons why staticly known regexps may not be
  316. convertable to `flex' input - for example, the Posix pattern language
  317. is more general than `flex''s.  In the long-run, it may be a good idea
  318. to extend Rx to support static compilation of regexps.  (*Note
  319. Improvements to Make::.)
  320. File: rx.info,  Node: Controlling Memory Use,  Prev: Avoiding Redundant Compilations,  Up: Performance Considerations
  321. Controlling Memory Use
  322. ----------------------
  323.    The size of the cache used by regexec is subject to control by
  324. programmers.  Additionally, by using lower level entry points,
  325. programmers can create multiple, distinct Rx caches.
  326.    This part of the code is subject to change and so is not yet
  327. documented.
  328.    See "default_cache" in rxsuper.c and the parameters at the top of
  329. "rxbasic.c" to find some parameters you can tune or hints about creating
  330. alternative regexec caches.
  331. File: rx.info,  Node: Semantic Tests,  Next: General Functions,  Prev: Performance Considerations,  Up: Top
  332. Semantic Tests
  333. ==============
  334.    The distribution of *Rx* includes a test-suite, aimed at testing the
  335. conformance of an implementation of the Posix regexp functions to the
  336. standard.
  337.    Currently, the tests come from two sources: a test-suite started by
  338. Henry Spencer, and the "Khadafy" test suite by Scott Anderson.
  339.    The tests come in three files:
  340.    * runtests.c    - The driver program.
  341.    * TESTS        - The list of test cases
  342.    * TESTS2C.sed    - A script to convert test cases into C.
  343. * Menu:
  344. * Running the Tests::           Invoking the test suite.
  345. * Adding New Tests::            Extending the test suite.
  346. File: rx.info,  Node: Running the Tests,  Next: Adding New Tests,  Prev: Semantic Tests,  Up: Semantic Tests
  347. Running the Tests
  348. -----------------
  349.    To build the test program, use `make runtests'.  (Detailed
  350. configuration and build instructions can be found in INSTALL).
  351.    Invoked with no arguments, `runtests' runs all test-cases.  For each
  352. test case, a sequence number is printed.  If there is a problem with
  353. that case, more information is printed.   Output like this:
  354.      #0
  355.      #1
  356.      #2
  357.      ...
  358.    indicates a successful run.   (The output format is likely to change
  359. in the future to make it easier to automate testing of Rx.)
  360.    With a single numeric argument, runtests executes just that test and
  361. no others.  This is handy when debugging.
  362.    Sometimes a bug will occur when all tests are run, but disappear when
  363. just the problematic test is run.  Usually this has to do with memory
  364. or cache corruption.
  365. File: rx.info,  Node: Adding New Tests,  Prev: Running the Tests,  Up: Semantic Tests
  366. Adding New Tests
  367. ----------------
  368.    This list of tests used by `runtests' is found in the file `TESTS'.
  369. Each line of that file is a list of colon separated fields similar to:
  370.      1:^(ab|cd)e:abcde
  371.    The first field is the expected return value of regexec, or '2'
  372. meaning that the pattern is not valid.
  373.    The second field is the regular expression being tested.
  374.    The third field is the string to which the pattern is to be compared.
  375.    The file `TESTS2C.sed' is used to convert the test cases into
  376. initializers for an array of structures (which is automated in the
  377. Makefile).
  378.    To add a new test case, add lines to `TESTS' and recompile
  379. `runtests'.
  380. File: rx.info,  Node: General Functions,  Next: Rx Theory,  Prev: Semantic Tests,  Up: Top
  381. General Functions
  382. =================
  383.    Here is a whirlwind tour of the lower-level Rx entry points and data
  384. structures.  This is not intended to be complete, but rather to be a
  385. help to anyone reading the code itself.
  386.    These are presented in the same order in which they might typically
  387. be used.
  388. * Menu:
  389. * Compiling Expressions::       Strings->Syntax Trees
  390. * Posixly Correct Matches::     Checking for a Posixly correct match.
  391. * Hairy Matches::               Matching with multi-part strings.
  392. * NFA Functions::               Forget Posix, eat NFAs raw.
  393. File: rx.info,  Node: Compiling Expressions,  Next: Posixly Correct Matches,  Prev: General Functions,  Up: General Functions
  394. Compiling Expressions
  395. ---------------------
  396.  - Internal Function: reg_errcode_t rx_parse (struct rexp_node **
  397.           rexp_p, __const__ char *pattern, int size, unsigned long
  398.           syntax, int cset_size, unsigned char *translate);
  399.      Compile a regular expression.
  400.      REXP_P will return a syntax tree for the pattern.  See
  401.      `"rxnode.h"' to learn about syntax trees.  Minimally, you should
  402.      know that syntax trees are reference counted using `rx_save_rexp'
  403.      and `rx_free_rexp'.
  404.      PATTERN and SIZE are the expression and its length.  The
  405.      expression need not be 0-terminated.
  406.      The bits set in SYNTAX control details of the language understood
  407.      by the parser.  The meaning of each bit is described in
  408.      `"rxgnucomp.h"'.
  409.      CSET_SIZE is usually 256.  It should not be much larger than that
  410.      or space-performance will suffer badly.
  411.      TRANSLATE is a translation table - an array of characters.
  412.      Characters in the pattern are looked up in TRANSLATE as they are
  413.      read.  Additionally, the pattern is compiled presuming that the
  414.      same translation table will be applied to characters in the string
  415.      being searched (meaning that the pattern is compiled in such a way
  416.      that the effect will be as if every character in the target string
  417.      is looked up in the translation table, even though the expense of
  418.      that lookup is usually avoided).
  419.      A return of 0 indicates success, otherwise, the error can be
  420.      looked up in the `rx_error_msg' array.
  421.  - Internal Function: int rx_posix_analyze_rexp (struct rexp_node ***
  422.           subexps, int * n_subexps, struct rexp_node * node, int id)
  423.      Staticly analyze a regular expression in preparation for matching.
  424.      This function fills in some fields of the nodes of a syntax tree.
  425.      `subexps' and `n_subexps' return a malloced array of pointers into
  426.      the syntax tree, one per parenthesized subexpression.  The caller
  427.      must eventually free this array.
  428.      `node' is the pattern to be analyzed.  The tree returned by
  429.      `rx_parse' is suitable for this.
  430.      `id' should be 1.
  431.      Ignore the return value.
  432.      This function is not robust in the case that `malloc' or `realloc'
  433.      returns 0 (which should be fixed).
  434.    You might expect that `rx_posix_analyze_rexp' and `rx_parse' should
  435. be combined.  They are not because the actions of
  436. `rx_posix_analyze_rexp' make sense for any syntax tree, regardless of
  437. how it is constructed.  `rx_parse' is just one way to build a syntax
  438. tree - it is subject to replacement and trees can be built without
  439. using a parser at all (c.f. `"rxnode.h"').
  440. File: rx.info,  Node: Posixly Correct Matches,  Next: Hairy Matches,  Prev: Compiling Expressions,  Up: General Functions
  441. Checking for Posixly Correct Matches with One-Piece Strings
  442. -----------------------------------------------------------
  443.    Looking for a match that is Posixly correct is conceptually tricky.
  444. Here is one way to think of it:
  445.    The Posix expression languages, absent of any consideration of the
  446. meaning of "leftmost-longest", underspecify the return value of
  447. `regexec'.  Consider the example:
  448.      Pattern:
  449.          foo\(.*\)\(.*\)bar
  450.      Target string:
  451.          fooxxxbar
  452.    Initially it is ambiguous how this should be matched.  The ambiguity
  453. is exposed by considering the possible bindings for the subexpressions
  454. `\1' and `\2':
  455.      Possible outcomes:
  456.      
  457.          \1 == "xxx" \2 == ""
  458.          \1 == "xx" \2 == "x"
  459.          \1 == "x" \2 == "xx"
  460.          \1 == "" \2 == "xxx"
  461.    Posix tells us that the first outcome is the prefered one if the
  462. illustrated pattern is used alone (this is a consequence of the
  463. "leftmost longest" rule).  But Posix also says the answer may be
  464. different if the pattern is a sub-pattern of a larger pattern.  For
  465. example:
  466.      Pattern:
  467.          foo\(.*\)\(.*\)bar\2
  468.      Target string:
  469.          fooxxxbarxx
  470.    Now the only acceptable outcome is:
  471.          \1 == "x" \2 == "xx"
  472.    Three entry points provide a relatively simple interface to this
  473. moderately complicated situation:
  474.  - Internal Function: struct rx_solutions * rx_basic_make_solutions
  475.           (struct rx_registers * regs, struct rexp_node * expression,
  476.           struct rexp_node ** subexps, int start, int end, struct
  477.           rx_context_rules * rules, char * str)
  478.  - Internal Function: void rx_basic_free_solutions (struct rx_solutions
  479.           * solns);
  480.  - Internal Function: enum rx_answers rx_next_solution (struct
  481.           rx_solutions * solns)
  482.  - Internal Function: void rx_basic_free_solutions (struct rx_solutions
  483.           * solns)
  484.      `make_solutions' returns a lazilly constructed stream of possible
  485.      solutions for a given regexp and target string.
  486.      `next_solution' constructs and returns the next solution from a
  487.      list returned by `make_solutions'.  Solutions are returned in order
  488.      of preferability according to the Posix spec.  So, the first
  489.      solution is the leftmost-longest, and the last, the
  490.      rightmost-shortest.
  491.      REGS is where subexpression extents are tracked.
  492.      EXPRESSION is the expression to solve.
  493.      SUBEXPS is as returned by `rx_posix_analyze_rexp'.
  494.      START and END are the integer addresses of the data to be compared
  495.      to the pattern.  A solution must match all characters starting at
  496.      START and ending at `END - 1'.
  497.      RULES are some bits that control the precise meaning of "^" and
  498.      "$".  See `"rxcontext.h"'.
  499.      STR is the data to be matched.  Note that anchoring operators can
  500.      cause the matcher to look beyond START and END when testing a
  501.      match.  It may make sense to pass START > 0, for example.
  502.      `make_solutions' returns a pointer to a solution list, or 0 if an
  503.      allocation fails.
  504.      `next_solution' returns a status which can be:
  505.           `rx_yes'    -- The pattern matches exactly.
  506.           `rx_maybe'    -- The pattern does not match, but might
  507.                      if more characters were added to the string.
  508.           `rx_no'    -- The pattern does not match and could not be
  509.                      made to match even by adding more characters.
  510.      In addition, REGS is filled in by `next_solution'.
  511.      Finally, `free_solutions' is used to release resources consumed by
  512.      a solution list.
  513. File: rx.info,  Node: Hairy Matches,  Next: NFA Functions,  Prev: Posixly Correct Matches,  Up: General Functions
  514. Hairy Matches and Suspendable Searches
  515. --------------------------------------
  516.    The functions `rx_basic_make_solutions' and
  517. `rx_basic_free_solutions' are used to find matches in a one-piece
  518. string.  More general entry points are provided for multi-piece strings,
  519. which may or may not be entirely available in memory at one time:
  520.  - Internal Function: struct rx_solutions * rx_make_solutions (struct
  521.           rx_registers * regs, struct rx_unfaniverse * verse, struct
  522.           rexp_node * expression, struct rexp_node ** subexps, int
  523.           cset_size, int start, int end, rx_vmfn vmfn, rx_contextfn
  524.           contextfn, void * closure)
  525.  - Internal Function: void rx_free_solutions (struct rx_solutions *
  526.           solns)
  527.      These functions are similar to their `_basic_' analogues, but
  528.      substitute some new parameters for the one piece string:
  529.      VMFN is a function provided by the caller that returns at least
  530.      part of the string being matched.
  531.      CONTEXTFN is a function provided by the caller that does the work
  532.      of the backreference operators, "^", and "$".
  533.      CLOSURE is data provided by the caller, passed through to vmfn and
  534.      contextfn.
  535.           typedef enum rx_answers (*rx_vmfn)
  536.                P((void * closure,
  537.               unsigned char ** burst, int * len, int * offset,
  538.               int start, int end, int need));
  539.           
  540.           typedef enum rx_answers (*rx_contextfn)
  541.                P((void * closure,
  542.               int type,
  543.               int start, int end,
  544.               struct rx_registers * regs));
  545.      `vmfn' is asked for a range of characters from START to END.  NEED
  546.      is in that range and is the only position that must be returned by
  547.      vmfn.  BURST, LEN, and OFFSET are output parameters.  OFFSET will
  548.      get the integer address of burst, and LEN the number of valid
  549.      characters in the burst.  VMFN may be asked for the empty string
  550.      from END to END and should be able to handle that case.
  551.      If `vmfn' provides the needed character, it should return `rx_yes'.
  552.      If `vmfn' can't provide the character now, but might be able to
  553.      later, it should return `rx_maybe'.  This will cause
  554.      `rx_next_solution' to quickly return `rx_maybe'.   If
  555.      `rx_next_solution' is called again, it will retry the call to vmfn
  556.      and possibly resume the search.
  557.      If `vmfn' can not provide the needed character, it should return
  558.      `rx_no'.  `rx_next_solution' will not normally ask for
  559.      out-of-range characters, so usually there is no good reason to
  560.      return `rx_no', but the code is supposed to be robust in case you
  561.      do.
  562.      The `contextfn' also returns a `yes/no/maybe' status.  It tests
  563.      whether the characters in START to END satisfy the operator TYPE.
  564.      `type' is an ascii value; one of the characters in "^$123456789".
  565. File: rx.info,  Node: NFA Functions,  Prev: Hairy Matches,  Up: General Functions
  566. NFA Functions and Super-NFA Functions
  567. -------------------------------------
  568.    Not really documented yet.
  569.      rx.h, rxnfa.h        -- translating an expression into an NFA.
  570.      
  571.      rxsuper.h        -- optimizing the NFA into a DFA, or at least
  572.                     an NFA with fewer branch points.
  573.      
  574.      rxanal.h        -- how to use DFAs to find longest matches,
  575.                     matches of a specific length, the shortest
  576.                     match, etc.
  577.      
  578.      rxsimp.h        -- Translating a Posix "regular
  579.                     expression" into a true regular expression
  580.                     that describes a superset language.
  581. File: rx.info,  Node: Rx Theory,  Next: Improvements to Make,  Prev: General Functions,  Up: Top
  582. Rx Theory
  583. =========
  584.    There are two match algorithms.  One is for truly regular regexps
  585. (those that can be reduced to a dfa).  The other is for non-regular
  586. regexps.
  587.    The dfa algorithm implements the idea suggested in `Compilers' by
  588. Aho, Sethi and Ullman:
  589.      [One] approach [to pattern matching regular expressions] is to use
  590.      a DFA, but avoid constructing all of the transition table by using
  591.      a technique called "lazy transition evaluation".  Here,
  592.      transitions are computed at run time [when] actually needed.
  593.      [T]ransitions are stored in a cache. [....] If the cache becomes
  594.      full, we can erase some previously computed transition to make
  595.      room for the new transition.
  596.    The implementation in Rx is generalized from that, but the above
  597. description covers what is used for Posix patterns.
  598.    The non-dfa algorithm implements a "recursive decomposition"
  599. technique described in email by Henry Spencer.  For a given pattern,
  600. this algorithm first checks to see if a simpler, superset language,
  601. DFA-pattern matches.  If it does, then this algorithm does the
  602. detail-work to see if the non-DFA pattern matches.
  603.    The detail work usually involves recursing on subpatterns.  For
  604. example, a concatentation of two subexpressions matches a string if the
  605. string can be divided into two parts, each matching one subexpression,
  606. in the right order.  More than one solution is often possible for a
  607. given pattern.  This ambiguity is the subject of the "leftmost longest"
  608. rules in the spec, and the back-tracking oriented stream-of-solution
  609. functions `rx_make_solutions', `rx_next_solution' and
  610. `rx_free_solutions'.
  611.      rxspencer.[ch]                 -- The non-DFA algorithm
  612.      rxanal.[ch] rxsuper.[ch] rxnfa.[ch]    -- The DFA algorithm
  613. File: rx.info,  Node: Improvements to Make,  Prev: Rx Theory,  Up: Top
  614. Improvements to Make
  615. ====================
  616.    An approximation of the GNU entry points is needed.  This can not
  617. easily be an exact approximation because the GNU entry points have no
  618. function for freeing a compiled expression - they assume that compiled
  619. expressions can be freed using a single call to "free(3)".  For that
  620. reason, do not use the names of the old GNU entry points ...use "rx_"
  621. instead.
  622.    This version of Rx hasn't been profiled and tuned.
  623.    It might be nice to have some C++ types to hide reference counting
  624. and provide handy constructors for rexp_nodes and nfa parts.
  625.    Right now, the regexp->regular regexp mapping in rxsimp.[ch] is
  626. cached for a particular input expression.  I think it would probably be
  627. a big win in many situations if it were cached, like unique nfas (c.f.
  628. rxunfa.[ch]), for equivalent expressions.
  629.    It would speed up matching to lift the non-regular constructs to the
  630. top of the syntax tree.   e.g., if you have:
  631.      pattern:  "abc$"
  632.      
  633.      syntax tree: (concat (cset "a")
  634.                       (concat (cset "b")
  635.                       (concat (cset "c")
  636.                           (operator "$"))))
  637.    it involves a lot more work (in "next_solution) than if you have the
  638. equivalent:
  639.      same pattern:  "abc$"
  640.      
  641.      syntax tree: (concat (concat (cset "a")
  642.                       (concat (cset "b")
  643.                           (cset "c")))
  644.                   (operator "$"))
  645.    in fact, while doing that, notice that subtrees of nothing-but-concat
  646. can conceivably be optimized so that next_solution just uses "strcmp".
  647.    For that matter, a tree which is a disjunction of conjunction (a
  648. tree of "|" whose leaves are trees of concat nodes) could be optimized
  649. to use a table method (Boyer/Moore?).  Again, this would be for
  650. next_solution but might involve adding stuff to rx_posix_analyze_rexp.
  651.    As more and more optimizations are added, programmers should be given
  652. simple control over which optimizations are important for a particular
  653. pattern.  For example, packages in emacs often include a few regexps
  654. that are used heavily - it would be worth the trouble to arrange for
  655. those regexps to be compiled specially.
  656.    Static compilation of regexps is mostly a job for lex, but posix
  657. patterns are more general and have a nicer interface.  What's more, it'd
  658. be nice to have the benefits of static compilation even for dynamicly
  659. loaded regexps (e.g., imagine if when an emacs lisp file is
  660. byte-compiled, the regexps it contains are also compiled).
  661.    A lot of optimizations apply to just syntax trees.  One approach to
  662. static compilation is to make an ugly but fast-reading syntax for trees,
  663. and a printer for that syntax.  Then, after optimiztaions, a pattern
  664. could be stored as a string and later read back in, already optimized.
  665.    A similar trick could be done for the nfa built in rxnfa.c.
  666.    next_solution already considers the length of a fixed-length
  667. subexpression, but many more lenght optimizations are possible.  I'd
  668. guess these will pay off well.
  669. Tag Table:
  670. Node: Top
  671. Node: Posix Entry Points
  672. Node: POSIX Regexp Compilation
  673. Node: Flags for POSIX Regexps
  674. Node: Matching POSIX Regexps
  675. Node: Regexp Subexpressions
  676. Node: Subexpression Complications
  677. 10740
  678. Node: Regexp Cleanup
  679. 13096
  680. Node: Performance Considerations
  681. 15419
  682. Node: Avoiding Redundant Compilations
  683. 15989
  684. Node: Controlling Memory Use
  685. 18120
  686. Node: Semantic Tests
  687. 18719
  688. Node: Running the Tests
  689. 19445
  690. Node: Adding New Tests
  691. 20369
  692. Node: General Functions
  693. 21121
  694. Node: Compiling Expressions
  695. 21775
  696. Node: Posixly Correct Matches
  697. 24531
  698. Node: Hairy Matches
  699. 28136
  700. Node: NFA Functions
  701. 31078
  702. Node: Rx Theory
  703. 31742
  704. Node: Improvements to Make
  705. 33591
  706. End Tag Table
  707.