CS 1206: Assignment 3

Due Friday, February 20, by 5pm

100 Points

1. Regular Expressions: What Strings Match an RE?

Consider the following text, taken from the manual page for a command called "flip" (if you would like to use flip, you can find it compiled for FreeBSD along with it's man page in the directory /home/faculty/sedwards/bin on the lab machines):

Flip is a file interchange program that converts text file
formats between **IX and MS-DOS.  It converts lines ending
with carriage-return (CR) and linefeed (LF) to lines ending
with just linefeed, or vice versa.

If we refer to these lines by number (1 through 4), then which line(s), if any, match each of the following REs?

/file/
/^f/
/^[Ff]/
/./
/ */
/line$s$?/
/convert|change/
/[Cc].*[Rr]/
/text.*file/
/[a-z][a-z]*ing/

Here, a line matches if there is at least one substring in the line that matches the given RE. Also, in the REs above "(" and ")" characters used alone match themselves, while "$" and "$" are used for grouping (these are the rules that ex/vi uses, while egrep uses the opposite conventions). All of these REs are also case-sensitive.

If you are unsure about a question, feel free to try out a few experiments with egrep or with the "search" command / in vi. Remember that neither of these programs expect you to enter the "/" delimiters when you type the RE for which to search, and that both use case sensitive searches by default.

2. Regular Expressions: What Strings Match an RE? (cont.)

For the next set of REs, identify all substrings that match each RE (without crossing lines, of course) in the four lines listed in Section 1. You can do this by listing all the matched strings. Remember that REs match the longest possible string. For example, the RE /(.*)/ matches the following string(s):

(CR) and linefeed (LF)

Find all possible matches for each of the following (egrep) REs:

/[Ff][^ ]*/
/line[a-z]*/
/c.*r/
/[a-z]*[e.]$/
/\*+/

3. Regular Expressions: Writing REs

Now it is your turn to write some REs to match specific text fragments. For each of the following questions, write an RE that matches the specified text (including but not limited to all of the underlined phrases in each example) and no other text in the given line, assuming that your RE is intended to be used with grep.

Matching "hello", "hi", or "howdy":

hello, there.  or is "hi" or "howdy" more to your liking?
-----                 --      -----

Matching "the", regardless of case:

The quick brown fox jumps over the lazy dog.
---                            ---

The last word in a sentence:

How many sentences are here? There are two.  No, three!
                       -----           ----      ------

A social security number:

The number 045-35-2344 is a random SSN.
           -----------

A word with five or more letters:

This sentence does not have many long words.
     --------                         -----

Any word beginning with the root "reus":

reusable software is software that was designed to be reused.
--------                                              ------

An entire sentence that ends in a period:

Does this sentence end in a period?  This one does.
                                     --------------

Any sequence beginning with "artificial" and ending with "intelligence":

Politicians can act artificial, but do they have intelligence?
                    -----------------------------------------

Any of "computer", "computers", or "computing":

computer science is the study of computing, and how computers work.
--------                         ---------          ---------

Matching any phrase of exactly three words separated by white space:

This is a short sentence.
---------
     ----------
        ----------------

For these questions, you may not simply list an underlined phrase itself--you must use at least one special character in your answer.

Submitting Your Answers

You are to hand in your assignment by sending an email message to the address cs1206@ei.cs.vt.edu. To receive credit, your mail message must be received by this account by the time and date listed above. It is your responsibility to successfully submit your assignment via email (remember that you will receive an auto-reply by the system when your message has been received successfully). Also, send yourself a copy for future reference. The messsage must be a plain ASCII text file, with no attachments, and in exactly the format defined below. Do not insert any extra notes or explanations.

The body of your message must be a plain ASCII text file that contains the following:

A subject line containing "DHH HW3", which indicates your lab section. Here, the D should be replaced by the day of your lab section (M for Monday, T for Tuesday, W for Wednesday, H for Thursday, and F for Friday), and HH should be replaced by the time of your lab section (8, 9, 10, or 11). If you do not include your lab section information in your subject line, you will lose points.
Your PID.
Your name.
Your student ID number.
Answers to all 25 of the above questions on REs:
- For each of the 10 questions in Section 1, give the problem number followed by the line number(s) for which lines match each RE (e.g., 4. 1,3,4). Use one line per problem.
- For each of the 5 questions in Section 2, give the problem number (on a line by itself) followed by all the possible matched strings, one per line, terminated by a blank line.
- For each of the 10 questions in Section 3, give the problem number followed by the RE you came up with (e.g, 16. h[eio]*).
Do not attach files produced by word processors or other programs---send plain ASCII text only.

L. T. Watson <ltw@cs.vt.edu>

Last modified: Thu Feb 19 12:01:08 EST 1998