In page 71 of Mathematics for Computer Science (page 77 in the pdf) it says that "The Turing award (the “Nobel Prize” of computer science) was ultimately bestowed on Robert Floyd, for, among other things, being discoverer of a simple program that would insert the brackets properly [into an arithmetic expression]."

What was this algorithm?

Based on the page for Floyd's award, it looks like the algorithm can be found in this paper.

  • $\begingroup$ No, I have not yet tried reading the paper. It's not a convenient time for me to do that; part of the reason I posted this here before trying to read it is so that I can find the paper again later (the other part being that if this algorithm were referenced without mentioning that he received the Turing award for it, it could be hard to find a reference) $\endgroup$ Sep 6 '18 at 3:55
  • 2
    $\begingroup$ "Inserting the brackets properly" is correct but misleading. His algorithm chooses an evaluation order for a complicated arithmetical expression that makes it take as few opcodes as possible, which on early computers would mean as few cycles as possible. $\endgroup$
    – Draconis
    Sep 6 '18 at 4:46
  • $\begingroup$ @Draconis: It's not misleading. It simply doesn't apply to the cited paper. As a description of parsing, it's a bit informal but I wouldn't say it's misleading: parsing an arithmetic expression like a+b*c is essentially the same as figuring out where to put brackets to make the expression unambiguous (without precedence rules). $\endgroup$
    – rici
    Sep 6 '18 at 16:54

The seminal paper referred to is "Syntactic Analysis and Operator Precedence" (1963), which describes the operator precedence algorithm still used by many simple expression parsers today.

The basic approach described by Floyd was not exactly new. It was described by Edsger Dijkstra in 1961; Dijsktra's procedure was a pragmatic, special-purpose algorithm used to parse Algol-60, commonly referred to as the "Shunting Yard Algorithm". Floyd's contribution was to formalise and extend the idea, making it into a practical general-purpose parsing technique.

Floyd's approach to parsing was highly influential on another young parsing investigator of the time, Donald Knuth, whose 1965 paper "On the Translation of Languages from Left to Right" introduced the LR(k) parsing algorithm, capable of parsing a much larger set of languages than operator precedence parsing. However, it was not until 1969 when Frank deRemer invented the computationally manageable LALR(1) algorithm described in "Practical Translators for LR(k) languages" that Knuth's discovery moved out of the theoretical realm and into practical compiler construction.

Floyd's 1961 paper "An algorithm for coding efficient arithmetic operations", cited in the OP, was not about parsing ("inserting brackets properly") but rather about efficiently ordering the computation of the parsed expression so as to maximize the use of scarce CPU resources, based on the very limited CPU architectures common at the time. Modern CPU architectures demand different algorithms, but parts of Floyd's 1961 algorithm can be found in simple optimizations for minimising the stack size in stack-based virtual machines (or, equivalently, the number of temporaries required in three-address-code).

For reference, a quick summary of Floyd's operator precedence algorithm. The algorithm takes as input a precedence grammar $G$, which is a context-free grammar with the property that no right-hand side contains two consecutive non-terminals. (This definition allows unit productions and null productions; in practice, these would usually be removed before proceeding since they do not participate in the parsing algorithm.)

As usual, we will write $G = \langle N, T, P, S\rangle$, where $N$ is the set of nonterminal symbols, $T$ the set of terminal symbols, $P \subset N \times (N \cup T)^*$ the set of productions and $S \in N$ the target (start) symbol. We will use uppercase letters to represent symbols in $N$, lowercase letters to represent symbols in $T$ and Greek letters to represent sentences which are elements of $(N\cup T)^*$. We write $\alpha \Rightarrow \beta$ if $\alpha$ derives $\beta$ (that is, $\alpha = \alpha_1 A \alpha_3$ and $\beta = \alpha_1\alpha_2\alpha_3$, where $A\rightarrow\alpha_2 \in P$). Also, we write $\Rightarrow^+$ and $\Rightarrow^*$ for the transitive closure and reflexive transitive closure of $\Rightarrow$.

Then we define three precedence relations over $T$: $\lessdot$, $\doteq$ and $\gtrdot$ , defined as follows:

$a \lessdot b \text{ if } A\rightarrow\alpha a B \beta \in P \text{ and either } B\Rightarrow^+b\gamma \text{ or } B\Rightarrow^+Cb\gamma$

$a \gtrdot b \text{ if } A\rightarrow\alpha B b \beta \in P \text{ and either } B\Rightarrow^+\gamma a \text{ or } B\Rightarrow^+\gamma aC$

$a \doteq b \text{ if either } A\rightarrow\alpha a b \beta \in P \text{ or } A\rightarrow\alpha a C b \beta \in P $

For an intuition about these symbols, think of a derivation being written with $\langle$ and $\rangle$ surrounding the strings replacing each nonterminal. Then $a\lessdot b$ holds if there is such a derivation where $b$ follows $a$ after a sequence of $\langle$s possibly followed by a single nonterminal. (Note that the operator property guarantees that there could not be two consecutive nonterminals.) In other words, ignoring nonterminals, $b$ is the first terminal in a reduction following $a$. $\gtrdot$ is analogous: $b$ is the first terminal following a reduction whose last terminal was $a$. (Again, the operator property guarantees that $b$ is not preceded by a nonterminal, since a nonterminal cannot follow a reduction.) $a\doteq b$ holds if $a$ and $b$ are consecutive terminals in a production, possibly separated by a (single) nonterminal.

Now, if the three precedence relations $\lessdot$, $\gtrdot$ and $\doteq$ are disjoint, we call $G$ an operator precedence grammar.

For simplicity, we will parse the augmented grammar

$$G' = \langle N\cup\{S'\}, T\cup\{\#\},P\cup S'\rightarrow S\#, S'\rangle$$

where $\#$ is some symbol not in $T$. It's easy to verify that $a\lessdot \#$ for every $a \in T$ and that there is no other precedence relation involving $\#$. We also add a $\#$ to the end of the input. Then we can parse the input as follows:

  1. Create a parser stack $S$ consisting only of the symbol $\#$.

  2. For each input symbol $b$ in turn, from left to right:

    1. While $TOP(S) \gtrdot b: \;POP(S)$
    2. If $b = \#$ and $top(S) = \#$, $ACCEPT$ the input
    3. If $TOP(S) \lessdot b \text{ or } TOP(S) \doteq b: \;PUSH(S, b)$. Otherwise, $REJECT$ the input.

In practice, we'll actually want to record the derivations discovered by this algorithm. If we $POP$ the stack in step 2.1, the popped symbols (both terminals and nonterminals) are accumulated into $X$, and just before we continue with step 2.2, we find the production in $P$ whose right-hand side is $X$, and output that production as a derivation step. If there is more than one such production, then we need some auxiliary algorithm to decide which one to use; usually, we sidestep the problem by requiring that the right-hand sides be unique. (This is also why it's common to eliminate unit and null productions, because the Floyd algorithm provides no clue whatsoever about when to insert their derivation steps.)

Like many others, I think Floyd's contribution to parsing theory was fundamental. But it is important not to be seduced by the beautiful simplicity of his algorithm. As Floyd himself noted, it suffers from two important issues:

  1. It is not sufficient to parse many programming languages, whose grammars cannot conveniently be written as operator grammars with unique right-hand sides or do not yield disjoint precedence relations.

  2. The fact that a string is accepted by the algorithm does not guarantee that the string is accepted by the grammar. Many syntactically invalid strings are accepted and must be filtered out using other algorithms.

Floyd's later work, including his investigation into bounded-context grammars, sought to overcome these shortcomings.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.