------------------------------------------------------------------------ Lesson 1: Introduction to grep ------------------------------------------------------------------------ I. BRIEF BACKGROUND In UNIX, all files (regardless of filetype, ASCII or binary, for instance) consist of lines and terminated by an EOF. Each line is terminated by “\n” (ASCII value 42 or 2A). In DOS text files end with “\r\n” where “\r” is ASCII 45 or 2D. While \n contributes to the byte count of the file it is not a part of any line. If you inspect "bash" (or csh, korn or any other shell) scripts you will find a liberal use of "grep", "sed" and "awk". A good bash programer needs to be an expert with these utilities. Separately, they are fun to use: terse and curiously addictive. We start off by learning how to use "grep". The simplest use of grep is to search for a fixed pattern. grep arose from "ed", the first line editor in UNIX. It stands for "Global search for REgular expressions and Print matching lines". Before proceeding further as I noted above a UNIX file consists of lines and such files are well suited to sed and awk, In contrast, your Windows emailer works best with a line per paragraph. grep, sed and awk are not terribly useful if your file consists of one long line! Before proceeding I have to tell you that grep or sed, cannot, ordinarily, search for \n. It is worth remembering this basic point. It is my experience that the fastest way to learn a programming language is via examples. Therefore, starting the next section I urge you NOT to read but "do it". Note below you type everything but not the "$". This is the "$" supplied by bash. The text following "#" is usually an explanation of a result and is not the result of output of any program. Occasionally lines starting with "#" are pure comments lines. Also the end-of-file signal is given by "control D" (spelt as cntrl D) NB: I will assume that you are familiar with the following UNIX features: > (redirection), | (pipe), control D (end of file), “ls”, “cat” and the “echo” commands. ------------------------------------------------------------------------ IB. First example ------------------------------------------------------------------------ The simplest format of grep is grep pattern inputstream where pattern can be unquoted (i.e. the search pattern spelt in the usual fashion) or quoted weakly ("...") or quoted strongly ('...'). For now we will start with no quoting and then gradually learn when quoting is necessary (and when a particular type of quoting is necessary. Below we use the UNIX echo command to feed an input line to grep. $ echo hello hello $ echo hello | grep e - #formally the input is the keyboard e #match $ echo hello | grep #this informal approach also works e $ echo hello | grep z #no result because there is no match However, typically grep is used with an input file rather than a stream of characters coming from a keyboard. [All input files used in this lesson can be found this sub-directory]. $ cat > SimpleInput.dat 1 hello, parvi rabbit 2 there are many types of rabbits, ordinary rabbits 3 and rabbits that have been bred over centuries. 4 Rabbits have been around, apparently, for at least 5 three million years. cntrl D $ grep rabbit SimpleInput.dat 1 hello, parvi rabbit #exact match 2 there are many types of rabbits, ordinary rabbits #match, even if plural 3 and rabbits that have been bred over centuries. Before I explain the result I remark that we are used to thinking in terms of "words". A word is (usually) a collection of pure alphabets preceded by a "blank" (which is usually a space character or perhaps a tab) and succeeded by a blank or a character from the set of punctuations (.;,?"'). When writing or thinking about UNIX abandon your training in English. grep (and other UNIX utilities) operate on a literal basis. In the example above we asked grep to search for "rabbit". It found matches to "rabbit on line 1, 2 and 3. You are comfortable with the match on line 1 but are likely not comfortable (or puzzled) by the matches reported on lines 2 and 3. The fact is that "rabbits" is also a match to "rabbit" in a literal sense. If you wanted to search exclusively for the word rabbit then you should say "find a pattern which is 'rabbit’ AND has a space preceding it AND a space or punctuation succeeding it". Even this may not be an air-tight prescription since it will miss the sentence which starts off "rabbit" (in this case the preceding character is a null character — for which there is no ASCII representation). Next, note that grep searches a line and upon finding the firs match stops the search and prints the line. It then proceeds to the next line For this reason, in the above example, line 2 is printed only once. The example above was perhaps the simplest possible search. grep has powerful search capability. You can specify a pattern via a framework and grep will find all patterns that match the framework. For that you have to learn "regular" expressions. ------------------------------------------------------------------------ II. ANCHORS: ^, $ ------------------------------------------------------------------------ Regular expressions (like pipes, universal file construct) lie at the heart of UNIX. There are many families of regular expression ("regexp"). We will start with the earliest and most basic regular expression (BRE). As noted above all UNIX lines consist of lines followed by an EOF. Lines have a beginning (null) and an end (\n which has an ASCII representation). Clearly, it makes sense to start with markers for the beginning and end of the line. The characters “^” and “$” are anchors (positional indicators) for the start and end of line. These two characters are called as "meta-characters" because they have extra-ordinary power (unless "escaped"; more on this later). I have to warn you that the rest of this section is not easy. You will find that your intuition will, almost always, be wrong. It is worth doing the exercises several times whilst synthesizing the results. Ideally, you should grasp this section fully proceeding ahead. However, likely you may find that this is not possible. If so, simply go ahead and keep revisiting this section! $ cat > InputRegEx.dat hello, parvi % hello, other rabbits .hello, kitty, & good morning, world # sayonara wall street$ cntrl D #Now we undertake a variety of searches $ grep ^h InputRegEx.dat #identify lines that begin with "h" hello, parvi rabbit $ grep ^% InputRegEx.dat #identify lines that begin with "%" % hello, rabbits $ grep parvi$ InputRegEx.dat #find lines ending with parvi hello, parvi #For pedagogical purpose I list some constructs which #are useless because they list all lines in the input file! $ grep $ filename #Clearly all lines have an ending (by construction) $ grep ^ filename #Clearly all lines have a beginning (by construction) #the following is useless since it does not list any line! $ grep A^ filename # if A is anything other than [ Please ponder the above command and convince yourself why there is no match. If you are not able to figure it out then talk to me. Additional Literature: The wikipedia has an excellent & comprehensive review on regular expressions. https://en.wikipedia.org/wiki/Regular_expression The article may be appreciated after you finish taking this class. ------------------------------------------------------------------------ IIB. First introduction to Quoting ------------------------------------------------------------------------ So far our patterns have not been “quoted”. We will find that sometimes you HAVE to quote. To illustrate this let us say that our goal is to find lines ending with "#". $ grep #$ InputRegEx.dat #fails! The reason this command failed is that "#" is a special character for the shell (“comment”(. Characters succeeding # are not read by the shell. The “do not read” feature lasts for the rest of the line. Quoting informs the shell that "#" should not be interpreted in the usual fashion. #Either quoting works $ grep '#$' InputRegEx.dat $ grep "#$" InputRegEx.dat For this reason, most users simply start quoting all patterns. There will be a more detailed and finer distinction between double and single quotes. Curious? Try $ grep '$A' InputFile #Will not return any hit regardless of what A is ------------------------------------------------------------------------ IIC. Converting meta-characters to literals ------------------------------------------------------------------------ #Goal: you want to list lines beginning with "." $ grep '^.' InputRegEx.dat #Naively you try the obvious approach hello, parvi rabbit % hello, rabbits .hello, kitty, & good morning, world # sayonara wall street$ Why did all lines get listed? All lines have a beginning, “^”. Most lines have at least one character. In regexp, as explained below (IV) “.” is a meta-character. It denotes one character (any character). Thus the pattern ^. is satisfied by lines which have one or more characters. In the above example, all lines satisfy this criterion. Clearly, we need to inform grep that we are genuinely looking for the period or “.” character. So we need to strip “.” of its special meaning. We do so by “escaping” it and that is “\,”. $ grep '^\.' InputRegEx.dat .hello, kitty #It worked! Do not fret too much if you do not understand this example. Below we have an entire section (VII) devoted to this painful issue. Curious? Try $ grep ^\. InputRegEx.dat #No output. Why? ------------------------------------------------------------------------ III. INTERLUDE: Line numbering, showing non-printable characters ------------------------------------------------------------------------ Since the UNIX framework for files is a series of lines it is only natural to have many utilities number each line. Numbering lines is extremely useful for identifying errors in bugs and identifying lines of interest when using line oriented editors like vi (or emacs for that matter). $ cat > Lines.dat a aa b ba #To make this “line with zero characters” line simply hit return cntrl D $ cat -e Lines.dat #with option "-e" control chars are revealed aa$ #"\n" is displayed as "$" b$ ba$ $ #Notice this line. It is a null line (no chars) $ cat -e -n Lines.dat # the option "-n" results in printing of input 1 a$ #line number 2 aa$ 3 b$ 4 ba$ 5 $ #make sure that there is no space preceding $. Incidentally, if you actually wanted to insert lines into a file that you have already constructed then you can do so by in at least a dozen ways. The classic method is $ nl Lines.dat > LinesNumbered.dat #try it out ------------------------------------------------------------------------ IIIb. Options ------------------------------------------------------------------------ All UNIX utilities have "options". grep has many options. It is worth reading the “man” pages (just to appreciate the richness of grep). Below we will use the option “-n” (for numbering output lines using input line number) $ grep -n ‘’ Lines.dat ------------------------------------------------------------------------ IV. Quantification: * . \{ \} ------------------------------------------------------------------------ A "." means match one character (any character) A "*" means (1) one or more of the character preceding it OR (2) a character of zero length. The rookie mistake is to forget (2). #list all lines which contain one character $ grep -n "." Lines.dat 1:a 2:aa 3:b 4:ba As you can see, line 5 is not in the output (because it is a null line; just \n). $ grep -n "a" Lines.dat #Search for lines containing "a" 1:a 2:aa 4:ba $ grep "^a" Lines.dat #Search lines starting with "a" 1:a 2:aa $ grep -n 'a*' Lines.dat #Any such command will match ALL lines 1:a #Why? (Think hard and only proceed after you have 2:aa #figured out the answer 3:b 4:ba 5: #Notice even this null line is also matched $ grep -n 'aa*' Lines.dat #matches one or more "a" 1:a 2:aa 4:ba $ grep -n 'a\{2\}' Lines.dat #Match two “a” in succession 2:aa $ grep -n 'a\{1,2\}' Lines.dat #Match "aa" or "a" 1:a 2:aa 3:ba $ grep -n 'a\{1,\}' Lines.dat #Matches “a”, “aa”, “aaa” and so on 1:a 2:aa 4:ba ROOKIE MISTAKE GIVES GREAT UNDERSTANDING: Now I address the usual rookie mistake. Review the command below. Do not execute command. First mentally compute your answer. Then execute the command and explain the rather surprising answer. Commit this example to memory. $ echo "abc" | grep 'z*' abc ------------------------------------------------------------------------ IVB. Introduction to sed ------------------------------------------------------------------------ I take the occasion to introduce "sed". No need to get stressed out! We will have two classes on sed. The usual invocation of sed is $ sed action InputFile The most famous action is to "identify and replace" (substitution). Say you have written a story (file: Storybook) in which the main protagonist is a dog. After finishing and upon reflection you decide to change the protagonist to a rabbit (naturally). $ sed 's/dog/rabbit/' Storybook #this is not a foolproof substitution. # ”dogged” becomes “rabbitged”. $There is a simple way to fix such errors. $ echo "abc" | sed 's/a/A/' #will substitute A for a, but for the first match Abc $ echo "abca" | sed 's/a/A/g' #will substitute A for a, for all matches $AbcA #the “flag” “g” stands for “global” (all matches) Having learnt one (but powerful) command in sed let us redo the rookie mistake exercise. $ echo "abc" | sed 's/b*/1/' 1abc $ echo "abc" | sed 's/b*/1/g' 1a1c1 Please ponder the outcomes! ------------------------------------------------------------------------ V. CHARACTER SET: ------------------------------------------------------------------------ A character set allows for a set of characters to be probed instead of only one. [abc] would match "a", "b" or "c" >> Remember a character set is still only one character << [If you want more than one character then you need to concatenate as in “[abc][xz]”. This pattern is matched by six combinations: ax, az, bx, bz, cx and cz.] Ranges are allowed (they map to underlying continuous range ASCII values; if this statement is not clear look up the ASCII table): For instance [0-9] is a character set which includes all digits from 0 to 9. By induction [a-z] a through z (lower case) [A-Z] A through Z (upper case) [a-d] a through d Ranges can be combined: [0-9a-z] This pattern is matched by digits and lower case alphabets. [a-zA-Z] This pattern is matched by alphabets, independent of case There is no ambiguity in the above construction. The first “-“ specifies the range a through z and the second dash specifies the range A through Z. Adding “^” as the first character in a set negates the entire set. For example, [^0-9] means all characters BUT the 10 digits. [It is unfortunate that “^” has another meaning; see II]. $ cat > Lines2.dat a b bc def 1 345 &%^?-+ cntrl D $ grep '[a-z]' Lines2.dat a b bc def $ grep '[0-9]' Lines2.dat 1 345 $ grep '[A-Z]' Lines2.dat $ grep '[^a-z]' Lines2.dat 1 345 &?-+ $ grep '[0-9a-z]' Lines2.dat a b bc def 1 345 $ grep [^0-9a-z] Lines2.dat #example of negating two ranges &?-+ ------------------------------------------------------------------------ VB. POSIX Character classes ------------------------------------------------------------------------ Rather than write [0-9] or [a-zA-Z] we can use POSIX character classes [:digit:] any digit, 0-9 [:alpha:] any alphabe (upper & lower), A-Z & a-z [:alnum:] any alpha or numeric character [:cntrl:] control characters [:print:] any printable characters (i.e [^[:cntrl:]]) [:blank:] a space or tab [:graph:] neither a space nor a tab POSIX classes can be used only within the character set framework. Thus the correct usage is always “[[:digit:]]”. $ grep '[[:digit:]]' Lines2.dat #selects lines with digits 1 345 $ grep [^[:digit:][:alpha:]] Lines2.dat #selects non-alphanumeric chars &?-+ COMMON ROOKIE MISTAKE: It is a common mistake to use “[:digit:]” instead of “[[:digit:]]. Study (and understand) the rather curious outcome $ grep '[:digit:]' Lines2.dat def ------------------------------------------------------------------------ VI. Back-referencing & Extracting Tokens ------------------------------------------------------------------------ The construct "\(RegularExpression\)" yields a token. The text thus captured is available in “\1”. Nine such tokens can be defined (in sequential order). Thus for example "\(.\)" captures a character. The simplest use of back-referencing is to search for a repeated pattern in the same line. Using back-reference saves retyping the pattern again. This is not the best use of back-references (actually it slows down the performance). $ grep '\(sky is blue\).*\1' BlueSky.dat The sky is blue at 10 am. The sky is blue at noon. A better example is to extract quoted words $ echo 'Hello, my name is "Kitty"' | grep "\([\"']\).*\1" PAUSE: You should pause here and understand the quoting construction here.The basic rule when you wish to use either quoting then you should build inside out. Start with the quoting for echo == 'Hello, my name is "Kitty"'. Here I wanted to quote Kitty with double quotes. Ergo, the outer quoting has to be single quote. Next the pattern for grep. Here I wanted to include both " and ' inside the pattern. Given that we want both quotes I arbitrarily chose " as the outer quote. Ergo, the double quote " must be escaped inside the patter. Having understood the quoting let us study the pattern "\([\"']\).*\1" The pattern is designed to find all characters enclosed between double quotes or single quotes. Say a double quote is found as grep scans from left to right. Then grep looks for a closing double quote and not a single quote. The same argument applies for a single quote. This is indeed a clever use of back-referencing. A fun use of back-reference is to identify palindromes. In this case the pattern to be identified is unknown. The expression "\(.\).\1" accurately describes 3-character palindrome, e.g. “ANA”, “dud”, “eve”, “you” and so on. Armed with tokens let us search for five character palindromes! $ cat > Palindrome.dat 1:In the city of GadaG there lived two dogs whose owner was on Mr. TenteT. 2:One was called RotoR and the other SoloS. 3:One day one dog ran away and other dog got hit by a bus. 4:SoloS and the owner became very sad. cntrl D $ grep -n '\(.\)\(.\).\2\1' Palindrome.dat 1:In the city of GadaG there lived two dogs whose owner was on Mr. TenteT. 2:One was called RotoR and the other SoloS. 3:One day one dog ran away and other dog got hit by a bus. 4:SoloS and the owner became very sad. The identification of GadaG and RotoR is clear. Incidentally, TeneT and SoloS were not identified by grep. The search stopped when a match was found. grep printed the line and went to the next line. [More below]. >> You may wish to figure out why line 3 is reported << Our third class will be on “sed”. However, modest use of sed will give insight into the above exercise. Here is a brief summary of how the substitution by sed works. $ sed ’s;Reg;Replace;' InFile replaces text found by regular expression, Reg, by text given by Replace. Below we will identify palindromes and replace them by “Z” (as a marker). $ sed 's;\(.\)\(.\).\2\1;Z;' Palindrome.dat In the city of Z there lived two dogs whose owner was on Mr. TenteT. One was called Z and the other SoloS. One day one dog ran away and other dZt hit by a bus. Z and the owner became very sad. ------------------------------------------------------------------------ VII. How to search for meta-characters ------------------------------------------------------------------------ The meta-characters for basic regular expressions (BRE) are ^ $ . * [ ] - & A meta-character is downgraded to an ordinary character by escaping it. That is when you wish to use any of the above characters literally then precede it by “\”. We have one such example in IIC. However, not all meta-characters need to be escaped (for sound reasons). Though it is a technical point it is not prudent to simply escape ALL meta-characters (though you can get away by escaping all of them; it is not POSIX compliant). $ cat > Metacharacter.dat We explore meta-characters here: *, ., ^, $, [, ] & -. We have not introduce & so far. #this is a null line (see III) .Some UNIX tools have line starting with a . In regular English no sentence ends in $ cntrl D $ grep '\$' Metacharacter.dat #Identify lines with a “$” character We explore meta-characters here: *, ., ^, $, [, ] & -. In regular English no sentence ends in $ $ grep ']' Metacharacter.dat We explore meta-characters here: *, ., ^, $, [, ] & -. #surprised? $ grep '[' Metacharacter.dat grep: brackets ([ ]) not balanced #hmm $ grep '\[' Metacharacter.dat #solution 1 We explore meta-characters here: *, ., ^, $, [, ] & -. $ grep '\^' Metacharacter.dat #find lines with “^” character We explore meta-characters here: *, ., ^, $, [, ] & -. You can deepen your understanding of the regular expression framework by exploring character sets containing meta-characters. To start with, meta-characters lose their special status when inside a character set. However, how you place them inside “[ ]” does matter. $ grep '[]]' Metacharacter.dat We explore meta-characters here: *, ., ^, $, [, ] & -. $ grep '[^]' Metacharacter.dat #hmmm grep: brackets ([ ]) not balanced $ grep '[]*]' Metacharacter.dat We explore meta—characters here: *, ., ^, $, [, ] & -. $ grep '[*]]' Metacharacter.dat does not return any line. Why? ------------------------------------------------------------------------ HOMEWORK: [1] Look at the file "BlankLines.dat". It has a varitey of blank lines. Use "grep -n" and identify (and count) all blank lines. Then do the same with a finer search (space, tab, null). Hint: "tab" is a control character and the way you pass this character to a pattern is "cntrl V tab".