Andrew Cooke | Contents | Latest | RSS | Previous | Next

C[omp]ute

Welcome to my blog, which was once a mailing list of the same name and is still generated by mail. Please reply via the "comment" links.

Always interested in offers/projects/new ideas. Eclectic experience in fields like: numerical computing; Python web; Java enterprise; functional languages; GPGPU; SQL databases; etc. Based in Santiago, Chile; telecommute worldwide. CV; email.

Personal Projects

Choochoo Training Diary

Last 100 entries

SSL Payment Reminder; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; Bitte aktualisieren Sie Ihre Kreditkartendaten, um Unterbrechungen zu vermeiden; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; Weekend Vibes: Time to Recharge and Refresh!; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=; =?UTF-8?B?VGhlIGJlc3QgY3VzdG9taXplZCBmcmVpZ2h0IHNvbHV0aW9uIGZyb20gRWFzZSBmcmVpZ2h0?=; =?UTF-8?B?RXhjbHVzaXZlIEVhc2VGcmVpZ2h0IEZyZWlnaHQgU2VydmljZXMgdGFpbG9yZWQganVzdCBmb3IgeW91?=

© 2006-2017 Andrew Cooke (site) / post authors (content).

Converting NFA to DFA

From: "andrew cooke" <andrew@...>

Date: Sun, 22 Mar 2009 14:07:07 -0400 (CLT) 

Generating an NFA from a regular expression is fairly easy (it's only
taken me a couple of weeks and a rewrite to work out what to do!).  But I
couldn't see how to go from NFAs to DFAs.  It's explained nicely in these
slides -
http://www.mit.edu/~6.035/lectures-2004/RegularExpressionsandGrammars.ppt
(slides 25 and 26).

Apparently it's called "Thompson's Construction".

However, it seems that it's n^2, while the Dragon book describes a nlog(n)
approach.

The Rex toolkit extends the Dragon book approach further with the "tunnel
algorithm", described in
ftp://www.cocolab.com/products/cocktail/doc.pdf/scangen.pdf

That last paper is very specific to lexers (the only choice, at least in
the example, is at the start), but that's exactly what I want.

Andrew

Python Code to Compile Regexps

From: andrew cooke <andrew@...>

Date: Fri, 4 Dec 2009 17:40:44 -0300 

This page gets a surprising number of hits.  I don't know if it's any
use, but the code I wrote (which just follows the basic Thompson's
algorithm - nothing special) is visible at
http://code.google.com/p/lepl/source/browse/src/lepl/regexp/core.py

That's part of LEPL, which is a parser for Python (and which includes
a pure-python regexp engine).  For more info see
http://www.acooke.org/lepl/

Andrew

Comment on this post