\documentclass{article}
\usepackage{amstext}
\def\reg{\setbox0\hbox{$\mathchar"20D$}%
\hbox to 0pt{\hbox to \wd0{\hfill\,\rm R\hfill}\hss}%
$\mathchar"20D$}\usepackage[latin1]{inputenc}
\title {Lab 3: Regular expressions. Shell Script.}
\date{}
\begin{document}

\maketitle

\section {Introduction}

\begin{itemize}

\item {\bf Topics:}

\begin{itemize}
\item  Regular expressions 

\begin{itemize}
\item  basic rules (see also course notes and UNIX in a nutshell, ch 6)
\item  \{\} in more details
\item  examples
\end{itemize}
\item  Use of REs in various UNIX applications:

\begin{itemize}
\item  grep, egrep
\item  vi, 
\item sed, 
\item emacs
\end{itemize}

\item  short shell script

\begin{itemize}
\item  variables
\item  return value  of each UNIX command
\item  if
\item  for
\item  case
\end{itemize}

\end{itemize}

\end {itemize}

\section{Regular Expressions (RE)}

{\bf RE} is a way of describing a set of  strings without having to list 
all the strings in your set. 
RE contains instructions on how to match the pattern. 
This is accomplished by using plain text and special tokens. 
A sample RE may look like:\\
\hspace*{2cm}   {\em hello}\\
This matches any bit of text which contain {\em hello}.  
It will not match {\em "Hello"} in {\em "Hello, world"} since REs are case sensitive. 
REs may also contain tokens. 
These tokens are used in place of other text. 
For example {\em hel*o} is a RE, where {\em *} is a token. 
As we will see later, {\em *} means 0 or more repetitions of the previous character.
Our RE will match {\em heo}, as well as {\em helo}, {\em hello} or {\em hellllllllo}.
   
REs are used by many UNIX  programs ({\em grep, egrep, sed, perl, vi, emacs } etc.).
Tokens may vary from program to program and you should refer to manual for 
the program to see, which tokens are supported. 
However the following  table  gives the basic rules used by most programs:

\subsection{Rules for forming (basic) RE:}

\hspace*{0.3cm}{\bf 1.  A non-special character is a RE matching that character.}\\
{\bf Example:}\\ 
\hspace*{2cm}{\em   a}\\
\hspace*{2cm}{\em   6}\\ 
\hspace*{2cm}{\em  \%}\\

Special characters are:  \\
\hspace*{2cm}{\em               "$.$"}\hspace*{1cm}    period\\
\hspace*{2cm}{\em             "$*$" }\hspace*{1cm}     asterisk\\
\hspace*{2cm}{\em  "$[$"         }\hspace*{1cm} left square bracket\\
\hspace*{2cm}{\em  "$\backslash$"}\hspace*{1cm}    backslash\\
\hspace*{2cm}{\em  " $\hat{ }$"        }\hspace*{1cm}   caret\\
\hspace*{2cm}{\em    "\$"       }\hspace*{1cm}    dollar sign\\

Note:
A special character used as "normal" must be preceded by a backslash.\\
{\bf Example: }\\
\hspace*{2cm}{\em Main$\backslash$$.$m3} \\
\hspace*{2cm}{\em first$\backslash$$.$java}\\


{\bf 2. If token {\em A} is RE and token {\em B} is RE, then token {\em AB} is also RE} 
    Token AB is called a concatenation of REs {\em A} and {\em B}.  
    RE first matches {\em A} then {\em B}.
\\
{\bf Example:}   RE {\em cs} matches the string "cs" because it first 
matches {\em c} and then {\em s}.
  \\             

{\bf 3. {\em (A)}  matches anything that matches 
token {\em A } ( precedence relations or grouping)}\\

    Notes:\\
    \begin{itemize}
          \item  "$($" is not listed as a special character.  As a result, 
	  in many UNIX applications, which support  "$($" we have to use 
	  "$\backslash$$($" to preserve its special meaning.\\                         
          \item  "$($$)$" has also another meaning : 
	  it will store the pattern for later replay. 
	  (see UNIX in a Nutshell)\\
     \end{itemize}
 
{\bf 4. {\em A$|$B} matches anything that matches token {\em A } or token {\em B}.}\\
{\bf Example :}\\
\hspace*{2cm} a) {\em  a$|$b} \\
\hspace*{2cm} b) {\em $($ab$)$$|$$($cd$)$}.\\

Similarly as before, since $|$ is not listed as a special character, 
$\backslash$ is used to preserve its special meaning. 
And so, \\
\hspace*{1cm}a) will be written as:{\em a$\backslash$$|$b}\\
\hspace*{1cm} b) will be written as 
{em $\backslash$$($ab$\backslash$$)$$\backslash$$|$$\backslash$$($cd$\backslash$$)$}
\\

