Category Archives: Algorithms

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

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

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

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

Token Tracers

When I started programming EasyExtend in 2006 one of the major problems was the correct grammar -> NFA translation. I used big grammars and testing for correctness required lots of source code. The first heuristics I used was ugly and … Continue reading