Basic Notes of Regular Expressions (Regex)

1. Introduction to Regular Expressions

   • What are regular expressions? They're a sequence of characters that define a search pattern, used for text matching or manipulating strings.
   • History and evolution: The concept originated from theoretical computer science research on finite automata theory in the mid-19th century. In the early days, they were implemented as specialized programs called "regular expression processors" (REP). Modern regex engines have evolved significantly since then, adding features like lookaround assertions, backtracking control verbs, and more.
   • Purpose and applications: Regex is widely used across various fields, including programming languages, software development tools, data analysis, web scraping, natural language processing, bioinformatics, and many others. It can be applied to tasks such as validating input formats, extracting information, replacing substrings, parsing log files, etc.

2. Basic syntax and patterns

   • Literal characters: Any character except metacharacters (^, $, \, ., *, +, ?, (, ), [, ], {, }) represents itself literally when it appears inside a regex.
   • Wildcard characters: Dot (.), which matches any single character; and whitespace characters (space, tab, newline), which match themselves literally.
   • Escaped sequences: Some characters need escaping using a backslash (\). These include reserved symbols like parentheses, brackets, braces, slashes, dots, question marks, plus signs, stars, carets, dollar signs, vertical bars, hyphens, and more.

3. Metacharacters and escapes

   • Metacharacter overview: Metacharacters are characters with specific meanings within a regex. They include anchors (^ and $), quantifiers (* and +), grouping constructs (( )), alternation operator |, word boundaries \b, line breaks \n, and more.

   • Escaping metacharacters: To use them as literal characters instead of their special meaning, escape them by preceding each one with a backslash ().

   • Commonly used metacharacters: Here are some examples:

     • ^: start anchor (matches at beginning of string);
     • $: end anchor (matches at end of string);
     • \d: digit class shorthand ([0-9]);
     • \w: alphanumeric class shorthand ([A-Za-z0-9_]);
     • \s: space class shorthand ([ \t\r\n\f]);
     • .: wildcard (any single char but newlines);
     • []: character set/class definition;
     • -: range indicator in sets;
     • (): capturing group;
     • (?:): non-capturing group;
     • (?=): positive lookahead assertion;
     • (?!): negative lookahead assertion;
     • (?<=): positive lookbehind assertion;
     • (?<!): negative lookbehind assertion;
     • {}: repetition count specifier;
     • *: zero or more occurrences;
     • +: one or more occurrences;
     • ?: optional occurrence;
     • |: alternative separator;
     • \: escape symbol.

4. Character classes and quantifiers

   • Character classes: Define a set of characters, usually represented between square brackets ([ ]). Inside these brackets, you can specify individual characters, ranges, or predefined character classes. Example: [abc] matches 'a', 'b', or 'c'; [a-zA-Z] matches all letters from 'a' to 'z'.

   • Quantifiers: Specify how often an element should repeat. There are several types:

     • x{m} - exactly m times;
     • x{m, n} - min m, max n times;
     • x{m, } - min m times;
     • x* - zero or more times;
     • x+ - one or more times;
     • x? - once or not at all;
     • x?? - lazily matched version of x?.

5. Anchors and boundaries

   • Start and end anchors: ^ and $ respectively mark the beginning and ending positions of a string. Example: /^hello/ only matches if 'hello' occurs at the very start of a string.
   • Word boundaries: \b indicates a transition point between words. This means either the boundary before the first letter of a word or after its last letter. Example: /\bcat\b/ will find instances of 'cat' surrounded by spaces, punctuation, or other non-word characters.
   • Line boundaries: ^ and $ also work differently depending on whether multiline mode is enabled. If so, they match the start and end points of lines rather than entire strings.

6. Grouping and capturing

   • Grouping parentheses: (...) create groups without storing captured values. You can nest multiple levels of parentheses to form complex structures.
   • Capture groups: (...), along with named capture groups <name>, store the value matched by their contents under index numbers or names. These can later be referenced through backreferences or accessed programmatically.
   • Non-capturing groups: (?:...) don't save anything, just help organize your regex into logical sections.

7. Alternation and branching

   • Alternation operator |: Separate alternatives with pipelines (|). Whichever part comes first wins. Example: /apple|banana/ matches both 'apple' and 'banana'.
   • Branch reset groups: (?|...) allow different branches to share the same numbered captures. This way, you can write shorter regexes while still preserving readability.
   • Conditional matching: (?(condition)(then)|(else)) checks condition and executes corresponding code block based on the result. Example: /(?(\d)\d|\D)/ matches digits followed by another digit or non-digits.

8. Lookahead and lookbehind assertions

   • Positive lookahead: (?=...) ensures what follows matches the specified pattern, but doesn't consume those characters. Example: /\d+(?=\.)/ finds integers followed by periods.
   • Negative lookahead: (?!...) makes sure what follows does NOT match the given pattern. Example: /\d+(?!\.)/ finds integers not followed by periods.
   • Positive lookbehind: (?<=...) works similarly to positive lookahead, but looks behind instead of ahead. Example: /(?<=[aeiou])[^aeiou]+/ matches consonants preceded by vowels.
   • Negative lookbehind: (?<!...) checks if there aren't certain characters immediately preceding the current position. Example: /(?<![aeiou])([^aeiou]+)/ matches consonant clusters not preceded by vowels.

9. Practical examples and use cases

   • Text search and manipulation: Find and replace, highlighting, tokenizing, splitting, etc.
   • Data validation and sanitization: Ensure correct formatting, eliminate invalid entries, remove malicious content.
   • Parsing and extracting information: Scrape websites, parse logs, analyze texts, etc.

10. Advanced techniques and optimization

• Backreferences: Refer to previously matched parts of the subject string. Example: /(\w+) \1/ matches repeated words separated by a space.
• Atomic groups: Prevent backtracking within a group. Example: /(?>\w+\s)+\w+/ prevents excessive backtracking during failed matches.
• Performance optimization: Write efficient regexes by avoiding unnecessary backtracking, greedy quantifiers, and nested groups.

11. Debugging and troubleshooting

• Testing and debugging tools: Websites like Regex101 provide interactive environments where you can test and debug your regexes online.
• Common pitfalls and errors: Misspelling metacharacters, incorrect usage of quantifiers, unbalanced parenthesis pairs, and more.
• Troubleshooting techniques: Check error messages, simplify your regex step by step, isolate problematic areas, and consult documentation.

12. Best practices and pitfalls to avoid

• Readable and maintainable regex: Keep your regex concise yet descriptive, comment heavily, and break down long ones into smaller pieces.
• Edge case handling: Be aware of potential edge cases and handle them appropriately.
• Performance considerations: Avoid catastrophic backtracking, prefer atomic groups over lazy quantifiers, and optimize your regex for performance.

13. Applications and integration with programming languages

• Python: Import re module, compile regex, call methods like match(), search(), split().
• JavaScript: Create RegExp objects, use built-ins like exec() and test().
• Java: java.util.regex package provides support for regex operations.

14. Resources and further reading

• Books and online tutorials: Mastering Regular Expressions, RegEx Cookbook, Regular Expression Pocket Reference.
• Online communities and forums: Stack Overflow, Reddit r/learnprogramming, Quora.
• Advanced topics and research papers: Nondeterministic Finite Automaton Theory, Fuzzy Logic, Natural Language Processing.

15. Glossary of terms

• Definitions of commonly used terms: Regex engine, flavor, metacharacter, character class, quantifier, alternation, lookaround, backreference, atomic group, catastrophic backtracking, etc.