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(n-1))) <function <lambda> at 0x000001AFD258D550> >>> fac(4) 24>>> (fac := lambda n: (1 if n<2 else n*fac(n-1))) <function <lambda> at 0x000001AFD258D550> … 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

. in your regular expression 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 … 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

Spirits – for M.

Posted in Vision | Leave a comment

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