CS211: Expressions

Up to this point, we've learned what variables are and how to use operations to perform computations using those variables. What we haven't explored are the fundamental units within the code that allow for the compiler to return the values of said computations. These units are called expressions.

A commonality across all programming languages is that expressions return values. Take, for example, the simple expression 3 * 2. We know now that it will evaluate to 6 because the * operator represents multiplication and the constants 3 and 2 are equivalent to their decimal symbols. What might be less obvious is that there are actually three expressions in that one, simple expression:

1. The constant value 3 in the left operand.
2. The constant value 2 in the right operand.
3. The operation of multiplying the left and right operand.

This can be made more clear if we were to replace 3 and 2 with the integer variables x and y, giving us x * y:

1. The value of the variable x (what is stored at the memory location mapped to the symbol x) in the left operand
2. The value of the variable y (what is stored at the memory location mapped to the symbol y) in the right operand
3. The operation of multiplying the left and right operand.

In order for the multiplication operation to be successful, the runtime must evaluate what is stored in the variables.

All expressions must be able to be evaluated deterministically and unambiguously. What do I mean by that? Well, take for example a more complicated set of expressions, 5 * 2 + 3 * 4. How exactly should that be evaluated by the compiler? Grade school math teaches us that it should evaluate to 22, and it turns out that's also the case in C, but why is that? If I read the symbols from left to right it tells me I should multiply 5 by 2, then add 4, and then multiply by 4, giving me 52. This is because, without precedence rules, infix notation is inherently ambiguous—there's no way to know how to order the expressions without external information about the symbols.

All programming languages that use infix notation must define precedence rules that govern expression evaluation order. It follows then that the C standard has exactly that:

In the second row, +, -, and * are unary operators.

When using the above rules, there can be absolutely no abiguity about the expression 5 * 2 + 3 * 4. We can see that binary * takes higher precedence than binary +. There are quite a lot of rules here, but most will become second nature after you get some experience under your belt.

Expressions can be constrasted with statements insofar as expressions always return values whereas statements do not. For example, an if statement, which we'll discuss next lecture, handles control flow, it does not return a value. This is in direct contradistinction with the + operator which will always return the value equal to the sum of the two operands on either side of it.

1. Evaluate the following expressions by hand using the precedence table, then verify in C using printf("%d\n", expr):
   • 5 * 2 + 3 * 4
   • 5 * (2 + 3) * 4
   • 10 - 4 / 2 + 1
   • 10 - 4 / (2 + 1)
2. The lecture identifies three sub-expressions in 3 * 2. How many sub-expressions can you identify in 5 * 2 + 3 * 4? List each one and the order in which they are evaluated according to the precedence table.
3. Download the AST builder script linked in the lecture and run it on a C file containing the expression 1 + ~2 + 3 * 4 / 5 * 6 & 7 | 8. Verify the output matches Listing 1. Then add parentheses to the expression to change the evaluation order and observe how the AST changes.
4. Write the fully parenthesized version of the following expressions as the compiler would evaluate them, then verify by computing the result:
   • 8 >> 1 + 1
   • 1 | 2 & 3
   • !0 + !1 * 2
   • 3 * 4 + 5 * 6 - 7 / 2
5. The second row of the precedence table notes that +, -, and * appear as unary operators. Write a C program that demonstrates the difference between unary and binary +, -, and * by using each in context. What does unary * do?
6. Write a C program that declares int x = 5 and int y = 3 and evaluates x = y = 2. Print x and y after the assignment. Using the associativity column of the precedence table, explain why the result is what it is.
7. The lecture states that expressions always return values but statements do not. Classify each of the following as an expression or a statement and explain why:
   • x + 1
   • int x = 5
   • x = x + 1
   • 3 * 4
8. Write a C program that evaluates (((1 + (~2)) + (((3 * 4) / 5) * 6)) & 7) | 8 and the equivalent unparenthesized version 1 + ~2 + 3 * 4 / 5 * 6 & 7 | 8. Do they produce the same result? What does this confirm about the precedence rules?
9. Using the precedence table, determine which of the following pairs of expressions are equivalent without running them. Then verify in C:
   • a + b * c and a + (b * c)
   • a & b | c and (a & b) | c
   • !a && b and (!a) && b
   • a = b = 0 and a = (b = 0)
10. The lecture gives ~1 + ~2 + 3 * 4 / 5 * 6 & 7 | 8 as an example of a confusing but valid C expression. Write your own complex expression using at least five different operators, write its fully parenthesized form, compute the result by hand, and then verify with a C program.