Programming: Principles and Practice Using C++ (2014)

---

6.3.5 Back to the drawing board

Now, we will look at the problem again and try not to dash ahead with another half-baked solution. One thing that we did discover was that having the program (calculator) evaluate only a single expression was tedious. We would like to be able to compute several expressions in a single invocation of our program; that is, our pseudo code grows to

while (not_finished) {
read_a_line
calculate // do the work
write_result
}

Clearly this is a complication, but when we think about how we use calculators, we realize that doing several calculations is very common. Could we let the user invoke our program several times to do several calculations? We could, but program startup is unfortunately (and unreasonably) slow on many modern operating systems, so we’d better not rely on that.

As we look at this pseudo code, our early attempts at solutions, and our examples of use, several questions - some with tentative answers - arise:

1. If we type in 45+5/7, how do we find the individual parts 45, +, 5, /, and 7 in the input? (Tokenize!)

2. What terminates an input expression? A newline, of course! (Always be suspicious of “of course”: “of course” is not a reason.)

3. How do we represent 45+5/7 as data so that we can evaluate it? Before doing the addition we must somehow turn the characters 4 and 5 into the integer value 45 (i.e., 4*10+5). (So tokenizing is part of the solution.)

4. How do we make sure that 45+5/7 is evaluated as 45+(5/7) and not as (45+5)/7?

5. What’s the value of 5/7? About .71, but that’s not an integer. Based on experience with calculators, we know that people would expect a floating-point result. Should we also allow floating-point inputs? Sure!

6. Can we have variables? For example, could we write

v=7
m=9
v*m

Good idea, but let’s wait until later. Let’s first get the basics working.

Possibly the most important decision here is the answer to question 6. In §7.8, you’ll see that if we had said yes we’d have almost doubled the size of the initial project. That would have more than doubled the time needed to get the initial version running. Our guess is that if you really are a novice, it would have at least quadrupled the effort needed and most likely pushed the project beyond your patience. It is most important to avoid “feature creep” early in a project. Instead, always first build a simple version, implementing the essential features only. Once you have something running, you can get more ambitious. It is far easier to build a program in stages than all at once. Saying yes to question 6 would have had yet another bad effect: it would have made it hard to resist the temptation to add further “neat features” along the line. How about adding the usual mathematical functions? How about adding loops? Once we start adding “neat features” it is hard to stop.

From a programmer’s point of view, questions 1, 3, and 4 are the most bothersome. They are also related, because once we have found a 45 or a +, what do we do with them? That is, how do we store them in our program? Obviously, tokenizing is part of the solution, but only part.

What would an experienced programmer do? When we are faced with a tricky technical question, there often is a standard answer. We know that people have been writing calculator programs for at least as long as there have been computers taking symbolic input from a keyboard. That is at least for 50 years. There has to be a standard answer! In such a situation, the experienced programmer consults colleagues and/or the literature. It would be silly to barge on, hoping to beat 50 years of experience in a morning.

6.4 Grammars

There is a standard answer to the question of how to make sense of expressions: first input characters are read and assembled into tokens (as we discovered). So if you type in

45+11.5/7

the program should produce a list of tokens representing

45
+
11.5
/
7

A token is a sequence of characters that represents something we consider a unit, such as a number or an operator.

After tokens have been produced, the program must ensure that complete expressions are understood correctly. For example, we know that 45+11.5/7 means 45+(11.5/7) and not (45+11.5)/7, but how do we teach the program that useful rule (division “binds tighter” than addition)? The standard answer is that we write a grammar defining the syntax of our input and then write a program that implements the rules of that grammar. For example:

// a simple expression grammar:
Expression:
Term
Expression "+" Term // addition
Expression "-" Term // subtraction
Term:
Primary
Term "*" Primary // multiplication
Term "/" Primary // division
Term "%" Primary // remainder (modulo)
Primary:
Number
"(" Expression ")" // grouping
Number:
floating-point-literal

This is a set of simple rules. The last rule is read “A Number is a floating-point-literal.” The next-to-last rule says, “A Primary is a Number or '(' followed by an Expression followed by ')'.” The rules for Expression and Term are similar; each is defined in terms of one of the rules that follow.

As seen in §6.3.2, our tokens - as borrowed from the C++ definition - are

• floating-point-literal (as defined by C++, e.g., 3.14, 0.274e2, or 42)

• +, -, *, /, % (the operators)

• (, ) (the parentheses)

From our first tentative pseudo code to this approach, using tokens and a grammar is actually a huge conceptual jump. It’s the kind of jump we hope for but rarely manage without help. This is what experience, the literature, and Mentors are for.

