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

[Programming] React Leaflet; AliExpress Independent Sellers; Applebaum - Twilight of Democracy; [Politics] Back + US Elections; [Programming,Exercise] Simple Timer Script; [News] 2019: The year revolt went global; [Politics] The world's most-surveilled cities; [Bike] Hope Freehub; [Restaurant] Mama Chau's (Chinese, Providencia); [Politics] Brexit Podcast; [Diary] Pneumonia; [Politics] Britain's Reichstag Fire moment; install cairo; [Programming] GCC Sanitizer Flags; [GPU, Programming] Per-Thread Program Counters; My Bike Accident - Looking Back One Year; [Python] Geographic heights are incredibly easy!; [Cooking] Cookie Recipe; Efficient, Simple, Directed Maximisation of Noisy Function; And for argparse; Bash Completion in Python; [Computing] Configuring Github Jekyll Locally; [Maths, Link] The Napkin Project; You can Masquerade in Firewalld; [Bike] Servicing Budget (Spring) Forks; [Crypto] CIA Internet Comms Failure; [Python] Cute Rate Limiting API; [Causality] Judea Pearl Lecture; [Security, Computing] Chinese Hardware Hack Of Supermicro Boards; SQLAlchemy Joined Table Inheritance and Delete Cascade; [Translation] The Club; [Computing] Super Potato Bruh; [Computing] Extending Jupyter; Further HRM Details; [Computing, Bike] Activities in ch2; [Books, Link] Modern Japanese Lit; What ended up there; [Link, Book] Logic Book; Update - Garmin Express / Connect; Garmin Forerunner 35 v 230; [Link, Politics, Internet] Government Trolls; [Link, Politics] Why identity politics benefits the right more than the left; SSH Forwarding; A Specification For Repeating Events; A Fight for the Soul of Science; [Science, Book, Link] Lost In Math; OpenSuse Leap 15 Network Fixes; Update; [Book] Galileo's Middle Finger; [Bike] Chinese Carbon Rims; [Bike] Servicing Shimano XT Front Hub HB-M8010; [Bike] Aliexpress Cycling Tops; [Computing] Change to ssh handling of multiple identities?; [Bike] Endura Hummvee Lite II; [Computing] Marble Based Logic; [Link, Politics] Sanity Check For Nuclear Launch; [Link, Science] Entropy and Life; [Link, Bike] Cheap Cycling Jerseys; [Link, Music] Music To Steal 2017; [Link, Future] Simulated Brain Drives Robot; [Link, Computing] Learned Index Structures; Solo Air Equalization; Update: Higher Pressures; Psychology; [Bike] Exercise And Fuel; Continental Race King 2.2; Removing Lowers; Mnesiacs; [Maths, Link] Dividing By Zero; [Book, Review] Ray Monk - Ludwig Wittgenstein: The Duty Of Genius; [Link, Bike, Computing] Evolving Lacing Patterns; [Jam] Strawberry and Orange Jam; [Chile, Privacy] Biometric Check During Mail Delivery; [Link, Chile, Spanish] Article on the Chilean Drought; [Bike] Extended Gear Ratios, Shimano XT M8000 (24/36 Chainring); [Link, Politics, USA] The Future Of American Democracy; Mass Hysteria; [Review, Books, Links] Kazuo Ishiguro - Never Let Me Go; [Link, Books] David Mitchell's Favourite Japanese Fiction; [Link, Bike] Rear Suspension Geometry; [Link, Cycling, Art] Strava Artwork; [Link, Computing] Useful gcc flags; [Link] Voynich Manuscript Decoded; [Bike] Notes on Servicing Suspension Forks; [Links, Computing] Snap, Flatpack, Appimage; [Link, Computing] Oracle is leaving Java (to die); [Link, Politics] Cubans + Ultrasonics; [Book, Link] Laurent Binet; VirtualBox; [Book, Link] No One's Ways; [Link] The Biggest Problem For Cyclists Is Bad Driving; [Computing] Doxygen, Sphinx, Breathe; [Admin] Brokw Recent Permalinks; [Bike, Chile] Buying Bearings in Santiago; [Computing, Opensuse] Upgrading to 42.3; [Link, Physics] First Support for a Physics Theory of Life; [Link, Bike] Peruvian Frame Maker; [Link] Awesome Game Theory Tit-For-Tat Thing; [Food, Review] La Fabbrica - Good Italian Food In Santiago; [Link, Programming] MySQL UTF8 Broken; [Link, Books] Latin American Authors

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

I Just Wrote a Regular Exression Engine!

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

