Mastering Regular Expressions

Table of Contents
Preface
	The Need for This Book
	Intended Audience
	How to Read This Book
	Organization
		The Details
		Tool-Specific Information
	Typographical Conventions
	Exercises
	Links, Code, Errata, and Contacts
		Safar i®Enabled
	Personal Comments and
Introduction to Regular Expressions
	Solving Real Problems
	Regular Expressions as a Language
		The Filename Analogy
		The Language Analogy
			The goal of this book
	The Regular-Expression Frame of Mind
		If You Have Some Regular-Expression Experience
		Searching Text Files: Egrep
	Egrep Metacharacter s
		Start and End of the Line
		Character Classes
			Matching any one of several character s
			Negated character classes
		Matching Any Character with Dot
		Alternation
			Matching any one of several subexpressions
		Ignoring Differences in Capitalization
		Word Boundaries
		In a Nutshell
		Optional Items
		Other Quantifiers: Repetition
			Defined range of matches: intervals
		Parentheses and Backreferences
		The Great Escape
	Expanding the Foundation
		Linguistic Diver sification
		The Goal of a Regular Expression
		A Few More Examples
			Variable names
			A string within double quotes
			Dollar amount (with optional cents)
			An HTTP/HTML URL
			An HTML tag
		Regular Expression Nomenclature
			Regex
			Matching
			Metacharacter
			Flavor
			Subexpression
			Character
		Improving on the Status Quo
		Summary
	Personal Glimpses
Extended Introductory Examples
	About the Examples
		A Short Introduction to Perl
	Matching Text with Regular Expressions
		Toward a More Real-World Example
		Side Effects of a Successful Match
		Intertwined Regular Expressions
			A short aside--metacharacter s galore
			Generic "whitespace" with \s
		Intermission
	Modifying Text with Regular Expressions
		Example: Form Letter
		Example: Prettifying a Stock Price
		Automated Editing
		A Small Mail Utility
			Real-world problems, real-world solutions
			The "real" real world
		Adding Commas to a Number with Lookaround
			Lookaround doesn't "consume" text
			A few more lookahead examples
			Back to the comma example . . .
			Word boundar ies and negative lookaround
			Commafication without lookbehind
		Text-to-HTML Conversion
			Cooking special characters
			Separating paragraphs
			"Linkizing" an email address
			Matching the username and hostname
			Putting it together
			"Linkizing" an HTTP URL
			Building a regex library
			Why `$' and ` @' sometimes need to be escaped
		That Doubled-Word Thing
			Double-word example in Perl
			Moving bits around: operators, functions, and objects
			Double-word example in Java