At first glance, a grammar probably looks like complete nonsense. Technical notation often does. However, please keep in mind that it is a general and elegant (as you will eventually appreciate) notation for something you have been able to do since middle school (or earlier). You have no problem calculating 1-2*3 and 1+2-3 and 3*2+4/2. It seems hardwired in your brain. However, could you explain how you do it? Could you explain it well enough for someone who had never seen conventional arithmetic to grasp? Could you do so for every combination of operators and operands? To articulate an explanation in sufficient detail and precisely enough for a computer to understand, we need a notation - and a grammar is a most powerful and conventional tool for that.

How do you read a grammar? Basically, given some input, you start with the “top rule,” Expression, and search through the rules to find a match for the tokens as they are read. Reading a stream of tokens according to a grammar is called parsing, and a program that does that is often called a parser or a syntax analyzer. Our parser reads the tokens from left to right, just like we type them and read them. Let’s try something really simple: Is 2 an expression?

1. An Expression must be a Term or end with a Term. That Term must be a Primary or end with a Primary. That Primary must start with a ( or be a Number. Obviously, 2 is not a (, but a floating-point-literal, which is a Number, which is a Primary.

2. That Primary (the Number 2) isn’t preceded by a /, *, or %, so it is a complete Term (rather than the end of a /, *, or % expression).

3. That Term (the Primary 2) isn’t preceded by a + or -, so it is a complete Expression (rather than the end of a + or - expression).

So yes, according to our grammar, 2 is an expression. We can illustrate the progression through the grammar like this:

This represents the path we followed through the definitions. Retracing our path, we can say that 2 is an Expression because 2 is a floating-point-literal, which is a Number, which is a Primary, which is a Term, which is an Expression.

Let’s try something a bit more complicated: Is 2+3 an Expression? Naturally, much of the reasoning is the same as for 2:

1. An Expression must be a Term or end with a Term, which must be a Primary or end with a Primary, and a Primary must start with a ( or be a Number. Obviously 2 is not a (, but it is a floating-point-literal, which is a Number, which is a Primary.

2. That Primary (the Number 2) isn’t preceded by a /, *, or %, so it is a complete Term (rather than the end of a /, *, or % expression).

3. That Term (the Primary 2) is followed by a +, so it is the end of the first part of an Expression and we must look for the Term after the +. In exactly the same way as we found that 2 was a Term, we find that 3 is a Term. Since 3 is not followed by a + or a - it is a complete Term (rather than the first part of a + or - Expression). Therefore, 2+3 matches the Expression+Term rule and is an Expression.

Again, we can illustrate this reasoning graphically (leaving out the floating-point-literal to Number rule to simplify):

This represents the path we followed through the definitions. Retracing our path, we can say that 2+3 is an Expression because 2 is a term which is an Expression, 3 is a Term, and an Expression followed by + followed by a Term is an Expression.

The real reason we are interested in grammars is that they can solve our problem of how to correctly parse expressions with both + and *, so let’s try 45+11.5*7. However, “playing computer” following the rules in detail as we did above is tedious, so let’s skip some of the intermediate steps that we have already gone through for 2 and 2+3. Obviously, 45, 11.5, and 7 are all floating-point-literals which are Numbers, which are Primarys, so we can ignore all rules below Primary. So we get:

1. 45 is an Expression followed by a +, so we look for a Term to finish the Expression+Term rule.

2. 11.5 is a Term followed by *, so we look for a Primary to finish the Term*Primary rule.

3. 7 is Primary, so 11.5*7 is a Term according to the Term*Primary rule. Now we can see that 45+11.5*7 is an Expression according to the Expression+Term rule. In particular, it is an Expression that first does the multiplication 11.5*7 and then the addition 45+11.5*7, just as if we had written 45+(11.5*7).

Again, we can illustrate this reasoning graphically (again leaving out the floating-point-literal to Number rule to simplify):

Again, this represents the path we followed through the definitions. Note how the Term*Primary rule ensures that 11.5 is multiplied by 7 rather than added to 45.

You may find this logic hard to follow at first, but many humans do read grammars, and simple grammars are not hard to understand. However, we were not really trying to teach you to understand 2+2 or 45+11.5*7. Obviously, you knew that already. We were trying to find a way for the computer to “understand” 45+11.5*7 and all the other complicated expressions you might give it to evaluate. Actually, complicated grammars are not fit for humans to read, but computers are good at it. They follow such grammar rules quickly and correctly with the greatest of ease. Following precise rules is exactly what computers are good at.

6.4.1 A detour: English grammar

If you have never before worked with grammars, we expect that your head is now spinning. In fact, it may be spinning even if you have seen a grammar before, but take a look at the following grammar for a very small subset of English:

Sentence:
Noun Verb // e.g., C++ rules
Sentence Conjunction Sentence // e.g., Birds fly but fish swim
Conjunction:
"and"
"or"
"but"
Noun:
"birds"
"fish"
"C++"
Verb:
"rules"
"fly"
"swim"

A sentence is built from parts of speech (e.g., nouns, verbs, and conjunctions). A sentence can be parsed according to these rules to determine which words are nouns, verbs, etc. This simple grammar also includes semantically meaningless sentences such as “C++ fly and birds rules,” but fixing that is a different matter belonging in a far more advanced book.

Many have been taught/shown such rules in middle school or in foreign language class (e.g., English classes). These grammar rules are very fundamental. In fact, there are serious neurological arguments for such rules being hardwired into our brains!

Now look at a parsing tree as we used above for expressions, but used here for simple English:

This is not all that complicated. If you had trouble with §6.4, then please go back and reread it from the beginning; it may make more sense the second time through!

6.4.2 Writing a grammar

How did we pick those expression grammar rules? “Experience” is the honest answer. The way we do it is simply the way people usually write expression grammars. However, writing a simple grammar is pretty straightforward: we need to know how to

1. Distinguish a rule from a token

2. Put one rule after another (sequencing)

3. Express alternative patterns (alternation)

4. Express a repeating pattern (repetition)

5. Recognize the grammar rule to start with

Different textbooks and different parser systems use different notational conventions and different terminology. For example, some call tokens terminals and rules non-terminals or productions. We simply put tokens in (double) quotes and start with the first rule. Alternatives are put on separate lines. For example:

List:
"{" Sequence "}"
Sequence:
Element
Element " ," Sequence
Element:
"A"
"B"

So a Sequence is either an Element or an Element followed by a Sequence using a comma for separation. An Element is either the letter A or the letter B. A List is a Sequence in “curly brackets.” We can generate these Lists (how?):

{ A }
{ B }
{ A,B }
{A,A,A,A,B }

However, these are not Lists (why not?):

{ }
A
{ A,A,A,A,B
{A,A,C,A,B }
{ A B C }
{A,A,A,A,B, }

This sequence rule is not one you learned in kindergarten or have hardwired into your brain, but it is still not rocket science. See §7.4 and §7.8.1 for examples of how we work with a grammar to express syntactic ideas.

6.5 Turning a grammar into code

There are many ways of getting a computer to follow a grammar. We’ll use the simplest one: we simply write one function for each grammar rule and use our type Token to represent tokens. A program that implements a grammar is often called a parser.

6.5.1 Implementing grammar rules

To implement our calculator, we need four functions: one to read tokens plus one for each rule in our grammar:

get_token() // read characters and compose tokens
// uses cin
expression() // deal with + and -
// calls term() and get_token()
term() // deal with *, /, and %
// calls primary() and get_token()
primary() // deal with numbers and parentheses
// calls expression() and get_token()

Note: Each function deals with a specific part of an expression and leaves everything else to other functions; this radically simplifies each function. This is much like a group of humans dealing with problems by letting each person handle problems in his or her own specialty, handing all other problems over to colleagues.

What should these functions actually do? Each function should call other grammar functions according to the grammar rule it is implementing and get_token() where a token is required in a rule. For example, when primary() tries to follow the (Expression) rule, it must call

get_token() // to deal with ( and )
expression() // to deal with Expression

What should such parsing functions return? How about the answer we really wanted? For example, for 2+3, expression() could return 5. After all, the information is all there. That’s what we’ll try! Doing so will save us from answering one of the hardest questions from our list: “How do I represent 45+5/7 as data so that I can evaluate it?” Instead of storing a representation of 45+5/7 in memory, we simply evaluate it as we read it from input. This little idea is really a major breakthrough! It will keep the program at a quarter of the size it would have been had we hadexpression() return something complicated for later evaluation. We just saved ourselves about 80% of the work.

The “odd man out” is get_token(): because it deals with tokens, not expressions, it can’t return the value of a sub-expression. For example, + and ( are not expressions. So, it must return a Token. We conclude that we want

// functions to match the grammar rules:
Token get_token() // read characters and compose tokens
double expression() // deal with + and -
double term() // deal with *, /, and %
double primary() // deal with numbers and parentheses

6.5.2 Expressions

Let’s first write expression(). The grammar looks like this:

Expression:
Term
Expression '+' Term
Expression '-' Term

Since this is our first attempt to turn a set of grammar rules into code, we’ll proceed through a couple of false starts. That’s the way it usually goes with new techniques, and we learn useful things along the way. In particular, a novice programmer can learn a lot from looking at the dramatically different behavior of similar pieces of code. Reading code is a useful skill to cultivate.

6.5.2.1 Expressions: first try

Looking at the Expression '+' Term rule, we try first calling expression(), then looking for + (and -) and then term():

double expression()
{
double left = expression(); // read and evaluate an Expression
Token t = get_token(); // get the next token
switch (t.kind) { // see which kind of token it is
case '+':
return left + term(); // read and evaluate a Term,
// then do an add
case '-':
return left - term(); // read and evaluate a Term,
// then do a subtraction
default:
return left; // return the value of the Expression
}
}

It looks good. It is almost a trivial transcription of the grammar. It is quite simple, really: first read an Expression and then see if it is followed by a + or a -, and if it is, read the Term.

Unfortunately, that doesn’t really make sense. How do we know where the expression ends so that we can look for a + or a -? Remember, our program reads left to right and can’t peek ahead to see if a + is coming. In fact, this expression() will never get beyond its first line: expression()starts by calling expression() which starts by calling expression() and so on “forever.” This is called an infinite recursion and will in fact terminate after a short while when the computer runs out of memory to hold the “never-ending” sequence of calls of expression(). The term recursion is used to describe what happens when a function calls itself. Not all recursions are infinite, and recursion is a very useful programming technique (see §8.5.8).

6.5.2.2 Expressions: second try

So what do we do? Every Term is an Expression, but not every Expression is a Term; that is, we could start looking for a Term and look for a full Expression only if we found a + or a -. For example:

double expression()
{
double left = term(); // read and evaluate a Term
Token t = get_token(); // get the next token
switch (t.kind) { // see which kind of token that is
case '+':
return left + expression(); // read and evaluate an Expression,
// then do an add
case '-':
return left - expression(); // read and evaluate an Expression,
// then do a subtraction
default:
return left; // return the value of the Term
}
}

This actually - more or less - works. We have tried it in the finished program and it parses every correct expression we throw at it (and no illegal ones). It even correctly evaluates most expressions. For example, 1+2 is read as a Term (with the value 1) followed by + followed by anExpression (which happens to be a Term with the value 2) and gives the answer 3. Similarly, 1+2+3 gives 6. We could go on for quite a long time about what works, but to make a long story short: How about 1-2-3? This expression() will read the 1 as a Term, then proceed to read 2-3 as anExpression (consisting of the Term 2 followed by the Expression 3). It will then subtract the value of 2-3 from 1. In other words, it will evaluate 1-(2-3). The value of 1-(2-3) is 2 (positive two). However, we were taught (in primary school or even earlier) that 1-2-3 means (1-2)-3 and therefore has the value -4 (negative four).

So we got a very nice program that just didn’t do the right thing. That’s dangerous. It is especially dangerous because it gives the right answer in many cases. For example, 1+2+3 gives the right answer (6) because 1+(2+3) equals (1+2)+3. What fundamentally, from a programming point of view, did we do wrong? We should always ask ourselves this question when we have found an error. That way we might avoid making the same mistake again, and again, and again.

Fundamentally, we just looked at the code and guessed. That’s rarely good enough! We have to understand what our code is doing and we have to be able to explain why it does the right thing.

Analyzing our errors is often also the best way to find a correct solution. What we did here was to define expression() to first look for a Term and then, if that Term is followed by a + or a -, look for an Expression. This really implements a slightly different grammar:

Expression:
Term
Term '+' Expression // addition
Term '-' Expression // subtraction

The difference from our desired grammar is exactly that we wanted 1-2-3 to be the Expression 1-2 followed by - followed by the Term 3, but what we got here was the Term 1 followed by - followed by the Expression 2-3; that is, we wanted 1-2-3 to mean (1-2)-3 but we got 1-(2-3).

Yes, debugging can be tedious, tricky, and time-consuming, but in this case we are really working through rules you learned in primary school and learned to apply without too much trouble. The snag is that we have to teach the rules to a computer - and a computer is a far slower learner than you are.

Note that we could have defined 1-2-3 to mean 1-(2-3) rather than (1-2)-3 and avoided this discussion altogether. Often, the trickiest programming problems come when we must match conventional rules that were established by and for humans long before we started using computers.

6.5.2.3 Expressions: third time lucky

So, what now? Look again at the grammar (the correct grammar in §6.5.2): any Expression starts with a Term and such a Term can be followed by a + or a -. So, we have to look for a Term, see if it is followed by a + or a -, and keep doing that until there are no more plusses or minuses. For example:

double expression()
{
double left = term(); // read and evaluate a Term
Token t = get_token(); // get the next token
while (t.kind=='+' || t.kind=='-') { // look for a + or a -
if (t.kind == '+')
left += term(); // evaluate Term and add
else
left -= term(); // evaluate Term and subtract
t = get_token();
}
return left; // finally: no more + or -; return the answer
}

This is a bit messier: we had to introduce a loop to keep looking for plusses and minuses. We also got a bit repetitive: we test for + and - twice and twice call get_token(). Because it obscures the logic of the code, let’s just get rid of the duplication of the test for + and -:

double expression()
{
double left = term(); // read and evaluate a Term
Token t = get_token(); // get the next token
while (true) {
switch (t.kind) {
case '+':
left += term(); // evaluate Term and add
t = get_token();
break;
case '-':
left -= term(); // evaluate Term and subtract
t = get_token();
break;
default:
return left; // finally: no more + or -; return the answer
}
}
}

Note that - except for the loop - this is actually rather similar to our first try (§6.5.2.1). What we have done is to remove the mention of expression() within expression() and replace it with a loop. In other words, we translated the Expression in the grammar rules for Expression into a loop looking for a Term followed by a + or a -.

6.5.3 Terms

The grammar rule for Term is very similar to the Expression rule:

Term:
Primary
Term '*' Primary
Term '/' Primary
Term '%' Primary

Consequently, the code should be very similar also. Here is a first try:

double term()
{
double left = primary();
Token t = get_token();
while (true) {
switch (t.kind) {
case '*':
left *= primary();
t = get_token();
break;
case '/':
left /= primary();
t = get_token();
break;
case '%':
left %= primary();
t = get_token();
break;
default:
return left;
}
}
}

Unfortunately, this doesn’t compile: the remainder operation (%) is not defined for floating-point numbers. The compiler kindly tells us so. When we answered question 5 in §6.3.5 - “Should we also allow floating-point inputs?” - with a confident “Sure!” we actually hadn’t thought the issue through and fell victim to feature creep. That always happens! So what do we do about it? We could at run time check that both operands of % are integers and give an error if they are not. Or we could simply leave % out of our calculator. Let’s take the simplest choice for now. We can always add % later; see §7.5.

After we eliminate the % case, the function works: terms are correctly parsed and evaluated. However, an experienced programmer will notice an undesirable detail that makes term() unacceptable. What would happen if you entered 2/0? You can’t divide by zero. If you try, the computer hardware will detect it and terminate your program with a somewhat unhelpful error message. An inexperienced programmer will discover this the hard way. So, we’d better check and give a decent error message:

double term()
{
double left = primary();
Token t = get_token();
while (true) {
switch (t.kind) {
case '*':
left *= primary();
t = get_token();
break;
case '/':
{ double d = primary();
if (d == 0) error("divide by zero");
left /= d;
t = get_token();
break;
}
default:
return left;
}
}
}

Why did we put the statements handling / into a block? The compiler insists. If you want to define and initialize variables within a switch-statement, you must place them inside a block.

6.5.4 Primary expressions

The grammar rule for primary expressions is also simple:

Primary:
Number
'(' Expression ')'

The code that implements it is a bit messy because there are more opportunities for syntax errors:

double primary()
{
Token t = get_token();
switch (t.kind) {
case '(': // handle ‘(‘ expression ‘)’
{ double d = expression();
t = get_token();
if (t.kind != ')') error("')' expected");
return d;
}
case '8': // we use ‘8’ to represent a number
return t.value; // return the number’s value
default:
error("primary expected");
}
}

Basically there is nothing new compared to expression() and term(). We use the same language primitives, the same way of dealing with Tokens, and the same programming techniques.

6.6 Trying the first version

To run these calculator functions, we need to implement get_token() and provide a main(). The main() is trivial: we just keep calling expression() and printing out its result:

int main()
try {
while (cin)
cout << expression() << '\n';
keep_window_open();
}
catch (exception& e) {
cerr << e.what() << '\n';
keep_window_open ();
return 1;
}
catch (...) {
cerr << "exception \n";
keep_window_open ();
return 2;
}

The error handling is the usual “boilerplate” (§5.6.3). Let us postpone the description of the implementation of get_token() to §6.8 and test this first version of the calculator.