Chapter 7 Recursive Data Types164
Expression Parsing
During the early development of computer science in the 1950’s and 60’s, creation
of effective programming language compilers was a central concern. A key aspect
in processing a program for compilation was expression parsing. One significant
problem was to take an expression likexCyz^2 yC 7andput inthe brackets that determined how it should be evaluated —should it beŒŒxCyçz^2 yçC7;or;
xCŒyz^2 ŒyC7çç;or;
ŒxCŒyz^2 ççŒyC7ç;or:::‹The Turing award (the “Nobel Prize” of computer science) was ultimately be-
stowed on Robert W Floyd, for, among other things, being discoverer of a simple
program that would insert the brackets properly.
In the 70’s and 80’s, this parsing technology was packaged into high-level
compiler-compilers that automatically generated parsers from expression gram-
mars. This automation of parsing was so effective that the subject no longer
demanded attention. It largely disappeared from the computer science curriculum
by the 1990’s.The matched strings can be nicely characterized as a recursive data type:Definition 7.2.1.Recursively define the set, RecMatch, of strings as follows:
Base case: 2 RecMatch. Constructor case: Ifs;t 2 RecMatch, then
[s]t 2 RecMatch:Here[s]trefers to the concatenation of strings which would be written in full
as
[.s.]t//:
From now on, we’ll usually omit the “’s.”
Using this definition, 2 RecMatch by the Base case, so lettingsDtDin
the constructor case implies
[]D[ ] 2 RecMatch: