Howto « Staffan Nöteberg's blog

Archive for the 'Howto' Category

Alphabet, string, language…

Published 2012-01-17 C# , Howto , Java , Programming , Python , Regex , Regexp , Regular Expressions , Ruby , Scala , Technology Leave a Comment
Tags: alphabet, language, string

An alphabet is a finite, nonempty set of symbols. Here are some examples of alphabets:

The binary alphabet {0, 1} contains only two symbols, namely 1 and 0.
The American Standard Code for Information Interchange, abbreviated ASCII, contains 128 symbols. Only 95 of these are printable. The others, such as Backspace (ASCII 8), are also symbols in our definition.
The set of the 95 printable symbols in ASCII is also an alphabet.
Unicode contains over 100,000 symbols – Arabic, Chinese, Latin and many other types. But even if it’s a very large number, it is still a finite number of symbols. Unicode is therefore an alphabet.
The set of the Cyrillic symbols in Unicode is an alphabet.
We can construct an alphabet consisting of a blue and a white dot. That is an alphabet consisting of two symbols, just like the binary alphabet.

Did you by any chance know that the word alphabet comes from alpha and beta, the first two letters of the 3000 year old Phoenician alphabet, and that alpha meant ox and beta meant house? However, the order of symbols does not make an alphabet unique. Thus, {a, b} is the same alphabet as {b, a}. The empty set — the set composed of zero symbols — is by definition not an alphabet.

A string is a finite (ordered) sequence of symbols chosen from an alphabet. Here are some examples of strings:

0110 and 1001 are two strings from the binary alphabet.
The strings kadikoy are uskudar are constructed with symbols from the ASCII alphabet.
футбол is a string from the Cyrillic alphabet.
اللوز is a string from the Arabic alphabet.
From any alphabet, it’s possible to create an empty string, i.e. a string consisting of zero symbols. By convention, we denote that string with the character ε.

The very same symbol can occur multiple times in a string. The order is significant; gof is not the same string as fog.

A language is a countable set of strings from a fixed alphabet. The restriction is that the alphabet is finite. The language may well include an infinite number of strings. Here are some examples of languages:

All binary numbers ending with 0. It includes 10, 100, 110, etc.
All palindromes — strings that are the same forwards and backwards – constructed from the symbols of ASCII.
All strings with an even number of symbols from Unicode.
The finite set {dog, cat, bird}.
The empty set — the language with no strings. This alphabet is by convention denoted Ø.
The language {ε} consisting solely of the empty string ε.

Our focus here is on regular expressions. A regular expression is an algebraic description of an entire language. All languages can’t be described by regular expressions. No regular expression can for example describe the language consisting of all palindromes created with symbols from ASCII. I will try to convince you that regular expressions are ridiculously simple and amazingly powerful. Regular expressions are based on two basic rules:

The empty string ε is a regular expression. It describes a language that has one single string, namely the empty string.
If a symbol a is a member of an alphabet, then a is a regular expression. It describes a language that has the string a as its only member.

That was easy, wasn’t it? In addition to the two basic rules, we have three operators that we’ll catch in four more rules. Out of pure laziness, we have conventions for precedence between the three operators, but more on that in an upcoming blog post. First, you should try the two basic rules in IRB. We write regular expressions between two dashes. You can e.g. write the regulars expression a as /a/. IRB can help us to figure out if a string is in a language described by a particular regular expression:

