| Andrew Cooke | Contents | Latest | RSS | Twitter | 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

Lepl parser for Python.

Colorless Green.

Photography around Santiago.

SVG experiment.

Professional Portfolio

Calibration of seismometers.

Data access via web services.

Cache rewrite.

Extending OpenSSH.

C-ORM: docs, API.

Last 100 entries

Payroll Service Quotes for Cat Soft LLC; (Beating Dead Horse) StackOverflow; Current State of Justice in China; Now Is Cat Soft LLC's Chance To Save Up To 32% On Mail; Axiom of Determinacy; Ewww; Fee Chaos Book; Course on Differential Geometry; Increase Efficiency with GPS Vehicle Tracking for Cat Soft LLC; Okay, but...; Sparse Matrices, Deep Learning; Sounds Bad; Applebaum Rape; Tomato Chutney v4; Have to add...; Culturally Liberal and Nothing More; Weird Finite / Infinite Result; Your diamond is a beaten up mess; Maths Books; Good Bike Route from Providencia / Las Condes to Panul\; Iain Pears (Author of Complex Plots); Plum Jam; Excellent; More Recently; For a moment I forgot StackOverflow sucked; A Few Weeks On...; Chilean Book Recommendations; How To Write Shared Libraries; Jenny Erpenbeck (Author); Dijkstra, Coins, Tables; Python libraries error on OpenSuse; Deserving Trump; And Smugness; McCloskey Economics Trilogy; cmocka - Mocks for C; Concept Creep (Americans); Futhark - OpenCL Language; Moved / Gone; Fan and USB issues; Burgers in Santiago; The Origin of Icosahedral Symmetry in Viruses; autoenum on PyPI; Jars Explains; Tomato Chutney v3; REST; US Elections and Gender: 24 Point Swing; PPPoE on OpenSuse Leap 42.1; SuperMicro X10SDV-TLN4F/F with Opensuse Leap 42.1; Big Data AI Could Be Very Bad Indeed....; Cornering; Postcapitalism (Paul Mason); Black Science Fiction; Git is not a CDN; Mining of Massive Data Sets; Rachel Kaadzi Ghansah; How great republics meet their end; Raspberry, Strawberry and Banana Jam; Interesting Dead Areas of Math; Later Taste; For Sale; Death By Bean; It's Good!; Tomato Chutney v2; Time ATAC MX 2 Pedals - First Impressions; Online Chilean Crafts; Intellectual Variety; Taste + Texture; Time Invariance and Gauge Symmetry; Jodorowsky; Tomato Chutney; Analysis of Support for Trump; Indian SF; TP-Link TL-WR841N DNS TCP Bug; TP-Link TL-WR841N as Wireless Bridge; Sending Email On Time; Maybe run a command; Sterile Neutrinos; Strawberry and Banana Jam; The Best Of All Possible Worlds; Kenzaburo Oe: The Changeling; Peach Jam; Taste Test; Strawberry and Raspberry Jam; flac to mp3 on OpenSuse 42.1; Also, Sebald; Kenzaburo Oe Interview; Otake (Kitani Minoru) move Black 121; Is free speech in British universities under threat?; I am actually good at computers; Was This Mansplaining?; WebFaction / LetsEncrypt / General Disappointment; Sensible Philosophy of Science; George Ellis; Misplaced Intuition and Online Communities; More Reading About Japan; Visibilty / Public Comments / Domestic Violence; Ferias de Santiago; More (Clearly Deliberate); Deleted Obit Post; And then a 50 yo male posts this...; We Have Both Kinds Of Contributors

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

Converting NFA to DFA

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

Date: Sun, 22 Mar 2009 11:40:21 -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