Copyright © 2007-2020
Robert W. Hasker

SE 3800 - Note 6
Stand Back!

The Problem

• Problem: how would I search for all of the uses of "int" in a program?
  • issue: the text can appear in many contexts
  • Can't just search for "int" - would pick up "pint" or "int_32".
• How to find all letters titled "Dear John" in the Enron Email Dataset
  • 423 megabytes of email, 200,399 messages, 158 users
  • What else might you want to find in this dataset
  • Find messages containing "exxon" and "shipment" - but what about shipping, shipped, and how to capitalize exxon anyways?
• 2013 Computer World UK article: Boeing 787s to create half a terabyte of data per flight, says Virgin Atlantic
  • Sensor readings frome engines, communication messages, routes
  • Might want to describe sequences of events like "5 misfires followed by an increase in fuel flow"
  • Could program these, but may need to allow exploration

Solution: regular expressions

• a way to define sets of strings

  Regular Expression	Set
  a	{ a }
  b	{ b }
  ab    -- sequence	{ ab }
  c | d    -- choice	{ c, d }
  a (b | c)	{ ab, ac }
  a5    -- repetition	{ aaaaa }
  a*	{ ε, a, aa, aaa, aaaa, aaaaa, ... }

  • a, b, c: simple characters; will do more realistic examples later
  • the ... above is dangerous; don't really know what follows next simply for the same reason we don't know what's next in { 5, 8, 11, ... }
  • ε - the empty string
  • 5th letter greek alphabet: α, β, γ, δ, ε ...
  • * often known as "Kleene Closure"

  More examples:

• "dear" in mixed case
• string of 1's followed by string of 0's
  • eg: 1111000, 1, 0
• example: unsigned binary numbers
• example: binary number with a binary point: 1101.001
• What does this give us?
  • sets of strings
  • language: set of strings specified by some RE
• How is it useful?
  • a way to provide more flexible search for strings
  • example: egrep:

            cd web/3800/notes
            egrep '(S|s)(Y|y)(N|n)(T|t)(A|a)(X|x)' *.html
    

    or at the Windows Command prompt (with GOW installed):

            c:
            cd web\3800\notes
            egrep "(S|s)(Y|y)(N|n)(T|t)(A|a)(X|x)" *.html
    

    Matches Syntax, SYNTAX, sYntax, etc.
• Suppose we want signed binary numbers
  • Could write (-1|-0|+1|+0|1|0)(1|0)* - works, but repetitive
  •    or +(0|1)*|-(0|1)*|(0|1)* - doesn't work!
  • Could write (-|+|)(0|1)* - not very definite
  • Solution: introduce ε to represent the empty string, also need to have at least one binary digit:

            (+|-|ε)(0|1)(0|1)*
    

    • Why do I say "the" empty string?
  • Example: aba w/ optional b: a (b|ε) a
  • Example: pattern to match both "for" and "foreach", allowing mixed case
• Precendence:
  • Use parentheses to group items
  • * (x*) has the highest precedence
  • concatenation (xy) is next highest
  • alternation (x|y) has the lowest precedence

Examples to try

• strings of 0's and 1's with at least one 1
• strings of a's and b's with at least 3 consecutive a's in them
• strings of a's and b's with at least 3 a's in them (anywhere)
• strings of a's and b's with no doubled a's or b's
• strings of a's and b's with every pair of a's separated by at least one b

How to write regular expressions?

• Like writing code: sequence, if, repetition
• Can translate from REs to code:
  • Assume input is the next character in the input stream; advance reads the next character, changing input; and error is used to throw an exception when reach an error
  • ab:

            if input != a
              error
            advance
            if input != b
              error
            advance
    

  • a^*: equivalent to

            while input == a
              advance
    

  • a | b:

            if input == a or input == b
              advance
            else
              error
    

  • Example: 0*1(0|1)*:

            while input == 0
              advance
            if input != 1
              error
            advance
            while input == 0 or input == 1
              advance
    

Shorthand

• (S|s)(Y|y)(N|n)(T|t)(A|a)(X|x) is tedious
• In some cases there's a switch; eg: -i on egrep ignores case
• More general solution: (A|a) can be written [Aa]
• RE: [Ss][Yy][Nn][Tt][Aa][Xx]
• Digits: [0123456789]
• Ranges: [a-zA-Z0-9]
• Limitations of ranges: ASCII assumption
• Grep, most regular expression tools add a number of shortcuts and extensions:
  • .: matches anything except a newline
  • ?: previous group is optional
  • \: escape special meaning of next character
    • Searching for array expressions in code:

              egrep \[[0-9a-zA-Z_]*\] *.cpp
        

  • \\: match a backslash
  • ^: anchor to start of line
  • $: anchor to end of line
  • [^xyz]: all but x, y or z (so . is [^\n]
    • Note [^xyz]. would match "ay" since the first letter is not an x, y, or z, and [^anythingatall] matches just one letter, not some string

Regular Expressions in Cucumber

• Cucumber-specific abbreviations:
  • \d: any digit
  • \w: any word character: [0-9A-Za-z_]
  • \s: any whitespace
• Additional items of note
  • \b: word boundary: \brun\b
  • \D: any non-digit, that is: [^0-9]
  • \W: non-word characters, that is: [^0-9A-Za-z_]
  • \S: non-spaces
• See Cucumber Regular Expressions Cheat Sheet from here
• Test regular expressions on rubular.com

Ruby example

• wordlines.rb: count lines with just words in them
• Example: ruby wordlines.rb *.html

Exercises

• lines starting with the word class
• C++ comments, both // and /*..*/ styles

So now you can say, stand back!