{\bf 5. {\em A*} , where token {\em A} is a RE, matches zero or more repetition of {\em A}}\\
{\bf Example:} \\

\hspace*{2cm} {\em a*} 	will match:\\
\hspace*{4cm} "" - an empty string\\
\hspace*{4cm} {\em  a} - one repetition of a\\
\hspace*{4cm} {\em aaaaaaa}  - more then one repetition of a  etc.\\

\hspace*{2cm} {\em w(ab)*}  will match:\\
\hspace*{4cm} {\em w}\\
\hspace*{4cm} {\em wab}\\
\hspace*{4cm} {\em wababab}      etc.\\

{\bf 6. '$.$' (single period) matches any character except newline $\backslash$n.}
\\
{\bf Example:}\\
\hspace*{2cm} {\em Main.m3}  will match:\\
\hspace*{4cm} {\em MainAm3} \\ 
\hspace*{4cm} {\em Main7m3}   etc.\\

Recall, that if  {\em Main.m3}  should be matched exactly, 
the appropriate RE  has to be written as {\em Main$\backslash$$.$m3}.
\\

{\bf {\em [ab]} - character classes}\\
\hspace*{2cm}    {\em $[$ab$]$} means $($a$|$b$)$\\
\hspace*{2cm}   {\em $[$abcdefg$]$} means{\em  $($a$|$b$|$c$|$d$|$e$|$f$|$g$)$}\\
Note, that a shortcut  like {\em $[$a$-$g$]$} is admissible. 
In case, the character '$-$' is really one of the character in $[$$]$, 
'$-$' has to be putted as first or last character in the list. 
For example: {\em $[$a$-$g$-$$]$} will match {\em a$|$b$|$c$|$d$|$e$|$f$|$g$|$$-$}.
\\

{\bf Examples:}\\ 
\hspace*{2cm} {\em $[$A$-$Za$-$z$]$$[$A$-$Za$-$z0$-$9\_$]$$*$} matches any modula3 
identifier or keyword\\
\hspace*{2cm} {\em $[$A$-$Z$]$$[$A$-$Z$]$$*$} matches any sequence 
of at least one capital letter\\

{\bf 7. {\em $[$\,$ \hat{ }$ab$]$}    inverted character classes }\\
{\bf Examples:}
 \hspace*{2cm} {\em $[$\,$\hat{ }$ab$]$ } matches anything except {\em $[$ab$]$}
\\
 \hspace*{2cm} {\em $[$\,$ \hat{ }$a$-$q$]$ } will match {\em t} or 
{\em u}  or {\em z} but not {\em a} or {\em d}.\\

{\bf  8.  {\em $ \hat{ }$A} - where {\em A} is a RE, matches anything that matches {\em A}, 
but only if it occurs at the beginning of the line.}\\

{\bf Example: }\\
\hspace*{2cm} {\em $ \hat{ }$\,$[$A$-$Z$]$} matches any capital letter 
at the beginning of the line.\\


{\bf 9. {\em A\$}  matches anything that matches {\em A} but only 
if it occurs at the end of a line}\\

{\bf Example:}  The following RE finds all lines that contain only one word END, 
perhaps with spaces before and after it:\\
\hspace*{2cm}   {\em "\,$ \hat{ }$ \hspace*{0.2cm} $*$END\hspace*{0.2cm}$*$\$"}\\



{\large Some additional rules not supported by all UNIX applications:}\\

{\bf 10. {\em A$+$}    	matches one or more repetitions of {\em A}.}\\  
     Note: {\em A$+$} is the same as {\em AA$*$} 
     and  many UNIX applications do not support '$+$' at all.
     Consult man pages of the particular application for what is or is not supported.\\

{\bf 11. {\em A?}  matches zero or one repetition of {\em A}}\\
      Note: ? is the same as $($A$|$$\epsilon$$)$\\

