Structures Midterm Review

Study points and highlights from Chapters 0-8

Gregory S. DeLozier, PhD

What to Be Able to Do

• Recognize the reusable patterns in each module.
• Trace source through tokens and a tree.
• Explain a result using the evaluator’s rules.
• Follow changes to the environment and output.
• Identify the stage responsible for an error.

Explain why, not just what prints.

New Features, Familiar Patterns

Learn the patterns as well as the individual features.

Language and Implementation

A grammar alone does not define execution.

Text Becomes Structure

An abstract syntax tree (AST) records operations and grouping.

Execution or Translation?

Different routes; preserve the program’s meaning.

Tokenization: Order Matters

Word boundaries keep printer an identifier.

Read the Expression Tree

3 + 4 * 5

Result: 23. The grouping is already in the tree.

Precedence and Associativity

Precedence separates levels; associativity groups a chain.

Parser Contracts

Extended Backus-Naur Form (EBNF):

term ::= unary { ("*" | "/") unary }
unary ::= "-" unary | factor

• A helper returns a node and unused tokens.
• { ... } means repetition; [ ... ] means optional.
• The public parser requires the whole input.

Zero or More: The Same Parser Loop

term      ::= unary     { ("*" | "/") unary }
logic_and ::= logic_not { "and" logic_not }

left, tokens = parse_operand(tokens)
while tokens[0]["tag"] in operators:
    op = tokens[0]["tag"]
    right, tokens = parse_operand(tokens[1:])
    left = {"tag": op, "left": left, "right": right}
return left, tokens

Optional Once, Repeat, or Recurse?

The grammar suggests the control structure.

Reuse Structure, Add Meaning

Similar nodes can still have different evaluation rules.

Find the Error’s Stage

Assignment Changes State

x = 2;
y = x + 3 * 4;
x = x + 1;

Lookup and Assignment Differ

• Lookup x: 3. Lookup y: 20.
• Ordinary assignment y = 7: writes here.
• The parent’s y stays 20.

Strings Are Values

Input and Output State

__input = "21";
answer = number(input()) * 2;
print(answer);

Know Which Version You Mean

New keywords can also invalidate old variable names.

Booleans Are Not Numbers

Ordering accepts two numbers or two strings, not booleans.

Explicit Conversions and Type

Logical Grouping

Weakest to strongest:

or → and → not → comparison → arithmetic

Short-Circuiting Skips Work

divisor = 0;
safe = divisor != 0 and 10 / divisor > 2;

No evaluation means no input, lookup, or runtime error.

Value and Status Are Separate

A false value is not a special status.

Reuse the Evaluation Contract

value, status = evaluate(child, environment)
if status is not None:
    return value, status
# Only now use the value or perform the next effect.

The same check protects assignment, print, conversions, arithmetic, conditions, and statement lists.

Propagate Before Continuing

x = 3;
x = exit(7) + number(input());

No input. No addition. No store. x stays 3.

Assertions Check Expectations

assert answer == 42, "Expected 42";

• True condition: normal completion.
• False condition: diagnostic to standard error, then exit 1.
• Explanation: mandatory string literal.

Conditional Selection

x = 1;
if (true) {
    x = 2;
} else {
    exit(9);
};
print(x);

Prints 2. Only the selected block runs.

Braces and Semicolons

if (true) { x = 1; } else { x = 2; };
print(x);

• Braces are required, even for one statement.
• No semicolon between the then block and else.
• Separate the complete if from the next statement.
• A newline or // comment is not a separator.

Trace the Loop

i = 0;
while (i < 3) {
    print(i);
    i = i + 1;
}

Three body executions, four condition checks.

Output: 0, 1, 2. Final i: 3.

Which Construct Handles Status?

An inner loop consumes its own break, not the outer loop’s work.

A Loop Can Refine an Answer

Newton’s square-root update:

guess = (guess + S / guess) / 2;

• Repeat while the estimate is changing.
• Compare the size of successive changes.
• Check the result by squaring it back.

newton.v combines arithmetic, state, loops, and assertions.

Study by Tracing

1. Identify the grammar and implementation pattern.
2. Group the expression or draw its tree.
3. Record the environment before each statement.
4. Mark skipped branches and operands.
5. Track output and the returned status separately.

When a result surprises you, locate the rule that explains it.