Posts

Common Optimizations for Levenshtein Edit Distance

I have been studying algorithms to compute the Levenshtein edit distance between two strings, which is defined as the minimum number of “edits” required to transform one string into another string. This is useful for a variety of things, from DNA sequence alignment to spell correction to address validation. I am studying it to resolve misspelled and OCR’ed scientific names of organisms to their real names, a famous problem in the field.
read more
Posts

Making a Pratt Parser Generator Part 1

A brief history of the Pratt parsing algorithm The history of programming language parsers is dominated by the thorny challenge of parsing expressions, mathematical expressions in particular, taking into account the precedence of operators in the expressions. Modern formal language theory began with the work of Noam Chomsky in the 1950s, in which Chomsky lays out a mathematical framework for linguistics. Under this mathematical framework, languages exist within a hierarchy of languages defined according to how difficult the language is to parse.
read more
Posts

Defining the Wolfram Language Part 2: Operator Properties

In this third installment of our n part series, “Defining the Wolfram Language,” we begin to study the properties, namely the arity, affix, associativity, and precedence, of the Mathematica operators we found in Part 1. If we ended Part 1 proud of our accomplishment—perhaps even a little smug—then we will get reacquainted with our humility in this article.

read more
Posts

Generalizing PEMDAS: What is an operator?

In programming languages, an operator is a symbol used to represent a specific operation such as subtraction of integers or dereferencing a pointer. The symbols +, *, and ! are commonly used as operators in many programming languages, for example. In this article we define some basic programming language terminology that allows us to categorize operators according to their different properties. Computation with Expressions Virtually all programming languages have expressions, like 2 + 4, which consist of operators (the + operator in 2 + 4) and their operands (or arguments; the 2 and the 4), that is, the things operators operate on.
read more
Posts

Defining the Wolfram Language Part 1: Finding Operators

Finding All Wolfram Language Operators

In this second article, Part 1 of an n part series on Defining the Wolfram Language, we start getting our hands dirty hunting down every single operator in Mathematica and each operator’s linguistic properties. To my knowledge, nobody outside of Wolfram has created such an exhaustive list before.

read more
Posts

Defining the Wolfram Language Part 0: The Challenge

What is the definition of the Wolfram Language? This is the first in a series of articles attempting to answer this question.

read more
Posts

The grammar of mathematical expressions

Using computers to do automatic translation has a long and rich history in computer science. A course in compiler construction is a veritable survey of topics in computer science running the gamut from formal languages to data structures and algorithms to Hopfcroft’s algorithm to minimize deterministic automata. One of the first things a student learns in a compiler construction course is how to formally describe the grammar of a language using (extended) Backus–Naur form (EBNF).

read more
Posts

Using Mathematica From Python

In which I show you how to programmatically interface with a Mathematica kernel from Python.

read more
Posts

What is the IELR(1) Parsing Algorithm?

This short article is for those students, programmers, and computer scientists who already have a basic idea of what a parser is and does but who want to know what that mysterious reference to “IELR(1)” means in the Bison parser generator manual. The IELR(1) Parsing Algorithm The IELR(1) parsing algorithm was developed in 2008 by Joel E. Denny as part of his Ph.D. research under the supervision of Brian A. Malloy at Clemson University.
read more