{\bf Examples:}\\
\hspace*{2cm}   {\em  a1p$[$1$-$4$]$$\backslash$$.$txt}    test cases for the assignment 1 \\
\hspace*{2cm}   {\em   $ \hat{ }$$[$$ \hat{ }$$.$$]$ }  any  character but '.' at 
the beginning of the line.\\
\hspace*{2cm}   {\em     H$[$aeiou$]$llo }    second letter is a vowel\\
\hspace*{2cm}   {\em    bugs$*$}                  bug, bugs, bugssss\\

   
{\large Multiple matches:}\\
{\em \{n,m\}}  must occur at least n times, but no more than m times.\\
{\em \{n,\,\,\}} at least n times\\
{\em \{\,\, ,m\}} no more than m times\\
{\em \{n\}}   	exactly n times\\
{\em $*$}	0 or more times $($same as {\em \{0,\,\, \}} $)$\\
{\em $+$}	1 or more times $($same as {\em \{1,\,\, \}} $)$\\
{\em ?} 	0 or 1 time $($same as {\em \{0,1\}}$)$\\\
{\bf Examples:}\\
\hspace*{2cm}   {\em quu$*$x $=$ qu$+$x$=$qu\{1,\,\, \}x}\\
\hspace*{2cm}   {\em qu$|$qux$=$qu?x$=$qu\{0,1\}x}\\
etc.\\

\subsection {Programs Using Regular Expressions}

Many UNIX programs and tools use Regular Expressions. 
In this sections we mention {\em grep}, {\em sed} and {\em vi}. 
For a complete description refer to the UNIX in a nutshell book.
 
\subsubsection {Grep and Egrep}

{\em Grep} and {\em egrep} are tools that search for patterns in files and  
find all lines containing a particular string.
\\
{\bf Format:}\\
\hspace*{2cm}   {\em   grep RE filename} \\
(see UNIX in a nutschell and man grep for more detailed description)
\\
{\bf Examples:}\\
\hspace*{2cm}   {\em   grep "youruserid" marks}	
- prints all lines which contain 'youruserid' in the file 'marks'\\
\hspace*{2cm}   {\em   grep "$\backslash$$*$" classlist}               
- prints all lines which contain a character '$*$'.\\
\hspace*{2cm}   {\em   grep "[Pp]roced.*" *.java} 
- prints all lines which contain Proced or proced in all files with extension java.\\  

Note the significant difference between '$*$' as used in RE and '$*$' used in shell.
Since shell may be easily confused by '$*$' or any other special character in 
regular expression, it is always recommended to quote (by using '' or "")  RE. 
\\
 
