The Festival of 1 + n + f(n-1) Lights

As Hanukkah approached and I gathered my holiday supplies, I ran through my list to make sure I had everything I needed. Latkes? Check. Chcoclate Gelt? Double check. Menorah? Check. Candles? Check.... I think? How many am i going to need? Now, I could

The Heart of Pratt Parsing: Top-Down Operator Precedence

In 1973 Vaughn Pratt published a paper about a method of top down expression parsing he devised while implementing the CGOL programming language to little fan fare. And quietly it sat forgotten as the academic world did mental gymnastics around LL(1),

Compiling expressions to P-Code by AST Traversal

Initially designed in the 1970's as a "portable assembly" language to facilitate implementing Pascal compilers on the varying computer architectures of the day, P-Code is the progenator of all modern bytecode interpreters. The success of the UCSD Pasca

Ternary Search Tries: String Specific Ordered Symbol Tables

It can be posited that strings are the most important data type in computing. Without character strings, all we have is a calculator. It is strings which allow us to compose documents, read and send emails, program in anything higher level than binary,

Digital Search Trees

Digital Search Trees are an interesting data structure. Often times they are used as a gentle introduction to bit-oriented data structures, such as PATRICIA tries. Having just covered some other bit focused data structures and algorithms in the previou

Search
Recent Posts
Meta