'a'[/a/] #=> "a" – the string a is matched by the regular expression /a/
''[/a/] #=> nil – the empty string is not matched by the regular expression /a/
'b'[/a/] #=> nil – the string b is not matched by the regular expression /a/
'a'[//] #=> "" – the string a is not matched by the empty regular expression / /

Only when IRB returns the entire string, it’s matched by the regular expression.

The forward tracking quantifier modifier

Published 2012-01-16 C# , Howto , Java , Programming , Python , Regex , Regexp , Regular Expressions , Ruby , Scala , Technology Leave a Comment
Tags: lazy, quantifier

Because of backtracking, we might sometimes match more than we hoped for. The task below is to catch all the div tags in an HTML document and put them in a vector. Our naïve solution gives the wrong answer:

'<div>a</div><span>c</span><div>b</div>'.scan /<div>.*<\/div>/ #=> ["<div>a</div><span>c</span><div>b</div>"]

Quantifiers are greedy in regex. They devour as much as they can. The dot in the idiom .* matches anything except newline (remember Barbapapa?). And the asterisk means that this anything is repeated as many times as possible. Since the string ends with a “</div>” the entire substring “a</div><span>c</span><div>b” will be consumed by .*.

There are many stories about greedy people who claim more than they need. As Louis Blanc wrote already 1840 in The Organization of Work: "From each according to his abilities, to each according to his needs." We don't think that the asterisk and the dot in the above example needs to consume more than the substring "<div>a</div>". Alexander Pushkin describes in The Tale of the Fisherman and the Fish how a magic fish promises to fulfill any of the fisherman's whishes. The fisherman's wife starts asking the fish for bigger and better things -- and she gets them -- until she eventually wants to become Ruler of the Sea. Then the magic fish takes back everything he gave the fisherman's wife.

As a complement to backtracking, regex also provides forward tracking. The quantifier tries to take as little as it can and then holds to see if the whole expression can be matched. If the entire expression can't be matched, then the quantifier will capture one more letter and holds to see if it's now possible to match everything. The method is repeated until either we can match everything or we can confirm that there's no possible way to create a match. Does it matter if we use forward tracking instead of backtracking? Well, the strings that can be matched with backtracking can also be matched with forward tracking and vice versa. But, when there are multiple possible matches, forward tracking will sometimes choose a different match than backtracking does.

There is no special symbol for forward tracking quantifiers. Instead, there's modifier symbol -- written as a question mark -- that can be used right after any quantifier. While * means repeat as many times as possible, *? means repeat as few times as possible. Similarly, we can modify all the other quantifiers:

At least one, as few as possible: +?
Zero or one, preferably zero: ??
Between 3 and 5, as few as possible: {3.5}?

Note that the question mark that modifies quantifiers isn't the same question mark that's used as the conditional quantifier. They can even be used in conjunction, as ?? shows above.

Here are some examples. The first one is the solution to the div tag problem:

'<div>a</div><span>c</span><div>b</div>'.scan /<div>.*?<\/div>/ #=> ["<div>a</div>", "<div>b</div>"]
'aa'[/a?/] #=> "a"
'aa'[/a??/] #=> ""
'aaaaa'[/a{2,4}/] #=> "aaaa"
'aaaaa'[/a{2,4}?/] #=> "aa"
'aaaaa'[/a{2,}/] #=> "aaaaa"
'aaaaa'[/a{2,}?/] #=> "aa"
'aaaaa'[/a{,4}/] #=> "aaaa"
'aaaaa'[/a{,4}?/] #=> ""

Regex memorizing — here’s the pushdown automaton

Published 2011-06-20 finite automata , Howto , Programming , Pushdown Automata , Regex , Regexp , Regular Expressions Leave a Comment

Pushdown automaton that matches all strings with
the same number of white and blue dots.

Formal regular expressions can be described by a finite automaton, but modern regex engines support un-regular operators. The problem with finite automata is that they don’t have any memory. Once they are in a state, they have no idea, how they got there. Wise guys invented the stack. When we add a stack to a finite automaton it becomes very powerful, but also quite complex. And of course, it’s not a finite automaton anymore – it’s a pushdown automaton. Why do I then describe the regex engines as finite automata when pushdown automata is a superset of finite automata?

The finite automaton reads a tape serially. Every new symbol read from the tape, initiates a transition in the automaton from the current state to a new state (the new state may be the same state as the current state). If we are in an accept state when we have read all the tape, then we have a match. In pushdown automata, we add a stack. For every iteration, the pushdown automaton may read a symbol from the tape, pop a symbol from the stack, or both. Depending on the current state, the symbol read from the tape and/or the symbol popped from the stack, the pushdown automaton can now initiate a state transition, push a symbol to the stack, or both. If we end up in a accept state when all the tape is read and the stack is at that time empty then we have a match.

The figure above shows a pushdown automaton that matches any input with the same number of blue and white dots – something that is impossible to describe with a finite automaton. This automaton has two states: a start state and an accept state. The four icons in the middle represents that a dot is popped or pushed from the stack. Suppose that the input is blue-white-white-blue:

Read blue dot and make a transition from the start state, through the third stack icon from the top – i.e. a blue dot is pushed to the stack – and back to the start state.
Read white dot and make a transition from the start state, through the first stack icon – i.e. a blue dot is popped from the stack – and back to the start state. Now the stack is empty.
Read white dot and make a transition from the start state, through the second stack icon from the top – i.e. a white dot is pushed to the stack – and back to the start state.
Read blue dot and make a transition from the start state, through the fourth stack icon – i.e. a white dot is popped from the stack – and to the accept state. Now the stack is empty again and all the input is read. It’s a match.

You can probably feel that the pushdown automaton gives us a tool for all kind of recursive implementations. Now that you understand how, I’ll go back to finite automata in all explanations where possible. It’s important for you to understand e.g. what backtracking and greediness does to performance and what input that will be matched. You don’t need a complicated pushdown automaton to learn that. We’ll stick to finite automaton in this book and at the same time remember that many operators in modern regex engines rely on a stack.

By the way: Did you notice the corner case bug in the pushdown automaton above? Doesn’t an empty input string have the same number of blue and white dots?

Dynamic typing inside the Java Virtual Machine

Published 2011-06-1 Bytecode , Howto , Java , JVM , Programming Leave a Comment
Tags: boxing, dynamic typing, static typing, type system

Take a look at the following Java program. Albeit it’s dynamic typing style, it’s accepted by the Java compiler javac:

public class Dynamic {
  public static void main(String[] args) {
	Object o;
	o = System.out;
	o = System.in;
	o = 1;
	o = "Hello World";
  }
}

The method body part of the compiled JVM code looks something like this:

   0:   getstatic       #2; //Field java/lang/System.out:Ljava/io/PrintStream;
   3:   astore_1
   4:   getstatic       #3; //Field java/lang/System.in:Ljava/io/InputStream;
   7:   astore_1
   8:   iconst_1
   9:   invokestatic    #4; //Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
   12:  astore_1
   13:  ldc     #5; //String Hello World
   15:  astore_1

At line 0, 4, 8, 9 and 13 something is pushed on the operand stack. Line 3, 7, 12 and 15 pop the top record from the operand stack and assign it to local variable #1. Line 8-9 is called boxing. Since o is a java.lang.Object and Java doesn’t allow java.lang.Object to take a primitive value, like the int 1, this value is boxed in a java.lang.Integer object at line 9. The Java compiler javac created line 9 because Java is based on static typing.

Dynamic typing means that values have types but variables don’t. In static typing, variables have types and are restricted to not refer to any random type of value. The local variable o has type java.lang.Object and can only refer to values of type java.lang.Object or its subtypes.

Unlike Java, local JVM variables are dynamically typed — NOT statically typed. We can safely remove line 9 (the conversion from int to java.lang.Integer) from the JVM code and it will still be perfectly valid JVM code. Local variable #1 will then in turn be assigned a PrintStream, an InputStream, an int and a String. This is possible because local variable #1 – like all local variables in the JVM – has no type.

Complicated logic calls for regex

Published 2011-05-30 Howto , Java , Programming , Regex , Regexp , Regular Expressions 1 Comment
Tags: ISO 8601

When is regex the proper tool? One use case is when you try to verify a text, and the verification rules have complicated logic. I found the following Java method in real production code. It verifies that a time zone designator adheres to the ISO 8601 standard:

public boolean isTimeDesignator(String designator) {
  if (designator.equals("Z")) {
    return true;
  } else if (designator.startsWith(" ") && designator.trim().equals("UTC")) {
    return true;
  } else if (designator.startsWith("+") || designator.startsWith("-")) {
    try {
      int hour = Integer.parseInt(designator.substring(1,3));
      int minute;
      if (3 == designator.length()) {
        minute = 0;
      } else if (5 == designator.length()) {
        minute = Integer.parseInt(designator.substring(3,5));
      } else if (6 == designator.length() && ':' == designator.charAt(3)) {
        minute = Integer.parseInt(designator.substring(4,6));
      } else {
        return false;
      }
      return 0 <= hour && 24 >= hour && 0 <= minute && 59 >= minute;
    } catch (NumberFormatException e) {
      return false;
    }
  }
    
  return false;
}

Only counting the if and else, there are 7 ways the control flow can traverse this code. Adding the NumberFormatException there’s another 3. These ten routes need to be covered by tests.

In ISO 8601, global time is always represented as an offset to Coordinated Universal Time, abbreviated UTC. UTC is informally equivalent to the Greenwich Mean Time, also known as GMT. The designator is an offset in hours and minutes to UTC. Hours are mandatory, but minutes and a colon in-between minutes and hours are optional. Offset zero can be represented as a space and then ‘UCT’ or as ‘Z’. Complicated?

In regex — still in Java — it’s rather crisp to verify:

public boolean isTimeDesignator(String designator) {
  return designator.matches("Z| +UTC|[+-]([01]\\d|2[0-4])(:?[0-5]\\d)?");
}

The latter solution may seem cryptic, for people without experience in regex. But if you think about it, the first solution is cryptic for anyone not proficient in imperative coding. And if you ask me, the first solution is hard to follow for anybody. To understand a regex, you need to understand regex. That’s a tautology. With regex in your repertoire, some problem classes can be solved much more smoothly and the solutions are easier to maintain.

Regex syntax and semantics varies

Published 2011-05-4 Howto , Java , Programming , Regex , Regexp , Regular Expressions , Ruby , Technology 1 Comment

Regex engines do differ in syntax and semantics. This is one reason why you can’t just find an expression with Google and use it in your code – without fully understand it.

Try for example the following in JIRB, the interactive JRuby tool:

irb(main):001:0> require 'java' => true irb(main):002:0> java.util.regex.Pattern.compile("a$").matcher("a\nb").find => false irb(main):003:0> "a\nb"[/a$/] => "a"

What happened?

The regex /a$/ matches the letter a just before something checked by a dollar sign assertion. The assert criteria is, by default, not the same in Ruby and Java. In Java, by default, the dollar sign matches at the end of the whole text and before any final line breaks. In Ruby, the dollar sign match at the end of every single line.

Here’s what the three lines of code above means:

First, we need to include the Java libraries by writing require 'java'. This might not be necessary, depending on your setup.
We compile a Java regex and test if part of the string of ‘a’ and ‘b’ with newline in-between can be matched. It can’t.
We compile the same regex in Ruby and test if part of the string of ‘a’ and ‘b’ with newline in-between can be matched. It can.

This is just one of many examples. If you are going to use regexes in your program, you need to understand them. It’s as simple as that.

Regex slides

Published 2011-03-21 Howto , Programming , Regex , Regexp , Regular Expressions , Technology 2 Comments
Tags: tad011, turku agile day

Slides from my regex session at Turku Agile Day are now available below and at Slideshare:

If you can’t see the whole picture due to Slideshare’s embed limits, click ‘zoom’ -> ‘zoom to page’ in the Slideshare tool bar above.

Regex at Windows’ command line

Published 2010-12-2 Howto , Regex , Regular Expressions 2 Comments
Tags: egrep, findstr, kleene, kleene star, windows

Regular Expressions are patterns that match strings in text files or text streams. All strings that can possibly be matched by a particular expression are collectively a regular language. Every regular language has at least one corresponding finite automaton. The finite automaton is a very simple state machine.

In order to match regular languages we need only three operations – Les trois Mousqetaires de Regex:

Kleene star, i.e * – repeat the preceding pattern zero or more times
Concatenation – match two consecutive patterns, e.g. 73 match 7 followed by 3
Alternation – match exactly one out of a list of patterns, i.e. logical OR

The precedence is as the list above. Sometimes, that’s not enough and thus we also need D’Artagnan, the fourth musketeer. I’m talking about parenthesis for grouping – just like in any other programming language.

The unix command-line tool egrep meets the regular expressions litmus test. It supports concatenation, Kleene star, alternation, and grouping.

What about Windows then?

There’s a built-in command-line tool in Windows called findstr. And findstr supports Kleene star and concatenation. That’s 2/4 of the mandatory operations we need to match regular languages. Unlike egrep, it lacks alternation and forced precedence with parenthesis – and thus you can’t use findstr for regular expressions.

What to do then if you want to write regular expressions at the command line in Windows? There are at least two alternatives:

UnxUtils are native Win32 ports of common GNU utilities. Native means that the executables only depend on the Microsoft C-runtime (msvcrt.dll) and not an emulation layer. One of the executables is egrep.
Cygwin is a Linux API emulation layer and a vast number of tools – among them egrep.

D’Artagnan and his three musketeer friends Athos, Porthos, and Aramis lived by the motto tous pour un, un pour tous. If you don’t have grouping and the three mandatory operations, then you can’t write regular expressions.

To translate idioms

Published 2010-10-15 Agile , Extreme Programming , Howto , XP 4 Comments
Tags: agile samurai, jonathan rasmusson

Currently, I’m translating Jonathan Rasmusson’s excellent book The Agile Samurai into Swedish on behalf of the Swedish publisher Studentlitteratur. The language is informal and simple. There are very few words that I have to look up in a dictionary. A more significant challenge is the idioms.

An idiom is an expression that has a figurative meaning in common use. This meaning differs from the literal meaning. It is not a proverb or an aphorism.

There are at least 25 000 idioms in American English. How can you, as a translator, understand unfamiliar idioms? With the right keywords, you can get help from Google.

JR writes “this is your chance to lay it on the line”. I realize that this is not about to put something on a line or to add it in a queue. But I have no idea what it really means. So, I searched Google for idiom+lay+line – like this:

http://www.google.com/search?q=idiom+lay+line

The first page found explains: ”lay it on the line (informal) to tell someone the truth although it will upset them. ’You’re just going to have to lay it on the line and tell her her work’s not good enough.’”

So it’s about being honest. It’s quite a difference between these two:

This is your chance to put it on the line (or add it in the queue)
This is your chance to be honest.

The question arises: what is the corresponding idiom in Swedish, i.e. the target language? To translate literally word by word is obviously not an option. It would be incomprehensible to Swedish readers. But there are Swedish idioms such as “var rakryggad” (keep your back straight) which roughly means the same thing.

However, just because the author used an idiom in the original text, it need not be an idiom in the translation. Many times, the best way is to descend the translators own personal literary ambitions and simply translate to a straight explanation: “This is your chance to be honest”.

Regex is not Regular

Published 2010-09-8 Howto , Programming , Regex , Regular Expressions , Ruby Leave a Comment
Tags: perl

Regular expressions span exactly the same languages as the mathematical construction called Finite atomata. With the Pumping lemma, we can prove that it’s impossible to create regular expressions for many problems, e.g.:

All palindromes
All text strings that doesn’t consist of a prime number of identical characters

Since Regular expressions have become popular as extensions to imperative programming languages, new features have been added. Languages from Context-free grammars and Pushdown automata (essentially a finite automata with an attached stack), can be matched with these features. Regular expressions are Type-3 and Context-free grammars are type-2 in the Chomsky hierarchy.

To not be confused we call these built-in languages that are more than Type-3, Regex. Regexes are more powerful than Regular expressions.

Non regular prime number finder

With the (non regular) feature back-reference, it’s possible to create a regex that only match strings with a prime number of identical characters:

irb(main):001:0> r = /^.?$|^((.)\2+?)\1+$/ => /^.?$|^((.)\2+?)\1+$/ irb(main):002:0> r.match "22" => nil irb(main):003:0> r.match "333" => nil irb(main):004:0> r.match "4444" => #<MatchData "4444" 1:"44" 2:"4"> irb(main):005:0> r.match "55555" => nil irb(main):006:0> r.match "tttttt" => #<MatchData "tttttt" 1:"tt" 2:"t">

Non regular palindrome finder

If we also add the (non regular) feature recursion, we can match all palindromes:

irb(main):001:0> p = /\A(?<palindrome>|.|(?:(?<prefix>.)\g<palindrome>\k<prefix+0>))\z/ => /\A(?<palindrome>|.|(?:(?<prefix>.)\g<palindrome>\k<prefix+0>))\z/ irb(main):002:0> p.match "otto" => #<MatchData "otto" palindrome:"otto" prefix:"t"> irb(main):003:0> p.match "dallas sallad" => #<MatchData "dallas sallad" palindrome:"dallas sallad" prefix:"s"> irb(main):004:0> p.match "rais air" => nil irb(main):005:0> p.match "1010" => nil

« Previous Page — Next Page »

Staffan Nöteberg's blog

Archive for the 'Howto' Category

Alphabet, string, language…

The forward tracking quantifier modifier

Regex memorizing — here’s the pushdown automaton

Dynamic typing inside the Java Virtual Machine

Complicated logic calls for regex

Regex syntax and semantics varies

Regex slides

Regex at Windows’ command line

To translate idioms

Regex is not Regular

Recent Posts

Most popular

Links

RSS feed

Staffan's just-read

Twitter feed

Follow “Staffan Nöteberg's blog”