Author Archives: kay

Recursions in Python 3.8

Posted on 13. July 2019 by kay

In Python 3.8 we can finally write short recursive functions: >>> (fac := lambda n: (1 if n<2 else n*fac(n-1))) at 0x000001AFD258D550>; >>> fac(4) 24>>> (fac := lambda n: (1 if n<2 else n*fac(n-1))) at 0x000001AFD258D550>; >>> fac(4) 24 In … Continue reading →

Posted in General | Leave a comment

Kites on a zebra crossing: an algorithmic challenge

Posted on 9. June 2012 by kay

Forget Sudoku A couple of moons ago I stumbled across an algorithmic puzzle which I want to share. It is not too simple s.t. an efficient solution can easily be seen but also not too complicated s.t. it is beyond … Continue reading →

Posted in Algorithms | Leave a comment

Greedy grammars and Any

Posted on 20. May 2012 by kay

I only vaguely remember my first encounter with a parser generator which must by dated back to the late 1990s. I guess it was Spark by John Aycock, an Early parser. What puzzled me back then was the need to … Continue reading →

Posted in Grammars, Parsing, Python | Leave a comment

The state of the Trail parser generator

Posted on 10. April 2012 by kay

White Easter Snow came back, if only for a brief moment, to remind me laying Trail to rest until next winter… x + + + + + + + + + – – – – – – – – – … Continue reading →

Posted in Algorithms, Grammars, Langscape, Parsing, TBP, Trail | Leave a comment

LL(*) faster than LL(1)?

Posted on 12. September 2011 by kay

No jumps When I began to work on EasyExtend in 2006 I grabbed a Python parser from the web, written by Jonathan Riehl ( it doesn’t seem to be available anymore ). It was a pure Python parser following closely … Continue reading →

Posted in Algorithms, Grammars, Parsing, Python, TBP | 4 Comments

Spirits – for M.

Posted on 26. April 2011 by kay
Posted in Vision | Leave a comment

Maptrackers

Posted on 12. April 2011 by kay

From graphs to maps A *Maptracker* is a special backtracking algorithm used to check the equivalence of certain maps which can be represented as connected, directed graphs or finite state machines. It shall be described in this article. The original … Continue reading →

Posted in Algorithms | 2 Comments

Patching tracebacks

Posted on 11. April 2011 by kay

One of the problems I early ran into  when working on EasyExtend ( and later on Langscape ) was to get error messages from code execution which were not corrupt. The situation is easily explained: you have a program `P` … Continue reading →

Posted in Algorithms, Langscape, Python | Leave a comment

Fuzzy string matching II – matching wordlists

Posted on 7. January 2011 by kay

Small misspellings An anonymous programming reddit commenter wrote about my fuzzy string matching article: A maximum edit distance of 2 or 3 is reasonable for most applications of edit distance. For example, cat and dog are only 3 edits away … Continue reading →

Posted in Algorithms, Python | 3 Comments

Fuzzy string matching

Posted on 21. December 2010 by kay

A damn hot algorithm I found the following article written by Nick Johnson about the use of finite state machines for approximate  string matches i.e. string matches which are not exact but bound by a given edit distance. The algorithm … Continue reading →

Posted in Algorithms, Python | 4 Comments