The Aho, Sethi, Ullman Direct DFA Construction, Part 1: Constructing the Followpos Table

Todays post is a overview of a (simplified) implementation of the Aho-Sethi-Ullman DFA Construction algorithm, aka "Algorithm 3.5: Construction of a DFA from a Regular Expression" originally found in "the dragon" book[1]. I'm going to take a moment to

Procedural Map Generation with Binary Space Partitioning

When creating a classical Rogue-like and for many other dungeon based games as well, the levels of the game are procedurally generated. This is so that each play through of the game offers the player a new experience - no two games are the sam

Exact Match String Searching: The Knuth-Morris-Pratt Algorithm

Searching for the occurence of one string within the body of a larger string is a process done millions of times, and is one of the central operations in text processing. It is performed as part of  querying a search engine and whenever you press

The visitor pattern: OOP takes on the Expression Problem

The visitor pattern is a behavioral design pattern first popularized in the "Gang of Four" book. It is used to separate operations on types from the types themselves. When using the composite pattern to build an AST from a class heiracrchy, as one woul

Improving mgcLisp's define syntax

When implementing mgclisp, I took a shortcut (gasp! horror!) when implementing user defined functions. Scheme, and pretty much every other modern lisp when defining a function allows you to write something along the lines of the following expression:

Search
Recent Posts
Meta