Copyright © 2007-2021
Robert W. Hasker

CS 3040 - Note 2
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, aaaaaa, ... }

  • 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)... but this doesn't work
  •    or +(0|1)*|-(0|1)*|(0|1)* - works, but repetitive
  • 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
  • sequence (xy) is next highest
  • choice (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 string
  • $: anchor to end of string
    • So "ab$" would match the strings "qab" and "ab" but not "abc", "axb", or "abb"
  • [^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
    • In [^[^x]], only the outer brackets and the first ^ and ] have special meaning; this RE is incorrect because it has too many closing brackets, and if you delete the last character you get the same as [^x[^] which would mean all but the x, circumflex, and left bracket.

Regular Expressions in ANTLR

• General rules:

          VARIABLE: regular expression ;
  

• Any text to be matched: in quotes

          SALUTATION: 'Hello';
  

• With alternative:

          SALUTATION: 'Hello' | 'Hi' | 'Greetings,';
  

• Dot: any character

          ANY: .;
  

• Parens: group
• Range: ..

          DIGIT: '0'..'9';
          LETTER: ('A'..'Z') | ('a'..'z');
  

• Range with other characters:

          IDENTIFIER_CHARACTER: ('a'..'z') | ('A'..'Z') | ('0'..'9') | '_';
  

• Repetition: +, *:

          NUMBER: ('0'..'9')+;
          ID: ('a'..'z')+('0'..'9')*;
  

• Optional:

          MONTH: '1'?('0'..'9');
  

• Negation:

          NON_DIGIT: ~('0'..'9');
  

Exercises using Standard REs

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

Exercises using ANTLR REs

• C++ comments in ANTLR
• Strings in C++

Assignment 1: regular expression tutorial

• See assignment 1 writeup

So now you can say, stand back!

In-class Exercises

Develop regular expressions for each of the following:

1. Pascal-style strings ("abc""xyz")
2. C-style strings ("asdf\"asf")
3. Floating-point numbers: 1.5e-23, 234e12, 0.54321
4. C-style comments: /* ... */