Boost C++ Libraries

What is xpressive?

xpressive is an object-oriented regular expression library. Regular expressions (regexes) can be written as strings that are parsed dynamically at runtime (dynamic regexes), or as expression templates that are parsed at compile-time (static regexes). Dynamic regexes have the advantage that they can be accepted from the user as input at runtime or read from an initialization file. Static regexes have several advantages. Since they are C++ expressions instead of strings, they can be syntax-checked at compile-time. Also, they can refer to other regexes and to themselves, giving static regexes the power of context-free grammars. Finally, since they are statically bound, the compiler can generate faster code for static regexes.

xpressive's dual nature is unique and powerful. Static xpressive is a bit like the Spirit Parser Framework. Like Spirit, you can build grammars with static regexes using expression templates. (Unlike Spirit, xpressive does exhaustive backtracking, trying every possibility to find a match for your pattern.) Dynamic xpressive is a bit like Boost.Regex. In fact, xpressive's interface should be familiar to anyone who has used Boost.Regex. xpressive's innovation comes from allowing you to mix and match static and dynamic regexes in the same program, and even in the same expression! You can embed a dynamic regex in a static regex, and the dynamic regex will participate fully in the search, back-tracking as needed to make the match succeed.

Hello, world!

Enough theory. Let's have a look at Hello World, xpressive style:

#include <iostream>
#include <boost/xpressive/xpressive.hpp>

using namespace boost::xpressive;

int main()
{
    std::string hello( "hello world!" );

    sregex rex = sregex::compile( "(\\w+) (\\w+)!" );
    smatch what;

    if( regex_match( hello, what, rex ) )
    {
        std::cout << what[0] << '\n'; // whole match
        std::cout << what[1] << '\n'; // first capture
        std::cout << what[2] << '\n'; // second capture
    }

    return 0;
}

This program outputs the following:

hello world!
hello
world

The first thing you'll notice about the code is that all the types in xpressive live in the boost::xpressive namespace.

	Note
	Most of the rest of the examples in this document will leave off the using namespace boost::xpressive; directive. Just pretend it's there.

Next, you'll notice the type of the regular expression object is sregex. If you are familiar with Boost.Regex, this is different than what you are used to. The "s" in "sregex" stands for "string", indicating that this regex can be used to find patterns in std::string objects. I'll discuss this difference and its implications in detail later.

Notice how the regex object is initialized:

sregex rex = sregex::compile( "(\\w+) (\\w+)!" );

To create a regular expression object from a string, you must call a factory method such as basic_regex::compile(). This is another area in which xpressive differs from other object-oriented regular expression libraries. Other libraries encourage you to think of a regular expression as a kind of string on steroids. In xpressive, regular expressions are not strings; they are little programs in a domain-specific language. Strings are only one representation of that language. Another representation is an expression template. For example, the above line of code is equivalent to the following:

sregex rex = (s1= +_w) >> ' ' >> (s2= +_w) >> '!';

This describes the same regular expression, except it uses the domain-specific embedded language defined by static xpressive.

As you can see, static regexes have a syntax that is noticeably different than standard Perl syntax. That is because we are constrained by C++'s syntax. The biggest difference is the use of >> to mean "followed by". For instance, in Perl you can just put sub-expressions next to each other:

abc

But in C++, there must be an operator separating sub-expressions:

a >> b >> c

In Perl, parentheses () have special meaning. They group, but as a side-effect they also create back-references like $1 and $2. In C++, there is no way to overload parentheses to give them side-effects. To get the same effect, we use the special s1, s2, etc. tokens. Assign to one to create a back-reference (known as a sub-match in xpressive).

You'll also notice that the one-or-more repetition operator + has moved from postfix to prefix position. That's because C++ doesn't have a postfix + operator. So:

"\\w+"

is the same as:

+_w

We'll cover all the other differences later.

Getting xpressive

