FWIW, here are some timings for different "flavors" of xpressive, and some other boost and non-boost search algo's. YMMW. Caveats: * contrived data (BMH probably doesn't help) std::string testStr = "Alternate days of the week are Tue and Thursday and Sat and Monday. " "And then Monday and Wed and Friday and Sun. " "Abbrev days in alpha order are Fri Mon Sat Sun Thu Tue Wed " "Full days in alpha order are Friday Monday Saturday Sunday Thursday Tuesday Wednesday " "Abbrev days in reverse alpha order are Wed Tue Thu Sun Sat Mon Fri " "Full days in reverse alpha order are Wednesday Tuesday Thursday Sunday Saturday Monday Friday " "Embedded abbrev days in reverse alpha order are 1Wed 2Tue 3Thu 4Sun 5Sat 6Mon 7Fri " "Embedded Full days in alpha order are 1Friday 2Monday 3Saturday 4Sunday 5Thursday 6Tuesday 7Wednesday " "Abbrev dot days in alpha order are Fri. Mon. Sat. Sun. Thu. Tue. Wed. " "Abbrev dot days in reverse alpha order are Wed. Tue. Thu. Sun. Sat. Mon. Fri. " "Near misses are Wed.X Tue.X Thu.X Sun.X Sat.X Mon.X Fri.X " "Near misses are WednesDay TuesDay ThursDay SunDay SaturDay MonDay FriDay " "Near misses are WeD TuE ThU SuN SaT MoN FrI " ; * not real confident of the numbers .... seem reasonable but ... Boost::xpressive-static: Elapsed for 10000 loops Ms: 422.72 Boost::xpressive-static: Elapsed for 100000 loops Ms: 4145.9 Boost::xpressive-dynamic-not-optimized: Elapsed for 10000 loops Ms: 429.847 Boost::xpressive-dynamic-not-optimized: Elapsed for 100000 loops Ms: 4392.54 Boost::xpressive-dynamic-optimized: Elapsed for 10000 loops Ms: 435.617 Boost::xpressive-dynamic-optimized: Elapsed for 100000 loops Ms: 4282.6 Boost::xpressive-static-iterator: Elapsed for 10000 loops Ms: 448.425 Boost::xpressive-static-iterator: Elapsed for 100000 loops Ms: 4379.07 Boost::regex: Elapsed for 10000 loops Ms: 622.377 Boost::regex: Elapsed for 100000 loops Ms: 5965.24 (can probably be tweaked and improved .... just q/d from example) FSM generator Elapsed for 10000 loops Ms: 2487.97 FSM generator Elapsed for 100000 loops Ms: 24870.5 Hand-tuned parser: Elapsed for 10000 loops Ms: 110.583 Hand-tuned parser: Elapsed for 100000 loops Ms: 1107.81 (no numbers for spirit .... barely started on its learning curve)