DTM powerpoint 3

• Regular expressions are a toolset rooted in a fundamental theoretical concept.
• Regular expressions describe patterns
• /st.k/ describes strings starting with "st", ending with "k", and having one symbol in between
• Example strings include stak, stbk, and stck
• Patterns depend on the symbols

Regular Expression Syntax

• Use / to start and end symbols
• Simple strings of characters can be used, such as /c/, /A100/, /natural language/, and /30 years!/

Disjunction

• Ordinary disjunction examples: /devoured|ate/ and /famil(y|ies)/
• Character classes are specified using square brackets
• /[Ss]pam/ matches Spam or spam
• /[Tt]he/ matches The or the
• /bec[oa]me/ matches become or became
• Ranges are short ways to write disjunctions
• [A-Z] matches uppercase letters
• [a-z] matches lowercase letters
• [0-9] matches digits
• Character classes can be combined
• [A-Za-z] matches any letter
• [A-Za-z0-9] matches alphanumeric characters
• Sets can be negated with ^
• [^Ss] matches neither S nor s
• [^A-Z] matches not an uppercase letter
• [^A-Za-z0-9] matches not an alphanumeric character
• Shorter ranges examples:
• \d matches any digit
• \s matches whitespace
• \w matches alphanumeric characters, including underscore
• Negations are in uppercase
• \D matches non-digits
• \S matches non-whitespace
• \W matches non-alphanumeric characters

Optionality

• '?' indicates an optional character
• /colou?r/ matches color or colour
• Use parentheses to list optional multi-character sequences
• /hello(oooooo)?/ matches hello or hellooooooo

Kleene Star

• Kleene * matches zero or more occurrences
• /a*/ allows zero or any number of a's in a row.
• Example:/abaab*a/
• Valid sequences include: abaaba, abaaaaaaaba, ba, baa, aabaaaabbbbbbbb, abba

Kleene Plus

• Kleene + matches one or more occurrences
• /a+/ accepts one or more a's in a row
• Example: /abaab+a/
• Acceptable strings include: abaaba, abaaaaaaaba, ba, baa, baba
• [0-9]* years and [0-9]+ dollars are more examples

Wildcard Character

• Use '.' to match anything
• Example: /beg.n/ (begin, began, begqn, beg!n, etc.)
• The most general regular expression is /.*/

Scope

• Curly brackets {} match a fixed length
• /hello{3}/ matches hellooo
• Default is 'greedy' matching
• /ab.*d/ in abcdaaad matches abcdaaad
• Use '?' for minimal matching
• /ab.*?d/ in abcdaaad matches abcd

Anchors

• Regular expressions can be anchored to the start or end of a string
• ^ marks the start of a string
• $ marks the end of a string
• /^abc/ anchors at the start
• /xyz$/ anchors at the end

Special Characters

• Metacharacters have special meanings: ^ $ * + ? { } [ ] \ | ( )
• These characters require escaping with \ when searching

Regular Expression Applications

• Regular expressions are used in many search scenarios, including document retrieval, web search, and NER
• Utilized in word processing for spelling variants, errors, and computation of frequencies from corpora
• Many Unix tools, editors, and programming languages incorporate regular expressions
• Implementations are efficient for searching large text files
• Tools and languages differ in the exact syntax

Grep

• Program for searching text files using regular expressions
• Standard on Unix, Linux, and Mac OSX, also available for Windows
• egrep is an extended version to support the full set of operators

Grep Examples

• 'and' in f.txt matches and, Ayn Rand, and Candy
• 'the year [0-9][0-9][0-9][0-9]' in f.txt matches the year 1776, the year 1812, and the year 2001
• 'why?' in f.txt matches why?, while 'why?' matches why
• 'couch|sofa' in f.txt matches couch or sofa
• 'un(interest|excit)ing' in f.txt matches uninteresting or unexciting
• 'o.e' in f.txt matches ore, one, and ole
• 'a*rgh' in f.txt matches argh, aargh, and aaargh
• 'sha(la)*' in f.txt matches sha, shala, and shalala
• 'john+y' in f.txt matches johny and johnny, but not johy
• 'joh?n' in f.txt matches jon and john

Named Entity Recognition (NER)

• The challenge is to identify names, dates, addresses, etc. in a text
• Relies on formulating smart regular expressions
• The goal is to maximize hits while minimizing false alarms

Exam Practice Questions

• Need to write regular expressions that match specific words
• Understanding regular experessions to identify patterns in language
• Apply regular expressions for language variants