There are two ways to get xpressive. The first is by downloading xpressive.zip at the Boost File Vault in the "Strings - Text Processing" directory. In addition to the source code and the Boost license, this archive contains a copy of this documentation in PDF format.

The second way is through anonymous CVS via the boost project on SourceForge.net. Just go to http://sf.net/projects/boost and follow the instructions there for anonymous CVS access.

Building with xpressive

xpressive is a header-only template library, which means you don't need to alter your build scripts or link to any separate lib file to use it. All you need to do is #include <boost/xpressive/xpressive.hpp>. If you are only using static regexes, you can improve compile times by only including xpressive_static.hpp. Likewise, you can include xpressive_dynamic.hpp if you only plan on using dynamic regexes.

Requirements

xpressive depends on Boost. You can download the latest version of the Boost libraries from http://boost.org. xpressive requires Boost version 1.32 or higher.

Supported Compilers

Currently, Boost.Xpressive is known to work on the following compilers:

Check the latest tests results at Boost's Regression Results Page.

	Note
	Please send any questions, comments and bug reports to eric <at> boost-consulting <dot> com.

You don't need to know much to start being productive with xpressive. Let's begin with the nickel tour of the types and algorithms xpressive provides.

Now that you know a bit about the tools xpressive provides, you can pick the right tool for you by answering the following two questions:

Know Your Iterator Type

Most of the classes in xpressive are templates that are parameterized on the iterator type. xpressive defines some common typedefs to make the job of choosing the right types easier. You can use the table below to find the right types based on the type of your iterator.

You should notice the systematic naming convention. Many of these types are used together, so the naming convention helps you to use them consistently. For instance, if you have a sregex, you should also be using a smatch.

If you are not using one of those four iterator types, then you can use the templates directly and specify your iterator type.

Know Your Task

Do you want to find a pattern once? Many times? Search and replace? xpressive has tools for all that and more. Below is a quick reference:

Tasks and Tools

To do this ...	Use this ...
See if a whole string matches a regex	The regex_match() algorithm
See if a string contains a sub-string that matches a regex	The regex_search() algorithm
Replace all sub-strings that match a regex	The regex_replace() algorithm
Find all the sub-strings that match a regex and step through them one at a time	The regex_iterator<> class
Split a string into tokens that each match a regex	The regex_token_iterator<> class
Split a string using a regex as a delimiter	The regex_token_iterator<> class

These algorithms and classes are described in excruciating detail in the Reference section.

	Tip
	Try clicking on a task in the table above to see a complete example program that uses xpressive to solve that particular task.

When using xpressive, the first thing you'll do is create a basic_regex<> object. This section goes over the nuts and bolts of building a regular expression in the two dialects xpressive supports: static and dynamic.

Static Regexes

Overview

The feature that really sets xpressive apart from other C/C++ regular expression libraries is the ability to author a regular expression using C++ expressions. xpressive achieves this through operator overloading, using a technique called expression templates to embed a mini-language dedicated to pattern matching within C++. These "static regexes" have many advantages over their string-based brethren. In particular, static regexes:

• are syntax-checked at compile-time; they will never fail at run-time due to a syntax error.
• can naturally refer to other C++ data and code, including other regexes, making it possible to build grammars out of regular expressions and bind user-defined actions that execute when parts of your regex match.
• are statically bound for better inlining and optimization. Static regexes require no state tables, virtual functions, byte-code or calls through function pointers that cannot be resolved at compile time.
• are not limited to searching for patterns in strings. You can declare a static regex that finds patterns in an array of integers, for instance.

Since we compose static regexes using C++ expressions, we are constrained by the rules for legal C++ expressions. Unfortunately, that means that "classic" regular expression syntax cannot always be mapped cleanly into C++. Rather, we map the regex constructs, picking new syntax that is legal C++.

Construction and Assignment

