Assignments‎ > ‎

Regular expressions

DUE: February 29, 2012 by 10am (submission on Blackboard)


Your submission will be a zipped up file with your implementations for each problem in it. Submit it on Blackboard as <lastname>_<firstname> Please follow the same instructions as for HW1 with respect how to package up the solutions before submission.

If you don’t absolutely need to have words on paper, don’t print this homework description out -- it has a lot of example output that makes it lengthy, and it will be easier to do some cutting and pasting etc right from the webpage.

1. Finding syllables
This problem uses the same text passage from H.G.Wells, The War of the Worlds (from Project Gutenberg, that was used in homework 2:



For this problem, you will perform series of manipulations and operations on this passage. Modify the stub program syllables.scala, looking at the comments in it for guidance. See the output at the end of this question for guidance on what your program’s output should be.


For this part, use a regular expression on the raw text String, and output the number of one syllable words. You should express the above definition of a vowel pattern, and use \b to indicate a word boundary. Don’t forget to handle capitalization (so “cat”, “Cat” and “CAT” are all one syllable words.) Also, remember that “new-comers” does indeed contain a one-syllable word since - is a boundary.


(b) Now, identify how many one syllable words (using the same definition as for (a) above) there are in the passage, but this time working with the passage as a List of Strings split on whitespace. You should get the same answer as for (a).


$ scala syllables.scala

Part (a)
Number of one syllable words on full String: ###

Part (b)
Number of one syllable words on split String: ###

2. Basic regular expressions

3. Regular expressions for capturing date expressions
  • September 7, 2011
  • 09-07-2011
  • 9/7/2011
  • the 7th of September, 2011


For this problem, modify the stub program dates.scala.

  • Y is a number 1900 to 2099





4. Finding names in the works of Mark Twain
This problem involves working with the Entire Works of Mark Twain from Project Gutenberg, which is available as twain.txt in the homework package.

(a) The name of the file containing the works of Twain should be entered as the first argument on the command line, and your program should read the contents of that file and assign it to the variable book. Notice that there is material about Project Gutenberg at the beginning and end of each file, and that there are consistent strings indicating where the actual text of a book starts and ends. Write a regular expression JustTextRE that matches these delimiters and captures the text in between them (as a regex group). Apply this regular expression to the text and obtain the matched text such that you can save it to a variable text.

Tip: you should print out the text and verify that it is correct for both files, though you should turn this output off once you’ve verified it is working.

Tip: you'll need to preface your regular expression with "(?s)" so that the "any" character '.' matches newlines.

(b) Write a regular expression for identifying names with titles in the text like "Mr. John Brown", "Mrs. Smith" and “Prof. William G. Jones”. You should handle Dr, Mr., Mrs., Miss, Ms., Prof. and Rev. Apply it to the text and print out each match to standard output. You’ll need to use “(?s)” again.

Hint: Check the output you are getting, and make sure you aren’t getting new lines between a title and the name. If you are, fix it -- easily done by mapping a fixer function over the match results.

(c) Use names.scala to process twain.txt, piping its output directly to the Unix utilities we looked at in class to obtain a list of all the names and their counts in reverse sorted order.  See the slides on Unix pipelines for help. Save the output as names_twain.txt and include it with your submission.

Tip: use a Unix redirect to send the output of the counting and sorting Unix pipeline to a file.

(d) In hw3_answers.txt, provide the ten most common names as output in part (c). Also, state what the count of “Mr. Twain” is.

(e) Discuss some of the obvious errors and why you think they happened. Make sure to note the error “Rev. Dr” being recognized as a name and explain why it happened. (Extra credit for writing a regex that parses such examples correctly.)

5. Extracting articles from the Federalist Papers
This problem involves working with the Federalist Papers from Project Gutenberg, which is available as the file federalist.txt in the homework package. You'll modify the stub file articles.scala. It will be considerably more challenging than any of the things you’ve done so far, and is the first step toward actually writing programs of the sort you will need to write when you are working with your own texts and problems. It will also form the basis for your work on homework 4, as you’ll extend this solution to extract the values from these texts to create the input for clustering algorithms to explore authorship in the Federalist Papers.

(a) The name of the file containing the Federalist Papers should be entered as the first argument on the command line, and your program should read the contents of that file and assign it to the variable book.  Use the regular expression JustTextRE from 4(a) to pull out the text of the Federalist papers (just copy your solution to articles.scala). Then, use the split method on strings to obtain an Array of the raw articles, which you can do by splitting on the lines that have the form “FEDERALIST. No.”.  Here’s an example that has a similar structure to it -- the key thing is to realize that the argument to split is a regular expression.

scala> val dialogue = "A simple dialogue. A: Hi. B: Hello. A: So, how are you? B: Fine. And you? A: Great. B: Goodbye. A: See you."


scala> dialogue.split("[AB]:")

res0: Array[java.lang.String] = Array("A simple dialogue. ", " Hi. ", " Hello. ", " So, how are you? ", " Fine. And you? ", " Great. ", " Goodbye. ", " See you.")

Assign the Array obtained by doing the split to the variable rawArticles, and then print the length of this Array. It should have 87 elements.

(b) There are 85 articles in the Federalist Papers. Find out why part (a) produces 87 elements and write the reasons down in hw3_answers.txt.

(c) The articles have a lot of information in a semi-structured format. For example, the beginning portion of article 34 has the article id, followed by the title, then the publication venue, the date, the author, the addressee, and then the text itself.


The Same Subject Continued

(Concerning the General Power of Taxation)

From the New York Packet.

Friday, January 4, 1788.


To the People of the State of New York:

I FLATTER myself it has been clearly shown in my last number

that the particular States, under the proposed Constitution, would

have COEQUAL authority with the Union in the article of revenue,


However, there are some minor variations in how these various elements are expressed (including at times being missing). Your job is to convert this semi-regular format into a Map from attributes like 'author', 'title', 'venue', 'date', ‘addressee’ and 'text' to their values. You will do this with a regular expression ArticleRE that you will design to match the elements of each article. With that regular expression, convert the Array[String] variable rawArticles into an Array[Map[String,String]] variable called articles.  

Notes and tips:
  • It will be useful to look at the example output in part (d) before attempting this part.
  • You should create the articles Array by flat mapping over rawArticles, using ArticleRE to return a Some(Map(...)) when it matches and a None when it doesn’t. Note that ArticleRE must match every one of the articles.
  • While building the ArticleRE regular expression, start by matching the id and letting the remaining material be matched with .+, calling the latter the “text” (even though initially it will contain the title and more). Then extend it to the title, then to the venue, and so on, making sure that each new element you add doesn’t start “unmatching” articles. (Check this by printing the length of articles, which should be 86.)
  • Obviously, you’ll need to use capture groups to extract the values that will populate the Map representing each article. Some of the values will be empty.
  • There are some very minor variations that are likely to cause you headaches. This is a real text, so this is representative of the actual sorts of semi-regular patterns you’ll need to deal with in the wild, so look at this as necessary character building on your way to regex ninja-hood. You can minimize headaches by following the incremental regex building strategy outlined above.
  • Make sure to capture the date on article 42 correctly.
  • When you add the values to the Map, you should remove newlines from the venue, title, date and author. You can use the replaceAll method on Strings for this.
A note on optionality and capture groups that will matter for your solution -- note the difference in the following examples:

scala> val OptionOutsideRE = """(a)(b)?(c)""".r

OptionOutsideRE: scala.util.matching.Regex = (a)(b)?(c)

scala> val OptionOutsideRE(x,y,z) = "abc"

x: String = a

y: String = b

z: String = c

scala> val OptionOutsideRE(x,y,z) = "ac"

x: String = a

y: String = null

z: String = c

scala> val OptionInsideRE = """(a)(b?)(c)""".r

OptionInsideRE: scala.util.matching.Regex = (a)(b?)(c)

scala> val OptionInsideRE(x,y,z) = "abc"

x: String = a

y: String = b

z: String = c

scala> val OptionInsideRE(x,y,z) = "ac"

x: String = a

y: String = ""

z: String = c

You’ll want to use the “inside” type so that you get empty strings rather than nulls when an optional element (like a date) is missing from a given article. Note that at times you’ll need to group things, so to change the regex (a)(bc)?(d) to an “inside” form, you need to use the ignore operator for capture groups, e.g. (a)((?:bc)?)(d). Make sure you understand what is going on with this, and if not, ask me right away.

Another note on building a large regular expression: you can and should break it up over multiple lines. Here’s a simple example of how you can do that:

val LowercaseThenDigitRE = (

 """([a-z]+)""" + // Get a series of lowercase characters

 """\s(\d+)"""     // Get a series of digits


For this problem, I recommend having the portion of the regular expression that is responsible for each element on its own line. Add comments to remind yourself what each does.

(d) Write code that loops over the articles Array, and for each element, prints out its keys and values in the format given below. For the text value, you should only print the first 200 characters (see the substring method for Strings).

Example output:

$ scala articles.scala federalist.txt

id: 1

title: General Introduction

author: HAMILTON

venue: For the Independent Journal.


addressee: To the People of the State of New York:


AFTER an unequivocal experience of the inefficacy of the

subsisting federal government, you are called upon to deliberate on

a new Constitution for the United States of America. The subject

speaks i

id: 2

title: Concerning Dangers from Foreign Force and Influence

author: JAY

venue: For the Independent Journal.


addressee: To the People of the State of New York:


WHEN the people of America reflect that they are now called upon


the most important that ever engaged their attention, the proprie

<many articles skipped in this output>

id: 15

title: The Insufficiency of the Present Confederation to Preserve the Union

author: HAMILTON

venue: For the Independent Journal.


addressee: To the People of the State of New York.




light, the importance of Union to your political safety and

happiness. I

id: 16

title: The Same Subject Continued (The Insufficiency of the Present Confederation to Preserve the Union)

author: HAMILTON

venue: From the New York Packet.

date: Tuesday, December 4, 1787.

addressee: To the People of the State of New York:


THE tendency of the principle of legislation for States, or

communities, in their political capacities, as it has been

exemplified by the experiment we have made of it, is equally

attested by the ev

<many articles skipped in this output>

id: 85

title: Concluding Remarks

author: HAMILTON

venue: From MCLEAN's Edition, New York.


addressee: To the People of the State of New York:


ACCORDING to the formal division of the subject of these papers,


discussion two points: "the analogy of the proposed government t

Note that in the actual output, the title for article 16 does not wrap to the next line (which could happen above if your browser window isn't wide enough), and yours also should not wrap.

6. Feedback
(a) How long did this homework take you?

(b) Do you have any suggestions?

(c) Do you have any complaints?

7. EXTRA: Another dataset?
Do you have another data set that you are interested in working with? If so, try working with it to get it into a similarly structured form as was done for the previous problem. Note that your inputs might look quite different -- for example, you might have each document in its own file, in which case you’ll need to learn about listing the files in a directory using Scala code, iterating over and opening those files, etc. Note that you by no means need to stick to English, nor do you need to stick with nicely edited text (messy tweets would be fine). Feel free to ask for suggestions or help.

Copyright 2012 Jason Baldridge



Jason Baldridge,
Feb 15, 2012, 9:48 PM