{\subsubsection{RE in vi:}

Another application which uses REs is the {\em vi} editor. 
For purpose of an exercise we will create a file 'temp' in the current directory.
Open a file by typing:\\
\hspace*{2cm}   {\em   vi temp}\\
and enter the following two lines:\\
\hspace*{2cm}   Tooting and froing\\
\hspace*{2cm}   until tomorrow morning\\

Now suppose we want to search for a string starting with 't' and ending with 'ing'. 
The correct regular expression is: {\em t.*ing}\\
Switch into the command mode by pressing \\
\hspace*{2cm}   {\em ESC} \\
and type\\
\hspace*{2cm}   {\em /t.*ing $($ENTER$)$}.
The cursor will point to the first character of the longest match '{\em ting and froing}'.\\
Press \\
\hspace*{2cm}   {\em   /    $($ ENTER$)$} 
and the cursor will move to the next match: '{\em til tomorrow morning}'.\\

For more options refer to the UNIX in a nutshell book.\\

\subsubsection{RE in sed:}

{\em SED} means a {\em S}tream {\em ED}itor.  
SED does not change the file it edits. 
It takes data from standard input  or a file, 
transforms them and passes them into a standard output.  
The UNIX command is {\em sed} and we will show only a few examples 
of its application for finding or replacing a string in the given text. 
More detailed description can be found in UNIX in a nutshell.\\  

Assume that we want to replace all occurrences of {\em t.*ing} in temp with {\em HELLO}. 
We can do so using:\\
\hspace*{2cm}   {\em   cat temp $|$ sed 's/t.*ing/HELLO/g'}\\
or \\ 
\hspace*{2cm}   {\em   sed 's/t.*ing/HELLO/g' temp}\\
Notice that the longest match is replaced.\\
Output goes to stdin.\\

\section {The Shell Script}

As mentioned in lab 2, scripting languages are similar to batch files in DOS
but are more powerful. They include variables, looping, conditional execution etc. 
We already saw how to write a simple shell script, 
here we introduce variables, conditional statements and loops. 
For a full description refer to the UNIX in a nutshell book.
There are also several courses available on the WEB.
For example a very nice introductory course in bourne shell can be found here:\\
\hspace*{2cm}   {\em   http://www.emerson.emory.edu/services/unixhelp1.3/Pages/scrpt/}\\


\subsection{The Basics}

A script should start with a line\\ 
\hspace*{2cm}   {\em   \#!/bin/sh}\\
Normally, '{\em \#}' introduces a comment line in shell. However, {\em \#!} is 
a special comment. It tells the shell that it is a script 
and should be run using the program {\em sh} (bourne shell) in the bin directory.
A script in korn shell will start with the line\\
\hspace*{2cm}   {\em   \#!/bin/ksh}\\
 for example.

\subsection{Variables}
Shell variables work on the principle of 'variable substitution'. 
This is different from nonscripting languages such as c$+$$+$.
If you want to use the name of a variable, type the name itself. 
If you want to substitute its value, type the dollar sign {\em \$} followed by name.
In case the value of the variable contains spaces, we have to use 
pair of double quotes (see the example below). 
To delimit name of the variable one has to use curly braces \{\}, 
as shown in the example.\\

{\bf Example:}\\
\hspace*{2cm}   {\em   \#! /bin/sh}\\
\hspace*{2cm}   {\em   class=cs241}\\
\hspace*{2cm}   {\em   longname="I like cs241"}\\
\hspace*{2cm}   {\em   echo class           \hspace*{2cm}\#prints class}\\
\hspace*{2cm}   {\em   echo \$class         \hspace*{2cm}\#prints cs241}\\
\hspace*{2cm}   {\em   echo \$classroom     \hspace*{1cm}\#prints nothing}\\
\hspace*{2cm}   {\em   echo \$\{class\}room \hspace*{1cm}\#prints cs241room}\\
\hspace*{2cm}   {\em   echo \$longname      \hspace*{1cm}\#prints I like cs241}\\
      

After execution the output will be:\\
\hspace*{2cm}   {\em   class}\\
\hspace*{2cm}   {\em   cs241}\\
\hspace*{2cm}   {\em   cs241room}\\
\hspace*{2cm}   {\em   I like cs241}\\


\subsection{Command Line Parameters}

When shell script is started, variables \$0 to \$9 are set to values 
of parameters passed from the command line.
\\

{\bf Example:} 
Create a script file {\em test.sh} by using {\em vi} editor:\\
\hspace*{1cm}   {\em   vi test.sh}\\
\hspace*{2cm}   {\em      \#!/bin/sh}\\
\hspace*{2cm}   {\em      echo Parameter 1: \$1}\\
\hspace*{2cm}   {\em      echo Parameter 2: \$2}\\

Save the file, allow execution by changing the permission 
and execute it with two input parameters {\em hello} and {\em world}:\\
\hspace*{2cm}   {\em   ./test.sh hello world}

The following output will be displayed:\\
\hspace*{2cm}   {\em         Parameter 1: hello}\\
\hspace*{2cm}   {\em         Parameter 2: world}\\
 

\subsection{Conditional Statements}

\subsubsection{The {\bf if} statement}

A typical example of the {\em if} statement is:\\
\hspace*{2cm}   {\em   	if bin/testprg}\\
\hspace*{2cm}   {\em         then}\\
\hspace*{2.5cm}   {\em      echo return from the testprg is true}\\
\hspace*{2cm}   {\em         else}\\
\hspace*{2.5cm}   {\em            echo return from the testprg is false}\\
\hspace*{2cm}   {\em         fi}\\ 

Every UNIX command returns on exit a value, which the shell can use. 
This value is held in the read-only shell variable \$?.
The value 0 (zero) signifies success; anything other than 0 (zero) signifies failure. 
In our example, if testprg executes successfully, 
the return value is 0 and the line:\\
\hspace*{2cm}   {\em   	return from the testprg is true}\\
is printed.
In case the execution was not successful, the line\\
\hspace*{2cm}   {\em    return from the testprg is false}\\
is printed.\\

The {\em if} statement is often used with the test program stored in 
{\em /usr/bin} directory. The test program has many parameters enabling 
it to check whether strings are equal or different, 
if the file exists, and much more. 
The complete description is in UNIX in a nutshell book.  
Sometimes the shorthand  $[$ $]$  for the {\em test} program is used.\\

{\bf Example:} Test if the file test.sh exists:\\
\hspace*{2cm}   {\em     if $[$ -f test.sh  $]$}\\
\hspace*{2cm}   {\em           then}\\
\hspace*{2.5cm}   {\em         echo file exists}\\
\hspace*{2cm}   {\em           else}\\
\hspace*{2.5cm}   {\em              echo file not found}\\
\hspace*{2cm}   {\em           fi}\\
     
Note the syntax of the {\em test} command: {\em $[$ $-$f file $]$}.
The spaces after '$[$' and before '$]$' are necessary.\\
 
The general syntax of the {\em if} statement is:\\
\hspace*{2cm}   {\em      if test}\\
\hspace*{2cm}   {\em      then}\\
\hspace*{2.5cm}   {\em       commands}     \hspace*{1.5cm}  (if condition is true)\\
\hspace*{2cm}   {\em      else}\\
\hspace*{2.5cm}   {\em         commands}   \hspace*{1.5cm}   (if condition is false)\\
\hspace*{2cm}   {\em     fi}\\

{\em then}, {\em else} and {\em fi} are shell reserved words and as such 
are only recognized after a newline or ; (semicolon).  
The {\em if} construct must end with a {\em fi} statement.\\
{\em if} statements may be nested:\\
\hspace*{2cm}   {\em      if ...}\\
\hspace*{2cm}   {\em      then ...}\\
\hspace*{2cm}   {\em      else if ...}\\
\hspace*{2.5cm}   {\em          ...}\\
\hspace*{2cm}   {\em        fi}\\
\hspace*{2cm}   {\em      fi}\\

The {\em elif} statement can be used as shorthand for an {\em else if}
statement. For example:\\ 
\hspace*{2cm}   {\em      if ...}\\
\hspace*{2cm}   {\em      then ...}\\
\hspace*{2cm}   {\em      elif ...}\\
\hspace*{2.5cm}   {\em        ...}\\
\hspace*{2cm}   {\em      fi}\\
\hspace*{2cm}   {\em   fi}\\


\subsubsection{The {\bf case} statement}

The {\em case} statement starts with the keyword '{\em case}' followed by 
the value to be tested and the keyword '{\em in}'. 
This is followed by series of options. 
Each value to be tested is on a separate line with a closing parenthesis '$)$' after it.
The code which should be executed comes after the value. 
After that there should be a line with double semi-colon ;;\\ 

The general syntax of the case statement is:\\
\hspace*{2cm}   {\em      case value in}\\
\hspace*{2cm}   {\em      pattern1) command(s)}\\
\hspace*{2cm}   {\em      ;;}\\
\hspace*{2cm}   {\em      pattern2) command(s)}\\
\hspace*{2cm}   {\em      ;;}\\
\hspace*{2cm}   {\em      patternN) command(s)}\\
\hspace*{2cm}   {\em      ;;}\\
 \hspace*{2cm}   {\em     esac}\\

After all the commands are executed, the control is passed to the 
first statement after the {\em esac}.

Several values can be matched in the same line. 
They must be separated from each other by a $|$ symbol. 
For example:\\
\hspace*{2cm}   {\em      case value in}\\
\hspace*{2cm}   {\em      pattern1$|$pattern2$)$ command}\\
\hspace*{2cm}   {\em      ...             ;;}\\

Patterns are checked for a match in the order in which they appear. 
A command is always carried out after the first instance of a pattern.

\subsubsection{The {\bf for} statement}

The {\em for} loop notation has the general form:\\
\hspace*{2cm}   {\em      for var in list-of-words}\\
\hspace*{2cm}   {\em      do}\\
\hspace*{2.5cm}   {\em        commands}\\
\hspace*{2cm}   {\em      done}\\

{\em commands} is a sequence of one or more commands 
separated by a newline or ; (semicolon).

The reserved words {\em do} and {\em done} must be preceded by a newline 
or ; (semicolon). Small loops can be written on a single line. For example:\\
\hspace*{2cm}   {\em      for var in list; do commands; done}\\

This is a simple example of a {\em for} loop and a 'command substitution':\\
\hspace*{2cm}   {\em   for  i in `ls `}\\
\hspace*{2cm}   {\em   do}\\
\hspace*{2.5cm}   {\em   echo "the name of the file is \$i"}\\
\hspace*{2cm}   {\em   done}\\

In this example, the command {\em ls} is executed first, 
since it is used inside back-quotes. 
Then the values are substituted to {\em i} and proper message is printed. 
Suppose that the result of the {\em ls} command is:\\
\hspace*{2cm}   {\em   first}\\
\hspace*{2cm}   {\em   test.sh}\\
Then the output from the {\em for} loop is:\\
\hspace*{2cm}   {\em    the name of the file is first}\\
\hspace*{2cm}   {\em    the name of the file is test.sh}\\

For information on {\em while} loop and other useful 
commands used refer to the UNIX in a nutshell book.


\subsection{Briefly About Linux}

Linux is a UNIX -like operating system designed for personal computers. 
It is freely available on the WEB:\\ 
\hspace*{2cm}   {\em   http://www.debian.org/}\\ 
\hspace*{2cm}   {\em   http://www.redhat.com/}\\
You may also purchase an installation disk with software needed 
for all cs courses in the Computer Club of UW 
or visit the book store.\\

{\bf Install Linux on your PC and enjoy!}

\end{document}