Date: Sat, 14 Mar 2009 22:02:50 -0300 (CLST)

Heh.  I just finished a regular expression engine in Python.  It's the
"real deal" in that it "compiles" to a finite state machine (so it runs in
time proportional to the length of the string to be matcher).  It doesn't
compress multiple character jumps into a single step, but it does
otherwise generate a compact machine (as far as I understand these
things).

Being pure Python it's both better and worse than the standard "re"
package.  In fact it's mainly worse - it must be slower, it doesn't match
sub-expressions, and it has a very, very simple syntax.

But it does have a few advantages.  First, it's a generator, so it yields
each match as it finds it.  Second, it takes a sequence, rather than a
string as an argument, which means that the entire string doesn't have to
be read into memory.  Third, I understand it and can take it apart and
extend it, which means I can add Python functions to it.  I could even
make it work with arbitrary lists (non-characters) pretty easily.

Actually, as I implemented this, I realised that there were various things
about the standard Python regexp implementation that I didn't understand
that well, so some of the above may be wrong.  Next thing to do is to look
more closely at the standard library (yes, perhaps I should have started
that way, but way back then I didn't know what to ask).

Here's the test I just got running.  Note that the matcher (the FSM) takes
a list of regexps, and that each has a tag (here, integers).  The results
include the tags.  Also, that's the full regexp syntax - all I support is
literal characters, ranges, and "*".

  def test_all(self):
    regexps = [_parser(1, 'a*'),
               _parser(2, 'a[a-cx]*'),
               _parser(3, 'aax')]
    fsm = Fsm(regexps)
    results = list(fsm.all_for_string('aaxbxcxdx'))
    assert results == [(1, ''), (1, 'a'), (2, 'a'),
                       (1, 'aa'), (2, 'aa'), (3, 'aax'),
                       (2, 'aax'), (2, 'aaxb'),
                       (2, 'aaxbx'), (2, 'aaxbxc'),
                       (2, 'aaxbxcx')]

The source will be in the next LEPL release.

Andrew

Corrected Test

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

Date: Sat, 14 Mar 2009 22:11:57 -0300 (CLST)

The test I meant to write (includes () grouping for *):

  def test_all(self):
    regexps = [_parser(1, 'a*'),
               _parser(2, 'a([a-c]x)*'),
               _parser(3, 'aax')]
    fsm = Fsm(regexps)
    results = list(fsm.all_for_string('aaxbxcxdx'))
    assert results == [(1, ''), (1, 'a'), (2, 'a'),
                       (1, 'aa'), (2, 'aax'), (3, 'aax'),
                       (2, 'aaxbx'), (2, 'aaxbxcx')]

Also, apologies for typos in text/title.  Given the nature of this
(email-based) blog it's too much effort to always be correcting things...

Andrew

Incomplete

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

Date: Sun, 15 Mar 2009 10:34:59 -0400 (CLT)

Ooops.  I had ignored embedded alternatives, only allowing a choice at the
start, thinking that I was not losing anything.  But in fact that means
the current implementation has no backtracking.  Fortunately, I don't
think it will be hard to extend.

Andrew

Possibly Complete

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

Date: Sun, 15 Mar 2009 21:08:14 -0400 (CLT)

Hmm.  I implemented choices without thinking that much, and now it strikes
me that there is no backtracking - the FSM just transitions away...  I
guess that makes sense?  I need to sleep on it.

Anyway, here's the current test:

    regexps = [unicode_parser(1, 'a*'),
               unicode_parser(2, 'a([a-c]x|axb)*'),
               unicode_parser(3, 'aax')]
    fsm = SimpleFsm(regexps, UNICODE)
    results = list(fsm.all_for_string('aaxbxcxdx'))
    assert results == [(1, ''), (1, 'a'), (2, 'a'), (1, 'aa'),
                       (2, 'aax'), (3, 'aax'), (2, 'aaxb'),
                       (2, 'aaxbx'), (2, 'aaxbxcx')], results

(The initial list could now be written as a single expression, except that
there is no way to specify a label in-line).

Andrew

Does Make Sense

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

Date: Sun, 15 Mar 2009 21:34:24 -0400 (CLT)

Of course it makes sense - my FSM is deterministic (which means it may
need exponential size for the lookup table in certain cases).

Also, I don't have "epsilon"?  Am I still incomplete?  I think so....
Perhaps best to add it with "?"?  In fact, perhaps I do have epsilon if I
just relax the parser to accept, for example, "(a|)"...

Should probably add "." and "^" too (although both those clearly sugar).

Andrew

Comment on this post