Syntax Specification

Syntax in a programming language is specificied using a mathematical device called a Grammar.

Relevant Notes: CS3310 (Formal Languages and Automata

Variables and Binding

Variables

Variable: Store data and associate it with a name.

• Used in imperative languages.

Variables have two values associated with them.

• Memory location and value.

int x = 42

int x = 42;
int *p = &x;

Binding

Binding: Association of a name to a particular property.

• e.g., memory, type, scope, and more.

\begin{matrix} &\text{Symbol} & & &\text{Property} \\ &x &\to& &p \end{matrix}

Types of Binding:

• Memory Allocation: Memory binding
• Typing: Type binding
• Scoping: Scope binding

Binding Time: When the binding happens

1. Dynamic Binding: If the binding happens while the program is running.
2. Static Binding: If the binding happens outside program execution.

More on Static Binding: Two types

1. Compiler does it
2. Lexer does it.

Note: This has nothing to do with the static keyword in Java.

Memory Binding (Memory Allocation)

Static Allocation: Allocation happens before execution (typically the compiler)

• Memory is allocated in data section.

Process Memory Heap:

TODO plantuml

• stack (stack frames)
• heap (dynamically allocated data)
• data (statically allocated data).
• text

Refresher: Frames store the local variables and parameters of a function call.

Dynamic Allocation: Allocation happens during execution.

• Memory is allocated in heap section.

// Statically allocate n=3
x = int[3];

// Dynamically allocate n=3
y = malloc(sizeof(int) * 3);

Type Checking

Typing: Assigning a type to every symbol in a program, and checking the type assignment makes sense.

Static Typing

Static Typing: Happens before execution, typically during compilation

• Explicit Typing: Type data explicitly stated in source code.
• Implicit Typing: Type data is inferred by type checking engine.

// Explicit Typing
let x : f64 = 1.0;

// Implicit Typing (type inference)
let y = 1.0;

On Overhead:

Typing adds a lot of overhead, which is why there’s a gap in performance between compiled and dynamic languages.

• In the modern day, with JIT and other optimizations, this gap is shortening.

Dynamic Typing

Dynamic Typing: Happens during execution

Strict Typing: When the type is allowed to change.

x := 42
// ...
x := "Apple"

Scope Binding

Scope: The region of a program where a symbol is visible.

Remember: This is about visibility, not permanence!

fn f() {
  let x = 42;
}

fn g() {
  let y = 42;
}

// We can statically define variables in c
f() {
  static x = 0;
  x++;
}

Static Scoping (Lexical Scoping)

Scoping happens while writing the program.

• Also called lexical scoping.

Dynamic Scoping

Whatever is in the stack exists everywhere.

z := 0
x := 0
call g
call f

function f() {
  // Shadows the x outside
  x := 42
  call g
}

function g() {
  // Uses the x in the function that called me 
  y := x \text{$+$} 7
}