<commit_before>## Unix Programming and Regular Expressions Workshop - Text Searching

## Sections:

* [Regular Expressions](#regular-expressions)
* [History and Types of Regular Expressions](#history-and-types-of-regular-expressions)
* [Unix Tools that use Regular Expressions](#unix-tools-that-use-regular-expressions)
* [Basic Regular Expressions](#basic-regular-expressions)
* [Extended Regular Expressions](#extended-regular-expressions)
* [Family of Regular Expression Tools](#family-of-regular-expression-tools)
* [Important Grep Options](#important-grep-options)
* [Good Practices for Regular Expressions](#good-practices-for-regular-expressions)
* [Bracket Expressions](#bracket-expressions)
* [Grep Examples](#grep-examples)
* [Interval Expressions](#interval-expressions)
* [Parenthesized Subexpressions](#parenthesized-subexpressions)
* [Basic Regular Expression Operator Precedence](#basic-regular-expression-operator-precedence)
* [Regular Expression Matching](#regular-expression-matching)
* [Intermediate Grep Examples](#intermediate-grep-examples)
* [Extended Regular Expressions](#extended-regular-expressions)
* [Bread Crumb Navigation](#bread-crumb-navigation)

#### Regular Expressions

[Regular Expressions](https://en.wikipedia.org/wiki/Regular_expression)

Regular expressions (regex) can be thought of as a language to describe matching text.

> A regular expression, regex or regexp (sometimes called a rational expression) is, in theoretical computer science and formal language theory, a sequence of characters that define a search pattern.

Regular Expressions are comprised of:

* Some regular characters that can stand for themselves like 'a'
* Metacharacters that can stand for a regular expression operation

Here is a chart on metacharacters:

| `Metacharacter` | `Description` |
| --- | --- |
| `^` | Matches the starting position within the string. In line-based tools, it matches the starting position of any line. |
| `.` | Matches any single character (many applications exclude newlines, and exactly which characters are considered newlines is flavor-, character-encoding-, and platform-specific, but it is safe to assume that the line feed character is included). Within POSIX bracket expressions, the dot character matches a literal dot. For example, a.c matches "abc", etc., but [a.c] matches only "a", ".", or "c". |
| `[]` | A bracket expression. Matches a single character that is contained within the brackets. For example, [abc] matches "a", "b", or "c". [a-z] specifies a range which matches any lowercase letter from "a" to "z". These forms can be mixed: [abcx-z] matches "a", "b", "c", "x", "y", or "z", as does [a-cx-z]. The - character is treated as a literal character if it is the last or the first (after the ^, if present) character within the brackets: [abc-], [-abc]. Note that backslash escapes are not allowed. The ] character can be included in a bracket expression if it is the first (after the ^) character: []abc]. |
| `[^]` | Matches a single character that is not contained within the brackets. For example, [^abc] matches any character other than "a", "b", or "c". [^a-z] matches any single character that is not a lowercase letter from "a" to "z". Likewise, literal characters and ranges can be mixed. |
| `$` | Matches the ending position of the string or the position just before a string-ending newline. In line-based tools, it matches the ending position of any line. |
| `()` | Defines a marked subexpression. The string matched within the parentheses can be recalled later (see the next entry, \n). A marked subexpression is also called a block or capturing group. BRE mode requires \( \). |
| `\n` | Matches what the nth marked subexpression matched, where n is a digit from 1 to 9. This construct is vaguely defined in the POSIX.2 standard. Some tools allow referencing more than nine capturing groups. |
| `*` | Matches the preceding element zero or more times. For example, ab*c matches "ac", "abc", "abbbc", etc. [xyz]* matches "", "x", "y", "z", "zx", "zyx", "xyzzy", and so on. (ab)* matches "", "ab", "abab", "ababab", and so on. |
| `{m, n}` | Matches the preceding element at least m and not more than n times. For example, a{3,5} matches only "aaa", "aaaa", and "aaaaa". This is not found in a few older instances of regexes. BRE mode requires \{m,n\}. |

* Expressions that denote categories of a regular expression

#### History and Types of Regular Expressions

> Regular expressions originated in 1956, when mathematician <NAME> described regular languages using his mathematical notation called regular sets. These arose in theoretical computer science, in the subfields of automata theory (models of computation) and the description and classification of formal languages. Other early implementations of pattern matching include the [SNOBOL language](https://en.wikipedia.org/wiki/SNOBOL), which did not use regular expressions, but instead its own pattern matching constructs.

* Different Unix tools have used different Regular Expression types
* This reflects the influence and interests in AT&T Research Labs (Kernighan, Ritchie, etc)

#### Unix Tools that use Regular Expressions

Unix Tools that use Regexes:

* grep

* sed

* awk

* vim

* emacs

#### Basic Regular Expressions

BRE (Basic Regular Expressions)

BRE . Although POSIX.2 leaves some implementation specifics undefined, BRE and ERE provide a "standard" which has since been adopted as the default syntax of many tools, where the choice of BRE or ERE modes is usually a supported option. For example, GNU grep has the following options: "grep -E" for ERE, and "grep -G" for BRE (the default), and "grep -P" for Perl regexes.

###### Examples of Regular Expressions

Here are some examples from the [Regular Expressions Wikipedia Page](https://en.wikipedia.org/wiki/Regular_expression):

* `.at` matches any three-character string ending with "at", including "hat", "cat", and "bat".

* `[hc]at` matches "hat" and "cat".

* `[^b]at` matches all strings matched by .at except "bat".

* `[^hc]at` matches all strings matched by .at other than "hat" and "cat".

* `^[hc]at` matches "hat" and "cat", but only at the beginning of the string or line.

* `[hc]at$` matches "hat" and "cat", but only at the end of the string or line.

* `\[.\]` matches any single character surrounded by "[" and "]" since the brackets are escaped, for example: "[a]" and "[b]".

* `s.*` matches s followed by zero or more characters, for example: "s" and "saw" and "seed".

#### Extended Regular Expressions

* ERE (Extended Regular Expressions) adds `?`, `+`, and `|`, and EREs removes the need to escape the metacharacters `( )` and `{ }`, which are required in BREs.

* Furthermore, as long as the POSIX standard syntax for regexes is adhered to, there can be, and often is, additional syntax to serve specific (yet POSIX compliant) applications

* The meaning of metacharacters escaped with a backslash is reversed for some characters in the POSIX Extended Regular Expression (ERE) syntax.

* With this syntax, a backslash causes the metacharacter to be treated as a literal character.

* So, for example, `\( \)` is now `( )` and `\{ \}` is now `{ }`.

* Additionally, support is removed for \n backreferences and the following metacharacters are added:

| `Metacharacter`	| `Description` |
| --- | --- |
| `?` |	Matches the preceding element zero or one time. For example, ab?c matches only "ac" or "abc". |
| `+`	| Matches the preceding element one or more times. For example, ab+c matches "abc", "abbc", "abbbc", and so on, but not "ac". |
| `&#124;`	| The choice (also known as alternation or set union) operator matches either the expression before or the expression after the operator. For example, `abc\|def` matches "abc" or "def". |

###### Examples of EREs

* [hc]?at matches "hat", "cat", and "at".

* [hc]*at matches "hat", "cat", "hhat", "chat", "hcat", "cchchat", "at", and so on.

* [hc]+at matches "hat", "cat", "hhat", "chat", "hcat", "cchchat", and so on, but not "at".

* cat|dog matches "cat" or "dog".

#### Family of Regular Expression Tools

###### Grep

Different `Grep` programs:

1. The `grep` utility searches any given input files, selecting lines that match one or more patterns.
2. The `egrep` interprets pattern as an extended regular expression
  1. Force regular `grep` to behave like `egrep` with `-E` flag.<commit_msg>Really fix pipe<commit_after>## Unix Programming and Regular Expressions Workshop - Text Searching

## Sections:

* [Regular Expressions](#regular-expressions)
* [History and Types of Regular Expressions](#history-and-types-of-regular-expressions)
* [Unix Tools that use Regular Expressions](#unix-tools-that-use-regular-expressions)
* [Basic Regular Expressions](#basic-regular-expressions)
* [Extended Regular Expressions](#extended-regular-expressions)
* [Family of Regular Expression Tools](#family-of-regular-expression-tools)
* [Important Grep Options](#important-grep-options)
* [Good Practices for Regular Expressions](#good-practices-for-regular-expressions)
* [Bracket Expressions](#bracket-expressions)
* [Grep Examples](#grep-examples)
* [Interval Expressions](#interval-expressions)
* [Parenthesized Subexpressions](#parenthesized-subexpressions)
* [Basic Regular Expression Operator Precedence](#basic-regular-expression-operator-precedence)
* [Regular Expression Matching](#regular-expression-matching)
* [Intermediate Grep Examples](#intermediate-grep-examples)
* [Extended Regular Expressions](#extended-regular-expressions)
* [Bread Crumb Navigation](#bread-crumb-navigation)

#### Regular Expressions

[Regular Expressions](https://en.wikipedia.org/wiki/Regular_expression)

Regular expressions (regex) can be thought of as a language to describe matching text.

> A regular expression, regex or regexp (sometimes called a rational expression) is, in theoretical computer science and formal language theory, a sequence of characters that define a search pattern.

Regular Expressions are comprised of:

* Some regular characters that can stand for themselves like 'a'
* Metacharacters that can stand for a regular expression operation

Here is a chart on metacharacters:

| `Metacharacter` | `Description` |
| --- | --- |
| `^` | Matches the starting position within the string. In line-based tools, it matches the starting position of any line. |
| `.` | Matches any single character (many applications exclude newlines, and exactly which characters are considered newlines is flavor-, character-encoding-, and platform-specific, but it is safe to assume that the line feed character is included). Within POSIX bracket expressions, the dot character matches a literal dot. For example, a.c matches "abc", etc., but [a.c] matches only "a", ".", or "c". |
| `[]` | A bracket expression. Matches a single character that is contained within the brackets. For example, [abc] matches "a", "b", or "c". [a-z] specifies a range which matches any lowercase letter from "a" to "z". These forms can be mixed: [abcx-z] matches "a", "b", "c", "x", "y", or "z", as does [a-cx-z]. The - character is treated as a literal character if it is the last or the first (after the ^, if present) character within the brackets: [abc-], [-abc]. Note that backslash escapes are not allowed. The ] character can be included in a bracket expression if it is the first (after the ^) character: []abc]. |
| `[^]` | Matches a single character that is not contained within the brackets. For example, [^abc] matches any character other than "a", "b", or "c". [^a-z] matches any single character that is not a lowercase letter from "a" to "z". Likewise, literal characters and ranges can be mixed. |
| `$` | Matches the ending position of the string or the position just before a string-ending newline. In line-based tools, it matches the ending position of any line. |
| `()` | Defines a marked subexpression. The string matched within the parentheses can be recalled later (see the next entry, \n). A marked subexpression is also called a block or capturing group. BRE mode requires \( \). |
| `\n` | Matches what the nth marked subexpression matched, where n is a digit from 1 to 9. This construct is vaguely defined in the POSIX.2 standard. Some tools allow referencing more than nine capturing groups. |
| `*` | Matches the preceding element zero or more times. For example, ab*c matches "ac", "abc", "abbbc", etc. [xyz]* matches "", "x", "y", "z", "zx", "zyx", "xyzzy", and so on. (ab)* matches "", "ab", "abab", "ababab", and so on. |
| `{m, n}` | Matches the preceding element at least m and not more than n times. For example, a{3,5} matches only "aaa", "aaaa", and "aaaaa". This is not found in a few older instances of regexes. BRE mode requires \{m,n\}. |

* Expressions that denote categories of a regular expression

#### History and Types of Regular Expressions

> Regular expressions originated in 1956, when mathematician <NAME> described regular languages using his mathematical notation called regular sets. These arose in theoretical computer science, in the subfields of automata theory (models of computation) and the description and classification of formal languages. Other early implementations of pattern matching include the [SNOBOL language](https://en.wikipedia.org/wiki/SNOBOL), which did not use regular expressions, but instead its own pattern matching constructs.

* Different Unix tools have used different Regular Expression types
* This reflects the influence and interests in AT&T Research Labs (Kernighan, Ritchie, etc)

#### Unix Tools that use Regular Expressions

Unix Tools that use Regexes:

* grep

* sed

* awk

* vim

* emacs

#### Basic Regular Expressions

BRE (Basic Regular Expressions)

BRE . Although POSIX.2 leaves some implementation specifics undefined, BRE and ERE provide a "standard" which has since been adopted as the default syntax of many tools, where the choice of BRE or ERE modes is usually a supported option. For example, GNU grep has the following options: "grep -E" for ERE, and "grep -G" for BRE (the default), and "grep -P" for Perl regexes.

###### Examples of Regular Expressions

Here are some examples from the [Regular Expressions Wikipedia Page](https://en.wikipedia.org/wiki/Regular_expression):

* `.at` matches any three-character string ending with "at", including "hat", "cat", and "bat".

* `[hc]at` matches "hat" and "cat".

* `[^b]at` matches all strings matched by .at except "bat".

* `[^hc]at` matches all strings matched by .at other than "hat" and "cat".

* `^[hc]at` matches "hat" and "cat", but only at the beginning of the string or line.

* `[hc]at$` matches "hat" and "cat", but only at the end of the string or line.

* `\[.\]` matches any single character surrounded by "[" and "]" since the brackets are escaped, for example: "[a]" and "[b]".

* `s.*` matches s followed by zero or more characters, for example: "s" and "saw" and "seed".

#### Extended Regular Expressions

* ERE (Extended Regular Expressions) adds `?`, `+`, and `|`, and EREs removes the need to escape the metacharacters `( )` and `{ }`, which are required in BREs.

* Furthermore, as long as the POSIX standard syntax for regexes is adhered to, there can be, and often is, additional syntax to serve specific (yet POSIX compliant) applications

* The meaning of metacharacters escaped with a backslash is reversed for some characters in the POSIX Extended Regular Expression (ERE) syntax.

* With this syntax, a backslash causes the metacharacter to be treated as a literal character.

* So, for example, `\( \)` is now `( )` and `\{ \}` is now `{ }`.

* Additionally, support is removed for \n backreferences and the following metacharacters are added:

| `Metacharacter`	| `Description` |
| --- | --- |
| `?` |	Matches the preceding element zero or one time. For example, ab?c matches only "ac" or "abc". |
| `+`	| Matches the preceding element one or more times. For example, ab+c matches "abc", "abbc", "abbbc", and so on, but not "ac". |
| <code>&#124;</code>	| The choice (also known as alternation or set union) operator matches either the expression before or the expression after the operator. For example, `abc\|def` matches "abc" or "def". |

###### Examples of EREs

* [hc]?at matches "hat", "cat", and "at".

* [hc]*at matches "hat", "cat", "hhat", "chat", "hcat", "cchchat", "at", and so on.

* [hc]+at matches "hat", "cat", "hhat", "chat", "hcat", "cchchat", and so on, but not "at".

* cat|dog matches "cat" or "dog".

#### Family of Regular Expression Tools

###### Grep

Different `Grep` programs:

1. The `grep` utility searches any given input files, selecting lines that match one or more patterns.
2. The `egrep` interprets pattern as an extended regular expression
  1. Force regular `grep` to behave like `egrep` with `-E` flag.
{'fraction_non_alphanumeric': 0.11292338829692243, 'fraction_numerical': 0.0019048752901958449, 'mean_word_length': 4.626255860683188, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 11, 'https://': 6, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4588347', 'n_tokens_mistral': 4830, 'n_tokens_neox': 4568, 'n_words': 2211}