Overview of Regular Expressions Features and Flavors
	Regular Expressions and Cars
	In This Chapter
	A Casual Stroll Across the Regex Landscape
		The Origins of Regular Expressions
			Grep's metacharacters
			Grep evolves
			Egrep evolves
			Other species evolve
			POSIXŁAn attempt at standardization
			Henry Spencer's regex package
			Perl evolves
			A partial consolidation of flavors
			Versions as of this book
		At a Glance
	Care and Handling of Regular Expressions
		Integrated Handling
		Procedural and Object-Oriented Handling
			Regex handling in Java
			Regex handling in VB and other .NET languages
			Regex handling in PHP
			Regex handling in Python
			Why do approaches differ?
		A Search-and-Replace Example
			Search and replace in Java
			Search and replace in VB.NET
			Search and replace in PHP
		Search and Replace in Other Languages
			Awk
			Tcl
			GNU Emacs
		Care and Handling: Summary
	Strings, Character Encodings, and Modes
		Strings as Regular Expressions
			Strings in Java
			Strings in VB.NET
			Strings in C#
			Strings in PHP
			Strings in Python
			Strings in Tcl
			Regex literals in Perl
		Character-Encoding Issues
			Richness of encoding-related support
		Unicode
			Characters versus combining-character sequences
			Multiple code points for the same character
			Unicode 3.1+ and code points beyond U +FFFF
			Unicode line terminator
		Regex Modes and Match Modes
			Case-insensitive match mode
			Free-spacing and comments regex mode
			Dot-matches-all match mode (a.k.a., Łsingle-line modeŁ)
			An unfortunate name.
			Enhanced line-anchor match mode (a.k.a., Łmultiline modeŁ)
			Literal-text regex mode
	Common Metacharacters and Features
		Constructs Covered in This Section
		Character Representations
			Character shorthands
			These are machine dependent?
			Octal escapeŁ \num
			Hex and Unicode escapes: \xnum, \x{num}, \unum, \Unum, ...
			Control characters: \cchar
		Character Classes and Class-Like Constructs
			Normal classes: [a-z]and [^a-z]
			Almost any character: dot
			Dot ver sus a negated character class
			Exactly one byte
			Unicode combining character sequence: \X
			Class shorthands: \w, \d, \s, \W, \D, \S
			Unicode properties, scripts, and blocks: \p{Prop }, \P{Prop }
			Scripts.
			Blocks.
			Other properties/qualities.
			Simple class subtraction:
			Full class set operations:
			Class subtraction with set operators.
			Mimicking class set operations with lookaround.
			POSIX bracket-expression Łcharacter classŁ: [[:alpha:]]
			POSIX bracket-expression Łcollating sequencesŁ: [[.span-ll.]]
			POSIX bracket-expression Łcharacter equivalentsŁ: [[=n=]]
			Emacs syntax classes
		Anchors and Other ŁZero-Width AssertionsŁ
			Start of line/string: ^, \A
			End of line/string: $, \Z, \z
			Start of match (or end of previous match): \G
			End of previous match, or start of the current match?
			Word boundaries: \b, \B, \<, \>, ...
			Lookahead (?=ŁŁŁ), (?!ŁŁŁ); Lookbehind, (?<=ŁŁŁ), (?ŁŁŁ)
			Atomic grouping: (?>ŁŁŁ)
			Alternation: ŁŁŁ<ŁŁŁ<ŁŁŁ
			Conditional: (?if then |else )
			Using lookaround as the test.
			Other tests for the conditional.
			Greedy quantifier s: ,, +, ?, {num,num}
			Inter valsŁ {min ,max }or \{min ,max \}
			Lazy quantifier s: , ?, +?, ??, {num,num}?
			Possessive quantifier s: , +, ++, ?+, {num,num}+
	Guide to the Advanced Chapters
The Mechanics of Expression Processing
	Start Your Engines!
		Two Kinds of Engines
		New Standards
			The impact of standards
		Regex Eng ine Types
		From the Depar tment of Redundancy Depar tment
		Testing the Engine Type
			Traditional NFA or not?
			DFA or POSIX NFA?
	Match Basics
		About the Examples
		Rule 1: The Match That Begins Earliest Wins
			The ŁtransmissionŁ and the bump-along
			The transmission's main work: the bump-along
		Engine Pieces and Par ts
			No ŁelectricŁ parentheses, backreferences, or lazy quantifier s
		Rule 2: The Standard Quantifiers Are Greedy
			A subjective example
			Being too greedy
			First come, fir st ser ved
			Getting down to the details
	Regex-Directed Versus Text-Directed
		NFA Engine: Regex-Directed
			The control benefits of an NFA engine
		DFA Engine: Text-Directed
		First Thoughts: NFA and DFA in Comparison
			Consequences to us as users
	Backtracking
		A Really Crummy Analogy
			A crummy little example
		Two Important Points on Backtracking
		Saved States
			A match without backtracking
			A match after backtracking
			A non-match
			A lazy match
		Backtracking and Greediness
			Star, plus, and their backtracking
			Revisiting a fuller example
	More About Greediness
		Problems of Greediness
		Multi-Character "Quotes"
		Using Lazy Quantifiers
		Greediness and Laziness Always Favor a Match
		The Essence of Greediness, Laziness, and Backtracking
		Possessive Quantifiers and Atomic Grouping
			Atomic grouping with !(?>ŁŁŁ)"
			The essence of atomic grouping
			Some states may remain.
			Faster failures with atomic grouping.
		Possessive Quantifier s, ?+, ++, ++, and {m,n}+
		The Backtracking of Lookaround
			Mimicking atomic grouping with positive lookahead
		Is Alternation Greedy?
		Taking Advantage of Ordered Alternation
			Ordered alternation pitfalls
	NFA, DFA, and POSIX
		"The Longest-Leftmost"
			Really, the longest
		POSIX and the Longest-Leftmost Rule
		Speed and Efficiency
			DFA efficiency
		Summary: NFA and DFA in Comparison
			DFA versus NFA: Differences in the pre-use compile
			DFA versus NFA: Differences in match speed
			DFA versus NFA: Differences in what is matched
			DFA versus NFA: Differences in capabilities
			DFA versus NFA: Differences in ease of implementation
	Summary
