Type Checking & Semantic Analysis: Rules, Systems, and Real-World Applications

TAKEAWAYS:

• Type checking ensures type safety by verifying that operations align with language rules (e.g., int + string fails in statically typed languages).
• Static type checking (compile-time) catches errors early (e.g., Java), while dynamic type checking (run-time) allows flexibility (e.g., Python).
• Syntax-directed definitions use attributes (synthesized/inherited) to propagate type info during parsing (e.g., E → id inherits type from id).
• Type expressions (e.g., array[int] of float) describe complex data structures and are checked recursively.
• Semantic analysis validates context-free rules (e.g., variable scope, operator precedence) beyond syntax.
• Real-world systems (e.g., eSewa’s payment validation, WhatsApp’s message encryption) rely on type/semantic checks to prevent runtime crashes.

1. What is Type Checking?

Type checking is the process of verifying that operations in a program adhere to the language’s type system. It ensures:

• Type compatibility: Operands of an operator match expected types (e.g., + for int but not string).
• Scope validity: Variables are declared before use.
• Semantic correctness: Rules like "arrays must have integer indices" are enforced.

Why is Type Checking Necessary?

Without type checking, programs may:

• Crash at runtime (e.g., NullPointerException in Java).
• Produce incorrect results (e.g., 5 + "2" → "52" in Python vs. error in C).
• Violate security (e.g., type confusion vulnerabilities in web apps).

Example (Type Error):

int x = 10;
string y = "hello";
int z = x + y;  // ERROR: Cannot add int and string

Visual:

flowchart TD
    A["Source Code"] --> B["Lexical Analysis"]
    B --> C["Syntax Analysis"]
    C --> D["Semantic Analysis\n(Type Checking)"]
    D -->|"Type Error"| E["Compiler Rejects"]
    D -->|"Valid"| F["Code Generation"]

2. Static vs. Dynamic Type Checking

Real-World Example: eSewa’s Transaction Validation

• Static Type Checking: eSewa’s backend (likely Java/C#) enforces that:
  • amount is decimal (not string).
  • user_id is integer (not null).
• Dynamic Check: If a user sends a malformed JSON (e.g., {"amount": "five"}), the API rejects it before processing.
• Why? Prevents financial fraud by ensuring data integrity.

3. Type Expressions and Type Systems

A type expression describes the structure of a type, e.g.:

• Primitive types: int, float, bool.
• Composite types:
  • array[int] of float → float[10].
  • record{name: string, age: int}.
  • pointer to int → int*.

Example: Type Expression for a 2D Array

graph LR
    A["array[5] of array[3] of float"] --> B["Type: array[5] of X"]
    B --> C["X: array[3] of float"]
    C --> D["float"]

Code Example (C):

float matrix[5][3];  // Type expression: array[5] of array[3] of float

Type Check for matrix[2][1] = 3.14:

1. Check 2 is int (valid index for array[5]).
2. Check 1 is int (valid index for array[3]).
3. Check 3.14 is float (matches matrix’s element type).

4. Syntax-Directed Type Checking

Type checking is often implemented using syntax-directed definitions (SDDs) with attributes. Attributes can be:

• Synthesized: Computed from child nodes (e.g., type of an expression).
• Inherited: Passed down from parent nodes (e.g., expected type in an assignment).

Example Grammar with Attributes

E → id       { E.type = id.type }
  | E1 op E2 { E.type = check(E1.type, E2.type, op) }
  | (E)      { E.type = E1.type }

Trace for x = 3 + y (where x is int, y is float):

Visual (Attribute Flow):

flowchart TD
    A["E → E1 op E2"] --> B["E1.type = int"]
    A --> C["E2.type = float"]
    B --> D["check(int, float, +)"]
    C --> D
    D --> E["ERROR: Type mismatch"]

5. Semantic Analysis Tasks

Beyond type checking, semantic analysis includes:

1. Scope Resolution: Ensuring variables are declared before use.
2. Operator Precedence: Validating expressions like a + b * c (multiplication before addition).
3. Control Flow Validation: Checking if conditions are boolean.
4. Storage Allocation: Assigning memory for variables.

Example: Scope Validation in a Block

int x = 10;
if (true) {
    int y = 20;
    x = y + 5;  // Valid: y is in scope
}
x = y + 1;     // ERROR: y is out of scope

Visual (Scope Tree):

graph TD
    A["Global Scope"] --> B["x: int"]
    A --> C["if-block"]
    C --> D["y: int"]
    D --> E["x = y + 5"]
    A --> F["x = y + 1\nERROR: y undefined"]

6. Real-World Applications

Example 1: WhatsApp’s Message Encryption (Type Safety)

• Static Type Checking: WhatsApp’s backend (likely Java/Kotlin) enforces:
  • Message objects must have sender: User, content: string, timestamp: long.
  • Encryption keys are byte[32] (not string).
• Why? Prevents buffer overflows or invalid key formats.

Example 2: Daraz’s Order Queue (Semantic Validation)

• Type Check: Order items must be:
  • product_id: int (not string).
  • quantity: int > 0.
• Semantic Check: Stock levels are validated before processing.
• Dynamic Check: If a user sends {"quantity": "zero"}, the API rejects it.

Example 3: NEPSE Stock Prices (Type Expressions)

• Type Expression:

  graph LR
      A["StockData"] --> B["symbol: string"]
      A --> C["price: float"]
      A --> D["volume: int"]

• Type Check: Ensures price is float (not string) when updating.

7. Worked Example: Type Checking for E → id | E1 op E2

Grammar:

E → id       { E.type = id.type }
  | E1 op E2 { E.type = check(E1.type, E2.type, op) }

Expression: a + b * c (where a: int, b: int, c: float)

Step-by-Step Trace:

Visual (Parse Tree with Types):

graph TD
    A["+"] --> B["a: int"]
    A --> C["*"]
    C --> D["b: int"]
    C --> E["c: float"]

8. Exam Tip: How to Score Full Marks

1. Define Clearly:
   • "Static type checking is performed at compile-time to ensure type compatibility before execution."
2. Use Examples:
   • Always pair definitions with code snippets (e.g., int x = "hello"; for dynamic typing).
3. Draw Diagrams:
   • Show attribute flow in syntax-directed definitions.
   • Draw scope trees for semantic analysis questions.
4. Compare Tables:
   • For static vs. dynamic, list languages, error timing, and performance.
5. Link to Real-World:
   • Mention eSewa’s validation, WhatsApp’s encryption, or Daraz’s order checks in essays.
6. Trace Step-by-Step:
   • For type checking, show state after each step (like the a + b * c example).

Common Pitfalls:

• Forgetting to mention inherited vs. synthesized attributes.
• Not validating operator precedence in semantic checks.
• Confusing type expressions with type declarations (e.g., array[int] vs. int arr[5]).