4/17/26
Motivation
• We often want to match a set of strings against a
pattern.
Regular Expressions • E.g., what are the words that end in “-ing”?
• Python provides a module that implements
regular expressions: import re
CMPUT 331 • Regular expressions are extremely useful and
powerful tools for programming in general.
• We will learn how to use them on the decryption
task.
1 2
Formal Grammars Regular Expressions
• Used in formal language • A regular expression is a sequence of
theory, computer science, and
characters that define a search pattern.
linguistics
• Describe which strings are valid • The simplest search pattern is the exact string
according to the language’s one is searching, like /woodchuck/.
syntax The Chomsky hierarchy
• Regular expression operators provide ways to
• Defined as a set of production
rules for rewriting strings, concisely specify a set of strings.
starting with a “start symbol” • For example, the set containing the three
• Automaton = computing device strings "Handel", "Händel", and "Haendel" can
be specified by the pattern /H[ä|ae?]ndel/
3 4
RE basic operators RE anchors
• The dot operator matches any char except ‘\n’
– be.t matches best, belt, beet, be3t, … • The caret anchor matches the start of the
• The star operator matches 0 or more repetitions string
of the previous character – ^be matches be, bet, beat (but not abe)
– be*t matches bt, bet, beet, beeet, ….
• The dollar anchor matches the end of the
• The square brackets operator matches any one
character listed within the square brackets: string
– be[ls]t matches belt, best – be$ matches be, abe, cube (but not bee)
– be[l-o]t matches belt, bemt, bent, beot
• They are often used to delimit the pattern
• The caret matches the complement of a set:
– be[^0-9]t matches belt, best, be#t (but not be4t) – ^.*be.*$ matches all strings that contain be
– be[^xyz]t matches belt, be5t (but not bext, beyt, bezt)
5 6
1
4/17/26
RE advanced operators Regular Expression Summary
• The plus operator matches 1 or more repetitions Regular Expression Interpretation
of the previous character
. match any character (wildcard)
– be+t matches bet, beet, beeet, …
• The question mark operator matches 0 or 1 [abc] match a or b or c
repetitions of the previous character [^abc] match any character other than
– bee?t matches bet, beet
[abc]+ match one or more occurrences
• The | operator is an “or” operator:
– hello|Hello matches hello, Hello [abc]* match zero or more occurrences
– a+|b+ matches a, b, aa, bb, aaa, bbb, …
[abc]? match zero or one occurrences
– ab+|ba+ matches ab, abb, abbb, …, ba, baa, baaa, …
(regex) create a capture group
7 8
RE module functions Matching words against patterns
• matchObj = [Link](pattern, string) - returns a def checkWord(regex):
match object if it finds pattern in string (or None). resList = []
• gList = [Link]() – returns a list of all
wordFile = open('[Link]')
capture groups matched.
for line in wordFile:
• newstring = [Link](pattern, repl, string) – like
replace but applies to all occurrences of pattern. if [Link](regex,line[:-1]):
• sList = [Link](pattern, string) – returns a list of [Link](line[:-1])
all substrings that match pattern in string. return resList
9 10
• Write a function that can extract the host
name from a URL.
• The host name is the part of the URL that
comes after http:// but before the next /
def getHost(url):
regex = ‘[Link]
g = [Link](regex, url)
if g:
return [Link](1)
else:
return None
11