2
"\\input texinfo @c -*-texinfo-*-"
3
"@c %**start of header"
6
"@setchapternewpage odd"
9
"@c This title page illustrates only one of the"
10
"@c two methods of forming a title page."
16
"@center except the chapter \"Posix Entry Points\" "
17
"@center from @emph{The GNU C Library} reference manual"
18
"@center by Sandra Loosemore"
20
"@center Richard M. Stallman, Roland McGrath, and Andrew Oram"
22
"@c The following two commands"
23
"@c start the copyright page."
25
"@vskip 0pt plus 1filll"
26
"Copyright @copyright{} 1995 Cygnus Support"
28
"except the chapter \"Posix Entry Points\" which is:"
30
"Copyright @copyright{} 1995 Free Software Foundation, Inc."
32
"Permission is granted to make and distribute verbatim copies of"
33
"this manual provided the copyright notice and this permission notice"
34
"are preserved on all copies."
36
"Permission is granted to copy and distribute modified versions of this"
37
"manual under the conditions for verbatim copying, provided that the entire"
38
"resulting derived work is distributed under the terms of a permission"
39
"notice identical to this one."
41
"Permission is granted to copy and distribute translations of this manual"
42
"into another language, under the above conditions for modified versions,"
43
"except that this permission notice may be stated in a translation approved"
48
"@node Top, Copying, (dir), (dir)"
51
"This document describes Rx."
54
"* Copying:: Sharing is good."
56
"* Posix Basic Regular Expressions:: A popular regexp syntax."
57
"* Posix Entry Points:: The POSIX way to regexp."
58
"* Beyond POSIX:: Hints about cool features."
59
"* Rx Theory:: Hints about how it works."
62
"@node Copying, Overview, Top, Top"
65
"@center Copyright (C) 1996"
67
"@center Berkeley, CA USA"
69
"@center except portions of \"POSIX Regex Functions\" which are"
70
"@center Copyright (C) 1995"
71
"@center Free Software Foundation, Inc."
74
"Permission to use, copy, modify, distribute, and sell this software and"
75
"its documentation for any purpose is hereby granted without fee,"
76
"provided that the above copyright notice appear in all copies and that"
77
"both that copyright notice and this permission notice appear in"
78
"supporting documentation."
83
"BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR"
84
"THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN"
85
"OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES"
86
"PROVIDE THE PROGRAM \"AS IS\" WITHOUT WARRANTY OF ANY KIND, EITHER"
87
"EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED"
88
"WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE"
89
"ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH"
90
"YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL"
91
"NECESSARY SERVICING, REPAIR OR CORRECTION."
94
"IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING"
95
"WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR"
96
"REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR"
97
"DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL"
98
"DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM"
99
"(INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED"
100
"INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF"
101
"THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER OR"
102
"OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES."
104
"@node Overview, Posix Basic Regular Expressions, Copying, Top"
107
"Nothing to say here, yet."
109
"@node Posix Basic Regular Expressions, Posix Entry Points, Overview, Top"
110
"@chapter Posix Basic Regular Expressions"
112
"The Posix Basic Regular Expression language is a notation for describing"
113
"textual patterns. Regexps are typically used by comparing them to a"
114
"string to see if that string matches the pattern, or by searching within"
115
"a string for a substring that matches."
117
"This chapter introduces the Posix regexp notation. This is not a formal"
118
"or precise definition of Posix regexps -- it is an intuitive and"
119
"hopefully expository description of them."
122
"* An Introduction to Regexps:: "
123
"* Literal Regexps:: "
124
"* Character Sets:: "
125
"* Subexpressions:: "
126
"* Repeated Subexpressions:: "
127
"* Optional Subexpressions:: "
128
"* Counted Subexpressions:: "
129
"* Alternative Subexpressions:: "
130
"* Backreferences:: "
131
"* A Summary of Regexp Syntax:: "
132
"* Ambiguous Patterns:: "
136
"@node An Introduction to Regexps, Literal Regexps, Posix Basic Regular Expressions, Posix Basic Regular Expressions"
137
"@section An Introduction to Regexps"
139
"In the simplest cases, a regexp is just a literal string that must"
140
"match exactly. For example, the pattern:"
146
"matches the string \"regexp\" and no others."
148
"Some characters have a special meaning when they occur in a regexp."
149
"They aren't matched literally as in the previous example, but instead"
150
"denote a more general pattern. For example, the character @code{*}"
151
"is used to indicate that the preceeding element of a regexp may be"
152
"repeated 0, 1, or more times. In the pattern:"
158
"the @code{*} indicates that the preceeding @code{o} can be repeated 0 or"
159
"more times. So the pattern matches:"
169
"Suppose you want to write a pattern that literally matches a special"
170
"character like @code{*} -- in other words, you don't want to @code{*} to"
171
"indicate a permissible repetition, but to match @code{*} literally. This"
172
"is accomplished by quoting the special character with a backslash. "
179
"matches the string:"
186
"and no other strings."
188
"In five cases, the pattern is reversed -- a backslash makes the"
189
"character special instead of making a special character normal. The"
190
"characters @code{+}, @code{?}, @code{|}, @code{(}, and @code{)} are"
191
"normal but the sequences @code{\\+}, @code{\\?}, @code{\\|}, @code{\\(}, and"
192
"@code{\\)} are special (their meaning is described later)."
194
"The remaining sections of this chapter introduce and explain the various"
195
"special characters that can occur in regexps."
197
"@node Literal Regexps, Character Sets, An Introduction to Regexps, Posix Basic Regular Expressions"
198
"@section Literal Regexps"
200
"A literal regexp is a string which contains no special characters."
201
"A literal regexp matches an identical string, but no other characters."
216
"Generally, whitespace characters, numbers, and letters are not special."
217
"Some punctuation characters are special and some are not (the syntax"
218
"summary at the end of this chapter makes a convenient reference for"
219
"which characters are special and which aren't)."
222
"@node Character Sets, Subexpressions, Literal Regexps, Posix Basic Regular Expressions"
223
"@section Character Sets"
225
"This section introduces the special characters @code{.} and @code{[}."
227
"@code{.} matches any character except the NULL character. For example:"
247
"@code{[} begins a @dfn{character set}. A character set is similar to"
248
"@code{.} in that it matches not a single, literal character, but any"
249
"of a set of characters. @code{[} is different from @code{.} in that"
250
"with @code{[}, you define the set of characters explicitly."
252
"There are three basic forms a character set can take."
254
"In the first form, the character set is spelled out:"
257
"[<cset-spec>] -- every character in <cset-spec> is in the set."
260
"In the second form, the character set indicated is the negation of"
261
"a character set is explicitly spelled out:"
264
"[^<cset-spec>] -- every character *not* in <cset-spec> is in the set."
267
"A @code{<cset-spec>} is more or less an explicit enumeration of a set"
268
"of characters. It can be written as a string of individual characters:"
274
"or as a range of characters:"
280
"These two forms can be mixed:"
286
"Note that special regexp characters (such as @code{*}) are @emph{not}"
287
"special within a character set. @code{-}, as illustrated above,"
288
"@emph{is} special, except, as illustrated below, when it is the first"
289
"character mentioned."
291
"This is a four-character set:"
297
"The third form of a character set makes use of a pre-defined \"character"
301
"[[:class-name:]] -- every character described by class-name is in the set."
304
"The supported character classes are:"
307
"alnum - the set of alpha-numeric characters"
308
"alpha - the set of alphabetic characters"
309
"blank - tab and space"
310
"cntrl - the control characters"
311
"digit - decimal digits"
312
"graph - all printable characters except space"
313
"lower - lower case letters"
314
"print - the \"printable\" characters"
315
"punct - punctuation"
316
"space - whitespace characters"
317
"upper - upper case letters"
318
"xdigit - hexidecimal digits"
321
"Finally, character class sets can also be inverted:"
324
"[^[:space:]] - all non-whitespace characters"
327
"Character sets can be used in a regular expression anywhere a literal"
330
"@node Subexpressions, Repeated Subexpressions, Character Sets, Posix Basic Regular Expressions"
331
"@section Subexpressions"
333
"A subexpression is a regular expression enclosed in @code{\\(} and"
334
"@code{\\)}. A subexpression can be used anywhere a single character or"
335
"character set can be used."
337
"Subexpressions are useful for grouping regexp constructs. For example,"
338
"the repeat operator, @code{*}, usually applies to just the preceeding"
339
"character. Recall that:"
354
"Using a subexpression, we can apply @code{*} to a longer string:"
369
"Subexpressions also have a special meaning with regard to backreferences"
370
"and substitutions (see @xref{Backreferences})."
373
"@node Repeated Subexpressions, Optional Subexpressions, Subexpressions, Posix Basic Regular Expressions"
374
"@section Repeated Subexpressions"
377
"@code{*} is the repeat operator. It applies to the preceeding"
378
"character, character set, subexpression or backreference. It indicates"
379
"that the preceeding element can be matched 0 or more times:"
397
"@code{\\+} is similar to @code{*} except that @code{\\+} requires the"
398
"preceeding element to be matched at least once. So while:"
414
"does not. Both match "
423
"Thus, @code{bana\\(na\\)+} is short-hand for @code{banana\\(na\\)*}."
426
"@node Optional Subexpressions, Counted Subexpressions, Repeated Subexpressions, Posix Basic Regular Expressions"
427
"@section Optional Subexpressions"
429
"@code{\\?} indicates that the preceeding character, character set, or"
430
"subexpression is optional. It is permitted to match, or to be skipped:"
449
"@node Counted Subexpressions, Alternative Subexpressions, Optional Subexpressions, Posix Basic Regular Expressions"
450
"@section Counted Subexpressions"
452
"An interval expression, @code{@{m,n@}} where @code{m} and @code{n} are"
453
"non-negative integers with @code{n >= m}, applies to the preceeding"
454
"character, character set, subexpression or backreference. It indicates"
455
"that the preceeding element must match at least @code{m} times and may"
456
"match as many as @code{n} times."
481
"@node Alternative Subexpressions, Backreferences, Counted Subexpressions, Posix Basic Regular Expressions"
482
"@section Alternative Subexpressions"
484
"An alternative is written:"
487
"regexp-1\\|regexp-2\\|regexp-3\\|..."
490
"It matches anything matched by some @code{regexp-n}. For example:"
493
"Crosby, Stills, \\(and Nash\\|Nash, and Young\\)"
499
"Crosby, Stills, and Nash"
505
"Crosby, Stills, Nash, and Young"
509
"@node Backreferences, A Summary of Regexp Syntax, Alternative Subexpressions, Posix Basic Regular Expressions"
510
"@section Backreferences, Extractions and Substitutions"
512
"A backreference is written @code{\\n} where @code{n} is some single digit"
513
"other than 0. To be a valid backreference, there must be at least"
514
"@code{n} parenthesized subexpressions in the pattern prior to the"
517
"A backreference matches a literal copy of whatever was matched by the"
518
"corresponding subexpression. For example,"
533
"In some applications, subexpressions are used to extract substrings."
534
"For example, Emacs has the functions @code{match-beginnning} and"
535
"@code{match-end} which report the positions of strings matched by"
536
"subexpressions. These functions use the same numbering scheme for"
537
"subexpressions as backreferences, with the additional rule that"
538
"subexpression 0 is defined to be the whole regexp."
540
"In some applications, subexpressions are used in string substitution."
541
"This again uses the backreference numbering scheme. For example, this sed"
545
"s/From:.*<\\(.*\\)>/To: \\1/"
548
"first matches the line:"
551
"From: Joe Schmoe <schmoe@@uspringfield.edu>"
554
"when it does, subexpression 1 matches \"schmoe@@uspringfield.edu\"."
555
"The command replaces the matched line with \"To: \\1\" after doing"
556
"subexpression substitution on it to get:"
559
"To: schmoe@@uspringfield.edu"
563
"@node A Summary of Regexp Syntax, Ambiguous Patterns, Backreferences, Posix Basic Regular Expressions"
564
"@section A Summary of Regexp Syntax"
566
"In summary, regexps can be:"
568
"@code{abcd} -- matching a string literally"
570
"@code{.} -- matching everything except NULL"
572
"@code{[a-z_?]}, @code{^[a-z_?]}, @code{[[:alpha:]]} and"
573
"@code{[^[:alpha:]]} -- matching character sets"
575
"@code{\\(subexp\\)} -- grouping an expression into a subexpression."
577
"@code{\\n} -- match a copy of whatever was matched by the nth subexpression."
579
"The following special characters and sequences can be applied to a"
580
"character, character set, subexpression, or backreference:"
582
"@code{*} -- repeat the preceeding element 0 or more times."
584
"@code{\\+} -- repeat the preceeding element 1 or more times."
586
"@code{\\?} -- match the preceeding element 0 or 1 time."
588
"@code{@{m,n@}} -- match the preceeding element at least @code{m}, and as"
589
"many as @code{n} times."
591
"@code{regexp-1\\|regexp-2\\|..} -- match any regexp-n."
593
"A special character, like @code{.} or @code{*} can be made into a literal"
594
"character by prefixing it with @code{\\}."
596
"A special sequence, like @code{\\+} or @code{\\?} can be made into a"
597
"literal character by dropping the @code{\\}."
600
"@node Ambiguous Patterns, , A Summary of Regexp Syntax, Posix Basic Regular Expressions"
601
"@section Ambiguous Patterns"
603
"Sometimes a regular expression appears to be ambiguous. For example, suppose"
604
"we compare the pattern:"
616
"either just the first 5 characters will match, or the whole string will match."
618
"In every case like this, the longer match is preferred. The whole"
621
"Sometimes there is ambiguity not about how many characters to match, but"
622
"where the subexpressions occur within the match. This can effect"
623
"extraction functions like Emacs' @code{match-beginning} or rewrite"
624
"functions like sed's @code{s} command. For example, consider matching"
628
"b\\(\\[^q]*\\)\\(ing\\)?"
637
"One possibility is that the first subexpression matches \"eginning\" and"
638
"the second is skipped. Another possibility is that the first"
639
"subexpression matches \"eginn\" and the second matches \"ing\"."
641
"The rule is that consistant with matching as many characters as "
642
"possible, the length of lower numbered subexpressions is maximized"
643
"in preference to maximizing the length of later subexpressions."
645
"In the case of the above example, the two possible matches are equal in"
646
"overall length. Therefore, it comes down to maximizing the"
647
"lower-numbered subexpression, \\1. The correct answer is that \\1 matches"
648
"\"eginning\" and \\2 is skipped."
650
"@node Posix Entry Points, Beyond POSIX, Posix Basic Regular Expressions, Top"
651
"@chapter Posix Entry Points"
653
"This section is excerpted from @emph{The GNU C Library} reference manual"
654
"by Sandra Loosemore with Richard M. Stallman, Roland McGrath, and Andrew"
657
"The GNU C library supports the standard POSIX.2 interface. Programs"
658
"using this interface should include the header file @file{rxposix.h}."
661
"* POSIX Regexp Compilation:: Using @code{regcomp} to prepare to match."
662
"* Flags for POSIX Regexps:: Syntax variations for @code{regcomp}."
663
"* Matching POSIX Regexps:: Using @code{regexec} to match the compiled"
664
" pattern that you get from @code{regcomp}."
665
"* Regexp Subexpressions:: Finding which parts of the string were matched."
666
"* Subexpression Complications:: Find points of which parts were matched."
667
"* Regexp Cleanup:: Freeing storage; reporting errors."
670
"@node POSIX Regexp Compilation, Flags for POSIX Regexps, Posix Entry Points, Posix Entry Points"
671
"@section POSIX Regular Expression Compilation"
673
"Before you can actually match a regular expression, you must"
674
"@dfn{compile} it. This is not true compilation---it produces a special"
675
"data structure, not machine instructions. But it is like ordinary"
676
"compilation in that its purpose is to enable you to ``execute'' the"
677
"pattern fast. (@xref{Matching POSIX Regexps}, for how to use the"
678
"compiled regular expression for matching.)"
680
"There is a special data type for compiled regular expressions:"
684
"@deftp {Data Type} regex_t"
685
"This type of object holds a compiled regular expression."
686
"It is actually a structure. It has just one field that your programs"
691
"This field holds the number of parenthetical subexpressions in the"
692
"regular expression that was compiled."
695
"There are several other fields, but we don't describe them here, because"
696
"only the functions in the library should use them."
699
"After you create a @code{regex_t} object, you can compile a regular"
700
"expression into it by calling @code{regcomp}."
704
"@deftypefun int regcomp (regex_t *@var{compiled}, const char *@var{pattern}, int @var{cflags})"
705
"@deftypefunx int regncomp (regex_t *@var{compiled}, int len, const char *@var{pattern}, int @var{cflags})"
706
"The function @code{regcomp} ``compiles'' a regular expression into a"
707
"data structure that you can use with @code{regexec} to match against a"
708
"string. The compiled regular expression format is designed for"
709
"efficient matching. @code{regcomp} stores it into @code{*@var{compiled}}."
711
"The parameter @var{pattern} points to the regular expression to be"
712
"compiled. When using @code{regcomp}, @var{pattern} must be"
713
"0-terminated. When using @code{regncomp}, @var{pattern} must be"
714
"@var{len} characters long."
716
"@code{regncomp} is not a standard function; strictly POSIX programs"
717
"should avoid using it."
719
"It's up to you to allocate an object of type @code{regex_t} and pass its"
720
"address to @code{regcomp}."
722
"The argument @var{cflags} lets you specify various options that control"
723
"the syntax and semantics of regular expressions. @xref{Flags for POSIX"
726
"If you use the flag @code{REG_NOSUB}, then @code{regcomp} omits from"
727
"the compiled regular expression the information necessary to record"
728
"how subexpressions actually match. In this case, you might as well"
729
"pass @code{0} for the @var{matchptr} and @var{nmatch} arguments when"
730
"you call @code{regexec}."
732
"If you don't use @code{REG_NOSUB}, then the compiled regular expression"
733
"does have the capacity to record how subexpressions match. Also,"
734
"@code{regcomp} tells you how many subexpressions @var{pattern} has, by"
735
"storing the number in @code{@var{compiled}->re_nsub}. You can use that"
736
"value to decide how long an array to allocate to hold information about"
737
"subexpression matches."
739
"@code{regcomp} returns @code{0} if it succeeds in compiling the regular"
740
"expression; otherwise, it returns a nonzero error code (see the table"
741
"below). You can use @code{regerror} to produce an error message string"
742
"describing the reason for a nonzero value; see @ref{Regexp Cleanup}."
746
"Here are the possible nonzero values that @code{regcomp} can return:"
752
"There was an invalid @samp{\\@{@dots{}\\@}} construct in the regular"
753
"expression. A valid @samp{\\@{@dots{}\\@}} construct must contain either"
754
"a single number, or two numbers in increasing order separated by a"
760
"There was a syntax error in the regular expression."
765
"A repetition operator such as @samp{?} or @samp{*} appeared in a bad"
766
"position (with no preceding subexpression to act on)."
771
"The regular expression referred to an invalid collating element (one not"
772
"defined in the current locale for string collation). "
777
"The regular expression referred to an invalid character class name."
782
"The regular expression ended with @samp{\\}."
787
"There was an invalid number in the @samp{\\@var{digit}} construct."
792
"There were unbalanced square brackets in the regular expression."
797
"An extended regular expression had unbalanced parentheses,"
798
"or a basic regular expression had unbalanced @samp{\\(} and @samp{\\)}."
803
"The regular expression had unbalanced @samp{\\@{} and @samp{\\@}}."
808
"One of the endpoints in a range expression was invalid."
813
"@code{regcomp} ran out of memory."
816
"@node Flags for POSIX Regexps, Matching POSIX Regexps, POSIX Regexp Compilation, Posix Entry Points"
817
"@section Flags for POSIX Regular Expressions"
819
"These are the bit flags that you can use in the @var{cflags} operand when"
820
"compiling a regular expression with @code{regcomp}."
826
"Treat the pattern as an extended regular expression, rather than as a"
827
"basic regular expression."
832
"Ignore case when matching letters."
837
"Don't bother storing the contents of the @var{matches-ptr} array."
842
"Treat a newline in @var{string} as dividing @var{string} into multiple"
843
"lines, so that @samp{$} can match before the newline and @samp{^} can"
844
"match after. Also, don't permit @samp{.} to match a newline, and don't"
845
"permit @samp{[^@dots{}]} to match a newline."
847
"Otherwise, newline acts like any other ordinary character."
850
"@node Matching POSIX Regexps, Regexp Subexpressions, Flags for POSIX Regexps, Posix Entry Points"
851
"@section Matching a Compiled POSIX Regular Expression"
853
"Once you have compiled a regular expression, as described in @ref{POSIX"
854
"Regexp Compilation}, you can match it against strings using"
855
"@code{regexec}. A match anywhere inside the string counts as success,"
856
"unless the regular expression contains anchor characters (@samp{^} or"
861
"@deftypefun int regexec (regex_t *@var{compiled}, char *@var{string}, size_t @var{nmatch}, regmatch_t @var{matchptr} @t{[]}, int @var{eflags})"
862
"@deftypefunx int regnexec (regex_t *@var{compiled}, int len, char *@var{string}, size_t @var{nmatch}, regmatch_t @var{matchptr} @t{[]}, int @var{eflags})"
863
"This function tries to match the compiled regular expression"
864
"@code{*@var{compiled}} against @var{string}."
866
"@code{regexec} returns @code{0} if the regular expression matches;"
867
"otherwise, it returns a nonzero value. See the table below for"
868
"what nonzero values mean. You can use @code{regerror} to produce an"
869
"error message string describing the reason for a nonzero value; "
870
"see @ref{Regexp Cleanup}."
872
"The parameter @var{string} points to the text to search. When using"
873
"@code{regexec}, @var{string} must be 0-terminated. When using"
874
"@code{regnexec}, @var{string} must be @var{len} characters long."
876
"@code{regnexec} is not a standard function; strictly POSIX programs"
877
"should avoid using it."
879
"The argument @var{eflags} is a word of bit flags that enable various"
882
"If you want to get information about what part of @var{string} actually"
883
"matched the regular expression or its subexpressions, use the arguments"
884
"@var{matchptr} and @var{nmatch}. Otherwise, pass @code{0} for "
885
"@var{nmatch}, and @code{NULL} for @var{matchptr}. @xref{Regexp"
889
"You must match the regular expression with the same set of current"
890
"locales that were in effect when you compiled the regular expression."
892
"The function @code{regexec} accepts the following flags in the"
893
"@var{eflags} argument:"
899
"Do not regard the beginning of the specified string as the beginning of"
900
"a line; more generally, don't make any assumptions about what text might"
906
"Do not regard the end of the specified string as the end of a line; more"
907
"generally, don't make any assumptions about what text might follow it."
910
"Here are the possible nonzero values that @code{regexec} can return:"
916
"The pattern didn't match the string. This isn't really an error."
921
"@code{regexec} ran out of memory."
924
"@node Regexp Subexpressions, Subexpression Complications, Matching POSIX Regexps, Posix Entry Points"
925
"@section Match Results with Subexpressions"
927
"When @code{regexec} matches parenthetical subexpressions of"
928
"@var{pattern}, it records which parts of @var{string} they match. It"
929
"returns that information by storing the offsets into an array whose"
930
"elements are structures of type @code{regmatch_t}. The first element of"
931
"the array (index @code{0}) records the part of the string that matched"
932
"the entire regular expression. Each other element of the array records"
933
"the beginning and end of the part that matched a single parenthetical"
938
"@deftp {Data Type} regmatch_t"
939
"This is the data type of the @var{matcharray} array that you pass to"
940
"@code{regexec}. It containes two structure fields, as follows:"
944
"The offset in @var{string} of the beginning of a substring. Add this"
945
"value to @var{string} to get the address of that part."
948
"The offset in @var{string} of the end of the substring."
954
"@deftp {Data Type} regoff_t"
955
"@code{regoff_t} is an alias for another signed integer type."
956
"The fields of @code{regmatch_t} have type @code{regoff_t}."
959
"The @code{regmatch_t} elements correspond to subexpressions"
960
"positionally; the first element (index @code{1}) records where the first"
961
"subexpression matched, the second element records the second"
962
"subexpression, and so on. The order of the subexpressions is the order"
963
"in which they begin."
965
"When you call @code{regexec}, you specify how long the @var{matchptr}"
966
"array is, with the @var{nmatch} argument. This tells @code{regexec} how"
967
"many elements to store. If the actual regular expression has more than"
968
"@var{nmatch} subexpressions, then you won't get offset information about"
969
"the rest of them. But this doesn't alter whether the pattern matches a"
970
"particular string or not."
972
"If you don't want @code{regexec} to return any information about where"
973
"the subexpressions matched, you can either supply @code{0} for"
974
"@var{nmatch}, or use the flag @code{REG_NOSUB} when you compile the"
975
"pattern with @code{regcomp}."
977
"@node Subexpression Complications, Regexp Cleanup, Regexp Subexpressions, Posix Entry Points"
978
"@section Complications in Subexpression Matching"
980
"Sometimes a subexpression matches a substring of no characters. This"
981
"happens when @samp{f\\(o*\\)} matches the string @samp{fum}. (It really"
982
"matches just the @samp{f}.) In this case, both of the offsets identify"
983
"the point in the string where the null substring was found. In this"
984
"example, the offsets are both @code{1}."
986
"Sometimes the entire regular expression can match without using some of"
987
"its subexpressions at all---for example, when @samp{ba\\(na\\)*} matches the"
988
"string @samp{ba}, the parenthetical subexpression is not used. When"
989
"this happens, @code{regexec} stores @code{-1} in both fields of the"
990
"element for that subexpression."
992
"Sometimes matching the entire regular expression can match a particular"
993
"subexpression more than once---for example, when @samp{ba\\(na\\)*}"
994
"matches the string @samp{bananana}, the parenthetical subexpression"
995
"matches three times. When this happens, @code{regexec} usually stores"
996
"the offsets of the last part of the string that matched the"
997
"subexpression. In the case of @samp{bananana}, these offsets are"
998
"@code{6} and @code{8}."
1000
"But the last match is not always the one that is chosen. It's more"
1001
"accurate to say that the last @emph{opportunity} to match is the one"
1002
"that takes precedence. What this means is that when one subexpression"
1003
"appears within another, then the results reported for the inner"
1004
"subexpression reflect whatever happened on the last match of the outer"
1005
"subexpression. For an example, consider @samp{\\(ba\\(na\\)*s \\)*} matching"
1006
"the string @samp{bananas bas }. The last time the inner expression"
1007
"actually matches is near the end of the first word. But it is "
1008
"@emph{considered} again in the second word, and fails to match there."
1009
"@code{regexec} reports nonuse of the ``na'' subexpression."
1011
"Another place where this rule applies is when the regular expression"
1012
"@w{@samp{\\(ba\\(na\\)*s \\|nefer\\(ti\\)* \\)*}} matches @samp{bananas nefertiti}."
1013
"The ``na'' subexpression does match in the first word, but it doesn't"
1014
"match in the second word because the other alternative is used there."
1015
"Once again, the second repetition of the outer subexpression overrides"
1016
"the first, and within that second repetition, the ``na'' subexpression"
1017
"is not used. So @code{regexec} reports nonuse of the ``na''"
1020
"@node Regexp Cleanup, , Subexpression Complications, Posix Entry Points"
1021
"@section POSIX Regexp Matching Cleanup"
1023
"When you are finished using a compiled regular expression, you can"
1024
"free the storage it uses by calling @code{regfree}."
1028
"@deftypefun void regfree (regex_t *@var{compiled})"
1029
"Calling @code{regfree} frees all the storage that @code{*@var{compiled}}"
1030
"points to. This includes various internal fields of the @code{regex_t}"
1031
"structure that aren't documented in this manual."
1033
"@code{regfree} does not free the object @code{*@var{compiled}} itself."
1036
"You should always free the space in a @code{regex_t} structure with"
1037
"@code{regfree} before using the structure to compile another regular"
1040
"When @code{regcomp} or @code{regexec} reports an error, you can use"
1041
"the function @code{regerror} to turn it into an error message string."
1045
"@deftypefun size_t regerror (int @var{errcode}, regex_t *@var{compiled}, char *@var{buffer}, size_t @var{length})"
1046
"This function produces an error message string for the error code"
1047
"@var{errcode}, and stores the string in @var{length} bytes of memory"
1048
"starting at @var{buffer}. For the @var{compiled} argument, supply the"
1049
"same compiled regular expression structure that @code{regcomp} or"
1050
"@code{regexec} was working with when it got the error. Alternatively,"
1051
"you can supply @code{NULL} for @var{compiled}; you will still get a"
1052
"meaningful error message, but it might not be as detailed."
1054
"If the error message can't fit in @var{length} bytes (including a"
1055
"terminating null character), then @code{regerror} truncates it."
1056
"The string that @code{regerror} stores is always null-terminated"
1057
"even if it has been truncated."
1059
"The return value of @code{regerror} is the minimum length needed to"
1060
"store the entire error message. If this is less than @var{length}, then"
1061
"the error message was not truncated, and you can use it. Otherwise, you"
1062
"should call @code{regerror} again with a larger buffer."
1064
"Here is a function which uses @code{regerror}, but always dynamically"
1065
"allocates a buffer for the error message:"
1068
"char *get_regerror (int errcode, regex_t *compiled)"
1070
" size_t length = regerror (errcode, compiled, NULL, 0);"
1071
" char *buffer = xmalloc (length);"
1072
" (void) regerror (errcode, compiled, buffer, length);"
1078
"@node Beyond POSIX, Rx Theory, Posix Entry Points, Top"
1079
"@chapter Beyond POSIX"
1081
"This section is not finished documentation, but rather a collection of"
1082
"pointers towards some of the interesting, non-standard features of Rx."
1084
"@section New Regexp Operators"
1086
"Rx supports some unusual regexp syntax."
1088
"@code{[[:cut N:]]} sets @code{pmatch[0].final_tag} to N and causes the"
1089
"matching to stop instantly. If N is 0, the overall match fails,"
1090
"otherwise it succeeds."
1092
"@code{[[:(:]] ... [[:):]]} is just like @code{\\( ... \\)} except that in"
1093
"the first case, no pmatch entries are changed, and the subexpression is"
1094
"not counted in the numbering of parenthesized subexpressions."
1096
"@code{[[:(:]] ... [[:):]]} can be used when you do not need to know"
1097
"where a subexpression matched but are only using parentheses to effect"
1098
"the parsing of the regexp. "
1100
"There are two reasons to use @code{[[:(:]] ... [[:):]]}:"
1102
"1. regexec will run faster."
1104
"2. Currently, only 8 backreferencable subexpressions are supported:"
1105
"@code{\\1 .. \\9}. Using @code{[[:(:]] ... [[:):]]} is a way to conserve"
1106
"backreferencable subexpression names in an expression with many"
1109
"@section New POSIX Functions"
1111
"@code{regncomp} and @code{regnexec} are non-standard generalizations of"
1112
"@code{regcomp} and @code{regexec}."
1114
"@section Tuning POSIX performance"
1116
"Two mysterious parmaters can be used to trade-off performance and"
1119
"At compile-time they are @code{RX_DEFAULT_DFA_CACHE_SIZE} and"
1120
"@code{RX_DEFAULT_NFA_DELAY}. "
1122
"If you want to mess with these (I generally don't advise it), I suggest"
1123
"experimenting for your particular application/memory situation; frob"
1124
"these by powers of two and try out the results on what you expect will"
1125
"be typical regexp workloads."
1127
"You can also set those parameters at run-time (before calling any regexp"
1128
"functions) by tweaking the corresponding variables:"
1130
"@code{rx_default_cache->bytes_allowed}"
1134
"@code{rx_basic_unfaniverse_delay}"
1138
"@section POSIX stream-style interface"
1140
"@code{rx_make_solutions}, @code{rx_next_solution}, and"
1141
"@code{rx_free_solutions} are a lower level alternative to the posix"
1142
"functions. Using those functions, you can compare a compiled regexp to"
1143
"a string that is not contiguous in memory or even a string that is not"
1144
"entirely in memory at any one time."
1146
"The code in rxposix.c points out how those functions are used."
1149
"@section DFAs Directly"
1151
"If you are only interested in pure regular expressions (no pmatch data,"
1152
"no backreferences, and no counted subexpressions), you can parse a"
1153
"regexp using @code{rx_parse}, convert it to an nfa using @code{rx_unfa},"
1154
"and run the dfa using @code{rx_init_system}, @code{rx_advance_to_final},"
1155
"and @code{rx_terminate_system}. The dfa Scheme primitives in"
1156
"@file{rgx.c} may provide some guide."
1158
"@node Rx Theory, , Beyond POSIX, Top"
1159
"@chapter Rx Theory"
1162
"There are two match algorithms. One is for truly regular regexps (those"
1163
"that can be reduced to a dfa). The other is for non-regular regexps."
1165
"The dfa algorithm implements the idea suggested in @cite{Compilers} by"
1166
"Aho, Sethi and Ullman:"
1169
"[One] approach [to pattern matching regular expressions] is to use a"
1170
"DFA, but avoid constructing all of the transition table by using a"
1171
"technique called \"lazy transition evaluation\". Here, transitions are"
1172
"computed at run time [when] actually needed. [T]ransitions are"
1173
"stored in a cache. [....] If the cache becomes full, we can erase some"
1174
"previously computed transition to make room for the new transition."
1177
"The implementation in Rx is generalized from that, but the above"
1178
"description covers what is used for Posix patterns. "
1180
"The non-dfa algorithm implements a \"recursive decomposition\" technique"
1181
"described in email by Henry Spencer. For a given pattern, this"
1182
"algorithm first checks to see if a simpler, superset language,"
1183
"DFA-pattern matches. If it does, then this algorithm does the"
1184
"detail-work to see if the non-DFA pattern matches."
1185
"\\input texinfo @c -*-texinfo-*-"
1186
"@c %**start of header"
1187
"@setfilename rx.info"
1189
"@setchapternewpage odd"
1190
"@c %**end of header"
1192
"@c This title page illustrates only one of the"
1193
"@c two methods of forming a title page."
1199
"@center except the chapter \"Posix Entry Points\" "
1200
"@center from @emph{The GNU C Library} reference manual"
1201
"@center by Sandra Loosemore"
1203
"@center Richard M. Stallman, Roland McGrath, and Andrew Oram"
1205
"@c The following two commands"
1206
"@c start the copyright page."
1208
"@vskip 0pt plus 1filll"
1209
"Copyright @copyright{} 1995 Cygnus Support"
1211
"except the chapter \"Posix Entry Points\" which is:"
1213
"Copyright @copyright{} 1995 Free Software Foundation, Inc."
1215
"Permission is granted to make and distribute verbatim copies of"
1216
"this manual provided the copyright notice and this permission notice"
1217
"are preserved on all copies."
1219
"Permission is granted to copy and distribute modified versions of this"
1220
"manual under the conditions for verbatim copying, provided that the entire"
1221
"resulting derived work is distributed under the terms of a permission"
1222
"notice identical to this one."
1224
"Permission is granted to copy and distribute translations of this manual"
1225
"into another language, under the above conditions for modified versions,"
1226
"except that this permission notice may be stated in a translation approved"
1231
"@node Top, Copying, (dir), (dir)"
1234
"This document describes Rx."
1237
"* Copying:: Sharing is good."
1238
"* Overview:: Fnord"
1239
"* Posix Basic Regular Expressions:: A popular regexp syntax."
1240
"* Posix Entry Points:: The POSIX way to regexp."
1241
"* Beyond POSIX:: Hints about cool features."
1242
"* Rx Theory:: Hints about how it works."
1245
"@node Copying, Overview, Top, Top"
1248
"@center Copyright (C) 1996"
1250
"@center Berkeley, CA USA"
1252
"@center except portions of \"POSIX Regex Functions\" which are"
1253
"@center Copyright (C) 1995"
1254
"@center Free Software Foundation, Inc."
1257
"Permission to use, copy, modify, distribute, and sell this software and"
1258
"its documentation for any purpose is hereby granted without fee,"
1259
"provided that the above copyright notice appear in all copies and that"
1260
"both that copyright notice and this permission notice appear in"
1261
"supporting documentation."
1263
"@center NO WARRANTY"
1266
"BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR"
1267
"THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN"
1268
"OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES"
1269
"PROVIDE THE PROGRAM \"AS IS\" WITHOUT WARRANTY OF ANY KIND, EITHER"
1270
"EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED"
1271
"WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE"
1272
"ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH"
1273
"YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL"
1274
"NECESSARY SERVICING, REPAIR OR CORRECTION."
1277
"IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING"
1278
"WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR"
1279
"REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR"
1280
"DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL"
1281
"DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM"
1282
"(INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED"
1283
"INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF"
1284
"THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER OR"
1285
"OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES."
1287
"@node Overview, Posix Basic Regular Expressions, Copying, Top"
1290
"Nothing to say here, yet."
1292
"@node Posix Basic Regular Expressions, Posix Entry Points, Overview, Top"
1293
"@chapter Posix Basic Regular Expressions"
1295
"The Posix Basic Regular Expression language is a notation for describing"
1296
"textual patterns. Regexps are typically used by comparing them to a"
1297
"string to see if that string matches the pattern, or by searching within"
1298
"a string for a substring that matches."
1300
"This chapter introduces the Posix regexp notation. This is not a formal"
1301
"or precise definition of Posix regexps -- it is an intuitive and"
1302
"hopefully expository description of them."
1305
"* An Introduction to Regexps:: "
1306
"* Literal Regexps:: "
1307
"* Character Sets:: "
1308
"* Subexpressions:: "
1309
"* Repeated Subexpressions:: "
1310
"* Optional Subexpressions:: "
1311
"* Counted Subexpressions:: "
1312
"* Alternative Subexpressions:: "
1313
"* Backreferences:: "
1314
"* A Summary of Regexp Syntax:: "
1315
"* Ambiguous Patterns:: "
1319
"@node An Introduction to Regexps, Literal Regexps, Posix Basic Regular Expressions, Posix Basic Regular Expressions"
1320
"@section An Introduction to Regexps"
1322
"In the simplest cases, a regexp is just a literal string that must"
1323
"match exactly. For example, the pattern:"
1329
"matches the string \"regexp\" and no others."
1331
"Some characters have a special meaning when they occur in a regexp."
1332
"They aren't matched literally as in the previous example, but instead"
1333
"denote a more general pattern. For example, the character @code{*}"
1334
"is used to indicate that the preceeding element of a regexp may be"
1335
"repeated 0, 1, or more times. In the pattern:"
1341
"the @code{*} indicates that the preceeding @code{o} can be repeated 0 or"
1342
"more times. So the pattern matches:"
1352
"Suppose you want to write a pattern that literally matches a special"
1353
"character like @code{*} -- in other words, you don't want to @code{*} to"
1354
"indicate a permissible repetition, but to match @code{*} literally. This"
1355
"is accomplished by quoting the special character with a backslash. "
1362
"matches the string:"
1369
"and no other strings."
1371
"In five cases, the pattern is reversed -- a backslash makes the"
1372
"character special instead of making a special character normal. The"
1373
"characters @code{+}, @code{?}, @code{|}, @code{(}, and @code{)} are"
1374
"normal but the sequences @code{\\+}, @code{\\?}, @code{\\|}, @code{\\(}, and"
1375
"@code{\\)} are special (their meaning is described later)."
1377
"The remaining sections of this chapter introduce and explain the various"
1378
"special characters that can occur in regexps."
1380
"@node Literal Regexps, Character Sets, An Introduction to Regexps, Posix Basic Regular Expressions"
1381
"@section Literal Regexps"
1383
"A literal regexp is a string which contains no special characters."
1384
"A literal regexp matches an identical string, but no other characters."
1399
"Generally, whitespace characters, numbers, and letters are not special."
1400
"Some punctuation characters are special and some are not (the syntax"
1401
"summary at the end of this chapter makes a convenient reference for"
1402
"which characters are special and which aren't)."
1405
"@node Character Sets, Subexpressions, Literal Regexps, Posix Basic Regular Expressions"
1406
"@section Character Sets"
1408
"This section introduces the special characters @code{.} and @code{[}."
1410
"@code{.} matches any character except the NULL character. For example:"
1430
"@code{[} begins a @dfn{character set}. A character set is similar to"
1431
"@code{.} in that it matches not a single, literal character, but any"
1432
"of a set of characters. @code{[} is different from @code{.} in that"
1433
"with @code{[}, you define the set of characters explicitly."
1435
"There are three basic forms a character set can take."
1437
"In the first form, the character set is spelled out:"
1440
"[<cset-spec>] -- every character in <cset-spec> is in the set."
1443
"In the second form, the character set indicated is the negation of"
1444
"a character set is explicitly spelled out:"
1447
"[^<cset-spec>] -- every character *not* in <cset-spec> is in the set."
1450
"A @code{<cset-spec>} is more or less an explicit enumeration of a set"
1451
"of characters. It can be written as a string of individual characters:"
1457
"or as a range of characters:"
1463
"These two forms can be mixed:"
1469
"Note that special regexp characters (such as @code{*}) are @emph{not}"
1470
"special within a character set. @code{-}, as illustrated above,"
1471
"@emph{is} special, except, as illustrated below, when it is the first"
1472
"character mentioned."
1474
"This is a four-character set:"
1480
"The third form of a character set makes use of a pre-defined \"character"
1484
"[[:class-name:]] -- every character described by class-name is in the set."
1487
"The supported character classes are:"
1490
"alnum - the set of alpha-numeric characters"
1491
"alpha - the set of alphabetic characters"
1492
"blank - tab and space"
1493
"cntrl - the control characters"
1494
"digit - decimal digits"
1495
"graph - all printable characters except space"
1496
"lower - lower case letters"
1497
"print - the \"printable\" characters"
1498
"punct - punctuation"
1499
"space - whitespace characters"
1500
"upper - upper case letters"
1501
"xdigit - hexidecimal digits"
1504
"Finally, character class sets can also be inverted:"
1507
"[^[:space:]] - all non-whitespace characters"
1510
"Character sets can be used in a regular expression anywhere a literal"
1513
"@node Subexpressions, Repeated Subexpressions, Character Sets, Posix Basic Regular Expressions"
1514
"@section Subexpressions"
1516
"A subexpression is a regular expression enclosed in @code{\\(} and"
1517
"@code{\\)}. A subexpression can be used anywhere a single character or"
1518
"character set can be used."
1520
"Subexpressions are useful for grouping regexp constructs. For example,"
1521
"the repeat operator, @code{*}, usually applies to just the preceeding"
1522
"character. Recall that:"
1537
"Using a subexpression, we can apply @code{*} to a longer string:"
1552
"Subexpressions also have a special meaning with regard to backreferences"
1553
"and substitutions (see @xref{Backreferences})."
1556
"@node Repeated Subexpressions, Optional Subexpressions, Subexpressions, Posix Basic Regular Expressions"
1557
"@section Repeated Subexpressions"
1560
"@code{*} is the repeat operator. It applies to the preceeding"
1561
"character, character set, subexpression or backreference. It indicates"
1562
"that the preceeding element can be matched 0 or more times:"
1580
"@code{\\+} is similar to @code{*} except that @code{\\+} requires the"
1581
"preceeding element to be matched at least once. So while:"
1597
"does not. Both match "
1606
"Thus, @code{bana\\(na\\)+} is short-hand for @code{banana\\(na\\)*}."
1609
"@node Optional Subexpressions, Counted Subexpressions, Repeated Subexpressions, Posix Basic Regular Expressions"
1610
"@section Optional Subexpressions"
1612
"@code{\\?} indicates that the preceeding character, character set, or"
1613
"subexpression is optional. It is permitted to match, or to be skipped:"
1632
"@node Counted Subexpressions, Alternative Subexpressions, Optional Subexpressions, Posix Basic Regular Expressions"
1633
"@section Counted Subexpressions"
1635
"An interval expression, @code{@{m,n@}} where @code{m} and @code{n} are"
1636
"non-negative integers with @code{n >= m}, applies to the preceeding"
1637
"character, character set, subexpression or backreference. It indicates"
1638
"that the preceeding element must match at least @code{m} times and may"
1639
"match as many as @code{n} times."
1644
"c\\([ad]\\)@{1,4@}"
1664
"@node Alternative Subexpressions, Backreferences, Counted Subexpressions, Posix Basic Regular Expressions"
1665
"@section Alternative Subexpressions"
1667
"An alternative is written:"
1670
"regexp-1\\|regexp-2\\|regexp-3\\|..."
1673
"It matches anything matched by some @code{regexp-n}. For example:"
1676
"Crosby, Stills, \\(and Nash\\|Nash, and Young\\)"
1682
"Crosby, Stills, and Nash"
1688
"Crosby, Stills, Nash, and Young"
1692
"@node Backreferences, A Summary of Regexp Syntax, Alternative Subexpressions, Posix Basic Regular Expressions"
1693
"@section Backreferences, Extractions and Substitutions"
1695
"A backreference is written @code{\\n} where @code{n} is some single digit"
1696
"other than 0. To be a valid backreference, there must be at least"
1697
"@code{n} parenthesized subexpressions in the pattern prior to the"
1700
"A backreference matches a literal copy of whatever was matched by the"
1701
"corresponding subexpression. For example,"
1716
"In some applications, subexpressions are used to extract substrings."
1717
"For example, Emacs has the functions @code{match-beginnning} and"
1718
"@code{match-end} which report the positions of strings matched by"
1719
"subexpressions. These functions use the same numbering scheme for"
1720
"subexpressions as backreferences, with the additional rule that"
1721
"subexpression 0 is defined to be the whole regexp."
1723
"In some applications, subexpressions are used in string substitution."
1724
"This again uses the backreference numbering scheme. For example, this sed"
1728
"s/From:.*<\\(.*\\)>/To: \\1/"
1731
"first matches the line:"
1734
"From: Joe Schmoe <schmoe@@uspringfield.edu>"
1737
"when it does, subexpression 1 matches \"schmoe@@uspringfield.edu\"."
1738
"The command replaces the matched line with \"To: \\1\" after doing"
1739
"subexpression substitution on it to get:"
1742
"To: schmoe@@uspringfield.edu"
1746
"@node A Summary of Regexp Syntax, Ambiguous Patterns, Backreferences, Posix Basic Regular Expressions"
1747
"@section A Summary of Regexp Syntax"
1749
"In summary, regexps can be:"
1751
"@code{abcd} -- matching a string literally"
1753
"@code{.} -- matching everything except NULL"
1755
"@code{[a-z_?]}, @code{^[a-z_?]}, @code{[[:alpha:]]} and"
1756
"@code{[^[:alpha:]]} -- matching character sets"
1758
"@code{\\(subexp\\)} -- grouping an expression into a subexpression."
1760
"@code{\\n} -- match a copy of whatever was matched by the nth subexpression."
1762
"The following special characters and sequences can be applied to a"
1763
"character, character set, subexpression, or backreference:"
1765
"@code{*} -- repeat the preceeding element 0 or more times."
1767
"@code{\\+} -- repeat the preceeding element 1 or more times."
1769
"@code{\\?} -- match the preceeding element 0 or 1 time."
1771
"@code{@{m,n@}} -- match the preceeding element at least @code{m}, and as"
1772
"many as @code{n} times."
1774
"@code{regexp-1\\|regexp-2\\|..} -- match any regexp-n."
1776
"A special character, like @code{.} or @code{*} can be made into a literal"
1777
"character by prefixing it with @code{\\}."
1779
"A special sequence, like @code{\\+} or @code{\\?} can be made into a"
1780
"literal character by dropping the @code{\\}."
1783
"@node Ambiguous Patterns, , A Summary of Regexp Syntax, Posix Basic Regular Expressions"
1784
"@section Ambiguous Patterns"
1786
"Sometimes a regular expression appears to be ambiguous. For example, suppose"
1787
"we compare the pattern:"
1799
"either just the first 5 characters will match, or the whole string will match."
1801
"In every case like this, the longer match is preferred. The whole"
1802
"string will match."
1804
"Sometimes there is ambiguity not about how many characters to match, but"
1805
"where the subexpressions occur within the match. This can effect"
1806
"extraction functions like Emacs' @code{match-beginning} or rewrite"
1807
"functions like sed's @code{s} command. For example, consider matching"
1811
"b\\(\\[^q]*\\)\\(ing\\)?"
1814
"against the string"
1820
"One possibility is that the first subexpression matches \"eginning\" and"
1821
"the second is skipped. Another possibility is that the first"
1822
"subexpression matches \"eginn\" and the second matches \"ing\"."
1824
"The rule is that consistant with matching as many characters as "
1825
"possible, the length of lower numbered subexpressions is maximized"
1826
"in preference to maximizing the length of later subexpressions."
1828
"In the case of the above example, the two possible matches are equal in"
1829
"overall length. Therefore, it comes down to maximizing the"
1830
"lower-numbered subexpression, \\1. The correct answer is that \\1 matches"
1831
"\"eginning\" and \\2 is skipped."
1833
"@node Posix Entry Points, Beyond POSIX, Posix Basic Regular Expressions, Top"
1834
"@chapter Posix Entry Points"
1836
"This section is excerpted from @emph{The GNU C Library} reference manual"
1837
"by Sandra Loosemore with Richard M. Stallman, Roland McGrath, and Andrew"
1840
"The GNU C library supports the standard POSIX.2 interface. Programs"
1841
"using this interface should include the header file @file{rxposix.h}."
1844
"* POSIX Regexp Compilation:: Using @code{regcomp} to prepare to match."
1845
"* Flags for POSIX Regexps:: Syntax variations for @code{regcomp}."
1846
"* Matching POSIX Regexps:: Using @code{regexec} to match the compiled"
1847
" pattern that you get from @code{regcomp}."
1848
"* Regexp Subexpressions:: Finding which parts of the string were matched."
1849
"* Subexpression Complications:: Find points of which parts were matched."
1850
"* Regexp Cleanup:: Freeing storage; reporting errors."
1853
"@node POSIX Regexp Compilation, Flags for POSIX Regexps, Posix Entry Points, Posix Entry Points"
1854
"@section POSIX Regular Expression Compilation"
1856
"Before you can actually match a regular expression, you must"
1857
"@dfn{compile} it. This is not true compilation---it produces a special"
1858
"data structure, not machine instructions. But it is like ordinary"
1859
"compilation in that its purpose is to enable you to ``execute'' the"
1860
"pattern fast. (@xref{Matching POSIX Regexps}, for how to use the"
1861
"compiled regular expression for matching.)"
1863
"There is a special data type for compiled regular expressions:"
1867
"@deftp {Data Type} regex_t"
1868
"This type of object holds a compiled regular expression."
1869
"It is actually a structure. It has just one field that your programs"
1874
"This field holds the number of parenthetical subexpressions in the"
1875
"regular expression that was compiled."
1878
"There are several other fields, but we don't describe them here, because"
1879
"only the functions in the library should use them."
1882
"After you create a @code{regex_t} object, you can compile a regular"
1883
"expression into it by calling @code{regcomp}."
1887
"@deftypefun int regcomp (regex_t *@var{compiled}, const char *@var{pattern}, int @var{cflags})"
1888
"@deftypefunx int regncomp (regex_t *@var{compiled}, int len, const char *@var{pattern}, int @var{cflags})"
1889
"The function @code{regcomp} ``compiles'' a regular expression into a"
1890
"data structure that you can use with @code{regexec} to match against a"
1891
"string. The compiled regular expression format is designed for"
1892
"efficient matching. @code{regcomp} stores it into @code{*@var{compiled}}."
1894
"The parameter @var{pattern} points to the regular expression to be"
1895
"compiled. When using @code{regcomp}, @var{pattern} must be"
1896
"0-terminated. When using @code{regncomp}, @var{pattern} must be"
1897
"@var{len} characters long."
1899
"@code{regncomp} is not a standard function; strictly POSIX programs"
1900
"should avoid using it."
1902
"It's up to you to allocate an object of type @code{regex_t} and pass its"
1903
"address to @code{regcomp}."
1905
"The argument @var{cflags} lets you specify various options that control"
1906
"the syntax and semantics of regular expressions. @xref{Flags for POSIX"
1909
"If you use the flag @code{REG_NOSUB}, then @code{regcomp} omits from"
1910
"the compiled regular expression the information necessary to record"
1911
"how subexpressions actually match. In this case, you might as well"
1912
"pass @code{0} for the @var{matchptr} and @var{nmatch} arguments when"
1913
"you call @code{regexec}."
1915
"If you don't use @code{REG_NOSUB}, then the compiled regular expression"
1916
"does have the capacity to record how subexpressions match. Also,"
1917
"@code{regcomp} tells you how many subexpressions @var{pattern} has, by"
1918
"storing the number in @code{@var{compiled}->re_nsub}. You can use that"
1919
"value to decide how long an array to allocate to hold information about"
1920
"subexpression matches."
1922
"@code{regcomp} returns @code{0} if it succeeds in compiling the regular"
1923
"expression; otherwise, it returns a nonzero error code (see the table"
1924
"below). You can use @code{regerror} to produce an error message string"
1925
"describing the reason for a nonzero value; see @ref{Regexp Cleanup}."
1929
"Here are the possible nonzero values that @code{regcomp} can return:"
1935
"There was an invalid @samp{\\@{@dots{}\\@}} construct in the regular"
1936
"expression. A valid @samp{\\@{@dots{}\\@}} construct must contain either"
1937
"a single number, or two numbers in increasing order separated by a"
1943
"There was a syntax error in the regular expression."
1948
"A repetition operator such as @samp{?} or @samp{*} appeared in a bad"
1949
"position (with no preceding subexpression to act on)."
1953
"@item REG_ECOLLATE"
1954
"The regular expression referred to an invalid collating element (one not"
1955
"defined in the current locale for string collation). "
1960
"The regular expression referred to an invalid character class name."
1965
"The regular expression ended with @samp{\\}."
1970
"There was an invalid number in the @samp{\\@var{digit}} construct."
1975
"There were unbalanced square brackets in the regular expression."
1980
"An extended regular expression had unbalanced parentheses,"
1981
"or a basic regular expression had unbalanced @samp{\\(} and @samp{\\)}."
1986
"The regular expression had unbalanced @samp{\\@{} and @samp{\\@}}."
1991
"One of the endpoints in a range expression was invalid."
1996
"@code{regcomp} ran out of memory."
1999
"@node Flags for POSIX Regexps, Matching POSIX Regexps, POSIX Regexp Compilation, Posix Entry Points"
2000
"@section Flags for POSIX Regular Expressions"
2002
"These are the bit flags that you can use in the @var{cflags} operand when"
2003
"compiling a regular expression with @code{regcomp}."
2008
"@item REG_EXTENDED"
2009
"Treat the pattern as an extended regular expression, rather than as a"
2010
"basic regular expression."
2015
"Ignore case when matching letters."
2020
"Don't bother storing the contents of the @var{matches-ptr} array."
2025
"Treat a newline in @var{string} as dividing @var{string} into multiple"
2026
"lines, so that @samp{$} can match before the newline and @samp{^} can"
2027
"match after. Also, don't permit @samp{.} to match a newline, and don't"
2028
"permit @samp{[^@dots{}]} to match a newline."
2030
"Otherwise, newline acts like any other ordinary character."
2033
"@node Matching POSIX Regexps, Regexp Subexpressions, Flags for POSIX Regexps, Posix Entry Points"
2034
"@section Matching a Compiled POSIX Regular Expression"
2036
"Once you have compiled a regular expression, as described in @ref{POSIX"
2037
"Regexp Compilation}, you can match it against strings using"
2038
"@code{regexec}. A match anywhere inside the string counts as success,"
2039
"unless the regular expression contains anchor characters (@samp{^} or"
2044
"@deftypefun int regexec (regex_t *@var{compiled}, char *@var{string}, size_t @var{nmatch}, regmatch_t @var{matchptr} @t{[]}, int @var{eflags})"
2045
"@deftypefunx int regnexec (regex_t *@var{compiled}, int len, char *@var{string}, size_t @var{nmatch}, regmatch_t @var{matchptr} @t{[]}, int @var{eflags})"
2046
"This function tries to match the compiled regular expression"
2047
"@code{*@var{compiled}} against @var{string}."
2049
"@code{regexec} returns @code{0} if the regular expression matches;"
2050
"otherwise, it returns a nonzero value. See the table below for"
2051
"what nonzero values mean. You can use @code{regerror} to produce an"
2052
"error message string describing the reason for a nonzero value; "
2053
"see @ref{Regexp Cleanup}."
2055
"The parameter @var{string} points to the text to search. When using"
2056
"@code{regexec}, @var{string} must be 0-terminated. When using"
2057
"@code{regnexec}, @var{string} must be @var{len} characters long."
2059
"@code{regnexec} is not a standard function; strictly POSIX programs"
2060
"should avoid using it."
2062
"The argument @var{eflags} is a word of bit flags that enable various"
2065
"If you want to get information about what part of @var{string} actually"
2066
"matched the regular expression or its subexpressions, use the arguments"
2067
"@var{matchptr} and @var{nmatch}. Otherwise, pass @code{0} for "
2068
"@var{nmatch}, and @code{NULL} for @var{matchptr}. @xref{Regexp"
2072
"You must match the regular expression with the same set of current"
2073
"locales that were in effect when you compiled the regular expression."
2075
"The function @code{regexec} accepts the following flags in the"
2076
"@var{eflags} argument:"
2082
"Do not regard the beginning of the specified string as the beginning of"
2083
"a line; more generally, don't make any assumptions about what text might"
2089
"Do not regard the end of the specified string as the end of a line; more"
2090
"generally, don't make any assumptions about what text might follow it."
2093
"Here are the possible nonzero values that @code{regexec} can return:"
2099
"The pattern didn't match the string. This isn't really an error."
2104
"@code{regexec} ran out of memory."
2107
"@node Regexp Subexpressions, Subexpression Complications, Matching POSIX Regexps, Posix Entry Points"
2108
"@section Match Results with Subexpressions"
2110
"When @code{regexec} matches parenthetical subexpressions of"
2111
"@var{pattern}, it records which parts of @var{string} they match. It"
2112
"returns that information by storing the offsets into an array whose"
2113
"elements are structures of type @code{regmatch_t}. The first element of"
2114
"the array (index @code{0}) records the part of the string that matched"
2115
"the entire regular expression. Each other element of the array records"
2116
"the beginning and end of the part that matched a single parenthetical"
2121
"@deftp {Data Type} regmatch_t"
2122
"This is the data type of the @var{matcharray} array that you pass to"
2123
"@code{regexec}. It containes two structure fields, as follows:"
2127
"The offset in @var{string} of the beginning of a substring. Add this"
2128
"value to @var{string} to get the address of that part."
2131
"The offset in @var{string} of the end of the substring."
2137
"@deftp {Data Type} regoff_t"
2138
"@code{regoff_t} is an alias for another signed integer type."
2139
"The fields of @code{regmatch_t} have type @code{regoff_t}."
2142
"The @code{regmatch_t} elements correspond to subexpressions"
2143
"positionally; the first element (index @code{1}) records where the first"
2144
"subexpression matched, the second element records the second"
2145
"subexpression, and so on. The order of the subexpressions is the order"
2146
"in which they begin."
2148
"When you call @code{regexec}, you specify how long the @var{matchptr}"
2149
"array is, with the @var{nmatch} argument. This tells @code{regexec} how"
2150
"many elements to store. If the actual regular expression has more than"
2151
"@var{nmatch} subexpressions, then you won't get offset information about"
2152
"the rest of them. But this doesn't alter whether the pattern matches a"
2153
"particular string or not."
2155
"If you don't want @code{regexec} to return any information about where"
2156
"the subexpressions matched, you can either supply @code{0} for"
2157
"@var{nmatch}, or use the flag @code{REG_NOSUB} when you compile the"
2158
"pattern with @code{regcomp}."
2160
"@node Subexpression Complications, Regexp Cleanup, Regexp Subexpressions, Posix Entry Points"
2161
"@section Complications in Subexpression Matching"
2163
"Sometimes a subexpression matches a substring of no characters. This"
2164
"happens when @samp{f\\(o*\\)} matches the string @samp{fum}. (It really"
2165
"matches just the @samp{f}.) In this case, both of the offsets identify"
2166
"the point in the string where the null substring was found. In this"
2167
"example, the offsets are both @code{1}."
2169
"Sometimes the entire regular expression can match without using some of"
2170
"its subexpressions at all---for example, when @samp{ba\\(na\\)*} matches the"
2171
"string @samp{ba}, the parenthetical subexpression is not used. When"
2172
"this happens, @code{regexec} stores @code{-1} in both fields of the"
2173
"element for that subexpression."
2175
"Sometimes matching the entire regular expression can match a particular"
2176
"subexpression more than once---for example, when @samp{ba\\(na\\)*}"
2177
"matches the string @samp{bananana}, the parenthetical subexpression"
2178
"matches three times. When this happens, @code{regexec} usually stores"
2179
"the offsets of the last part of the string that matched the"
2180
"subexpression. In the case of @samp{bananana}, these offsets are"
2181
"@code{6} and @code{8}."
2183
"But the last match is not always the one that is chosen. It's more"
2184
"accurate to say that the last @emph{opportunity} to match is the one"
2185
"that takes precedence. What this means is that when one subexpression"
2186
"appears within another, then the results reported for the inner"
2187
"subexpression reflect whatever happened on the last match of the outer"
2188
"subexpression. For an example, consider @samp{\\(ba\\(na\\)*s \\)*} matching"
2189
"the string @samp{bananas bas }. The last time the inner expression"
2190
"actually matches is near the end of the first word. But it is "
2191
"@emph{considered} again in the second word, and fails to match there."
2192
"@code{regexec} reports nonuse of the ``na'' subexpression."
2194
"Another place where this rule applies is when the regular expression"
2195
"@w{@samp{\\(ba\\(na\\)*s \\|nefer\\(ti\\)* \\)*}} matches @samp{bananas nefertiti}."
2196
"The ``na'' subexpression does match in the first word, but it doesn't"
2197
"match in the second word because the other alternative is used there."
2198
"Once again, the second repetition of the outer subexpression overrides"
2199
"the first, and within that second repetition, the ``na'' subexpression"
2200
"is not used. So @code{regexec} reports nonuse of the ``na''"
2203
"@node Regexp Cleanup, , Subexpression Complications, Posix Entry Points"
2204
"@section POSIX Regexp Matching Cleanup"
2206
"When you are finished using a compiled regular expression, you can"
2207
"free the storage it uses by calling @code{regfree}."
2211
"@deftypefun void regfree (regex_t *@var{compiled})"
2212
"Calling @code{regfree} frees all the storage that @code{*@var{compiled}}"
2213
"points to. This includes various internal fields of the @code{regex_t}"
2214
"structure that aren't documented in this manual."
2216
"@code{regfree} does not free the object @code{*@var{compiled}} itself."
2219
"You should always free the space in a @code{regex_t} structure with"
2220
"@code{regfree} before using the structure to compile another regular"
2223
"When @code{regcomp} or @code{regexec} reports an error, you can use"
2224
"the function @code{regerror} to turn it into an error message string."
2228
"@deftypefun size_t regerror (int @var{errcode}, regex_t *@var{compiled}, char *@var{buffer}, size_t @var{length})"
2229
"This function produces an error message string for the error code"
2230
"@var{errcode}, and stores the string in @var{length} bytes of memory"
2231
"starting at @var{buffer}. For the @var{compiled} argument, supply the"
2232
"same compiled regular expression structure that @code{regcomp} or"
2233
"@code{regexec} was working with when it got the error. Alternatively,"
2234
"you can supply @code{NULL} for @var{compiled}; you will still get a"
2235
"meaningful error message, but it might not be as detailed."
2237
"If the error message can't fit in @var{length} bytes (including a"
2238
"terminating null character), then @code{regerror} truncates it."
2239
"The string that @code{regerror} stores is always null-terminated"
2240
"even if it has been truncated."
2242
"The return value of @code{regerror} is the minimum length needed to"
2243
"store the entire error message. If this is less than @var{length}, then"
2244
"the error message was not truncated, and you can use it. Otherwise, you"
2245
"should call @code{regerror} again with a larger buffer."
2247
"Here is a function which uses @code{regerror}, but always dynamically"
2248
"allocates a buffer for the error message:"
2251
"char *get_regerror (int errcode, regex_t *compiled)"
2253
" size_t length = regerror (errcode, compiled, NULL, 0);"
2254
" char *buffer = xmalloc (length);"
2255
" (void) regerror (errcode, compiled, buffer, length);"
2261
"@node Beyond POSIX, Rx Theory, Posix Entry Points, Top"
2262
"@chapter Beyond POSIX"
2264
"This section is not finished documentation, but rather a collection of"
2265
"pointers towards some of the interesting, non-standard features of Rx."
2267
"@section New Regexp Operators"
2269
"Rx supports some unusual regexp syntax."
2271
"@code{[[:cut N:]]} sets @code{pmatch[0].final_tag} to N and causes the"
2272
"matching to stop instantly. If N is 0, the overall match fails,"
2273
"otherwise it succeeds."
2275
"@code{[[:(:]] ... [[:):]]} is just like @code{\\( ... \\)} except that in"
2276
"the first case, no pmatch entries are changed, and the subexpression is"
2277
"not counted in the numbering of parenthesized subexpressions."
2279
"@code{[[:(:]] ... [[:):]]} can be used when you do not need to know"
2280
"where a subexpression matched but are only using parentheses to effect"
2281
"the parsing of the regexp. "
2283
"There are two reasons to use @code{[[:(:]] ... [[:):]]}:"
2285
"1. regexec will run faster."
2287
"2. Currently, only 8 backreferencable subexpressions are supported:"
2288
"@code{\\1 .. \\9}. Using @code{[[:(:]] ... [[:):]]} is a way to conserve"
2289
"backreferencable subexpression names in an expression with many"
2292
"@section New POSIX Functions"
2294
"@code{regncomp} and @code{regnexec} are non-standard generalizations of"
2295
"@code{regcomp} and @code{regexec}."
2297
"@section Tuning POSIX performance"
2299
"Two mysterious parmaters can be used to trade-off performance and"
2302
"At compile-time they are @code{RX_DEFAULT_DFA_CACHE_SIZE} and"
2303
"@code{RX_DEFAULT_NFA_DELAY}. "
2305
"If you want to mess with these (I generally don't advise it), I suggest"
2306
"experimenting for your particular application/memory situation; frob"
2307
"these by powers of two and try out the results on what you expect will"
2308
"be typical regexp workloads."
2310
"You can also set those parameters at run-time (before calling any regexp"
2311
"functions) by tweaking the corresponding variables:"
2313
"@code{rx_default_cache->bytes_allowed}"
2317
"@code{rx_basic_unfaniverse_delay}"
2321
"@section POSIX stream-style interface"
2323
"@code{rx_make_solutions}, @code{rx_next_solution}, and"
2324
"@code{rx_free_solutions} are a lower level alternative to the posix"
2325
"functions. Using those functions, you can compare a compiled regexp to"
2326
"a string that is not contiguous in memory or even a string that is not"
2327
"entirely in memory at any one time."
2329
"The code in rxposix.c points out how those functions are used."
2332
"@section DFAs Directly"
2334
"If you are only interested in pure regular expressions (no pmatch data,"
2335
"no backreferences, and no counted subexpressions), you can parse a"
2336
"regexp using @code{rx_parse}, convert it to an nfa using @code{rx_unfa},"
2337
"and run the dfa using @code{rx_init_system}, @code{rx_advance_to_final},"
2338
"and @code{rx_terminate_system}. The dfa Scheme primitives in"
2339
"@file{rgx.c} may provide some guide."
2341
"@node Rx Theory, , Beyond POSIX, Top"
2342
"@chapter Rx Theory"
2345
"There are two match algorithms. One is for truly regular regexps (those"
2346
"that can be reduced to a dfa). The other is for non-regular regexps."
2348
"The dfa algorithm implements the idea suggested in @cite{Compilers} by"
2349
"Aho, Sethi and Ullman:"
2352
"[One] approach [to pattern matching regular expressions] is to use a"
2353
"DFA, but avoid constructing all of the transition table by using a"
2354
"technique called \"lazy transition evaluation\". Here, transitions are"
2355
"computed at run time [when] actually needed. [T]ransitions are"
2356
"stored in a cache. [....] If the cache becomes full, we can erase some"
2357
"previously computed transition to make room for the new transition."
2360
"The implementation in Rx is generalized from that, but the above"
2361
"description covers what is used for Posix patterns. "
2363
"The non-dfa algorithm implements a \"recursive decomposition\" technique"
2364
"described in email by Henry Spencer. For a given pattern, this"
2365
"algorithm first checks to see if a simpler, superset language,"
2366
"DFA-pattern matches. If it does, then this algorithm does the"
2367
"detail-work to see if the non-DFA pattern matches."
2368
"\\input texinfo @c -*-texinfo-*-"
2369
"@c %**start of header"
2370
"@setfilename rx.info"
2372
"@setchapternewpage odd"
2373
"@c %**end of header"
2375
"@c This title page illustrates only one of the"
2376
"@c two methods of forming a title page."
2382
"@center except the chapter \"Posix Entry Points\" "
2383
"@center from @emph{The GNU C Library} reference manual"
2384
"@center by Sandra Loosemore"
2386
"@center Richard M. Stallman, Roland McGrath, and Andrew Oram"
2388
"@c The following two commands"
2389
"@c start the copyright page."
2391
"@vskip 0pt plus 1filll"
2392
"Copyright @copyright{} 1995 Cygnus Support"
2394
"except the chapter \"Posix Entry Points\" which is:"
2396
"Copyright @copyright{} 1995 Free Software Foundation, Inc."
2398
"Permission is granted to make and distribute verbatim copies of"
2399
"this manual provided the copyright notice and this permission notice"
2400
"are preserved on all copies."
2402
"Permission is granted to copy and distribute modified versions of this"
2403
"manual under the conditions for verbatim copying, provided that the entire"
2404
"resulting derived work is distributed under the terms of a permission"
2405
"notice identical to this one."
2407
"Permission is granted to copy and distribute translations of this manual"
2408
"into another language, under the above conditions for modified versions,"
2409
"except that this permission notice may be stated in a translation approved"
2414
"@node Top, Copying, (dir), (dir)"
2417
"This document describes Rx."
2420
"* Copying:: Sharing is good."
2421
"* Overview:: Fnord"
2422
"* Posix Basic Regular Expressions:: A popular regexp syntax."
2423
"* Posix Entry Points:: The POSIX way to regexp."
2424
"* Beyond POSIX:: Hints about cool features."
2425
"* Rx Theory:: Hints about how it works."
2428
"@node Copying, Overview, Top, Top"
2431
"@center Copyright (C) 1996"
2433
"@center Berkeley, CA USA"
2435
"@center except portions of \"POSIX Regex Functions\" which are"
2436
"@center Copyright (C) 1995"
2437
"@center Free Software Foundation, Inc."
2440
"Permission to use, copy, modify, distribute, and sell this software and"
2441
"its documentation for any purpose is hereby granted without fee,"
2442
"provided that the above copyright notice appear in all copies and that"
2443
"both that copyright notice and this permission notice appear in"
2444
"supporting documentation."
2446
"@center NO WARRANTY"
2449
"BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR"
2450
"THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN"
2451
"OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES"
2452
"PROVIDE THE PROGRAM \"AS IS\" WITHOUT WARRANTY OF ANY KIND, EITHER"
2453
"EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED"
2454
"WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE"
2455
"ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH"
2456
"YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL"
2457
"NECESSARY SERVICING, REPAIR OR CORRECTION."
2460
"IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING"
2461
"WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR"
2462
"REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR"
2463
"DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL"
2464
"DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM"
2465
"(INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED"
2466
"INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF"
2467
"THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER OR"
2468
"OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES."
2470
"@node Overview, Posix Basic Regular Expressions, Copying, Top"
2473
"Nothing to say here, yet."
2475
"@node Posix Basic Regular Expressions, Posix Entry Points, Overview, Top"
2476
"@chapter Posix Basic Regular Expressions"
2478
"The Posix Basic Regular Expression language is a notation for describing"
2479
"textual patterns. Regexps are typically used by comparing them to a"
2480
"string to see if that string matches the pattern, or by searching within"
2481
"a string for a substring that matches."
2483
"This chapter introduces the Posix regexp notation. This is not a formal"
2484
"or precise definition of Posix regexps -- it is an intuitive and"
2485
"hopefully expository description of them."
2488
"* An Introduction to Regexps:: "
2489
"* Literal Regexps:: "
2490
"* Character Sets:: "
2491
"* Subexpressions:: "
2492
"* Repeated Subexpressions:: "
2493
"* Optional Subexpressions:: "
2494
"* Counted Subexpressions:: "
2495
"* Alternative Subexpressions:: "
2496
"* Backreferences:: "
2497
"* A Summary of Regexp Syntax:: "
2498
"* Ambiguous Patterns:: "
2502
"@node An Introduction to Regexps, Literal Regexps, Posix Basic Regular Expressions, Posix Basic Regular Expressions"
2503
"@section An Introduction to Regexps"
2505
"In the simplest cases, a regexp is just a literal string that must"
2506
"match exactly. For example, the pattern:"
2512
"matches the string \"regexp\" and no others."
2514
"Some characters have a special meaning when they occur in a regexp."
2515
"They aren't matched literally as in the previous example, but instead"
2516
"denote a more general pattern. For example, the character @code{*}"
2517
"is used to indicate that the preceeding element of a regexp may be"
2518
"repeated 0, 1, or more times. In the pattern:"
2524
"the @code{*} indicates that the preceeding @code{o} can be repeated 0 or"
2525
"more times. So the pattern matches:"
2535
"Suppose you want to write a pattern that literally matches a special"
2536
"character like @code{*} -- in other words, you don't want to @code{*} to"
2537
"indicate a permissible repetition, but to match @code{*} literally. This"
2538
"is accomplished by quoting the special character with a backslash. "
2545
"matches the string:"
2552
"and no other strings."
2554
"In five cases, the pattern is reversed -- a backslash makes the"
2555
"character special instead of making a special character normal. The"
2556
"characters @code{+}, @code{?}, @code{|}, @code{(}, and @code{)} are"
2557
"normal but the sequences @code{\\+}, @code{\\?}, @code{\\|}, @code{\\(}, and"
2558
"@code{\\)} are special (their meaning is described later)."
2560
"The remaining sections of this chapter introduce and explain the various"
2561
"special characters that can occur in regexps."
2563
"@node Literal Regexps, Character Sets, An Introduction to Regexps, Posix Basic Regular Expressions"
2564
"@section Literal Regexps"
2566
"A literal regexp is a string which contains no special characters."
2567
"A literal regexp matches an identical string, but no other characters."
2582
"Generally, whitespace characters, numbers, and letters are not special."
2583
"Some punctuation characters are special and some are not (the syntax"
2584
"summary at the end of this chapter makes a convenient reference for"
2585
"which characters are special and which aren't)."
2588
"@node Character Sets, Subexpressions, Literal Regexps, Posix Basic Regular Expressions"
2589
"@section Character Sets"
2591
"This section introduces the special characters @code{.} and @code{[}."
2593
"@code{.} matches any character except the NULL character. For example:"
2613
"@code{[} begins a @dfn{character set}. A character set is similar to"
2614
"@code{.} in that it matches not a single, literal character, but any"
2615
"of a set of characters. @code{[} is different from @code{.} in that"
2616
"with @code{[}, you define the set of characters explicitly."
2618
"There are three basic forms a character set can take."
2620
"In the first form, the character set is spelled out:"
2623
"[<cset-spec>] -- every character in <cset-spec> is in the set."
2626
"In the second form, the character set indicated is the negation of"
2627
"a character set is explicitly spelled out:"
2630
"[^<cset-spec>] -- every character *not* in <cset-spec> is in the set."
2633
"A @code{<cset-spec>} is more or less an explicit enumeration of a set"
2634
"of characters. It can be written as a string of individual characters:"
2640
"or as a range of characters:"
2646
"These two forms can be mixed:"
2652
"Note that special regexp characters (such as @code{*}) are @emph{not}"
2653
"special within a character set. @code{-}, as illustrated above,"
2654
"@emph{is} special, except, as illustrated below, when it is the first"
2655
"character mentioned."
2657
"This is a four-character set:"
2663
"The third form of a character set makes use of a pre-defined \"character"
2667
"[[:class-name:]] -- every character described by class-name is in the set."
2670
"The supported character classes are:"
2673
"alnum - the set of alpha-numeric characters"
2674
"alpha - the set of alphabetic characters"
2675
"blank - tab and space"
2676
"cntrl - the control characters"
2677
"digit - decimal digits"
2678
"graph - all printable characters except space"
2679
"lower - lower case letters"
2680
"print - the \"printable\" characters"
2681
"punct - punctuation"
2682
"space - whitespace characters"
2683
"upper - upper case letters"
2684
"xdigit - hexidecimal digits"
2687
"Finally, character class sets can also be inverted:"
2690
"[^[:space:]] - all non-whitespace characters"
2693
"Character sets can be used in a regular expression anywhere a literal"
2696
"@node Subexpressions, Repeated Subexpressions, Character Sets, Posix Basic Regular Expressions"
2697
"@section Subexpressions"
2699
"A subexpression is a regular expression enclosed in @code{\\(} and"
2700
"@code{\\)}. A subexpression can be used anywhere a single character or"
2701
"character set can be used."
2703
"Subexpressions are useful for grouping regexp constructs. For example,"
2704
"the repeat operator, @code{*}, usually applies to just the preceeding"
2705
"character. Recall that:"
2720
"Using a subexpression, we can apply @code{*} to a longer string:"
2735
"Subexpressions also have a special meaning with regard to backreferences"
2736
"and substitutions (see @xref{Backreferences})."
2739
"@node Repeated Subexpressions, Optional Subexpressions, Subexpressions, Posix Basic Regular Expressions"
2740
"@section Repeated Subexpressions"
2743
"@code{*} is the repeat operator. It applies to the preceeding"
2744
"character, character set, subexpression or backreference. It indicates"
2745
"that the preceeding element can be matched 0 or more times:"
2763
"@code{\\+} is similar to @code{*} except that @code{\\+} requires the"
2764
"preceeding element to be matched at least once. So while:"
2780
"does not. Both match "
2789
"Thus, @code{bana\\(na\\)+} is short-hand for @code{banana\\(na\\)*}."
2792
"@node Optional Subexpressions, Counted Subexpressions, Repeated Subexpressions, Posix Basic Regular Expressions"
2793
"@section Optional Subexpressions"
2795
"@code{\\?} indicates that the preceeding character, character set, or"
2796
"subexpression is optional. It is permitted to match, or to be skipped:"
2815
"@node Counted Subexpressions, Alternative Subexpressions, Optional Subexpressions, Posix Basic Regular Expressions"
2816
"@section Counted Subexpressions"
2818
"An interval expression, @code{@{m,n@}} where @code{m} and @code{n} are"
2819
"non-negative integers with @code{n >= m}, applies to the preceeding"
2820
"character, character set, subexpression or backreference. It indicates"
2821
"that the preceeding element must match at least @code{m} times and may"
2822
"match as many as @code{n} times."
2827
"c\\([ad]\\)@{1,4@}"
2847
"@node Alternative Subexpressions, Backreferences, Counted Subexpressions, Posix Basic Regular Expressions"
2848
"@section Alternative Subexpressions"
2850
"An alternative is written:"
2853
"regexp-1\\|regexp-2\\|regexp-3\\|..."
2856
"It matches anything matched by some @code{regexp-n}. For example:"
2859
"Crosby, Stills, \\(and Nash\\|Nash, and Young\\)"
2865
"Crosby, Stills, and Nash"
2871
"Crosby, Stills, Nash, and Young"
2875
"@node Backreferences, A Summary of Regexp Syntax, Alternative Subexpressions, Posix Basic Regular Expressions"
2876
"@section Backreferences, Extractions and Substitutions"
2878
"A backreference is written @code{\\n} where @code{n} is some single digit"
2879
"other than 0. To be a valid backreference, there must be at least"
2880
"@code{n} parenthesized subexpressions in the pattern prior to the"
2883
"A backreference matches a literal copy of whatever was matched by the"
2884
"corresponding subexpression. For example,"
2899
"In some applications, subexpressions are used to extract substrings."
2900
"For example, Emacs has the functions @code{match-beginnning} and"
2901
"@code{match-end} which report the positions of strings matched by"
2902
"subexpressions. These functions use the same numbering scheme for"
2903
"subexpressions as backreferences, with the additional rule that"
2904
"subexpression 0 is defined to be the whole regexp."
2906
"In some applications, subexpressions are used in string substitution."
2907
"This again uses the backreference numbering scheme. For example, this sed"
2911
"s/From:.*<\\(.*\\)>/To: \\1/"
2914
"first matches the line:"
2917
"From: Joe Schmoe <schmoe@@uspringfield.edu>"
2920
"when it does, subexpression 1 matches \"schmoe@@uspringfield.edu\"."
2921
"The command replaces the matched line with \"To: \\1\" after doing"
2922
"subexpression substitution on it to get:"
2925
"To: schmoe@@uspringfield.edu"
2929
"@node A Summary of Regexp Syntax, Ambiguous Patterns, Backreferences, Posix Basic Regular Expressions"
2930
"@section A Summary of Regexp Syntax"
2932
"In summary, regexps can be:"
2934
"@code{abcd} -- matching a string literally"
2936
"@code{.} -- matching everything except NULL"
2938
"@code{[a-z_?]}, @code{^[a-z_?]}, @code{[[:alpha:]]} and"
2939
"@code{[^[:alpha:]]} -- matching character sets"
2941
"@code{\\(subexp\\)} -- grouping an expression into a subexpression."
2943
"@code{\\n} -- match a copy of whatever was matched by the nth subexpression."
2945
"The following special characters and sequences can be applied to a"
2946
"character, character set, subexpression, or backreference:"
2948
"@code{*} -- repeat the preceeding element 0 or more times."
2950
"@code{\\+} -- repeat the preceeding element 1 or more times."
2952
"@code{\\?} -- match the preceeding element 0 or 1 time."
2954
"@code{@{m,n@}} -- match the preceeding element at least @code{m}, and as"
2955
"many as @code{n} times."
2957
"@code{regexp-1\\|regexp-2\\|..} -- match any regexp-n."
2959
"A special character, like @code{.} or @code{*} can be made into a literal"
2960
"character by prefixing it with @code{\\}."
2962
"A special sequence, like @code{\\+} or @code{\\?} can be made into a"
2963
"literal character by dropping the @code{\\}."
2966
"@node Ambiguous Patterns, , A Summary of Regexp Syntax, Posix Basic Regular Expressions"
2967
"@section Ambiguous Patterns"
2969
"Sometimes a regular expression appears to be ambiguous. For example, suppose"
2970
"we compare the pattern:"
2982
"either just the first 5 characters will match, or the whole string will match."
2984
"In every case like this, the longer match is preferred. The whole"
2985
"string will match."
2987
"Sometimes there is ambiguity not about how many characters to match, but"
2988
"where the subexpressions occur within the match. This can effect"
2989
"extraction functions like Emacs' @code{match-beginning} or rewrite"
2990
"functions like sed's @code{s} command. For example, consider matching"
2994
"b\\(\\[^q]*\\)\\(ing\\)?"
2997
"against the string"
3003
"One possibility is that the first subexpression matches \"eginning\" and"
3004
"the second is skipped. Another possibility is that the first"
3005
"subexpression matches \"eginn\" and the second matches \"ing\"."
3007
"The rule is that consistant with matching as many characters as "
3008
"possible, the length of lower numbered subexpressions is maximized"
3009
"in preference to maximizing the length of later subexpressions."
3011
"In the case of the above example, the two possible matches are equal in"
3012
"overall length. Therefore, it comes down to maximizing the"
3013
"lower-numbered subexpression, \\1. The correct answer is that \\1 matches"
3014
"\"eginning\" and \\2 is skipped."
3016
"@node Posix Entry Points, Beyond POSIX, Posix Basic Regular Expressions, Top"
3017
"@chapter Posix Entry Points"
3019
"This section is excerpted from @emph{The GNU C Library} reference manual"
3020
"by Sandra Loosemore with Richard M. Stallman, Roland McGrath, and Andrew"
3023
"The GNU C library supports the standard POSIX.2 interface. Programs"
3024
"using this interface should include the header file @file{rxposix.h}."
3027
"* POSIX Regexp Compilation:: Using @code{regcomp} to prepare to match."
3028
"* Flags for POSIX Regexps:: Syntax variations for @code{regcomp}."
3029
"* Matching POSIX Regexps:: Using @code{regexec} to match the compiled"
3030
" pattern that you get from @code{regcomp}."
3031
"* Regexp Subexpressions:: Finding which parts of the string were matched."
3032
"* Subexpression Complications:: Find points of which parts were matched."
3033
"* Regexp Cleanup:: Freeing storage; reporting errors."
3036
"@node POSIX Regexp Compilation, Flags for POSIX Regexps, Posix Entry Points, Posix Entry Points"
3037
"@section POSIX Regular Expression Compilation"
3039
"Before you can actually match a regular expression, you must"
3040
"@dfn{compile} it. This is not true compilation---it produces a special"
3041
"data structure, not machine instructions. But it is like ordinary"
3042
"compilation in that its purpose is to enable you to ``execute'' the"
3043
"pattern fast. (@xref{Matching POSIX Regexps}, for how to use the"
3044
"compiled regular expression for matching.)"
3046
"There is a special data type for compiled regular expressions:"
3050
"@deftp {Data Type} regex_t"
3051
"This type of object holds a compiled regular expression."
3052
"It is actually a structure. It has just one field that your programs"
3057
"This field holds the number of parenthetical subexpressions in the"
3058
"regular expression that was compiled."
3061
"There are several other fields, but we don't describe them here, because"
3062
"only the functions in the library should use them."
3065
"After you create a @code{regex_t} object, you can compile a regular"
3066
"expression into it by calling @code{regcomp}."
3070
"@deftypefun int regcomp (regex_t *@var{compiled}, const char *@var{pattern}, int @var{cflags})"
3071
"@deftypefunx int regncomp (regex_t *@var{compiled}, int len, const char *@var{pattern}, int @var{cflags})"
3072
"The function @code{regcomp} ``compiles'' a regular expression into a"
3073
"data structure that you can use with @code{regexec} to match against a"
3074
"string. The compiled regular expression format is designed for"
3075
"efficient matching. @code{regcomp} stores it into @code{*@var{compiled}}."
3077
"The parameter @var{pattern} points to the regular expression to be"
3078
"compiled. When using @code{regcomp}, @var{pattern} must be"
3079
"0-terminated. When using @code{regncomp}, @var{pattern} must be"
3080
"@var{len} characters long."
3082
"@code{regncomp} is not a standard function; strictly POSIX programs"
3083
"should avoid using it."
3085
"It's up to you to allocate an object of type @code{regex_t} and pass its"
3086
"address to @code{regcomp}."
3088
"The argument @var{cflags} lets you specify various options that control"
3089
"the syntax and semantics of regular expressions. @xref{Flags for POSIX"
3092
"If you use the flag @code{REG_NOSUB}, then @code{regcomp} omits from"
3093
"the compiled regular expression the information necessary to record"
3094
"how subexpressions actually match. In this case, you might as well"
3095
"pass @code{0} for the @var{matchptr} and @var{nmatch} arguments when"
3096
"you call @code{regexec}."
3098
"If you don't use @code{REG_NOSUB}, then the compiled regular expression"
3099
"does have the capacity to record how subexpressions match. Also,"
3100
"@code{regcomp} tells you how many subexpressions @var{pattern} has, by"
3101
"storing the number in @code{@var{compiled}->re_nsub}. You can use that"
3102
"value to decide how long an array to allocate to hold information about"
3103
"subexpression matches."
3105
"@code{regcomp} returns @code{0} if it succeeds in compiling the regular"
3106
"expression; otherwise, it returns a nonzero error code (see the table"
3107
"below). You can use @code{regerror} to produce an error message string"
3108
"describing the reason for a nonzero value; see @ref{Regexp Cleanup}."
3112
"Here are the possible nonzero values that @code{regcomp} can return:"
3118
"There was an invalid @samp{\\@{@dots{}\\@}} construct in the regular"
3119
"expression. A valid @samp{\\@{@dots{}\\@}} construct must contain either"
3120
"a single number, or two numbers in increasing order separated by a"
3126
"There was a syntax error in the regular expression."
3131
"A repetition operator such as @samp{?} or @samp{*} appeared in a bad"
3132
"position (with no preceding subexpression to act on)."
3136
"@item REG_ECOLLATE"
3137
"The regular expression referred to an invalid collating element (one not"
3138
"defined in the current locale for string collation). "
3143
"The regular expression referred to an invalid character class name."
3148
"The regular expression ended with @samp{\\}."
3153
"There was an invalid number in the @samp{\\@var{digit}} construct."
3158
"There were unbalanced square brackets in the regular expression."
3163
"An extended regular expression had unbalanced parentheses,"
3164
"or a basic regular expression had unbalanced @samp{\\(} and @samp{\\)}."
3169
"The regular expression had unbalanced @samp{\\@{} and @samp{\\@}}."
3174
"One of the endpoints in a range expression was invalid."
3179
"@code{regcomp} ran out of memory."
3182
"@node Flags for POSIX Regexps, Matching POSIX Regexps, POSIX Regexp Compilation, Posix Entry Points"
3183
"@section Flags for POSIX Regular Expressions"
3185
"These are the bit flags that you can use in the @var{cflags} operand when"
3186
"compiling a regular expression with @code{regcomp}."
3191
"@item REG_EXTENDED"
3192
"Treat the pattern as an extended regular expression, rather than as a"
3193
"basic regular expression."
3198
"Ignore case when matching letters."
3203
"Don't bother storing the contents of the @var{matches-ptr} array."
3208
"Treat a newline in @var{string} as dividing @var{string} into multiple"
3209
"lines, so that @samp{$} can match before the newline and @samp{^} can"
3210
"match after. Also, don't permit @samp{.} to match a newline, and don't"
3211
"permit @samp{[^@dots{}]} to match a newline."
3213
"Otherwise, newline acts like any other ordinary character."
3216
"@node Matching POSIX Regexps, Regexp Subexpressions, Flags for POSIX Regexps, Posix Entry Points"
3217
"@section Matching a Compiled POSIX Regular Expression"
3219
"Once you have compiled a regular expression, as described in @ref{POSIX"
3220
"Regexp Compilation}, you can match it against strings using"
3221
"@code{regexec}. A match anywhere inside the string counts as success,"
3222
"unless the regular expression contains anchor characters (@samp{^} or"
3227
"@deftypefun int regexec (regex_t *@var{compiled}, char *@var{string}, size_t @var{nmatch}, regmatch_t @var{matchptr} @t{[]}, int @var{eflags})"
3228
"@deftypefunx int regnexec (regex_t *@var{compiled}, int len, char *@var{string}, size_t @var{nmatch}, regmatch_t @var{matchptr} @t{[]}, int @var{eflags})"
3229
"This function tries to match the compiled regular expression"
3230
"@code{*@var{compiled}} against @var{string}."
3232
"@code{regexec} returns @code{0} if the regular expression matches;"
3233
"otherwise, it returns a nonzero value. See the table below for"
3234
"what nonzero values mean. You can use @code{regerror} to produce an"
3235
"error message string describing the reason for a nonzero value; "
3236
"see @ref{Regexp Cleanup}."
3238
"The parameter @var{string} points to the text to search. When using"
3239
"@code{regexec}, @var{string} must be 0-terminated. When using"
3240
"@code{regnexec}, @var{string} must be @var{len} characters long."
3242
"@code{regnexec} is not a standard function; strictly POSIX programs"
3243
"should avoid using it."
3245
"The argument @var{eflags} is a word of bit flags that enable various"
3248
"If you want to get information about what part of @var{string} actually"
3249
"matched the regular expression or its subexpressions, use the arguments"
3250
"@var{matchptr} and @var{nmatch}. Otherwise, pass @code{0} for "
3251
"@var{nmatch}, and @code{NULL} for @var{matchptr}. @xref{Regexp"
3255
"You must match the regular expression with the same set of current"
3256
"locales that were in effect when you compiled the regular expression."
3258
"The function @code{regexec} accepts the following flags in the"
3259
"@var{eflags} argument:"
3265
"Do not regard the beginning of the specified string as the beginning of"
3266
"a line; more generally, don't make any assumptions about what text might"
3272
"Do not regard the end of the specified string as the end of a line; more"
3273
"generally, don't make any assumptions about what text might follow it."
3276
"Here are the possible nonzero values that @code{regexec} can return:"
3282
"The pattern didn't match the string. This isn't really an error."
3287
"@code{regexec} ran out of memory."
3290
"@node Regexp Subexpressions, Subexpression Complications, Matching POSIX Regexps, Posix Entry Points"
3291
"@section Match Results with Subexpressions"
3293
"When @code{regexec} matches parenthetical subexpressions of"
3294
"@var{pattern}, it records which parts of @var{string} they match. It"
3295
"returns that information by storing the offsets into an array whose"
3296
"elements are structures of type @code{regmatch_t}. The first element of"
3297
"the array (index @code{0}) records the part of the string that matched"
3298
"the entire regular expression. Each other element of the array records"
3299
"the beginning and end of the part that matched a single parenthetical"
3304
"@deftp {Data Type} regmatch_t"
3305
"This is the data type of the @var{matcharray} array that you pass to"
3306
"@code{regexec}. It containes two structure fields, as follows:"
3310
"The offset in @var{string} of the beginning of a substring. Add this"
3311
"value to @var{string} to get the address of that part."
3314
"The offset in @var{string} of the end of the substring."
3320
"@deftp {Data Type} regoff_t"
3321
"@code{regoff_t} is an alias for another signed integer type."
3322
"The fields of @code{regmatch_t} have type @code{regoff_t}."
3325
"The @code{regmatch_t} elements correspond to subexpressions"
3326
"positionally; the first element (index @code{1}) records where the first"
3327
"subexpression matched, the second element records the second"
3328
"subexpression, and so on. The order of the subexpressions is the order"
3329
"in which they begin."
3331
"When you call @code{regexec}, you specify how long the @var{matchptr}"
3332
"array is, with the @var{nmatch} argument. This tells @code{regexec} how"
3333
"many elements to store. If the actual regular expression has more than"
3334
"@var{nmatch} subexpressions, then you won't get offset information about"
3335
"the rest of them. But this doesn't alter whether the pattern matches a"
3336
"particular string or not."
3338
"If you don't want @code{regexec} to return any information about where"
3339
"the subexpressions matched, you can either supply @code{0} for"
3340
"@var{nmatch}, or use the flag @code{REG_NOSUB} when you compile the"
3341
"pattern with @code{regcomp}."
3343
"@node Subexpression Complications, Regexp Cleanup, Regexp Subexpressions, Posix Entry Points"
3344
"@section Complications in Subexpression Matching"
3346
"Sometimes a subexpression matches a substring of no characters. This"
3347
"happens when @samp{f\\(o*\\)} matches the string @samp{fum}. (It really"
3348
"matches just the @samp{f}.) In this case, both of the offsets identify"
3349
"the point in the string where the null substring was found. In this"
3350
"example, the offsets are both @code{1}."
3352
"Sometimes the entire regular expression can match without using some of"
3353
"its subexpressions at all---for example, when @samp{ba\\(na\\)*} matches the"
3354
"string @samp{ba}, the parenthetical subexpression is not used. When"
3355
"this happens, @code{regexec} stores @code{-1} in both fields of the"
3356
"element for that subexpression."
3358
"Sometimes matching the entire regular expression can match a particular"
3359
"subexpression more than once---for example, when @samp{ba\\(na\\)*}"
3360
"matches the string @samp{bananana}, the parenthetical subexpression"
3361
"matches three times. When this happens, @code{regexec} usually stores"
3362
"the offsets of the last part of the string that matched the"
3363
"subexpression. In the case of @samp{bananana}, these offsets are"
3364
"@code{6} and @code{8}."
3366
"But the last match is not always the one that is chosen. It's more"
3367
"accurate to say that the last @emph{opportunity} to match is the one"
3368
"that takes precedence. What this means is that when one subexpression"
3369
"appears within another, then the results reported for the inner"
3370
"subexpression reflect whatever happened on the last match of the outer"
3371
"subexpression. For an example, consider @samp{\\(ba\\(na\\)*s \\)*} matching"
3372
"the string @samp{bananas bas }. The last time the inner expression"
3373
"actually matches is near the end of the first word. But it is "
3374
"@emph{considered} again in the second word, and fails to match there."
3375
"@code{regexec} reports nonuse of the ``na'' subexpression."
3377
"Another place where this rule applies is when the regular expression"
3378
"@w{@samp{\\(ba\\(na\\)*s \\|nefer\\(ti\\)* \\)*}} matches @samp{bananas nefertiti}."
3379
"The ``na'' subexpression does match in the first word, but it doesn't"
3380
"match in the second word because the other alternative is used there."
3381
"Once again, the second repetition of the outer subexpression overrides"
3382
"the first, and within that second repetition, the ``na'' subexpression"
3383
"is not used. So @code{regexec} reports nonuse of the ``na''"
3386
"@node Regexp Cleanup, , Subexpression Complications, Posix Entry Points"
3387
"@section POSIX Regexp Matching Cleanup"
3389
"When you are finished using a compiled regular expression, you can"
3390
"free the storage it uses by calling @code{regfree}."
3394
"@deftypefun void regfree (regex_t *@var{compiled})"
3395
"Calling @code{regfree} frees all the storage that @code{*@var{compiled}}"
3396
"points to. This includes various internal fields of the @code{regex_t}"
3397
"structure that aren't documented in this manual."
3399
"@code{regfree} does not free the object @code{*@var{compiled}} itself."
3402
"You should always free the space in a @code{regex_t} structure with"
3403
"@code{regfree} before using the structure to compile another regular"
3406
"When @code{regcomp} or @code{regexec} reports an error, you can use"
3407
"the function @code{regerror} to turn it into an error message string."
3411
"@deftypefun size_t regerror (int @var{errcode}, regex_t *@var{compiled}, char *@var{buffer}, size_t @var{length})"
3412
"This function produces an error message string for the error code"
3413
"@var{errcode}, and stores the string in @var{length} bytes of memory"
3414
"starting at @var{buffer}. For the @var{compiled} argument, supply the"
3415
"same compiled regular expression structure that @code{regcomp} or"
3416
"@code{regexec} was working with when it got the error. Alternatively,"
3417
"you can supply @code{NULL} for @var{compiled}; you will still get a"
3418
"meaningful error message, but it might not be as detailed."
3420
"If the error message can't fit in @var{length} bytes (including a"
3421
"terminating null character), then @code{regerror} truncates it."
3422
"The string that @code{regerror} stores is always null-terminated"
3423
"even if it has been truncated."
3425
"The return value of @code{regerror} is the minimum length needed to"
3426
"store the entire error message. If this is less than @var{length}, then"
3427
"the error message was not truncated, and you can use it. Otherwise, you"
3428
"should call @code{regerror} again with a larger buffer."
3430
"Here is a function which uses @code{regerror}, but always dynamically"
3431
"allocates a buffer for the error message:"
3434
"char *get_regerror (int errcode, regex_t *compiled)"
3436
" size_t length = regerror (errcode, compiled, NULL, 0);"
3437
" char *buffer = xmalloc (length);"
3438
" (void) regerror (errcode, compiled, buffer, length);"
3444
"@node Beyond POSIX, Rx Theory, Posix Entry Points, Top"
3445
"@chapter Beyond POSIX"
3447
"This section is not finished documentation, but rather a collection of"
3448
"pointers towards some of the interesting, non-standard features of Rx."
3450
"@section New Regexp Operators"
3452
"Rx supports some unusual regexp syntax."
3454
"@code{[[:cut N:]]} sets @code{pmatch[0].final_tag} to N and causes the"
3455
"matching to stop instantly. If N is 0, the overall match fails,"
3456
"otherwise it succeeds."
3458
"@code{[[:(:]] ... [[:):]]} is just like @code{\\( ... \\)} except that in"
3459
"the first case, no pmatch entries are changed, and the subexpression is"
3460
"not counted in the numbering of parenthesized subexpressions."
3462
"@code{[[:(:]] ... [[:):]]} can be used when you do not need to know"
3463
"where a subexpression matched but are only using parentheses to effect"
3464
"the parsing of the regexp. "
3466
"There are two reasons to use @code{[[:(:]] ... [[:):]]}:"
3468
"1. regexec will run faster."
3470
"2. Currently, only 8 backreferencable subexpressions are supported:"
3471
"@code{\\1 .. \\9}. Using @code{[[:(:]] ... [[:):]]} is a way to conserve"
3472
"backreferencable subexpression names in an expression with many"
3475
"@section New POSIX Functions"
3477
"@code{regncomp} and @code{regnexec} are non-standard generalizations of"
3478
"@code{regcomp} and @code{regexec}."
3480
"@section Tuning POSIX performance"
3482
"Two mysterious parmaters can be used to trade-off performance and"
3485
"At compile-time they are @code{RX_DEFAULT_DFA_CACHE_SIZE} and"
3486
"@code{RX_DEFAULT_NFA_DELAY}. "
3488
"If you want to mess with these (I generally don't advise it), I suggest"
3489
"experimenting for your particular application/memory situation; frob"
3490
"these by powers of two and try out the results on what you expect will"
3491
"be typical regexp workloads."
3493
"You can also set those parameters at run-time (before calling any regexp"
3494
"functions) by tweaking the corresponding variables:"
3496
"@code{rx_default_cache->bytes_allowed}"
3500
"@code{rx_basic_unfaniverse_delay}"
3504
"@section POSIX stream-style interface"
3506
"@code{rx_make_solutions}, @code{rx_next_solution}, and"
3507
"@code{rx_free_solutions} are a lower level alternative to the posix"
3508
"functions. Using those functions, you can compare a compiled regexp to"
3509
"a string that is not contiguous in memory or even a string that is not"
3510
"entirely in memory at any one time."
3512
"The code in rxposix.c points out how those functions are used."
3515
"@section DFAs Directly"
3517
"If you are only interested in pure regular expressions (no pmatch data,"
3518
"no backreferences, and no counted subexpressions), you can parse a"
3519
"regexp using @code{rx_parse}, convert it to an nfa using @code{rx_unfa},"
3520
"and run the dfa using @code{rx_init_system}, @code{rx_advance_to_final},"
3521
"and @code{rx_terminate_system}. The dfa Scheme primitives in"
3522
"@file{rgx.c} may provide some guide."
3524
"@node Rx Theory, , Beyond POSIX, Top"
3525
"@chapter Rx Theory"
3528
"There are two match algorithms. One is for truly regular regexps (those"
3529
"that can be reduced to a dfa). The other is for non-regular regexps."
3531
"The dfa algorithm implements the idea suggested in @cite{Compilers} by"
3532
"Aho, Sethi and Ullman:"
3535
"[One] approach [to pattern matching regular expressions] is to use a"
3536
"DFA, but avoid constructing all of the transition table by using a"
3537
"technique called \"lazy transition evaluation\". Here, transitions are"
3538
"computed at run time [when] actually needed. [T]ransitions are"
3539
"stored in a cache. [....] If the cache becomes full, we can erase some"
3540
"previously computed transition to make room for the new transition."
3543
"The implementation in Rx is generalized from that, but the above"
3544
"description covers what is used for Posix patterns. "
3546
"The non-dfa algorithm implements a \"recursive decomposition\" technique"
3547
"described in email by Henry Spencer. For a given pattern, this"
3548
"algorithm first checks to see if a simpler, superset language,"
3549
"DFA-pattern matches. If it does, then this algorithm does the"
3550
"detail-work to see if the non-DFA pattern matches."
3551
"\\input texinfo @c -*-texinfo-*-"
3552
"@c %**start of header"
3553
"@setfilename rx.info"
3555
"@setchapternewpage odd"
3556
"@c %**end of header"
3558
"@c This title page illustrates only one of the"
3559
"@c two methods of forming a title page."
3565
"@center except the chapter \"Posix Entry Points\" "
3566
"@center from @emph{The GNU C Library} reference manual"
3567
"@center by Sandra Loosemore"
3569
"@center Richard M. Stallman, Roland McGrath, and Andrew Oram"
3571
"@c The following two commands"
3572
"@c start the copyright page."
3574
"@vskip 0pt plus 1filll"
3575
"Copyright @copyright{} 1995 Cygnus Support"
3577
"except the chapter \"Posix Entry Points\" which is:"
3579
"Copyright @copyright{} 1995 Free Software Foundation, Inc."
3581
"Permission is granted to make and distribute verbatim copies of"
3582
"this manual provided the copyright notice and this permission notice"
3583
"are preserved on all copies."
3585
"Permission is granted to copy and distribute modified versions of this"
3586
"manual under the conditions for verbatim copying, provided that the entire"
3587
"resulting derived work is distributed under the terms of a permission"
3588
"notice identical to this one."
3590
"Permission is granted to copy and distribute translations of this manual"
3591
"into another language, under the above conditions for modified versions,"
3592
"except that this permission notice may be stated in a translation approved"
3597
"@node Top, Copying, (dir), (dir)"
3600
"This document describes Rx."
3603
"* Copying:: Sharing is good."
3604
"* Overview:: Fnord"
3605
"* Posix Basic Regular Expressions:: A popular regexp syntax."
3606
"* Posix Entry Points:: The POSIX way to regexp."
3607
"* Beyond POSIX:: Hints about cool features."
3608
"* Rx Theory:: Hints about how it works."
3611
"@node Copying, Overview, Top, Top"
3614
"@center Copyright (C) 1996"
3616
"@center Berkeley, CA USA"
3618
"@center except portions of \"POSIX Regex Functions\" which are"
3619
"@center Copyright (C) 1995"
3620
"@center Free Software Foundation, Inc."
3623
"Permission to use, copy, modify, distribute, and sell this software and"
3624
"its documentation for any purpose is hereby granted without fee,"
3625
"provided that the above copyright notice appear in all copies and that"
3626
"both that copyright notice and this permission notice appear in"
3627
"supporting documentation."
3629
"@center NO WARRANTY"
3632
"BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR"
3633
"THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN"
3634
"OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES"
3635
"PROVIDE THE PROGRAM \"AS IS\" WITHOUT WARRANTY OF ANY KIND, EITHER"
3636
"EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED"
3637
"WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE"
3638
"ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH"
3639
"YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL"
3640
"NECESSARY SERVICING, REPAIR OR CORRECTION."
3643
"IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING"
3644
"WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR"
3645
"REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR"
3646
"DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL"
3647
"DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM"
3648
"(INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED"
3649
"INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF"
3650
"THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER OR"
3651
"OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES."
3653
"@node Overview, Posix Basic Regular Expressions, Copying, Top"
3656
"Nothing to say here, yet."
3658
"@node Posix Basic Regular Expressions, Posix Entry Points, Overview, Top"
3659
"@chapter Posix Basic Regular Expressions"
3661
"The Posix Basic Regular Expression language is a notation for describing"
3662
"textual patterns. Regexps are typically used by comparing them to a"
3663
"string to see if that string matches the pattern, or by searching within"
3664
"a string for a substring that matches."
3666
"This chapter introduces the Posix regexp notation. This is not a formal"
3667
"or precise definition of Posix regexps -- it is an intuitive and"
3668
"hopefully expository description of them."
3671
"* An Introduction to Regexps:: "
3672
"* Literal Regexps:: "
3673
"* Character Sets:: "
3674
"* Subexpressions:: "
3675
"* Repeated Subexpressions:: "
3676
"* Optional Subexpressions:: "
3677
"* Counted Subexpressions:: "
3678
"* Alternative Subexpressions:: "
3679
"* Backreferences:: "
3680
"* A Summary of Regexp Syntax:: "
3681
"* Ambiguous Patterns:: "
3685
"@node An Introduction to Regexps, Literal Regexps, Posix Basic Regular Expressions, Posix Basic Regular Expressions"
3686
"@section An Introduction to Regexps"
3688
"In the simplest cases, a regexp is just a literal string that must"
3689
"match exactly. For example, the pattern:"
3695
"matches the string \"regexp\" and no others."
3697
"Some characters have a special meaning when they occur in a regexp."
3698
"They aren't matched literally as in the previous example, but instead"
3699
"denote a more general pattern. For example, the character @code{*}"
3700
"is used to indicate that the preceeding element of a regexp may be"
3701
"repeated 0, 1, or more times. In the pattern:"
3707
"the @code{*} indicates that the preceeding @code{o} can be repeated 0 or"
3708
"more times. So the pattern matches:"
3718
"Suppose you want to write a pattern that literally matches a special"
3719
"character like @code{*} -- in other words, you don't want to @code{*} to"
3720
"indicate a permissible repetition, but to match @code{*} literally. This"
3721
"is accomplished by quoting the special character with a backslash. "
3728
"matches the string:"
3735
"and no other strings."
3737
"In five cases, the pattern is reversed -- a backslash makes the"
3738
"character special instead of making a special character normal. The"
3739
"characters @code{+}, @code{?}, @code{|}, @code{(}, and @code{)} are"
3740
"normal but the sequences @code{\\+}, @code{\\?}, @code{\\|}, @code{\\(}, and"
3741
"@code{\\)} are special (their meaning is described later)."
3743
"The remaining sections of this chapter introduce and explain the various"
3744
"special characters that can occur in regexps."
3746
"@node Literal Regexps, Character Sets, An Introduction to Regexps, Posix Basic Regular Expressions"
3747
"@section Literal Regexps"
3749
"A literal regexp is a string which contains no special characters."
3750
"A literal regexp matches an identical string, but no other characters."
3765
"Generally, whitespace characters, numbers, and letters are not special."
3766
"Some punctuation characters are special and some are not (the syntax"
3767
"summary at the end of this chapter makes a convenient reference for"
3768
"which characters are special and which aren't)."
3771
"@node Character Sets, Subexpressions, Literal Regexps, Posix Basic Regular Expressions"
3772
"@section Character Sets"
3774
"This section introduces the special characters @code{.} and @code{[}."
3776
"@code{.} matches any character except the NULL character. For example:"
3796
"@code{[} begins a @dfn{character set}. A character set is similar to"
3797
"@code{.} in that it matches not a single, literal character, but any"
3798
"of a set of characters. @code{[} is different from @code{.} in that"
3799
"with @code{[}, you define the set of characters explicitly."
3801
"There are three basic forms a character set can take."
3803
"In the first form, the character set is spelled out:"
3806
"[<cset-spec>] -- every character in <cset-spec> is in the set."
3809
"In the second form, the character set indicated is the negation of"
3810
"a character set is explicitly spelled out:"
3813
"[^<cset-spec>] -- every character *not* in <cset-spec> is in the set."
3816
"A @code{<cset-spec>} is more or less an explicit enumeration of a set"
3817
"of characters. It can be written as a string of individual characters:"
3823
"or as a range of characters:"
3829
"These two forms can be mixed:"
3835
"Note that special regexp characters (such as @code{*}) are @emph{not}"
3836
"special within a character set. @code{-}, as illustrated above,"
3837
"@emph{is} special, except, as illustrated below, when it is the first"
3838
"character mentioned."
3840
"This is a four-character set:"
3846
"The third form of a character set makes use of a pre-defined \"character"
3850
"[[:class-name:]] -- every character described by class-name is in the set."
3853
"The supported character classes are:"
3856
"alnum - the set of alpha-numeric characters"
3857
"alpha - the set of alphabetic characters"
3858
"blank - tab and space"
3859
"cntrl - the control characters"
3860
"digit - decimal digits"
3861
"graph - all printable characters except space"
3862
"lower - lower case letters"
3863
"print - the \"printable\" characters"
3864
"punct - punctuation"
3865
"space - whitespace characters"
3866
"upper - upper case letters"
3867
"xdigit - hexidecimal digits"
3870
"Finally, character class sets can also be inverted:"
3873
"[^[:space:]] - all non-whitespace characters"
3876
"Character sets can be used in a regular expression anywhere a literal"
3879
"@node Subexpressions, Repeated Subexpressions, Character Sets, Posix Basic Regular Expressions"
3880
"@section Subexpressions"
3882
"A subexpression is a regular expression enclosed in @code{\\(} and"
3883
"@code{\\)}. A subexpression can be used anywhere a single character or"
3884
"character set can be used."
3886
"Subexpressions are useful for grouping regexp constructs. For example,"
3887
"the repeat operator, @code{*}, usually applies to just the preceeding"
3888
"character. Recall that:"
3903
"Using a subexpression, we can apply @code{*} to a longer string:"
3918
"Subexpressions also have a special meaning with regard to backreferences"
3919
"and substitutions (see @xref{Backreferences})."
3922
"@node Repeated Subexpressions, Optional Subexpressions, Subexpressions, Posix Basic Regular Expressions"
3923
"@section Repeated Subexpressions"
3926
"@code{*} is the repeat operator. It applies to the preceeding"
3927
"character, character set, subexpression or backreference. It indicates"
3928
"that the preceeding element can be matched 0 or more times:"
3946
"@code{\\+} is similar to @code{*} except that @code{\\+} requires the"
3947
"preceeding element to be matched at least once. So while:"
3963
"does not. Both match "
3972
"Thus, @code{bana\\(na\\)+} is short-hand for @code{banana\\(na\\)*}."
3975
"@node Optional Subexpressions, Counted Subexpressions, Repeated Subexpressions, Posix Basic Regular Expressions"
3976
"@section Optional Subexpressions"
3978
"@code{\\?} indicates that the preceeding character, character set, or"
3979
"subexpression is optional. It is permitted to match, or to be skipped:"
3998
"@node Counted Subexpressions, Alternative Subexpressions, Optional Subexpressions, Posix Basic Regular Expressions"
3999
"@section Counted Subexpressions"
4001
"An interval expression, @code{@{m,n@}} where @code{m} and @code{n} are"
4002
"non-negative integers with @code{n >= m}, applies to the preceeding"
4003
"character, character set, subexpression or backreference. It indicates"
4004
"that the preceeding element must match at least @code{m} times and may"
4005
"match as many as @code{n} times."
4010
"c\\([ad]\\)@{1,4@}"
4030
"@node Alternative Subexpressions, Backreferences, Counted Subexpressions, Posix Basic Regular Expressions"
4031
"@section Alternative Subexpressions"
4033
"An alternative is written:"
4036
"regexp-1\\|regexp-2\\|regexp-3\\|..."
4039
"It matches anything matched by some @code{regexp-n}. For example:"
4042
"Crosby, Stills, \\(and Nash\\|Nash, and Young\\)"
4048
"Crosby, Stills, and Nash"
4054
"Crosby, Stills, Nash, and Young"
4058
"@node Backreferences, A Summary of Regexp Syntax, Alternative Subexpressions, Posix Basic Regular Expressions"
4059
"@section Backreferences, Extractions and Substitutions"
4061
"A backreference is written @code{\\n} where @code{n} is some single digit"
4062
"other than 0. To be a valid backreference, there must be at least"
4063
"@code{n} parenthesized subexpressions in the pattern prior to the"
4066
"A backreference matches a literal copy of whatever was matched by the"
4067
"corresponding subexpression. For example,"
4082
"In some applications, subexpressions are used to extract substrings."
4083
"For example, Emacs has the functions @code{match-beginnning} and"
4084
"@code{match-end} which report the positions of strings matched by"
4085
"subexpressions. These functions use the same numbering scheme for"
4086
"subexpressions as backreferences, with the additional rule that"
4087
"subexpression 0 is defined to be the whole regexp."
4089
"In some applications, subexpressions are used in string substitution."
4090
"This again uses the backreference numbering scheme. For example, this sed"
4094
"s/From:.*<\\(.*\\)>/To: \\1/"
4097
"first matches the line:"
4100
"From: Joe Schmoe <schmoe@@uspringfield.edu>"
4103
"when it does, subexpression 1 matches \"schmoe@@uspringfield.edu\"."
4104
"The command replaces the matched line with \"To: \\1\" after doing"
4105
"subexpression substitution on it to get:"
4108
"To: schmoe@@uspringfield.edu"
4112
"@node A Summary of Regexp Syntax, Ambiguous Patterns, Backreferences, Posix Basic Regular Expressions"
4113
"@section A Summary of Regexp Syntax"
4115
"In summary, regexps can be:"
4117
"@code{abcd} -- matching a string literally"
4119
"@code{.} -- matching everything except NULL"
4121
"@code{[a-z_?]}, @code{^[a-z_?]}, @code{[[:alpha:]]} and"
4122
"@code{[^[:alpha:]]} -- matching character sets"
4124
"@code{\\(subexp\\)} -- grouping an expression into a subexpression."
4126
"@code{\\n} -- match a copy of whatever was matched by the nth subexpression."
4128
"The following special characters and sequences can be applied to a"
4129
"character, character set, subexpression, or backreference:"
4131
"@code{*} -- repeat the preceeding element 0 or more times."
4133
"@code{\\+} -- repeat the preceeding element 1 or more times."
4135
"@code{\\?} -- match the preceeding element 0 or 1 time."
4137
"@code{@{m,n@}} -- match the preceeding element at least @code{m}, and as"
4138
"many as @code{n} times."
4140
"@code{regexp-1\\|regexp-2\\|..} -- match any regexp-n."
4142
"A special character, like @code{.} or @code{*} can be made into a literal"
4143
"character by prefixing it with @code{\\}."
4145
"A special sequence, like @code{\\+} or @code{\\?} can be made into a"
4146
"literal character by dropping the @code{\\}."
4149
"@node Ambiguous Patterns, , A Summary of Regexp Syntax, Posix Basic Regular Expressions"
4150
"@section Ambiguous Patterns"
4152
"Sometimes a regular expression appears to be ambiguous. For example, suppose"
4153
"we compare the pattern:"
4165
"either just the first 5 characters will match, or the whole string will match."
4167
"In every case like this, the longer match is preferred. The whole"
4168
"string will match."
4170
"Sometimes there is ambiguity not about how many characters to match, but"
4171
"where the subexpressions occur within the match. This can effect"
4172
"extraction functions like Emacs' @code{match-beginning} or rewrite"
4173
"functions like sed's @code{s} command. For example, consider matching"
4177
"b\\(\\[^q]*\\)\\(ing\\)?"
4180
"against the string"
4186
"One possibility is that the first subexpression matches \"eginning\" and"
4187
"the second is skipped. Another possibility is that the first"
4188
"subexpression matches \"eginn\" and the second matches \"ing\"."
4190
"The rule is that consistant with matching as many characters as "
4191
"possible, the length of lower numbered subexpressions is maximized"
4192
"in preference to maximizing the length of later subexpressions."
4194
"In the case of the above example, the two possible matches are equal in"
4195
"overall length. Therefore, it comes down to maximizing the"
4196
"lower-numbered subexpression, \\1. The correct answer is that \\1 matches"
4197
"\"eginning\" and \\2 is skipped."
4199
"@node Posix Entry Points, Beyond POSIX, Posix Basic Regular Expressions, Top"
4200
"@chapter Posix Entry Points"
4202
"This section is excerpted from @emph{The GNU C Library} reference manual"
4203
"by Sandra Loosemore with Richard M. Stallman, Roland McGrath, and Andrew"
4206
"The GNU C library supports the standard POSIX.2 interface. Programs"
4207
"using this interface should include the header file @file{rxposix.h}."
4210
"* POSIX Regexp Compilation:: Using @code{regcomp} to prepare to match."
4211
"* Flags for POSIX Regexps:: Syntax variations for @code{regcomp}."
4212
"* Matching POSIX Regexps:: Using @code{regexec} to match the compiled"
4213
" pattern that you get from @code{regcomp}."
4214
"* Regexp Subexpressions:: Finding which parts of the string were matched."
4215
"* Subexpression Complications:: Find points of which parts were matched."
4216
"* Regexp Cleanup:: Freeing storage; reporting errors."
4219
"@node POSIX Regexp Compilation, Flags for POSIX Regexps, Posix Entry Points, Posix Entry Points"
4220
"@section POSIX Regular Expression Compilation"
4222
"Before you can actually match a regular expression, you must"
4223
"@dfn{compile} it. This is not true compilation---it produces a special"
4224
"data structure, not machine instructions. But it is like ordinary"
4225
"compilation in that its purpose is to enable you to ``execute'' the"
4226
"pattern fast. (@xref{Matching POSIX Regexps}, for how to use the"
4227
"compiled regular expression for matching.)"
4229
"There is a special data type for compiled regular expressions:"
4233
"@deftp {Data Type} regex_t"
4234
"This type of object holds a compiled regular expression."
4235
"It is actually a structure. It has just one field that your programs"
4240
"This field holds the number of parenthetical subexpressions in the"
4241
"regular expression that was compiled."
4244
"There are several other fields, but we don't describe them here, because"
4245
"only the functions in the library should use them."
4248
"After you create a @code{regex_t} object, you can compile a regular"
4249
"expression into it by calling @code{regcomp}."
4253
"@deftypefun int regcomp (regex_t *@var{compiled}, const char *@var{pattern}, int @var{cflags})"
4254
"@deftypefunx int regncomp (regex_t *@var{compiled}, int len, const char *@var{pattern}, int @var{cflags})"
4255
"The function @code{regcomp} ``compiles'' a regular expression into a"
4256
"data structure that you can use with @code{regexec} to match against a"
4257
"string. The compiled regular expression format is designed for"
4258
"efficient matching. @code{regcomp} stores it into @code{*@var{compiled}}."
4260
"The parameter @var{pattern} points to the regular expression to be"
4261
"compiled. When using @code{regcomp}, @var{pattern} must be"
4262
"0-terminated. When using @code{regncomp}, @var{pattern} must be"
4263
"@var{len} characters long."
4265
"@code{regncomp} is not a standard function; strictly POSIX programs"
4266
"should avoid using it."
4268
"It's up to you to allocate an object of type @code{regex_t} and pass its"
4269
"address to @code{regcomp}."
4271
"The argument @var{cflags} lets you specify various options that control"
4272
"the syntax and semantics of regular expressions. @xref{Flags for POSIX"
4275
"If you use the flag @code{REG_NOSUB}, then @code{regcomp} omits from"
4276
"the compiled regular expression the information necessary to record"
4277
"how subexpressions actually match. In this case, you might as well"
4278
"pass @code{0} for the @var{matchptr} and @var{nmatch} arguments when"
4279
"you call @code{regexec}."
4281
"If you don't use @code{REG_NOSUB}, then the compiled regular expression"
4282
"does have the capacity to record how subexpressions match. Also,"
4283
"@code{regcomp} tells you how many subexpressions @var{pattern} has, by"
4284
"storing the number in @code{@var{compiled}->re_nsub}. You can use that"
4285
"value to decide how long an array to allocate to hold information about"
4286
"subexpression matches."
4288
"@code{regcomp} returns @code{0} if it succeeds in compiling the regular"
4289
"expression; otherwise, it returns a nonzero error code (see the table"
4290
"below). You can use @code{regerror} to produce an error message string"
4291
"describing the reason for a nonzero value; see @ref{Regexp Cleanup}."
4295
"Here are the possible nonzero values that @code{regcomp} can return:"
4301
"There was an invalid @samp{\\@{@dots{}\\@}} construct in the regular"
4302
"expression. A valid @samp{\\@{@dots{}\\@}} construct must contain either"
4303
"a single number, or two numbers in increasing order separated by a"
4309
"There was a syntax error in the regular expression."
4314
"A repetition operator such as @samp{?} or @samp{*} appeared in a bad"
4315
"position (with no preceding subexpression to act on)."
4319
"@item REG_ECOLLATE"
4320
"The regular expression referred to an invalid collating element (one not"
4321
"defined in the current locale for string collation). "
4326
"The regular expression referred to an invalid character class name."
4331
"The regular expression ended with @samp{\\}."
4336
"There was an invalid number in the @samp{\\@var{digit}} construct."
4341
"There were unbalanced square brackets in the regular expression."
4346
"An extended regular expression had unbalanced parentheses,"
4347
"or a basic regular expression had unbalanced @samp{\\(} and @samp{\\)}."
4352
"The regular expression had unbalanced @samp{\\@{} and @samp{\\@}}."
4357
"One of the endpoints in a range expression was invalid."
4362
"@code{regcomp} ran out of memory."
4365
"@node Flags for POSIX Regexps, Matching POSIX Regexps, POSIX Regexp Compilation, Posix Entry Points"
4366
"@section Flags for POSIX Regular Expressions"
4368
"These are the bit flags that you can use in the @var{cflags} operand when"
4369
"compiling a regular expression with @code{regcomp}."
4374
"@item REG_EXTENDED"
4375
"Treat the pattern as an extended regular expression, rather than as a"
4376
"basic regular expression."
4381
"Ignore case when matching letters."
4386
"Don't bother storing the contents of the @var{matches-ptr} array."
4391
"Treat a newline in @var{string} as dividing @var{string} into multiple"
4392
"lines, so that @samp{$} can match before the newline and @samp{^} can"
4393
"match after. Also, don't permit @samp{.} to match a newline, and don't"
4394
"permit @samp{[^@dots{}]} to match a newline."
4396
"Otherwise, newline acts like any other ordinary character."
4399
"@node Matching POSIX Regexps, Regexp Subexpressions, Flags for POSIX Regexps, Posix Entry Points"
4400
"@section Matching a Compiled POSIX Regular Expression"
4402
"Once you have compiled a regular expression, as described in @ref{POSIX"
4403
"Regexp Compilation}, you can match it against strings using"
4404
"@code{regexec}. A match anywhere inside the string counts as success,"
4405
"unless the regular expression contains anchor characters (@samp{^} or"
4410
"@deftypefun int regexec (regex_t *@var{compiled}, char *@var{string}, size_t @var{nmatch}, regmatch_t @var{matchptr} @t{[]}, int @var{eflags})"
4411
"@deftypefunx int regnexec (regex_t *@var{compiled}, int len, char *@var{string}, size_t @var{nmatch}, regmatch_t @var{matchptr} @t{[]}, int @var{eflags})"
4412
"This function tries to match the compiled regular expression"
4413
"@code{*@var{compiled}} against @var{string}."
4415
"@code{regexec} returns @code{0} if the regular expression matches;"
4416
"otherwise, it returns a nonzero value. See the table below for"
4417
"what nonzero values mean. You can use @code{regerror} to produce an"
4418
"error message string describing the reason for a nonzero value; "
4419
"see @ref{Regexp Cleanup}."
4421
"The parameter @var{string} points to the text to search. When using"
4422
"@code{regexec}, @var{string} must be 0-terminated. When using"
4423
"@code{regnexec}, @var{string} must be @var{len} characters long."
4425
"@code{regnexec} is not a standard function; strictly POSIX programs"
4426
"should avoid using it."
4428
"The argument @var{eflags} is a word of bit flags that enable various"
4431
"If you want to get information about what part of @var{string} actually"
4432
"matched the regular expression or its subexpressions, use the arguments"
4433
"@var{matchptr} and @var{nmatch}. Otherwise, pass @code{0} for "
4434
"@var{nmatch}, and @code{NULL} for @var{matchptr}. @xref{Regexp"
4438
"You must match the regular expression with the same set of current"
4439
"locales that were in effect when you compiled the regular expression."
4441
"The function @code{regexec} accepts the following flags in the"
4442
"@var{eflags} argument:"
4448
"Do not regard the beginning of the specified string as the beginning of"
4449
"a line; more generally, don't make any assumptions about what text might"
4455
"Do not regard the end of the specified string as the end of a line; more"
4456
"generally, don't make any assumptions about what text might follow it."
4459
"Here are the possible nonzero values that @code{regexec} can return:"
4465
"The pattern didn't match the string. This isn't really an error."
4470
"@code{regexec} ran out of memory."
4473
"@node Regexp Subexpressions, Subexpression Complications, Matching POSIX Regexps, Posix Entry Points"
4474
"@section Match Results with Subexpressions"
4476
"When @code{regexec} matches parenthetical subexpressions of"
4477
"@var{pattern}, it records which parts of @var{string} they match. It"
4478
"returns that information by storing the offsets into an array whose"
4479
"elements are structures of type @code{regmatch_t}. The first element of"
4480
"the array (index @code{0}) records the part of the string that matched"
4481
"the entire regular expression. Each other element of the array records"
4482
"the beginning and end of the part that matched a single parenthetical"
4487
"@deftp {Data Type} regmatch_t"
4488
"This is the data type of the @var{matcharray} array that you pass to"
4489
"@code{regexec}. It containes two structure fields, as follows:"
4493
"The offset in @var{string} of the beginning of a substring. Add this"
4494
"value to @var{string} to get the address of that part."
4497
"The offset in @var{string} of the end of the substring."
4503
"@deftp {Data Type} regoff_t"
4504
"@code{regoff_t} is an alias for another signed integer type."
4505
"The fields of @code{regmatch_t} have type @code{regoff_t}."
4508
"The @code{regmatch_t} elements correspond to subexpressions"
4509
"positionally; the first element (index @code{1}) records where the first"
4510
"subexpression matched, the second element records the second"
4511
"subexpression, and so on. The order of the subexpressions is the order"
4512
"in which they begin."
4514
"When you call @code{regexec}, you specify how long the @var{matchptr}"
4515
"array is, with the @var{nmatch} argument. This tells @code{regexec} how"
4516
"many elements to store. If the actual regular expression has more than"
4517
"@var{nmatch} subexpressions, then you won't get offset information about"
4518
"the rest of them. But this doesn't alter whether the pattern matches a"
4519
"particular string or not."
4521
"If you don't want @code{regexec} to return any information about where"
4522
"the subexpressions matched, you can either supply @code{0} for"
4523
"@var{nmatch}, or use the flag @code{REG_NOSUB} when you compile the"
4524
"pattern with @code{regcomp}."
4526
"@node Subexpression Complications, Regexp Cleanup, Regexp Subexpressions, Posix Entry Points"
4527
"@section Complications in Subexpression Matching"
4529
"Sometimes a subexpression matches a substring of no characters. This"
4530
"happens when @samp{f\\(o*\\)} matches the string @samp{fum}. (It really"
4531
"matches just the @samp{f}.) In this case, both of the offsets identify"
4532
"the point in the string where the null substring was found. In this"
4533
"example, the offsets are both @code{1}."
4535
"Sometimes the entire regular expression can match without using some of"
4536
"its subexpressions at all---for example, when @samp{ba\\(na\\)*} matches the"
4537
"string @samp{ba}, the parenthetical subexpression is not used. When"
4538
"this happens, @code{regexec} stores @code{-1} in both fields of the"
4539
"element for that subexpression."
4541
"Sometimes matching the entire regular expression can match a particular"
4542
"subexpression more than once---for example, when @samp{ba\\(na\\)*}"
4543
"matches the string @samp{bananana}, the parenthetical subexpression"
4544
"matches three times. When this happens, @code{regexec} usually stores"
4545
"the offsets of the last part of the string that matched the"
4546
"subexpression. In the case of @samp{bananana}, these offsets are"
4547
"@code{6} and @code{8}."
4549
"But the last match is not always the one that is chosen. It's more"
4550
"accurate to say that the last @emph{opportunity} to match is the one"
4551
"that takes precedence. What this means is that when one subexpression"
4552
"appears within another, then the results reported for the inner"
4553
"subexpression reflect whatever happened on the last match of the outer"
4554
"subexpression. For an example, consider @samp{\\(ba\\(na\\)*s \\)*} matching"
4555
"the string @samp{bananas bas }. The last time the inner expression"
4556
"actually matches is near the end of the first word. But it is "
4557
"@emph{considered} again in the second word, and fails to match there."
4558
"@code{regexec} reports nonuse of the ``na'' subexpression."
4560
"Another place where this rule applies is when the regular expression"
4561
"@w{@samp{\\(ba\\(na\\)*s \\|nefer\\(ti\\)* \\)*}} matches @samp{bananas nefertiti}."
4562
"The ``na'' subexpression does match in the first word, but it doesn't"
4563
"match in the second word because the other alternative is used there."
4564
"Once again, the second repetition of the outer subexpression overrides"
4565
"the first, and within that second repetition, the ``na'' subexpression"
4566
"is not used. So @code{regexec} reports nonuse of the ``na''"
4569
"@node Regexp Cleanup, , Subexpression Complications, Posix Entry Points"
4570
"@section POSIX Regexp Matching Cleanup"
4572
"When you are finished using a compiled regular expression, you can"
4573
"free the storage it uses by calling @code{regfree}."
4577
"@deftypefun void regfree (regex_t *@var{compiled})"
4578
"Calling @code{regfree} frees all the storage that @code{*@var{compiled}}"
4579
"points to. This includes various internal fields of the @code{regex_t}"
4580
"structure that aren't documented in this manual."
4582
"@code{regfree} does not free the object @code{*@var{compiled}} itself."
4585
"You should always free the space in a @code{regex_t} structure with"
4586
"@code{regfree} before using the structure to compile another regular"
4589
"When @code{regcomp} or @code{regexec} reports an error, you can use"
4590
"the function @code{regerror} to turn it into an error message string."
4594
"@deftypefun size_t regerror (int @var{errcode}, regex_t *@var{compiled}, char *@var{buffer}, size_t @var{length})"
4595
"This function produces an error message string for the error code"
4596
"@var{errcode}, and stores the string in @var{length} bytes of memory"
4597
"starting at @var{buffer}. For the @var{compiled} argument, supply the"
4598
"same compiled regular expression structure that @code{regcomp} or"
4599
"@code{regexec} was working with when it got the error. Alternatively,"
4600
"you can supply @code{NULL} for @var{compiled}; you will still get a"
4601
"meaningful error message, but it might not be as detailed."
4603
"If the error message can't fit in @var{length} bytes (including a"
4604
"terminating null character), then @code{regerror} truncates it."
4605
"The string that @code{regerror} stores is always null-terminated"
4606
"even if it has been truncated."
4608
"The return value of @code{regerror} is the minimum length needed to"
4609
"store the entire error message. If this is less than @var{length}, then"
4610
"the error message was not truncated, and you can use it. Otherwise, you"
4611
"should call @code{regerror} again with a larger buffer."
4613
"Here is a function which uses @code{regerror}, but always dynamically"
4614
"allocates a buffer for the error message:"
4617
"char *get_regerror (int errcode, regex_t *compiled)"
4619
" size_t length = regerror (errcode, compiled, NULL, 0);"
4620
" char *buffer = xmalloc (length);"
4621
" (void) regerror (errcode, compiled, buffer, length);"
4627
"@node Beyond POSIX, Rx Theory, Posix Entry Points, Top"
4628
"@chapter Beyond POSIX"
4630
"This section is not finished documentation, but rather a collection of"
4631
"pointers towards some of the interesting, non-standard features of Rx."
4633
"@section New Regexp Operators"
4635
"Rx supports some unusual regexp syntax."
4637
"@code{[[:cut N:]]} sets @code{pmatch[0].final_tag} to N and causes the"
4638
"matching to stop instantly. If N is 0, the overall match fails,"
4639
"otherwise it succeeds."
4641
"@code{[[:(:]] ... [[:):]]} is just like @code{\\( ... \\)} except that in"
4642
"the first case, no pmatch entries are changed, and the subexpression is"
4643
"not counted in the numbering of parenthesized subexpressions."
4645
"@code{[[:(:]] ... [[:):]]} can be used when you do not need to know"
4646
"where a subexpression matched but are only using parentheses to effect"
4647
"the parsing of the regexp. "
4649
"There are two reasons to use @code{[[:(:]] ... [[:):]]}:"
4651
"1. regexec will run faster."
4653
"2. Currently, only 8 backreferencable subexpressions are supported:"
4654
"@code{\\1 .. \\9}. Using @code{[[:(:]] ... [[:):]]} is a way to conserve"
4655
"backreferencable subexpression names in an expression with many"
4658
"@section New POSIX Functions"
4660
"@code{regncomp} and @code{regnexec} are non-standard generalizations of"
4661
"@code{regcomp} and @code{regexec}."
4663
"@section Tuning POSIX performance"
4665
"Two mysterious parmaters can be used to trade-off performance and"
4668
"At compile-time they are @code{RX_DEFAULT_DFA_CACHE_SIZE} and"
4669
"@code{RX_DEFAULT_NFA_DELAY}. "
4671
"If you want to mess with these (I generally don't advise it), I suggest"
4672
"experimenting for your particular application/memory situation; frob"
4673
"these by powers of two and try out the results on what you expect will"
4674
"be typical regexp workloads."
4676
"You can also set those parameters at run-time (before calling any regexp"
4677
"functions) by tweaking the corresponding variables:"
4679
"@code{rx_default_cache->bytes_allowed}"
4683
"@code{rx_basic_unfaniverse_delay}"
4687
"@section POSIX stream-style interface"
4689
"@code{rx_make_solutions}, @code{rx_next_solution}, and"
4690
"@code{rx_free_solutions} are a lower level alternative to the posix"
4691
"functions. Using those functions, you can compare a compiled regexp to"
4692
"a string that is not contiguous in memory or even a string that is not"
4693
"entirely in memory at any one time."
4695
"The code in rxposix.c points out how those functions are used."
4698
"@section DFAs Directly"
4700
"If you are only interested in pure regular expressions (no pmatch data,"
4701
"no backreferences, and no counted subexpressions), you can parse a"
4702
"regexp using @code{rx_parse}, convert it to an nfa using @code{rx_unfa},"
4703
"and run the dfa using @code{rx_init_system}, @code{rx_advance_to_final},"
4704
"and @code{rx_terminate_system}. The dfa Scheme primitives in"
4705
"@file{rgx.c} may provide some guide."
4707
"@node Rx Theory, , Beyond POSIX, Top"
4708
"@chapter Rx Theory"
4711
"There are two match algorithms. One is for truly regular regexps (those"
4712
"that can be reduced to a dfa). The other is for non-regular regexps."
4714
"The dfa algorithm implements the idea suggested in @cite{Compilers} by"
4715
"Aho, Sethi and Ullman:"
4718
"[One] approach [to pattern matching regular expressions] is to use a"
4719
"DFA, but avoid constructing all of the transition table by using a"
4720
"technique called \"lazy transition evaluation\". Here, transitions are"
4721
"computed at run time [when] actually needed. [T]ransitions are"
4722
"stored in a cache. [....] If the cache becomes full, we can erase some"
4723
"previously computed transition to make room for the new transition."
4726
"The implementation in Rx is generalized from that, but the above"
4727
"description covers what is used for Posix patterns. "
4729
"The non-dfa algorithm implements a \"recursive decomposition\" technique"
4730
"described in email by Henry Spencer. For a given pattern, this"
4731
"algorithm first checks to see if a simpler, superset language,"
4732
"DFA-pattern matches. If it does, then this algorithm does the"
4733
"detail-work to see if the non-DFA pattern matches."
4735
"The detail work usually involves recursing on subpatterns. For example,"
4736
"a concatentation of two subexpressions matches a string if the string"
4737
"can be divided into two parts, each matching one subexpression, in the"
4738
"right order. More than one solution is often possible for a given"
4739
"pattern. This ambiguity is the subject of the \"leftmost longest\" rules"
4740
"in the spec, and the back-tracking oriented stream-of-solution functions"
4741
"@code{rx_make_solutions}, @code{rx_next_solution} and"
4742
"@code{rx_free_solutions}."
4745
"rxspencer.[ch] -- The non-DFA algorithm"
4746
"rxanal.[ch] rxsuper.[ch] rxnfa.[ch] -- The DFA algorithm"
added
removed
lib/common_test/priv/rx-1.5/rgx-perf/longdotstr/data.c