You create a static regex by assigning one to an object of type basic_regex<>. For instance, the following defines a regex that can be used to find patterns in objects of type std::string:

sregex re = '$' >> +_d >> '.' >> _d >> _d;

Assignment works similarly.

Character and String Literals

In static regexes, character and string literals match themselves. For instance, in the regex above, '$' and '.' match the characters '$' and '.' respectively. Don't be confused by the fact that $ and . are meta-characters in Perl. In xpressive, literals always represent themselves.

When using literals in static regexes, you must take care that at least one operand is not a literal. For instance, the following are not valid regexes:

sregex re1 = 'a' >> 'b';         // ERROR!
sregex re2 = +'a';               // ERROR!

The two operands to the binary >> operator are both literals, and the operand of the unary + operator is also a literal, so these statements will call the native C++ binary right-shift and unary plus operators, respectively. That's not what we want. To get operator overloading to kick in, at least one operand must be a user-defined type. We can use xpressive's as_xpr() helper function to "taint" an expression with regex-ness, forcing operator overloading to find the correct operators. The two regexes above should be written as:

sregex re1 = as_xpr('a') >> 'b'; // OK
sregex re2 = +as_xpr('a');       // OK

Sequencing and Alternation

As you've probably already noticed, sub-expressions in static regexes must be separated by the sequencing operator, >>. You can read this operator as "followed by".

// Match an 'a' followed by a digit
sregex re = 'a' >> _d;

Alternation works just as it does in Perl with the | operator. You can read this operator as "or". For example:

// match a digit character or a word character one or more times
sregex re = +( _d | _w );

Grouping and Captures

In Perl, parentheses () have special meaning. They group, but as a side-effect they also create back-references like $1 and $2. In C++, parentheses only group -- there is no way to give them side-effects. To get the same effect, we use the special s1, s2, etc. tokens. Assigning to one creates a back-reference. You can then use the back-reference later in your expression, like using \1 and \2 in Perl. For example, consider the following regex, which finds matching HTML tags:

"<(\\w+)>.*?</\\1>"

In static xpressive, this would be:

'<' >> (s1= +_w) >> '>' >> -*_ >> "</" >> s1 >> '>'

Notice how you capture a back-reference by assigning to s1, and then you use s1 later in the pattern to find the matching end tag.

	Tip
	Grouping without capturing a back-reference  In xpressive, if you just want grouping without capturing a back-reference, you can just use () without s1. That is the equivalent of Perl's (?:) non-capturing grouping construct.

Case-Insensitivity and Internationalization

Perl lets you make part of your regular expression case-insensitive by using the (?i:) pattern modifier. xpressive also has a case-insensitivity pattern modifier, called icase. You can use it as follows:

sregex re = "this" >> icase( "that" );

In this regular expression, "this" will be matched exactly, but "that" will be matched irrespective of case.

Case-insensitive regular expressions raise the issue of internationalization: how should case-insensitive character comparisons be evaluated? Also, many character classes are locale-specific. Which characters are matched by digit and which are matched by alpha? The answer depends on the std::locale object the regular expression object is using. By default, all regular expression objects use the global locale. You can override the default by using the imbue() pattern modifier, as follows:

std::locale my_locale = /* initialize a std::locale object */;
sregex re = imbue( my_locale )( +alpha >> +digit );

This regular expression will evaluate alpha and digit according to my_locale. See the section on Localization and Regex Traits for more information about how to customize the behavior of your regexes.

Static xpressive Syntax Cheat Sheet

The table below lists the familiar regex constructs and their equivalents in static xpressive.

Perl syntax vs. Static xpressive syntax

