REF REGEXP                                     Jonathan Meyer Sept 1992

       COPYRIGHT University of Sussex 1993. All Rights Reserved.

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
<<<<<<<<<<<<<<<<<<<                              >>>>>>>>>>>>>>>>>>>>>>>
<<<<<<<<<<<<<<<<<<<      REGULAR EXPRESSIONS     >>>>>>>>>>>>>>>>>>>>>>>
<<<<<<<<<<<<<<<<<<<                              >>>>>>>>>>>>>>>>>>>>>>>
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

This file describes the Poplog  regular expression matcher. The  regular
expression matcher is used in Ved and other Poplog facilities to perform
pattern-based (or `wildcard') searching in strings.

         CONTENTS - (Use <ENTER> g to access required sections)

  1   Introduction

  2   Poplog Regular Expressions
      2.1   The Escape Character
      2.2   Word Boundaries
      2.3   Ved Search Patterns
      2.4   Literal mode
      2.5   Long regular expressions

  3   Constructing Regular Expressions
      3.1   Single Character Matching
      3.2   Multi Character Matching
      3.3   Concatenation
      3.4   Sub-expressions
      3.5   Operators
      3.6   Ved Compatibility patterns
      3.7   Long Regular Expressions
      3.8   The Case Mode

  4   Compiling Regular Expressions

  5   Bracketed Sub-expressions

  6   Miscellaneous



---------------
1  Introduction
---------------

Regular expressions  are  a  powerful and  flexible  way  of  performing
pattern matching  in strings,  popularised by  UNIX facilities  such  as
grep, awk, vi, ed, sed, etc.

The Poplog regular expression matcher lets you to search Poplog  strings
and words using regular  expressions. You have  the option of  searching
from left-to-right  or  from right-to-left,  and  of case  sensitive  or
insensitive searching.

See REF * VEDSEARCH for  details of  how to use  regular expressions  in
Ved.  TEACH * REGEXP  gives  an  introduction  to  constructing  regular
expressions.




-----------------------------
2  Poplog Regular Expressions
-----------------------------

The main  differences  between  Poplog  regular  expressions  and  those
provided by the `C' library described in UNIX * REGEXP are:



2.1  The Escape Character
-------------------------

Because the backslash character `\' already has a meaning to the  Poplog
itemiser in strings, the Poplog regular expression compiler uses the `@'
(at) character as its escape code  instead of the `\' character used  by
the `C' regular expression matcher. This means that, in Poplog,  instead
of writing:

    \(hello\)

you write:

    @(hello@)



2.2  Word Boundaries
--------------------
The @< and @> operators can  be matched using * vedchartype rather  than
the more simplified approach used in the `C' regular expression matcher.
Using * vedchartype means that  word boundaries are language  sensitive,
and obey the rules of the Pop-11 itemiser.



2.3  Ved Search Patterns
------------------------
As well as  the regular  expression patterns  described in  UNIX * grep,
regexp_compile recognises the additional search patterns @a, @z, and @?.
These are provided for compatibility with exisiting search facilities in
Ved.



2.4  Literal mode
-----------------
Unlike UNIX regular expressions, in Poplog the characters $ ^ . * [  and
] stand for themselves, and  are not special wildcard characters  UNLESS
they are preceded by an escape (eg. @. or @*). Thus, in Poplog,  instead
of writing

    .*[abc]

you write:

    @.@*@[abc@]


2.5  Long regular expressions
-----------------------------
The regular expression matcher can handle regular expressions which span
more than one line of text. See Long Regular Expressions below.




-----------------------------------
3  Constructing Regular Expressions
-----------------------------------

This  section  describes  the   rules  used  for  constructing   regular
expressions.



3.1  Single Character Matching
------------------------------
The following one-character regular expressions match a single character:

   c    An ordinary character is a one-character regular expression that
        matches that character.

   @.   An escaped `.'  (period) is a  one-character regular  expression
        that matches any character except NEWLINE.

   @[string@]
        A non-empty  string of  characters  enclosed in  escaped  square
        brackets is a one-character regular expression that matches  any
        one character in that string.

        If, however,  the first  character of  the string  is a  `^'  (a
        circumflex  or  caret),  the  one-character  regular  expression
        matches  any  character   except  NEWLINE   and  the   remaining
        characters in the string. The `^' has this special meaning  only
        if it occurs first in the string.

        The `-' (minus) may be used  to indicate a range of  consecutive
        ASCII  characters;   for  example,   [0-9]  is   equivalent   to
        [0123456789]. The `-'  loses this special  meaning if it  occurs
        first (after an initial `^', if any) or last in the string.



3.2  Multi Character Matching
-----------------------------
The asterisk is used for multiple character matching:

   @*   Any one-character regular expression followed by escaped `*' (an
        asterisk) is  a regular  expression that  matches zero  or  more
        occurrences of the one-character regular expression.

        If there is any choice, the longest leftmost string that permits
        a match is chosen.



3.3  Concatenation
------------------
Single and multi character regular expressions can be concatenated  with
other regular expressions to form  compound expressions which match  the
concatenation of the strings  matched by each  component of the  regular
expression. Thus you can build complex regular expressions by  combining
one or more single and multi character regular expressions.



3.4  Sub-expressions
--------------------
Regular expressions can  contain up to  nine sub-expressions,  specified
using the @( @) brackets:

   @( and @)
        A regular expression enclosed between the character sequences @(
        and  @)  matches  whatever  the  unadorned  regular   expression
        matches. See @n below.

You  can refer back to a sub-expression using the @n expression:

   @N   The expression @N  (where N  is a  digit 1-9)  matches the  same
        string of characters  as was matched  by an expression  enclosed
        between @( and @) earlier in the same regular expression.

        The sub-expression  specified is  that  beginning with  the  nth
        occurrence of @( counting from the left.

        For example, the expression ^@(.*@)@1$ matches a line consisting
        of two repeated appearances of the same string.



3.5  Operators
--------------
The following special operators can be used in regular expressions:

   @<   The  sequence  @<  in   a  regular  expression  constrains   the
        one-character regular expression  immediately following it  only
        to match something at the beginning of a "word"; that is, either
        at the beginning of a line,  or just before a letter, digit,  or
        underscore (_) and after a character  not one of these (but  see
        the description of the FLAGS argument to regexp_compile).

   @>   The  sequence  @>  in   a  regular  expression  constrains   the
        one-character regular expression  immediately following it  only
        to match something at  the end of a  "word"; that is, either  at
        the end of a line, or just before a character which is neither a
        letter, digit, nor  underscore (_) (but  see the description  of
        the FLAGS argument to regexp_compile).

   @{m@}
   @{m,@}
   @{m,n@}
        A regular  expression  followed  by @{m@},  @{m,@},  or  @{m,n@}
        matches a range  of occurrences of  the regular expression.  The
        values of m and n must  be non-negative integers less than  256.

            @{m@}   matches exactly m  occurrences;
            @{m,@}  matches at  least m occurrences;
            @{m,n@} matches any number of occurrences between m and  n
                    inclusive.

        Whenever a choice exists, the regular expression matches as many
        occurrences as possible.

   @^   An escaped circumflex or caret (^) at the beginning of an entire
        regular expression constrains that  regular expression to  match
        an initial segment of a line.

   @$   An escaped currency symbol ($) at  the end of an entire  regular
        expression constrains that regular  expression to match a  final
        segment of a line.

Note that the construction

    @^entire regular expression@$

constrains the entire regular expression to match the entire line.



3.6  Ved Compatibility patterns
-------------------------------
The following patterns can be  specified in regular expressions for  Ved
compatibility:

   @a   The same as @^ at the start an expression.

   @z   The same as @$ at the end of an expression.

   @?   The same as @. in an expression, ie. it matches any character.

   @@   This matches the single character "@".

   @C   Where C is one of `/', `\', `"', or ``' matches C.



3.7  Long Regular Expressions
-----------------------------
Regular expressions are, by convention, used to perform pattern matching
against single lines in  a text file -  a single regular expression  can
match at most all of the characters of one line in a file.

It is useful to be able to  search for patterns which span line  breaks.
For example, you might wish to  search for text which started with  'if'
on one line and 'endif' on the next line.

The Poplog regular expression matcher provides support for multiple line
(`long')  regular  expressions.  These   work  by  deviding  a   regular
expression for  matching  several  lines into  several  smaller  regular
expressions each matching a  single line. Line  breaks are indicated  in
the regular expression by writing `@$' (or `@z', ie. constrain to end of
line) followed immediately by `@^' (or  `@z', ie. constrain to start  of
line). For example:

    dog@$@^cat

Matches text which contains 'dog', followed by a line break, followed by
'cat'. The long-string expression matcher does not allow sub-expressions
to span over line breaks. Thus the following expression is illegal:

    '@(some text @z@a and some more text@)'

Instead you must write:

    '@(some text @)@z@a@( and some more text@)'



3.8  The Case Mode
------------------
You can turn  on and off  case sensitivity  in the middle  of a  regular
expression using @i and @c.

    @i  makes the matcher ignore the case of the characters that follow.

    @c  turns on case sensitivity, making the matcher examine case.




--------------------------------
4  Compiling Regular Expressions
--------------------------------

regexp_compile(regexp_string) -> (error_info, regexp_p)      [procedure]
regexp_compile(regexp_string, flags, delim_char)
                              -> (error_info, regexp_p)
        Takes a regular expression regexp_string (a string or word)  and
        compiles ito  into  an  efficient  internal  representation  for
        performing regular expression string comparisons.

        The optional flags argument  is an integer  whose bits have  the
        following meanings:

            Bit     Meaning
            ---     -------
             1      If set,  the resulting  regexp_p  will not  be  case
                    sensitive.  If   clear,   then  the   matcher   will
                    distinguish between upper and lower case  characters
                    See REF * isuppercode, * islowercode.

             2      If set, the regular expression will only match  non-
                    embedded items, otherwise it will match embedded  or
                    non-embedded items. This implicitly inserts a @< and
                    @> at the start  and end of  the expression, and  is
                    used for " and ` searches in Ved.

             3      If set, the pattern $ (or @z) followed by ^ (or  @a)
                    will be  treated  as  a line  break,  and  a  `long'
                    regular expression matcher  will be  built. See  the
                    section on 'Long Expressions' below.

             4      If set, word  boundaries are  identified in  strings
                    passed  to  the  regexp_p  using  the  * VEDCHARTYPE
                    mechanism, otherwise  they are  identified with  the
                    simpler algorithm used by the `C' regular expression
                    matcher (where words are  formed from letter  codes,
                    number codes, or the underscore (_) character).
                    See        REF * isalphacode,        * isnumbercode,
                    REF * pop_character_set.

             5      If set, occurrences of a tab character (`\t`,  ASCII
                    9) in strings passed to the regexp_p are expected to
                    be followed by  a number of  padding tab  characters
                    determined by vedindentstep.  This flag is  provided
                    to allow Ved buffer strings containing hard tabs  to
                    be      searched.      See      REF * veddecodetabs,
                    REF * vedencodetabs, HELP * vednotabs.

        If the flags argument is omitted, all bits default to 0.

        The optional delim_char  is an ASCII  character code that  marks
        the end  of the  regular  expression. regexp_compile  will  stop
        parsing regexp_string once  it reaches  a delim_char  character.
        For example, in an editor like Ved this character would  usually
        be `/`. If delim_char is false, or if the delim_char argument is
        omitted, the whole of the regexp_string is used.

        If  regexp_string  can  be  successfully  parsed  and  compiled,
        error_info will be false and regexp_p will be a procedure of the
        form:

            regexp_p(n, string, len, back) -> (start_index, num_chars)

        The integer n specifies  where to start  searching in string  (a
        string or word), and len specifies how many characters should be
        examined. If len  is false,  the rest of  the string  from n  is
        used.

        If back  is false,  searching  is done  from  left to  right  in
        string. If it is true, searching is done from right to left (ie.
        backwards) starting at the  position n + len  -1 (or the end  of
        the string if  len is false).  If it  is an integer,  it is  the
        subscript in the string where backward searching starts.

        On completion,  start_index  and  num_chars  indicate  where  in
        string the regular expression matches.  If there is no match  in
        string, both start_index and num_chars will be false.  Otherwise
        the matching portion of the string can be obtained using:

            substring(start_index, num_chars, string)

        For example,

            vars err, searchp;

            ;;; the regular expression is 'd@.@*s' - which matches a 'd'
            ;;; followed by any number of characters followed by 's'

            regexp_compile('d@.@*s') -> (err, searchp);

            searchp =>
            ** <procedure d@.@*s>

            searchp(1, 'this string wont match', false, false) =>
            ** false false ;;; no match can be found

            searchp(1, 'this string does match', false, false) =>
            ** 13 4

            ;;; there was a match - use * substring to identify it:
            substring(13, 4, 'this string does match') =>
            ** does

        Note that  the  * pdprops of  regexp_p  is set  to  the  regular
        expression string that it matches.

        If regexp_string cannot be successfully parsed and compiled into
        a regular expression, error_info will be a string containing  an
        error message, and regexp_p will be a procedure which mishaps if
        called (regexp_p  will always  be a  procedure so  that you  can
        reliably   assign   it   identifiers   whose   * identtype    is
        "procedure"). For example:

            regexp_compile('@[a-z') -> (err, searchp);
            err =>
            ** '[] imbalance'

            regexp_compile('@[a-z@]') -> (err, searchp);
            err =>
            ** <false>

        A common usage of regexp_compile is therefore:

            if (regexp_compile(string) -> searchp ->> err) then
                mishap(string, 1, err);
            endif;

        Long Expressions
        ----------------
        You set bit 5 of the flags argument to regexp_compile to  enable
        compilation of long regular expressions. The resulting  regexp_p
        procedure is of the form:

            regexp_p(n, string_1, string_2, ..., string_m, len, back)
                    -> (start_index, num_chars)

        Where  the   integer  m   is  determined   by  adding   one   to
        regexp_break_count, n  is an  index in  string_1 where  matching
        starts, and len is  the number of  characters of string_m  which
        are included in  the search. If  m is one  (ie. the search  only
        spans one line), then len characters starting from n in string_1
        are used. len may be false, in which case as many characters  as
        possible from  string_m are  used. All  characters from  strings
        string_2 to string_m-1 are used. back is as before.

        If a  match is  found, start_index  is the  index into  string_1
        where  the  match  starts,  and  num_chars  is  the  number   of
        characters in string_m that are included in the match. Otherwise
        start_index and num_chars are both false.

        If m is 1, the matching portion of text is retrieved using:

            substring(start_index, string_1, num_chars)

        Otherwise, it is:

            allbutfirst(start_index - 1, string_1)
            <> string_2 <> ... <> substring(1, num_chars, string_m)




----------------------------
5  Bracketed Sub-expressions
----------------------------

Regular expressions can have  up to 9 sub-expessions  enclosed in @(  @)
brackets. You can find out how many sub-expessions a regular  expression
has, and also where those sub-expessions matched in the last search.

regexp_subexp_count(regexp_p) -> n                           [procedure]
        Returns the number  of bracketed @(  @) sub-expessions found  in
        the regular  expression  that  was  compiled  into  regexp_p  by
        regexp_compile.  n  will  be  0   if  there  are  no   bracketed
        expressions. The current implementation allows up to 9 of  these
        bracketed expressions.


regexp_subexp(n, regexp_p) -> (start_index, len, string)     [procedure]
        After regexp_p has  been successfully applied  to a string  (ie.
        the string can  be matched against  the regular expression),  an
        internal table is set to the  locations in the string where  any
        bracketed  @(  @)  sub-expessions  in  the  regular   expression
        matched.  You   can  access   elements  of   this  table   using
        regexp_subexp. It  returns the  start index  and length  of  the
        substring enclosed by the  n'th @( @)  pattern. It also  returns
        the string which the sub-expression was matched against.

        For example:

            ;;; compile a regular expression
            vars procedure searchp;

            regexp_compile('h@(....@) world') -> (,searchp);

            searchp =>
            ** <procedure h@(....@) world>

            ;;; apply searchp to the string 'hello world':

            searchp(1, 'hello world', false, false) =>
            ** 1 11 ;;; ie. the whole string matches

            ;;; find out where the first bracketed expression matched:
            regexp_subexp(1, searchp) =>
            ** 2 4 hello world

            substring(regexp_subexp(1, searchp)) =>
            ** ello




----------------
6  Miscellaneous
----------------

isregexp(item) -> bool                                       [procedure]
        true if item is a regular expression matching procedure compiled
        by regexp_compile.


regexp_delimeter(regexp_p) -> n                              [procedure]
        Returns the index of the location of the delimeter character  in
        the string  regexp_string  passed to  regexp_compile  to  create
        regexp_p, or false  in no  delimeter character  appeared in  the
        string.


regexp_break_count(regexp_p) -> n                            [procedure]
        Returns the number  of line  breaks that appear  in the  regular
        expression encoded by regexp_p.  For any expression which  spans
        only a single line, this will  be 0. For an expression  spanning
        two lines, this will be 1, etc.


regexp_anchored(regexp_p) -> bool                            [procedure]
        true if the regexp_p expression includes an @a, @z, @^ or @$  to
        anchor the expression to the start or end of a line.




--- C.all/ref/regexp
--- Copyright University of Sussex 1993. All rights reserved.
