2001-05

<body stylesrc="index.html" background="images/Bkgrnd02T2.gif"> <table border="0" cellpadding="6" cellspacing="0" width="810"> <tr> <td align="right" valign="top" height="1" width="161"> <p align="center"><img border="0" src="images/Accent03.gif" align="left" width="142" height="37"> </p> <p align="left"><b><font size="2">May 2001 - Vol. 2 No. 5</font></b></p> </td> <td height="1" width="621"> <p align="center">  <a href="index.html" target="_top">[Home]</a> <a href="Newsletters.html" target="_top">[Up]</a> <a href="2001-06.html" target="_top">[Next]</a> <a href="2001-04.html" target="_top">[Previous]</a></td> </tr> <tr> <td valign="top" height="529" bgcolor="#FFFFCC" width="161"> <font size="2"> <p><a href="#TechTalk"><b>Tech Talk</b></a><br> <a href="#The Basics of RE">The Basics of RE</a> </p> <p><a href="#Editorial"><b>Editorial</b></a><br> <a href="#Linux Development Directions">Linux Development Directions</a><a href="#C++ Object-Oriented Preprocessor"><br> C++ OO Preprocessor</a> </p> <p><a href="#Inline Functions"><b>Inline Functions</b></a></p><p><a href="#Trends"><b>Trends</b></a><br> <a href="#An Aside">An Aside<br> </a><a href="#SourceForge Statistics">SourceForge Statistics</a></p></font> </td> <td height="277" bgcolor="#FFCC99" width="621"> <b> <h1><a name="TechTalk"><font color="#000000">Tech Talk</font></a></h1> <h2><font face="Arial" color="#000000"><a name="The Basics of RE">The Basics of RE</a> (Regular Expressions) — Part 2</font></h2> </b> <i><font SIZE="2"> <p>By </font><a href="Author-JesusMonroy.html">Jesus Monroy, Jr.</a></p> </i> <b> <h3><font face="Arial">Quick Review</font></h3> </b> <p>In the last article we examined some simple examples of how to use RE. We will quickly review part one.</p> <div align="center"> <center> <table BORDER="1" CELLSPACING="1" WIDTH="339"> <tr> <td VALIGN="middle" bgcolor="#FFFFFF"><b><font FACE="Courier New" SIZE="2"> <p>the</font></b></td> <td VALIGN="middle" bgcolor="#FFFFFF"><font SIZE="2"> <p>bind to the single word ‘the’.</font></td> </tr> <tr> <td VALIGN="middle" bgcolor="#FFFFFF"><b><font FACE="Courier New" SIZE="2"> <p>a</font></b></td> <td VALIGN="middle" bgcolor="#FFFFFF"><font SIZE="2"> <p>bind to the single letter ‘a’.</font></td> </tr> <tr> <td VALIGN="middle" bgcolor="#FFFFFF"><b><font FACE="Courier New" SIZE="2"> <p>aaa</font></b></td> <td VALIGN="middle" bgcolor="#FFFFFF"><font SIZE="2"> <p>bind to three ‘a’ characters in a row.</font></td> </tr> <tr> <td VALIGN="middle" bgcolor="#FFFFFF"><b><font FACE="Courier New" SIZE="2"> <p>.</font></b></td> <td VALIGN="middle" bgcolor="#FFFFFF"><font SIZE="2"> <p>bind to any single character.</font></td> </tr> <tr> <td VALIGN="middle" bgcolor="#FFFFFF"><b><font FACE="Courier New" SIZE="2"> <p>^</font></b></td> <td VALIGN="middle" bgcolor="#FFFFFF"><font SIZE="2"> <p>bind to the beginning of line</font></td> </tr> <tr> <td VALIGN="middle" bgcolor="#FFFFFF"><b><font FACE="Courier New" SIZE="2"> <p>$</font></b></td> <td VALIGN="middle" bgcolor="#FFFFFF"><font SIZE="2"> <p>bind to the end of the line</font></td> </tr> <tr> <td VALIGN="middle" bgcolor="#FFFFFF"><b><font FACE="Courier New" SIZE="2"> <p>a{1-3}</font></b></td> <td VALIGN="middle" bgcolor="#FFFFFF"><font SIZE="2"> <p>bind to ‘a’, ‘aa’ or ‘aaa’</font></td> </tr> <tr> <td VALIGN="middle" bgcolor="#FFFFFF"><b><font FACE="Courier New" SIZE="2"> <p>[a-z]</font></b></td> <td VALIGN="middle" bgcolor="#FFFFFF"><font SIZE="2"> <p>bind to any lower case letter</font></td> </tr> <tr> <td VALIGN="middle" bgcolor="#FFFFFF"><b><font FACE="Courier New" SIZE="2"> <p>[^np]</font></b></td> <td VALIGN="middle" bgcolor="#FFFFFF"><font SIZE="2"> <p>bind to any lower case letter, except ‘n’ and ‘p’</font></td> </tr> <tr> <td VALIGN="middle" bgcolor="#FFFFFF"><b><font FACE="Courier New" SIZE="2"> <p>\.</font></b></td> <td VALIGN="middle" bgcolor="#FFFFFF"><font SIZE="2"> <p>bind to the period ‘.’ character</font></td> </tr> <tr> <td VALIGN="middle" bgcolor="#FFFFFF"><b><font FACE="Courier New" SIZE="2"> <p>\\</font></b></td> <td VALIGN="middle" bgcolor="#FFFFFF"><font SIZE="2"> <p>bind to backslash ‘\’ character</font></td> </tr> </table> </center> </div> <b> <i><font FACE="Arial"> <p ALIGN="CENTER">Table #1: Meta-characters</p> </font></i></b> <p>One quick note, most programs expect an RE to be on a single line. That is, if looking for three ‘a’ (a{3}) in a row, most programs expect to find</p> <b> <blockquote> <p><font FACE="Courier New" SIZE="2">this is an example of aaa</p> </blockquote> </font> </b> <p>not</p> <b> <blockquote> <p><font FACE="Courier New" SIZE="2">this is a broken example<br> of aa<br> a</p> </blockquote> </font> </b> <p>The later example can be constructed as a RE – but not by all programs, and only when explicitly told to do so. We won't cover that here.</p> <b> <h3><font face="Arial">Return Value</font></h3> </b> <p>One thing we have not discussed up until now is if we could detect whether a match occurred. In some cases, we might want to know if the RE did not bind. Specifically, Perl, Awk, Lex and Yacc are languages which can take action base on the returned value of a RE. In the next section, we will see examples of how this works.</p> <b> <h3><font face="Arial">The Logic of More Complex REs</font></h3> </b> <p>Some of the meta-characters we did not considered in the first article include:</p> <div align="center"> <center> <table BORDER="1" CELLSPACING="1" width="220"> <tr> <td VALIGN="top" bgcolor="#FFFFFF"><b><font SIZE="2"> <p>?</font></b></td> <td VALIGN="top" bgcolor="#FFFFFF"><font SIZE="2"> <p>question mark</font></td> <td VALIGN="top" bgcolor="#FFFFFF"><font SIZE="2"> <p>Zero or one</font></td> </tr> <tr> <td VALIGN="top" bgcolor="#FFFFFF"><b><font SIZE="2"> <p>*</font></b></td> <td VALIGN="top" bgcolor="#FFFFFF"><font SIZE="2"> <p>star (asterisk)</font></td> <td VALIGN="top" bgcolor="#FFFFFF"><font SIZE="2"> <p>Zero, one or more</font></td> </tr> <tr> <td VALIGN="top" bgcolor="#FFFFFF"><b><font SIZE="2"> <p>+</font></b></td> <td VALIGN="top" bgcolor="#FFFFFF"><font SIZE="2"> <p>plus sign</font></td> <td VALIGN="top" bgcolor="#FFFFFF"><font SIZE="2"> <p>One or more</font></td> </tr> </table> </center> </div> <b> <i><font FACE="Arial"> <p ALIGN="CENTER">Table #2: Meta-modifiers</p> </font></i></b> <p>These meta-characters are modifiers on other meta-characters. If we use the ‘.’ as an example, then we might better see how they are used. To refresh our memory, the period ‘.’ is a meta-character that binds to any character.</p> <p>So, if we use the modifiers in conjunction with the period we get:</p> <b> <font SIZE="2"> <div align="center"> <center> <table BORDER="1" CELLSPACING="1"> <tr> <td VALIGN="top" bgcolor="#FFFFFF"><b><font FACE="Courier New" SIZE="2"> <p>.?</font></b></td> <td VALIGN="top" bgcolor="#FFFFFF"><font SIZE="2"> <p>bind to zero or one characters</font></td> </tr> <tr> <td VALIGN="top" bgcolor="#FFFFFF"><b><font FACE="Courier New" SIZE="2"> <p>.*</font></b></td> <td VALIGN="top" bgcolor="#FFFFFF"><font SIZE="2"> <p>bind to zero, one or more characters</font></td> </tr> <tr> <td VALIGN="top" bgcolor="#FFFFFF"><b><font FACE="Courier New" SIZE="2"> <p>.+</font></b></td> <td VALIGN="top" bgcolor="#FFFFFF"><font SIZE="2"> <p>bind to one or more characters</font></td> </tr> </table> </center> </div> </font> <i><p ALIGN="CENTER"><font face="Arial">Example #1: Meta-modifiers</font></p> </i></b> <p>In the first example, the ‘.?’, usually phrased as 'zero or one' occurrence, will always succeed, or return a value of true. Similarly so, ‘.*’ will always return true. However, when we use ‘.+’, this means that we must bind to with at least one (1) character or the value return is false. As a side note, a single period without a modifier ‘.’ will return true if once it finds one character. If it finds no characters, it returns false.</p> <p>Another noteworthy item is the greediness of the star (*) character. When the star is used in conjunction with the ‘.’ symbol, it grabs all the characters. This might matter when trying to parse data fields, like CSV (comma separated values). In just a bit we will see how this matters, and one way to handle this.</p> <b> <h3><font face="Arial">Character Set Exclusion</font></h3> </b> <p>One special case worth noting is the meta-characters that defines a character exclusion set. It is written like this:</p> <b> <font SIZE="2"> <blockquote> <p>[^n] </font> </b> bind to any lower case alphabetic character, except ‘n’</p> </blockquote> <p>This useful when we want to grab a string encased in a pair of delimiters. Here are some common examples:</p> <div align="center"> <center> <table BORDER="1" CELLSPACING="1" WIDTH="220"> <tr> <td VALIGN="top" bgcolor="#FFFFFF"><b><font FACE="Courier New" SIZE="2"> <p>,[^,],</font></b></td> <td VALIGN="top" bgcolor="#FFFFFF"><font SIZE="2"> <p>grab comma delimited</font></td> </tr> <tr> <td VALIGN="top" bgcolor="#FFFFFF"><b><font FACE="Courier New" SIZE="2"> <p>"[^"]*"</font></b></td> <td VALIGN="top" bgcolor="#FFFFFF"><font SIZE="2"> <p>grab inside double quotes</font></td> </tr> <tr> <td VALIGN="top" bgcolor="#FFFFFF"><b><font FACE="Courier New" SIZE="2"> <p>'[^']+'</font></b></td> <td VALIGN="top" bgcolor="#FFFFFF"><font SIZE="2"> <p>grab inside single quotes</font></td> </tr> <tr> <td VALIGN="top" bgcolor="#FFFFFF"><b><font FACE="Courier New" SIZE="2"> <p>^[^\s]*</font></b></td> <td VALIGN="top" bgcolor="#FFFFFF"><font SIZE="2"> <p>grab string without spaces</font></td> </tr> </table> </center> </div> <b> <i><p ALIGN="CENTER"><font face="Arial">Example #2: Meta-modifiers</font></p> </i></b> <p>In the first example, grab anything in between commas. In the second example, we grab anything inside a pair of double quotes. Both are commonly used for CSV (comma separated values) formats. The third example is similar to the second, except we use single quotes and it only returns true if there is something in between the quotes. The fourth example grabs the first word on the beginning of a line.</p> <p>I should now continue with the point mentioned earlier about the star ‘*’ being greedy when it binds. If you'll note, in the last set of examples I wrote</p> <b> <blockquote> <p><font FACE="Courier New" SIZE="2">"[^"]*"</p> </blockquote> </font> </b> <p>not</p> <b> <blockquote> <p><font FACE="Courier New" SIZE="2">".*"</p> </blockquote> </font> </b> <p>The reason is, in the later case, the star (*) becomes greedy and grabs everything after the first single quote ("), even the end-of-line character. To avoid this, we wrote ("[^"]*").</p> <p>To explain this a bit further, let's look at the character set exclusion rule, [^"]. This tells us to we want to exclude the double quote (") character from our set. Implicitly, this says “include everything else”. As such, if we include the portion with the star ([^"]*), the RE will bind to all characters, except the double quote ("). It will then continue until it finds the next double quote or the end-of-line. If it finds the end-of-line, it will fail (or return false).</p> <p>If we then include a look at the original RE, we see that it will bind when it finds the first double quote ("), then stop when it finds the next double quote ("). Also, unless it finds both double quotes, the RE will return false.</p> <p>Lastly, with regards to using quoting characters, some programs ‘interpret’ the meaning of characters within the quotes. For example, when using Lex, all meta-characters lose their meta meaning when inside double quotes, except for “C escape sequences”.</p> <b> <h3><font face="Arial">Grouping</font></h3> </b> <p>One other special case worth mentioning are the grouping symbols. Their meta-characters are:</p> <div align="center"> <center> <table BORDER="1" CELLSPACING="1" WIDTH="220"> <tr> <td VALIGN="top" bgcolor="#FFFFFF"><b><font FACE="Courier New" SIZE="2"> <p>|</font></b></td> <td VALIGN="top" bgcolor="#FFFFFF"><font SIZE="2"> <p>pipe character</font></td> </tr> <tr> <td VALIGN="top" bgcolor="#FFFFFF"><b><font FACE="Courier New" SIZE="2"> <p>()</font></b></td> <td VALIGN="top" bgcolor="#FFFFFF"><font SIZE="2"> <p>round braces</font></td> </tr> </table> </center> </div> <p>They can be used by themselves, but are often used in combination to form more complex statements. Here is an example with the pipe character ‘|’.</p> <b> <p><font FACE="Courier New" SIZE="2">cow|pig|sheep</p> </font> </b> <p>In this example, the RE will bind with any of the three words. That is, this RE example will return true if either cow, pig or sheep is found on the line.</p> <p>As for the round braces, we will give the fairly complex example:</p> <b> <p><font FACE="Courier New" SIZE="2">([0-9]+)|([0-9]*\.[0-9]+)</p> </font> </b> <p>We can see the RE breaks into 2 parts. On the left is [0-9]+. On the right is [0-9]*\.[0-9]+</p> <p>The left binds to one or more numerical digits. The right binds to a decimal value that may or may not start with a numerical digit and trails with one or more numerical digits. For example:</p> <b> <font FACE="Courier New" SIZE="2"> <blockquote> <p>.8<br> 25.273684<br> 0678.900<br> 0,0</p> </blockquote> </font> <h3><font face="Arial">Left to Right Precedent Ordering</font></h3> </b> <p>Lastly, there is precedent ordering. With the exception of *grouping*, RE does not have precedent ordering; it works from left to right. That is, if you build a slightly more complex RE, the binding starts from the left and works to the right. Here is a quick example:</p> <b> <blockquote> <p><font FACE="Courier New" SIZE="2">A (quick)? fox jumped<br> (up|down)\.</p> </blockquote> </font> </b> <p>Some legal results are:</p> <b> <font FACE="Courier New" SIZE="2"> <blockquote> <p>A fox jumped up.<br> A fox jumped down.<br> A quick fox jumped up.<br> A quick fox jumped down.</p> </blockquote> </font> </b> <p>That's it. I hope you found this short tutorial and examples useful. In the next article, I hope to show RE in action with Lex, the lexical analyzer.</p> <b> <h1><font color="#000000"><a name="Editorial">Editorial</a></font></h1> </b> <i> <p>By <a href="Author-RegCharney.html">Reg. Charney</a></p> </i> <b> <h3><font face="Arial"><a name="Linux Development Directions">Linux Development Directions</a></font></h3> </b> <i> <font SIZE="3"> <p>Just read a terrific article on the latest Linux kernel hackers summit by Chris DiBona. It was fun to read and gave a good flavor of where Linux development is heading. You can find the full article at http://noframes.linuxjournal.com/articles/buzz/0048.html. Areas discussed at the conference included:</p> <ul> <li>Requirements for a High Performance Database.</li> <li>SCTP (Streaming Control Transport Protocol) Linux Kernel Implementation.</li> <li>Advanced Filesystem Integration (XFS).</li> <li>Hot Plug</li> <li>Linux 2.6 Memory Management</li> <li>Security Enhanced Linux</li> <li>Asynchronous I/O</li> <li>Linux and Power Management</li> <li>Larry McVoy on BitKeeper</li> </ul> <p>This is a conference of the best and brightest of the Open Source software movement. Read Chris’s article.</p> </font> </i> <b> <h3><font face="Arial"><a name="C++ Object-Oriented Preprocessor">C++ Object-Oriented Preprocessor</a></font></h3> </b> <i> <font SIZE="3"> <p>Through sheer good fortune, I came across an article in the IEEE Proc. on Software, Vol. 147, No 2, April 2000. In it, Willink and Muchnick describe an Object-Oriented Preprocessor fit for C++. I plan to do a synopsis of their proposal in a future issue, but if you can’t wait, their paper is available at, <a href="http://www.computing.surrey.ac.uk/research/dsrg/fog/FogIee.pdf">www.computing.surrey.ac.uk/research/dsrg/fog/FogIee.pdf</a>. That paper summarizes the much more substantial work in <a href="http://www.computing.surrey.ac.uk/research/dsrg/fog/v/FogThesis.pdf">www.computing.surrey.ac.uk/research/dsrg/fog/v/FogThesis.pdf</a>.</p> </font> <b> <h1><font color="#000000"><a name="Inline Functions">Inline Functions</a></font></h1> </b> <p><b>By <a href="Author-AllanKelly.html"> Allan Kelly</a></b></p> </i> <p>C++ inline functions may optimise code: inline function saves you the overhead of a function call, that is: loading parameters onto the stack, making a jump, popping parameters off the stack, and then do it all in reverse when you return.</p> <p>Modern CPUs have pipelines that a function call can disrupt when called, and again, when it returns. By inlining we potentially allow the CPU to further improve execution.</p> <p>Not only this, but a compiler may be able to optimise code which it has been inlined in a way it cannot if there is a function call simply because the optimisation becomes visible, e.g. optimising register allocations. In the case of empty functions – fairly typical of constructors – making the function inline may allow the compiler to remove the call altogether.</p> <p>Sometimes an inline function may save time and space. Making a function call requires instruction codes to make the call both on the part of the caller and callee. On occasions, the number of bytes required for this may actually be greater than the number of bytes in the function body itself.</p> <p>With these kinds of optimisations available, we might wonder why we don’t just make all functions inline. In my opinion there are downsides that out weigh the advantages.</p> <p>For starters, inline is only a hint to the compiler. The compile can ignore it if the function is too big or too complex. Compilers differ in what they will and will not inline.</p> <p>Other reasons I avoid using inline are:<br> </p> <ul> <li>Code bloat: inline functions usually make your code bigger because you duplicate code for each function invocation.</li> <li>Increased CPU cache misses: if you increase a function’s size with inline functions, it may outgrow the cache, and fewer big functions may be held in cache at once.</li> <li>Coupling between headers and implementation increases. A header with interface and implementation is more likely to change than one with interface alone. Changes in a combined header file will cause a bigger rebuild because other files depend on your header files. By contrast, if the code is in the implementation file, only that file needs to be recompiled. On large systems the difference can be hours.</li> <li>By giving the implementation in the header file you are less likely to be able to forward declare classes, so you have to include another header file – increasing coupling and making the code less flexible and more prone to ripple effects – again increasing build times.</li> <li>Perhaps more significant is what a lot of inline functions says about your design. Inlining is typically used for get and set functions. Classes with lots of such functions aren’t really hiding anything, they are just containers for values that begs the question – just how object-oriented is your design?</li> <li>Finding code in source files can be time consuming. If you have lots of inline functions you need to look in .h files as well. This may seem trivial, but on a large system with several thousand files the time adds up.</li> </ul> <p>Inlines may improve performance. However, they will always make your code less flexible.</p> <b><i> <h1><font color="#000000"><a name="Trends">Trends</a></font></h1> </i></b><i> <p>By <a href="Author-RegCharney.html">Reg. Charney</a></p> <b><font FACE="Arial" SIZE="3"> <p><a name="An Aside">An Aside</a></p> </font></b></i><font SIZE="3"> <p>I collect my statistics on a monthly basis. I have done that for May 2001, but the news is once again, unexciting, to say the least.. The general trend is downwards, but there are no real surprises and I don’t want to make news out of nothing. Thus, I looked for facts that I thought you might be interested in. Hence the accompanying table of statistics from the SourceForge home page (www.sourceforge.org).</p> <p>Some of you may know about the SourceForge, but many of you may not. The SourceForge is a sophisticated means of configuration management and publication. It offers CVS, mailing lists, bug tracking, message boards/forums, task management, site hosting, permanent file archival, full backups, and total web-based administration.</p> <p>It is hosted by VA Linux and made available for free to anyone with an Open Source project. You can even get a copy for your own firm’s internal use.</p> <p>I chose to write about it this month because of the number of ongoing Open Source projects that may be of interest to you. Also I wanted to show the strength of the Open Source movement. On this one site alone, there are almost 20,000 projects and over 160,000 users. There are also thousands of games available, many ported from other operating systems.</p> <p>Since its free, go visit and maybe you will be interested enough to want to actively participate.</p> <b><font FACE="Arial"> <p><a name="SourceForge Statistics">SourceForge Statistics</a></p> </font></b> <p>Hosted Projects: <b>19,709</b> Registered Users: <b>160,177</p> </b></font><b><font FACE="Arial"> <table border="1" width="100%"> <tr> <td width="44%" bgcolor="#FFFFFF"><b><font size="2">Top Project Downloads</font></b> <p><font size="2">(7,619) The Freenet Project<br> (6,909) AbiWord<br> (6,348) Open Source Napster Server<br> (5,694) MiKTeX<br> (5,339) Back Orifice 2000<br> (4,744) Tux Racer<br> (4,541) WinPenguins<br> (3,238) Audacity<br> (3,177) VirtualDub<br> (2,860) jEdit</font></p> <b><font FACE="Arial"> <p><font size="2">Highest Ranked Users</font></p> </font></b> <p><font size="2">1 - (5.0041) Tim Perdue<br> 2 - (4.8605) James Byers<br> 3 - (4.7353) Luke Ehresman<br> 4 - (4.2937) Uriah Welcome<br> 5 - (4.1639) Nathan Ehresman<br> 6 - (3.9460) Brandon Wiley<br> 7 - (3.5279) Peter Hutnick<br> 8 - (3.5092) Paul Joseph Thompson<br> 9 - (3.4479) Eric Warmenhoven<br> 10 - (3.3777) Theodore Ts'o</font></td> <td width="56%" bgcolor="#FFFFFF"><b><font size="2">Most Active This Week</font></b> <p><font size="2">(100.0000% ) SourceForge<br> ( 99.9793% ) MiKTeX<br> ( 99.9585% ) phpAdsNew<br> ( 99.9378% ) phpGroupWare<br> ( 99.9170% ) Gaim<br> ( 99.8963% ) Gnucleus<br> ( 99.8756% ) Miranda ICQ Client<br> ( 99.8548% ) EtherApe<br> ( 99.8341% ) Python<br> ( 99.8134% ) DocBook Open Repository<br> ( 99.7926% ) SquirrelMail<br> ( 99.7719% ) HSQL Database Engine<br> ( 99.7511% ) Firewall Builder<br> ( 99.7304% ) FreeCraft real-time strategy game engine<br> ( 99.7097% ) RadeonTweaker<br> ( 99.6889% ) jboss.org<br> ( 99.6682% ) Crystal Space 3D Engine<br> ( 99.6474% ) jEdit<br> ( 99.6267% ) net-snmp<br> ( 99.6060% ) Enlightenment</font></td> </tr> </table> </font></b> <p>  </td> </tr> </table> </body>