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.¹ But computer programmers needed practical, efficient algorithms to parse computer programs for translation to machine code. Parsers of the 1950s relied on ad hoc logic rather than systematic algorithms (a feature which persists to this day, though to a much lesser degree). The 1960s was a golden age of parsing algorithm research when nearly all of the concepts and algorithms we use today were discovered and rigorously studied. By the early 1970s, parsing theory had evolved to the point that Stephen C. Johnson, a computer scientist at Bell Labs / AT&T, was able to start work on YACC (now “Yacc”), “Yet Another Compiler Compiler.”² YACC was first publically described in 1975 and shipped with Unix version 3³ and is still in use today.

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. The IELR(1) algorithm is a variation of the so-called “minimal” LR(1) algorithm developed by David Pager in 1977, which itself is a variation of the LR(k) parsing algorithm invented by Donald Knuth in 1965. The IE in IELR(1) stands for inadequacy elimination (see last section).

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.

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. This language is barrowed from mathematics where, for example, $17/2 + \sin(\pi/2)$ is an expression that evaluates to the value $19/2$. Most programming languages also have other language constructs like statements and declarations that are not expressions. In some languages, like Wolfram Language, everything is an expression. In these languages, an entire program itself is an expression, albeit possibly a very complex one, and executing a program is called evaluation.

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.

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

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).