home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 278.lha / RegexLibrary_v1.0 / ReadMe < prev    next >
Text File  |  1989-08-06  |  25KB  |  585 lines
  1.                          regex.library - v1.0
  2.                     An Amiga Shared Library of the
  3.                     GNU Regular Expression Package
  4.  
  5.                 Ported by Edwin Hoogerbeets 24/07/89
  6.  
  7. This collection of files may be copied and distributed under the GNU Public
  8. Licence. See the comment at the top of regex.c for details.
  9.  
  10. Adapted from Elib by Jim Mackraz, mklib by Edwin Hoogerbeets, and the
  11. GNU regular expression package by the Free Software Foundation.
  12.  
  13.  
  14. A General View of How it is Used:
  15.  
  16.   A regular expression is a concise method of describing a pattern of
  17.   characters in a string. By use of special wildcards, almost any pattern
  18.   can be described. A regular expression pattern can be used for searching
  19.   strings in such programs as editors or other string handling programs.
  20.  
  21.   A regular expression pattern must first be compiled into a form more
  22.   easily understood by the matching routines. The compiled form is stored
  23.   in a buffer structure called `struct re_pattern_buffer.' The buffer must
  24.   first be initialized to allocate memory or resources. The pattern is
  25.   compiled into this buffer. Strings can then be matched against the
  26.   compiled regular expression as many times as desired. When the matching
  27.   is done, the buffer is terminated, and the program can exit.
  28.  
  29.   There are two parts to the source: the linkable libraries and the Amiga
  30.   shared library routines. The linkable libraries contains the
  31.   non-re-entrant routines and the glue code that allows access to the
  32.   shared library routines. The shared library contains routines that
  33.   compile and match regular expressions.
  34.  
  35.   To use the library, copy regex.library to your libs: directory and simply
  36.   execute a program that uses the library, such as tinygrep.
  37.  
  38.  
  39. GNU Regular Expressions:
  40.  
  41.   The following table details the various special characters understood in
  42.   each of the grep and egrep style regular expressions:
  43.  
  44.     (grep)  (egrep)     (explanation)
  45.       .        .        matches any single character except newline
  46.       \?       ?        postfix operator; preceeding item is optional
  47.       *        *        postfix operator; preceeding item 0 or more times
  48.       \+       +        postfix operator; preceeding item 1 or more times
  49.       \|       |        infix operator; matches either argument
  50.       ^        ^        matches the empty string at the beginning of a line
  51.       $        $        matches the empty string at the end of a line
  52.       \<       \<       matches the empty string at the beginning of a word
  53.       \>       \>       matches the empty string at the end of a word
  54.      [chars] [chars]    match any character in the given class; if the
  55.                         first character after [ is ^, match any character
  56.                         not in the given class; a range of characters may
  57.                         be specified by <first>-<last>; for example, \W
  58.                         (below) is equivalent to the class [^A-Za-z0-9]
  59.      \( \)    ( )       parentheses are used for grouping and to override
  60.                         operator precedence
  61.      \<1-9>   \<1-9>    \<n> matches a repeat of the text matched earlier
  62.                         in the regexp by the subexpression inside the
  63.                         nth opening parenthesis
  64.       \        \        any special character may be preceded by a backslash
  65.                         to match it literally
  66.  
  67.   Operator precedence is (highest to lowest) ?, *, and +, concatenation,
  68.   and finally |.  All other constructs are syntactically identical to
  69.   normal characters.
  70.  
  71.  
  72. Writing a C Program That Uses Regular Expressions:
  73.  
  74.   To write a program that uses the library, include the header file regex.h
  75.   at the top of your source. This declares the data structures and function
  76.   return types for you.
  77.  
  78.   You must do an OpenLibrary() call on regex.library and assign the pointer
  79.   obtained to the external variable RegexBase. The pointer RegexBase is
  80.   then used to find functions within regex.library, and thus RegexBase must
  81.   be valid before using any of these library routines. A RegexBase variable
  82.   is already provided in regex.lib. When linking, give the -lregex flag to
  83.   include regex.lib (the linkable library code).
  84.  
  85.   To use the routines, first declare a struct re_pattern_buffer variable
  86.   and call re_initialize_buffer() with a pointer to this buffer. (Specific
  87.   details of the regex functions are listed below.)
  88.  
  89.   Then, determine a regular expression you wish to compile, perhaps from
  90.   user input. Call the function re_compile_pattern() with a pointer to your
  91.   buffer and the string you wish to compile. Now the buffer will contain
  92.   the compiled regular expression ready for matching.
  93.  
  94.   Next, you can search for your pattern in any given text by calling
  95.   re_search() with the compiled buffer and the string you wish to search
  96.   on. This will locate the regular expression anywhere in the string you
  97.   passed to it, within the bounds specified.
  98.  
  99.   If you are looking for an exact match, however, re_match() is the
  100.   function you want. It returns true when the regular expression matches
  101.   the string starting at the character specified.
  102.  
  103.   When you are done with the buffer, you must call re_terminate_buffer()
  104.   to reclaim all memory and resources used by the library.
  105.  
  106.   Two programs, tester.c and tinygrep.c, are included in the distribution
  107.   as simple examples of programming with the library.
  108.  
  109.   Tester allows you to enter grep style regular expressions and match them
  110.   against a string.
  111.  
  112.   Tinygrep is a small implementation of the popular grep program that uses
  113.   the regex library to search for patterns in text files. However, it is
  114.   not overall as fast as GNU grep, or even Manx grep. This is because these
  115.   other programs handle their slowest part (input) much better. To make
  116.   tinygrep faster, the regular expression searching could be performed
  117.   directly on the input buffer.
  118.  
  119.  
  120. Assembler Support:
  121.  
  122.   If you are writing in assembler instead of C, the registers expected for
  123.   function parameters are listed along with the function descriptions
  124.   below.
  125.  
  126.   The sequence of calls to the functions in regex.library described for C
  127.   still apply. However, instead of using the glue code to call the library,
  128.   you should call the regex.library functions directly following this
  129.   example:
  130.  
  131.       ; assembler example of calling re_terminate_buffer()
  132.       ;
  133.  
  134.       ; define the library offsets
  135.       include 'regex.i'
  136.  
  137.       ; setup arguments in appropriate registers here
  138.       ; d0 is where the buffer pointer parameter should go
  139.  
  140.       move.l  bufp,d0
  141.  
  142.       ; get the address of the library and jump to the appropriate point
  143.  
  144.       move.l  _RegexBase,a6
  145.       jsr     _LVOre_terminate_buffer(a6)
  146.  
  147.       ; d0 should now contain the result
  148.  
  149.   To use different functions, replace the re_terminate_buffer part of the
  150.   jsr line with the function name you wish to call. The _LVO with the
  151.   function name is expanded to a number which is the offset from register
  152.   a6 where the address of the function you are calling can be found.
  153.  
  154.  
  155. Functions in regex.library:
  156.  
  157.   This is a more detailed description of each of the functions and
  158.   variables offered by the regex package. These functions are available
  159.   from C by linking with the regex.lib.
  160.  
  161.   Regex offers the following entry points:
  162.  
  163.     D0                         D0   D1
  164.     char *re_initialize_buffer(bufp,table)
  165.     struct re_pattern_buffer *bufp;
  166.     char *table;
  167.  
  168.       This function is used to initialize a pattern buffer `bufp' that is
  169.       used to compile regular expressions. Declare a variable of type
  170.       `struct re_pattern_buffer' variable on the stack or dynamically
  171.       allocate room for it, and pass a pointer to the new memory to
  172.       re_initialize_buffer(). The fields of the buffer are filled in for
  173.       you.
  174.  
  175.       The `table' parameter is a pointer to a translation table used to
  176.       equate characters during matching. When a character is matched, it is
  177.       used as an index into this table to find the resulting character. One
  178.       use for this might be to translate all vowels to the character @, so
  179.       that @ can be used in a regular expression to match any vowel. If the
  180.       table parameter is NULL, no translation is performed on the
  181.       characters, and each character is matched literally. (See the
  182.       __Upcase table below for another example)
  183.  
  184.       If re_initialize_buffer succeeds, a NULL pointer is returned. If an
  185.       error occurs, a pointer to one of the following fixed strings is
  186.       returned:
  187.  
  188.         "No buffer"          - you passed a NULL pointer, not a pointer
  189.                                to a regular expression buffer
  190.         "Memory exhausted"   - Not enough memory in the system to
  191.                                initialize the buffer
  192.  
  193.  
  194.     D0                        D0
  195.     LONG  re_terminate_buffer(bufp)
  196.     struct re_pattern_buffer *bufp;
  197.  
  198.       This function must be called to free the memory and resources
  199.       allocated during the initialize routine. It is not fatal if this
  200.       routine is not called before the your program exits, but all the
  201.       memory will not be returned to the system. (for which you will get
  202.       royalled flamed on the nets, believe me! 8-)
  203.  
  204.       A value of 1 is returned for a successful termination, and 0 for the
  205.       error condition. An error (zero) means you passed a NULL pointer to
  206.       the function.
  207.  
  208.  
  209.     D0                       D0       D1    A0    A1
  210.     char *re_compile_pattern(pattern, size, bufp, ob)
  211.     char *pattern;
  212.     long size, ob;
  213.     struct re_pattern_buffer *bufp;
  214.  
  215.       This function compiles a regular expression `pattern' with length
  216.       `size' into the properly initialized buffer `bufp.'
  217.  
  218.       Different syntaxes for regular expressions exist. The syntax you
  219.       would like is specified in the `ob' parameter. The ob parameter can
  220.       be one of the following defined flags:
  221.  
  222.       (In general, the presence of one of the flags below indicates that
  223.       the character referenced should be treated as a wildcard. If the flag
  224.       is absent, then the character is not treated as a wildcard.)
  225.  
  226.       RE_NO_BK_PARENS
  227.  
  228.         Treat parentheses as the grouping wildcard. To specify a literal
  229.         parenthesis the pattern \( or \) is needed. If this flag is left
  230.         out, \( and \) are the grouping wildcards and ( and ) match the
  231.         literal parentheses.
  232.  
  233.       RE_NO_BK_VBAR
  234.  
  235.         Treat the vertical bar as the "or"-operator, and \| as a literal
  236.         vertical bar. If this flag is left out, the syntax is reversed.
  237.  
  238.       RE_BK_PLUS_QM
  239.  
  240.         Treat the plus and the question mark characters as wildcards, and
  241.         \+ and \? as the literal characters.
  242.  
  243.       RE_TIGHT_VBAR
  244.  
  245.         Bind the vertical bar tighter than the ^ and $ operators. This
  246.         means that the vertical bar takes precedence over the ^ and $ in a
  247.         single expression.
  248.  
  249.       RE_NEWLINE_OR
  250.  
  251.         Treat the newline character `\n' as a an "or"-operator. This might
  252.         be useful in a program such as fgrep.
  253.  
  254.       RE_CONTEXT_INDEP_OPS
  255.  
  256.         Treat certain wildcards characters as wildcards only in certain
  257.         contexts. Specifically, this applies to:
  258.  
  259.           ^ - only special at the beginning of a line, or after ( or |
  260.           $ - only special at the end of a line, or before ) or |
  261.           *, +, ? - only special when not after the beginning of a line,
  262.                     (, or |
  263.  
  264.       Some programs have a combination of the above flags as their default.
  265.       The following flags give the syntax of some well-known Unix
  266.       utilities in terms of the above flags:
  267.  
  268.       RE_SYNTAX_AWK      - emulate awk regular expressions
  269.       RE_SYNTAX_EGREP    - emulate egrep regular expressions
  270.       RE_SYNTAX_GREP     - emulate grep regular expressions
  271.       RE_SYNTAX_EMACS    - emulate emacs-like regular expressions
  272.  
  273.       If re_compile_pattern() is successful in compiling the given regular
  274.       expression, a NULL pointer is returned. If an error condition occurs,
  275.       a pointer to one of the following fixed strings is returned.
  276.  
  277.         "Invalid regular expression"          - eg: "\(ab\)*123\" has an
  278.                                                     invalid trailing '\'
  279.  
  280.         "Unmatched \("                        - eg: "\(ab*123" has no
  281.                                                     closing "\)"
  282.  
  283.         "Unmatched \)"                        - eg: "ab\)*123" has no
  284.                                                     opening "\("
  285.  
  286.         "Premature end of regular expression" - eg: "foo[1-9" has no ']'
  287.  
  288.         "Nesting too deep"                    - you have too many levels
  289.                                                 of groupings: "\( \)"
  290.  
  291.         "Regular expression too big"          - the regular expression
  292.                                                 needed more than 64K to
  293.                                                 store -- Try using a
  294.                                                 shorter one!
  295.  
  296.         "Memory exhausted"                    - Close some windows!
  297.  
  298.  
  299.     D0                       D0
  300.     LONG  re_compile_fastmap(bufp)
  301.     struct re_pattern_buffer *bufp;
  302.  
  303.       If the initial part of a pattern does not match the string starting
  304.       at a certain position, the whole expression will not match the string
  305.       starting at that position.
  306.  
  307.       On this basis, it is possible to compute which characters can
  308.       possibly be found at the start the pattern. If a string does not
  309.       start with one of these characters, it cannot match the pattern.
  310.       These collections of possible starting characters are called a
  311.       fastmap.
  312.  
  313.       Fastmaps make pattern searching much faster by reducing the number of
  314.       failed full matches.
  315.  
  316.       This function takes a compiled pattern in buffer `bufp' and computes
  317.       a fastmap for it, which is stored in the `fastmap' field of the
  318.       buffer. The fastmap is then used in the re_search() function while
  319.       searching a string for a regular expression. If this function is
  320.       not called before a re_search(), then re_search() will call it
  321.       for you.
  322.  
  323.  
  324.     D0              D0     D1      A0    A1        D2     D3
  325.     LONG  re_search(pbufp, string, size, startpos, range, regs)
  326.     struct re_pattern_buffer *pbufp;
  327.     char *string;
  328.     long size, startpos, range;
  329.     struct re_registers *regs;
  330.  
  331.       This function searches the string `string' of size `size' for the
  332.       regular expression previously compiled to the buffer `pbufp.' The
  333.       `startpos' parameter is the index into the string to start searching.
  334.       If the search is unsuccessful at startpos, it is tried at startpos+1
  335.       and so forth. The `range' parameter tells how far from the start
  336.       position to go before failing. It is up to the caller to make sure
  337.       that range is not so large as to take the starting position outside
  338.       of the input strings. If the range parameter is negative, then the
  339.       search will proceed from startpos to startpos-1 and so forth until
  340.       -range positions have been checked.
  341.  
  342.       The `regs' parameter is a place to store information about exactly
  343.       what was matched if the search is successful, including
  344.       subexpressions. A subexpression is any part of a regular expression
  345.       bounded by parentheses. The `start' field of a re_registers structure
  346.       is an array of character pointers to the beginning of each
  347.       subexpression matched. The `end' field is an array of character
  348.       pointers to the character just past the end of each subexpression.
  349.  
  350.       For example,
  351.  
  352.         regs->start[0] to regs->end[0] is the entire expression matched
  353.  
  354.         regs->start[1] to regs->end[1] is the subexpression contained
  355.           in the first \( \) grouping if there is one
  356.  
  357.         regs->start[2] to regs->end[2] is the subexpression contained
  358.           in the second \( \) grouping if there is one
  359.  
  360.       and so on. If a NULL pointer is passed as the `regs' parameter,
  361.       no information on matching is stored.
  362.  
  363.       There is a maximum of NREGS groupings available. If you really need
  364.       more, you can change the definition of NREGS in regex.h and recompile
  365.       the library.
  366.  
  367.       The return value is the position of the start of the of the string
  368.       that matches the regular expression. If there is no match, a -1 is
  369.       returned. If there was some internal error, a -2 is returned.
  370.  
  371.       The function re_search() depends on re_search_2() below to do
  372.       its grunt work.
  373.  
  374.  
  375.     D0                D0     D1       D0     A1       D2     D3
  376.     LONG  re_search_2(pbufp, string1, size1, string2, size2, startpos,
  377.  
  378.                       D4     D5    D6
  379.                       range, regs, mstop)
  380.     struct re_pattern_buffer *pbufp;
  381.     char *string1, *string2;
  382.     long size1, size2;
  383.     long startpos;
  384.     register long range;
  385.     struct re_registers *regs;
  386.     long mstop;
  387.  
  388.       This function works the same as re_search, with the exception that it
  389.       takes different arguments. The regular expression in the buffer
  390.       `pbufp' is searched for in the concatenation of `string1' and
  391.       `string2.' The parameters `size1' and `size2' are the lengths of
  392.       string1 and string2 respectively. The `startpos' is the starting
  393.       position of the search and the the `range' is how many characters
  394.       further to try the search, just as in re_search. The `regs' parameter
  395.       is a pointer to a re_registers structure which is space for storing
  396.       information about what exactly was matched.
  397.  
  398.       The return value is the position of the start of the of the string
  399.       that matches the regular expression. If there is no match, a -1 is
  400.       returned. If there was some internal error, a -2 is returned.
  401.  
  402.       See the description of the re_search() function for more details.
  403.  
  404.  
  405.     D0            D0     D1      A0    A1   D2
  406.     LONG re_match(pbufp, string, size, pos, regs)
  407.     struct re_pattern_buffer *pbufp;
  408.     char *string;
  409.     long size, pos;
  410.     struct re_registers *regs;
  411.  
  412.       This function matches the compiled regular expression in `pbufp'
  413.       against `string,' which is of length `size.' The `pos' parameter is
  414.       the position in the string to start the matching. The `regs'
  415.       parameter points to space to store information about the part of the
  416.       string that matched the regular expression. See the description of
  417.       the re_search() function for more details of the `regs' parameter.
  418.  
  419.       The return value is the length of the string that matches the regular
  420.       expression. If there is no match, a -1 is returned. If there was some
  421.       internal error, a -2 is returned.
  422.  
  423.       The difference between re_search() and re_match() is that re_search()
  424.       finds the regular expression anywhere in a certain range of a string
  425.       by looking at different starting positions, while re_match() only
  426.       looks at the starting position specified.
  427.  
  428.     D0              D0     D1       A0     A1       D2     D3   D4    D5
  429.     LONG re_match_2(pbufp, string1, size1, string2, size2, pos, regs, mstop)
  430.     struct re_pattern_buffer *pbufp;
  431.     unsigned char *string1, *string2;
  432.     long size1, size2;
  433.     long pos;
  434.     struct re_registers *regs;
  435.     long mstop;
  436.  
  437.       This function is much like re_match(), except that two strings are
  438.       specified as parameters. The function matches the compiled regular
  439.       expression in `pbufp' against the concatenation of `string1' and
  440.       `string2,' which are of length `size1' and `size2' respectively. The
  441.       `pos' parameter is the position in the string to start the matching.
  442.       The `regs' parameter points to space to store information about the
  443.       part of the string that matched the regular expression. See the
  444.       description of the re_search() function for more details of the
  445.       `regs' parameter.
  446.  
  447.       The return value is the length of the string that matches the regular
  448.       expression. If there is no match, a -1 is returned. If there was some
  449.       internal error, a -2 is returned.
  450.  
  451.  
  452. Functions in regex.lib:
  453.  
  454.     The following entry points are for compatibility with the BSD Unix
  455.     regular expression package. The BSD regular expression package does not
  456.     fiddle with such piddly re-entrant ideas as user buffers, and thus a
  457.     static buffer is used for you when compiling regular expressions.
  458.  
  459.     If you are writing your program in assembler, you will have to link
  460.     with the aregex.lib as well as regex.lib to access these functions.
  461.     This is because these routines are written in C, and parameters must be
  462.     put on the stack. The glue code in aregex.lib does this for you. For
  463.     assembler programs, the entry points for these functions are the
  464.     function names without a leading underscore character. (ie. re_comp and
  465.     re_exec, instead of _re_comp and _re_exec)
  466.  
  467.     D0
  468.     char *re_BSD_initialize()
  469.  
  470.       This function initializes the internal buffer. This function should
  471.       be placed at the beginning of any program using the BSD entry points.
  472.  
  473.  
  474.     void  re_BSD_terminate()
  475.  
  476.       This function frees the system resources used by the initialize
  477.       routine. This function should be placed at the end of any program
  478.       using the BSD entry points.
  479.  
  480.  
  481.     D0             D0
  482.     char *re_comp( s )
  483.     char *s;
  484.  
  485.       Compile the pattern in the string `s' for use in subsequent matchings.
  486.       If the internal buffer has not been properly initialized, this
  487.       function will detect the condition and call re_BSD_initialize()
  488.       for you. This means it is not critical to call the initialize
  489.       routine, but it is a good idea anyway.
  490.  
  491.       If the string s is a NULL pointer, the previous regular expression
  492.       will be used.
  493.  
  494.       If the compilation is succesful, a NULL pointer is returned.
  495.       Otherwise, a pointer to one of fixed strings returned by
  496.       re_compile_buffer() is returned. (see the description of
  497.       re_compile_buffer() above for details.) As well, re_comp() may
  498.       return a pointer to the following string:
  499.  
  500.         "No previous regular expression" - re_BSD_initialize was never
  501.                                            called
  502.  
  503.  
  504.     D0             D0
  505.     LONG  re_exec( s )
  506.     char *s;
  507.  
  508.       Use the last compiled pattern to match against the string `s.'
  509.       Like re_search(), this function returns a -1 for no match, a -2 for
  510.       internal error, and the position of the beginning of the matched
  511.       string for a successful matching.
  512.  
  513.  
  514. Variables in regex.lib:
  515.  
  516.   The following variables are also provided in the linkable library for
  517.   programming convenience:
  518.  
  519.     struct RegexBase *RegexBase
  520.  
  521.       Assign the results of an OpenLibrary() on regex.library to this
  522.       variable. It is used to find the jump table in memory so that
  523.       the shared library routines can be executed.
  524.  
  525.  
  526.     char __Upcase[]
  527.  
  528.       This is a pre-defined translation table for use in a call to
  529.       re_initialize_buffer(). It is a translation table that turns
  530.       all lower case letters into upper case letters, effectively
  531.       making the regular expression case insensitive while matching.
  532.  
  533.  
  534. Still To Do:
  535.  
  536.   - providing a Modula II, Lattice, PDC and/or Draco linkable support
  537.     library
  538.  
  539.     Not having Modula II or Lattice, these are difficult for me to do right
  540.     now... However, if you do do any of these, I would be eager to hear
  541.     from you!
  542.  
  543.     I suspect the Lattice support would simply consist of a header file
  544.     of #pragmas, but I have little idea how that would work.
  545.  
  546.  
  547. Files:
  548.     alink.asm         - assembler glue code source for aregex.lib
  549.     aregex.lib        - interface between assembler and regex.library
  550.     interface.asm     - interface between assembler and C within
  551.                         regex.library
  552.     lib1.c            - BSD style entry points to regex.library
  553.     lib2.c            - default uppercase translation table
  554.     library.c         - main shared library routines of regex.library
  555.     library.h         - header for library.c
  556.     link.asm          - C glue code source for regex.lib
  557.     makefile          - makefile for Manx
  558.     malloc.c          - support routines for regex.library
  559.     ReadMe            - this file
  560.     regex.c           - regular expression code in regex.library
  561.     regex.h           - C header file for anything to do with regex
  562.     regex.i           - assembler header file for anything to do with regex
  563.     regex.lib         - interface code between C and regex.library
  564.     regex.library     - Amiga shared library
  565.     rtag.asm          - ROM tag code for regex.library
  566.     startup.asm       - modified small model startup code for regex.library
  567.     tester            - test program
  568.     tester.c          - source to the above
  569.     tinygrep          - small, almost-useful test program
  570.     tinygrep.c        - source to the above
  571.  
  572.  
  573. Please redirect any comments, criticisms or vivacious vixens:
  574.  
  575. Edwin Hoogerbeets
  576. Usenet: ehoogerbeets@rose.waterloo.edu        (school account until Aug '89)
  577.         or edwin@watcsc.waterloo.edu          (permanent account)
  578.         or w-edwinh@microsoft.uucp            (Sept '89 to Dec '89)
  579. CIS:    72647,3675                            (funds-dependent permanent 8-)
  580.  
  581. Remember, pillows don't hit people. People do.
  582.  
  583.  
  584.  
  585.