Practical Regex Techniques
	Regex Balancing Act
	A Few Short Examples
		Continuing with Continuation Lines
		Matching an IP Address
			Know your context
		Working with Filenames
			Removing the leading path from a filename
			Accessing the filename from a path
			Both leading path and filename
		Matching Balanced Sets of Parentheses
		Watching Out for Unwanted Matches
		Matching Delimited Text
			Allowing escaped quotes in double-quoted strings
		Knowing Your Data and Making Assumptions
		Stripping Leading and Trailing Whitespace
	HTML-Related Examples
		Matching an HTML Tag
		Matching an HTML Link
		Examining an HTTP URL
		Validating a Hostname
		Plucking Out a URL in the Real World
	Extended Examples
		Keeping in Sync with Your Data
			Keeping the match in sync with expectations
			Maintaining sync after a non-match as well
			Maintaining sync with \G
			This example in perspective
		Parsing CSV Files
			Distrusting the bump-along
			Another approach.
			One change for the sake of efficiency
			Other CSV formats
Crafting an Efficient Expression
	Tests and Backtracks
	Traditional NFA versus POSIX NFA
	A Sobering Example
		A Simple Change--Placing Your Best Foot Forward
		Efficiency Versus Correctness
		Advancing Further--Localizing the Greediness
		Reality Check
			"Exponential" matches
	A Global View of Backtracking
		More Work for a POSIX NFA
		Work Required During a Non-Match
		Being More Specific
		Alternation Can Be Expensive
	Benchmarking
		Know What You're Measuring
		Benchmarking with PHP
		Benchmarking with Java
		Benchmarking with VB.NET
		Benchmarking with Ruby
		Benchmarking with Python
		Benchmarking with Tcl
	Common Optimizations
		No Free Lunch
		Everyone's Lunch is Different
		The Mechanics of Regex Application
		Pre-Application Optimizations
			Compile caching
			Compile caching in the integrated approach
			Compile caching in the procedural approach
			Compile caching in the object-oriented approach
			Pre-check of required character/substring optimization
			Length-cognizance optimization
		Optimizations with the Transmission
			Start of string/line anchor optimization
			Implicit-anchor optimization
			End of string/line anchor optimization
			Initial character/c lass/substring discrimination optimization
			Embedded literal string check optimization
			Length-cognizance transmission optimization
		Optimizations of the Regex Itself
			Literal string concatenation optimization
			Simple quantifier optimization
			Needless parentheses elimination
			Character following lazy quantifier optimization
			"Excessive" backtracking detection
			Exponential (a.k.a., super-linear) short-circuiting
			State-suppression with possessive quantifiers
			Small quantifier equivalence
			Need cognizance
	Techniques for Faster Expressions
		Common Sense Techniques
			Avoid recompiling
			Use non-capturing parentheses
			Don't add superfluous parentheses
			Don't use superfluous character classes
			Use leading anchors
		Expose Literal Text
			"Factor out" required components from quantifier s
			"Factor out" required components from the front of alternation
		Expose Anchors
			Expose ^and \Gat the front of expressions
			Expose $at the end of expressions
		Lazy Versus Greedy: Be Specific
		Split Into Multiple Regular Expressions
		Mimic Initial-Character Discrimination
			Don't do this with Tcl
			Don't do this with PHP
		Use Atomic Grouping and Possessive Quantifier s
		Lead the Engine to a Match
			Put the most likely alternative first
			Distribute into the end of alternation
				This optimization can be dangerous.
	Unrolling the Loop
		Method 1: Building a Regex From Past Experiences
			Constructing a general Łunrolling-the-loopŁ pattern
		The Real Unrolling-the-Loop" Patter n
			Avoiding the neverending match
				1) The start of special and normal must never inter sect.
				2) Special must not match nothingness.
				3) Special must be atomic.
			General things to look out for
		Method 2: A Top-Down View
		Method 3: An Internet Hostname
			Observations
		Using Atomic Grouping and Possessive Quantifier s
			Making a neverending match safe with possessive quantifier s
			Making a neverending match safe with atomic grouping
		Short Unrolling Examples
			Unrolling "multi-character" quotes
			Unrolling the continuation-line example
			Unrolling the CSV regex
		Unrolling C Comments
			To unroll or to not unroll . . .
			Avoiding regex headaches
			A direct approach
			Making it work
			Unrolling the C loop
				Return to reality
	The Freeflowing Regex
		A Helping Hand to Guide the Match
		A Well-Guided Regex is a Fast Regex
		Wrapup
	In Summary: Think!