Perl	Static xpressive	Meaning
.	_	any character (assuming Perl's /s modifier).
ab	a >> b	sequencing of a and b sub-expressions.
a|b	a | b	alternation of a and b sub-expressions.
(a)	(s1= a)	group and capture a back-reference.
(?:a)	(a)	group and do not capture a back-reference.
\1	s1	a previously captured back-reference.
a*	*a	zero or more times, greedy.
a+	+a	one or more times, greedy.
a?	!a	zero or one time, greedy.
a{n,m}	repeat<n,m>(a)	between n and m times, greedy.
a*?	-*a	zero or more times, non-greedy.
a+?	-+a	one or more times, non-greedy.
a??	-!a	zero or one time, non-greedy.
a{n,m}?	-repeat<n,m>(a)	between n and m times, non-greedy.
^	bos	beginning of sequence assertion.
$	eos	end of sequence assertion.
\b	_b	word boundary assertion.
\B	~_b	not word boundary assertion.
\n	_n	literal newline.
.	~_n	any character except a literal newline (without Perl's /s modifier).
\r?\n|\r	_ln	logical newline.
[^\r\n]	~_ln	any single character not a logical newline.
\w	_w	a word character, equivalent to set[alnum | '_'].
\W	~_w	not a word character, equivalent to ~set[alnum | '_'].
\d	_d	a digit character.
\D	~_d	not a digit character.
\s	_s	a space character.
\S	~_s	not a space character.
[:alnum:]	alnum	an alpha-numeric character.
[:alpha:]	alpha	an alphabetic character.
[:blank:]	blank	a horizontal white-space character.
[:cntrl:]	cntrl	a control character.
[:digit:]	digit	a digit character.
[:graph:]	graph	a graphable character.
[:lower:]	lower	a lower-case character.
[:print:]	print	a printing character.
[:punct:]	punct	a punctuation character.
[:space:]	space	a white-space character.
[:upper:]	upper	an upper-case character.
[:xdigit:]	xdigit	a hexadecimal digit character.
[0-9]	range('0','9')	characters in range '0' through '9'.
[abc]	as_xpr('a') | 'b' |'c'	characters 'a', 'b', or 'c'.
[abc]	(set= 'a','b','c')	same as above
[0-9abc]	set[ range('0','9') | 'a' | 'b' | 'c' ]	characters 'a', 'b', 'c' or in range '0' through '9'.
[0-9abc]	set[ range('0','9') | (set= 'a','b','c') ]	same as above
[^abc]	~(set= 'a','b','c')	not characters 'a', 'b', or 'c'.
(?i:stuff)	icase(stuff)	match stuff disregarding case.
(?>stuff)	keep(stuff)	independent sub-expression, match stuff and turn off backtracking.
(?=stuff)	before(stuff)	positive look-ahead assertion, match if before stuff but don't include stuff in the match.
(?!stuff)	~before(stuff)	negative look-ahead assertion, match if not before stuff.
(?<=stuff)	after(stuff)	positive look-behind assertion, match if after stuff but don't include stuff in the match. (stuff must be constant-width.)
(?<!stuff)	~after(stuff)	negative look-behind assertion, match if not after stuff. (stuff must be constant-width.)

sregex re = sregex::compile( "this|that", regex_constants::icase );

sregex_compiler compiler;
sregex re = compiler.compile( "this|that", regex_constants::icase );

std::locale my_locale = /* initialize your locale object here */;
sregex_compiler compiler;
compiler.imbue( my_locale );
sregex re = compiler.compile( "\\w+|\\d+" );

Overview

Once you have created a regex object, you can use the regex_match() and regex_search() algorithms to find patterns in strings. This page covers the basics of regex matching and searching. In all cases, if you are familiar with how regex_match() and regex_search() in the Boost.Regex library work, xpressive's versions work the same way.

Seeing if a String Matches a Regex

The regex_match() algorithm checks to see if a regex matches a given input.

	Warning
	The regex_match() algorithm will only report success if the regex matches the whole input, from beginning to end. If the regex matches only a part of the input, regex_match() will return false. If you want to search through the string looking for sub-strings that the regex matches, use the regex_search() algorithm.

The input can be a std::string, a C-style null-terminated string or a pair of iterators. In all cases, the type of the iterator used to traverse the input sequence must match the iterator type used to declare the regex object. (You can use the table in the Quick Start to find the correct regex type for your iterator.)

cregex cre = +_w;  // this regex can match C-style strings
sregex sre = +_w;  // this regex can match std::strings

if( regex_match( "hello", cre ) )              // OK
    { /*...*/ }

if( regex_match( std::string("hello"), sre ) ) // OK
    { /*...*/ } 

if( regex_match( "hello", sre ) )              // ERROR! iterator mis-match!
    { /*...*/ }

The regex_match() algorithm optionally accepts a match_results<> struct as an out parameter. If given, the regex_match() algorithm fills in the match_results<> struct with information about which parts of the regex matched which parts of the input.

cmatch what;
cregex cre = +(s1= _w);

// store the results of the regex_match in "what"
if( regex_match( "hello", what, cre ) )
{
    std::cout << what[1] << '\n'; // prints "o"
}

The regex_match() algorithm also optionally accepts a match_flag_type bitmask. With match_flag_type, you can control certain aspects of how the match is evaluated. See the match_flag_type reference for a complete list of the flags and their meanings.

std::string str("hello");
sregex sre = bol >> +_w;

// match_not_bol means that "bol" should not match at [begin,begin)
if( regex_match( str.begin(), str.end(), sre, regex_constants::match_not_bol ) )
{
    // should never get here!!!
}

Click here to see a complete example program that shows how to use regex_match(). And check the regex_match() reference to see a complete list of the available overloads.

Searching for Matching Sub-Strings

Use regex_search() when you want to know if an input sequence contains a sub-sequence that a regex matches. regex_search() will try to match the regex at the beginning of the input sequence and scan forward in the sequence until it either finds a match or exhausts the sequence.

In all other regards, regex_search() behaves like regex_match() (see above). In particular, it can operate on std::string, C-style null-terminated strings or iterator ranges. The same care must be taken to ensure that the iterator type of your regex matches the iterator type of your input sequence. As with regex_match(), you can optionally provide a match_results<> struct to receive the results of the search, and a match_flag_type bitmask to control how the match is evaluated.

Click here to see a complete example program that shows how to use regex_search(). And check the regex_search() reference to see a complete list of the available overloads.

Overview

Sometimes, it is not enough to know simply whether a regex_match() or regex_search() was successful or not. If you pass an object of type match_results<> to regex_match() or regex_search(), then after the algorithm has completed successfully the match_results<> will contain extra information about which parts of the regex matched which parts of the sequence. In Perl, these sub-sequences are called back-references, and they are stored in the variables $1, $2, etc. In xpressive, they are objects of type sub_match<>, and they are stored in the match_results<> structure, which acts as a vector of sub_match<> objects.

match_results

So, you've passed a match_results<> object to a regex algorithm, and the algorithm has succeeded. Now you want to examine the results. Most of what you'll be doing with the match_results<> object is indexing into it to access its internally stored sub_match<> objects, but there are a few other things you can do with a match_results<> object besides.

The table below shows how to access the information stored in a match_results<> object named what.

There is more you can do with the match_results<> object, but that will be covered when we talk about Grammars and Nested Matches.

sub_match

When you index into a match_results<> object, you get back a sub_match<> object. A sub_match<> is basically a pair of iterators. It is defined like this:

template< class BidirectionalIterator >
struct sub_match
    : std::pair< BidirectionalIterator, BidirectionalIterator >
{
    bool matched;
    // ...
};

Since it inherits publicaly from std::pair<>, sub_match<> has first and second data members of type BidirectionalIterator. These are the beginning and end of the sub-sequence this sub_match<> represents. sub_match<> also has a Boolean matched data member, which is true if this sub_match<> participated in the full match.

The following table shows how you might access the information stored in a sub_match<> object called sub.

Results Invalidation

Results are stored as iterators into the input sequence. Anything which invalidates the input sequence will invalidate the match results. For instance, if you match a std::string object, the results are only valid until your next call to a non-const member function of that std::string object. After that, the results held by the match_results<> object are invalid. Don't use them!

Regular expressions are not only good for searching text; they're good at manipulating it. And one of the most common text manipulation tasks is search-and-replace. xpressive provides the regex_replace() algorithm for searching and replacing.

regex_replace()

Performing search-and-replace using regex_replace() is simple. All you need is an input sequence, a regex object, and a format string. There are two versions of the regex_replace() algorithm. The first accepts the input sequence as std::basic_string<> and returns the result in a new std::basic_string<>. The second accepts the input sequence as a pair of iterators, and writes the result into an output iterator. Below are examples of each.

std::string input("This is his face");
sregex re = as_xpr("his");                // find all occurrences of "his" ...
std::string format("her");                // ... and replace them with "her"

// use the version of regex_replace() that operates on strings
std::string output = regex_replace( input, re, format );
std::cout << output << '\n';

// use the version of regex_replace() that operates on iterators
std::ostream_iterator< char > out_iter( std::cout );
regex_replace( out_iter, input.begin(), input.end(), re, format );

The above program prints out the following:

Ther is her face
Ther is her face

Notice that all the occurrences of "his" have been replaced with "her".

Click here to see a complete example program that shows how to use regex_replace(). And check the regex_replace() reference to see a complete list of the available overloads.

The Format String

As with Perl, you can refer to sub-matches in the format string. The table below shows the escape sequences xpressive recognizes in the format string.

Any other sequence beginning with '$' simply represents itself. For example, if the format string were "$a" then "$a" would be inserted into the output sequence.

Replace Options

The regex_replace() algorithm takes an optional bitmask parameter to control the formatting. The possible values of the bitmask are:

These flags live in the regex_constants namespace.

regex_token_iterator<> is the Ginsu knife of the text manipulation world. It slices! It dices! This section describes how to use the highly-configurable regex_token_iterator<> to chop up input sequences.

Overview

You initialize a regex_token_iterator<> with an input sequence, a regex, and some optional configuration parameters. The regex_token_iterator<> will use regex_search() to find the first place in the sequence that the regex matches. When dereferenced, the regex_token_iterator<> returns a token in the form of a std::basic_string<>. Which string it returns depends on the configuration parameters. By default it returns a string corresponding to the full match, but it could also return a string corresponding to a particular marked sub-expression, or even the part of the sequence that didn't match. When you increment the regex_token_iterator<>, it will move to the next token. Which token is next depends on the configuration parameters. It could simply be a different marked sub-expression in the current match, or it could be part or all of the next match. Or it could be the part that didn't match.

As you can see, regex_token_iterator<> can do a lot. That makes it hard to describe, but some examples should make it clear.

Example 1: Simple Tokenization

This example uses regex_token_iterator<> to chop a sequence into a series of tokens consisting of words.

std::string input("This is his face");
sregex re = +_w;                      // find a word

// iterate over all the words in the input
sregex_token_iterator begin( input.begin(), input.end(), re ), end;

// write all the words to std::cout
std::ostream_iterator< std::string > out_iter( std::cout, "\n" );
std::copy( begin, end, out_iter );

This program displays the following:

This
is
his
face

Example 2: Simple Tokenization, Reloaded

This example also uses regex_token_iterator<> to chop a sequence into a series of tokens consisting of words, but it uses the regex as a delimiter. When we pass a -1 as the last parameter to the regex_token_iterator<> constructor, it instructs the token iterator to consider as tokens those parts of the input that didn't match the regex.

std::string input("This is his face");
sregex re = +_s;                      // find white space

// iterate over all non-white space in the input. Note the -1 below:
sregex_token_iterator begin( input.begin(), input.end(), re, -1