
Recent Posts
Archives
 July 2019
 June 2012
 May 2012
 April 2012
 September 2011
 April 2011
 January 2011
 December 2010
 November 2010
 August 2010
 July 2010
 June 2010
 April 2010
 March 2010
 February 2010
 January 2010
 December 2009
 October 2009
 September 2009
 August 2009
 July 2009
 June 2009
 May 2009
 April 2009
 March 2009
 February 2009
Categories
Meta
Author Archives: kay
Recursions in Python 3.8
In Python 3.8 we can finally write short recursive functions: >>> (fac := lambda n: (1 if n<2 else n*fac(n1))) at 0x000001AFD258D550>; >>> fac(4) 24>>> (fac := lambda n: (1 if n<2 else n*fac(n1))) at 0x000001AFD258D550>; >>> fac(4) 24 In … Continue reading
Posted in General
Leave a comment
Kites on a zebra crossing: an algorithmic challenge
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
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
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)?
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
Maptrackers
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
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
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
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