Perl
	In This Chapter
	Perl in Earlier Chapters
	Regular Expressions as a Language
		Perl's Greatest Strength
		Perl's Greatest Weakness
	Perl's Regex Flavor
		Regex Operands and Regex Literals
			Features supported by regex literals
			Picking your own regex delimiters
		How Regex Literals Are Parsed
		Regex Modifiers
	Regex-Related Perlisms
		Dynamic Scope and Regex Match Effects
			Global and private var iables
			Dynamically scoped values
			A better analogy: clear transparencies
			Regex side effects and dynamic scoping
			Dynamic scoping ver sus lexical scoping
		Expression Context
			Contorting an expression
		Special Variables Modified by a Match
			Using $1within a regex?
	The qr/ŁŁŁ/ Operator and Regex Objects
		Building and Using Regex Objects
			Match modes (or lack thereof) are ver y sticky
		Viewing Regex Objects
		Using Regex Objects for Efficiency
	The Match Operator
		Match's Regex Operand
			Using a regex literal
			Using a regex object
			The default regex
			Special match-once ?ŁŁŁ?
		Specifying the Match Target Operand
			The default target
			Negating the sense of the match
		Different Uses of the Match Operator
			Normal "does this match?"--scalar context without /g
			Normal "pluck data from a string"Łlist context, without /g
			"Pluck all matches"Łlist context, with the /g modifier
		Iterative Matching: Scalar Context, with /g
			The "current match location" and the pos()function
			Pre-setting a string's pos
			Using \G
			"Tag-team" matching with /gc
			Pos-related summary
		The Match Operator's Environmental Relations
			The match operator's side effects
			Outside influences on the match operator
			Keeping your mind in context (and context in mind)
	The Substitution Operator
		The Replacement Operand
		The /e Modifier
			Multiple uses of /e
		Context and Return Value
	The Split Operator
		Basic Split
			Basic match operand
			Target string operand
			Basic chunk-limit operand
			Advanced split
		Returning Empty Elements
			Trailing empty elements
			The chunk-limit operand's second job
			Special matches at the ends of the string
		Split's Special Regex Operands
			Split has no side effects
		Split's Match Operand with Capturing Parentheses
	Fun with Perl Enhancements
		Using a Dynamic Regex to Match Nested Pair s
		Using the Embedded-Code Construct
			Using embedded code to display match-time information
			Using embedded code to see all matches
			Finding the longest match
			Finding the longest-leftmost match
			Using embedded code in a conditional
		Using local in an Embedded-Code Construct
		A Warning About Embedded Code and my Variables
		Matching Nested Constructs with Embedded Code
		Overloading Regex Literals
			Adding start- and end-of-word metacharacter s
			Adding support for possessive quantifiers
		Problems with Regex-Literal Overloading
		Mimicking Named Capture
	Perl Efficiency Issues
		"There's More Than One Way to Do It"
		Regex Compilation, the /o Modifier, qr/ŁŁŁ/,
			The internal mechanics of preparing a regex
			Perl steps to reduce regex compilation
			Unconditional caching
			On-demand recompilation
			The "compile once" /o modifier
			Potential "gotchas" of /o
			Using regex objects for efficiency
			Using /o with qr/ŁŁŁ/
			Using the default regex for efficiency
		Understanding the "Pre-Match" Copy
			Pre-match copy suppor ts $1, $&, $', $+, . . .
			The pre-match copy is not always needed
			The variables $`, $&, and $'are naughty
			How expensive is the pre-match copy?
			Avoiding the pre-match copy
				Don't use naughty modules.
		The Study Function
			When not to use study
			When study can help
		Benchmarking
		Regex Debugging Information
			Run-time debugging infor mation
			Other ways to invoke debugging messages
	Final Comments
Java
	Java's Regex Flavor
		Java Support for \p{ŁŁŁ}and \P{ŁŁŁ}
			Unicode proper ties
			Unicode blocks
			Special Java character proper ties
		Unicode Line Terminators
	Using java.util.regex
	The Pattern.compile()Factor y
		Pattern's matchermethod
	The Matcher Object
		Applying the Regex
		Querying Match Results
			Match-result example
		Simple Search and Replace
			Simple search and replace examples
			The replacement argument
		Advanced Search and Replace
			Search-and-replace examples
		In-Place Search and Replace
			Using a different-sized replacement
		The Matcher's Reg ion
			Points to keep in mind
			Setting and inspecting region bounds
			Looking outside the current region
			Transparent bounds
			Anchoring bounds
		Method Chaining
		Methods for Building a Scanner
			Examples illustrating hitEndand requireEnd
			The hitEndbug and its workaround
		Other Matcher Methods
			Querying a matcher's target text
	Other Pattern Methods
		Pattern's split Method, with One Argument
			Empty elements with adjacent matches
		Pattern's split Method, with Two Arguments
			Split with a limit less than zero
			Split with a limit of zero
			Split with a limit greater than zero
	Additional Examples
		Adding Width and Height Attributes to Image Tags
		Validating HTML with Multiple Patterns Per Matcher
		Parsing Comma-Separated Values (CSV) Text
	Java Version Differences
		Differences Between 1.4.2 and 1.5.0
			New methods in Java 1.5.0
			Unicode-support differences between 1.4.2 and 1.5.0
		Differences Between 1.5.0 and 1.6
.NET
	.NET's Regex Flavor
		Additional Comments on the Flavor
			Named capture
			An unfortunate consequence
			Conditional tests
			"Compiled" expressions
			Right-to-left matching
			Backslash-dig it ambiguities
			ECMAScr ipt mode
	Using .NET Regular Expressions
		Regex Quickstart
			Quickstart: Checking a string for match
			Quickstart: Matching and getting the text matched
			Quickstart: Matching and getting captured text
			Quickstart: Search and replace
		Package Overview
			Importing the regex namespace
		Core Object Overview
			Regex objects
			Match objects
			Group objects
			Capture objects
			All results are computed at match time
	Core Object Details
		Creating Regex Objects
			Catching exceptions
			Regex options
		Using Regex Objects
			Using a replacement delegate
			Using Splitwith capturing parentheses
		Using Match Objects
		Using Group Objects
	Static "Convenience" Functions
		Regex Caching
		Support Functions
			Regex.Escape(string )
			Regex.Unescape(str ing )
			Match.Empty
			Regex.CompileToAssembly(ŁŁŁ)
	Advanced .NET
		Regex Assemblies
		Matching Nested Constructs
		Capture Objects
PHP
	PHP's Regex Flavor
	The Preg Function Interface
	"Pattern" Arguments
		PHP single-quoted strings
		Delimiters
		Pattern modifiers
			Mode modifiers outside the regex
			PHP-specific modifiers
	The Preg Functions
		preg_match
			Capturing match data
			Trailing "non-participatory" elements stripped
			Named capture
			Getting more details on the match: PREG_OFFSET_CAPTURE
			The offset argument
		preg_match_all
			Collecting match data
				The default PREG_PATTERN_ORDER ar rangement
				The PREG_SET_ORDER ar rangement
			pregR matchR alland the PREG_OFFSET_CAPTURE flag
			pregR matchR allwith named capture
		preg_replace
			Basic one-string, one-pattern, one-replacement pregR replace
			Multiple subjects, patterns, and replacements
				Ordering of array arguments
		preg_replace_callback
			A callback versus the e pattern modifier
		preg_split
			preg_split's limit argument
			preg_split's flag arguments
		preg_grep
		preg_quote
	"Missing" Preg Functions
		preg_regex_to_pattern
			The problem
			The solution
		Syntax-Checking an Unknown Pattern Argument
		Syntax-Checking an Unknown Regex
	Recursive Expressions
		Matching Text with Nested Parentheses
			Recursive reference to a set of capturing parentheses
			Recursive reference via named capture
			More on possessive quantifiers
		No Backtracking Into Recursion
		Matching a Set of Nested Parentheses
	PHP Efficiency Issues
		The S Pattern Modifier: "Study"
			Standard optimizations, without the S pattern modifier
			Enhancing the optimization with the S pattern modifier
			When the S pattern modifier can't help
			Suggested use
	Extended Examples
		CSV Parsing with PHP
		Checking Tagged Data for Proper Nesting
			The main body of this expression
			Possessive quantifiers
			Real-world XML
			HTML ?
Index