IndentationSensitiveLanguages

Indentation obviously requires the ability to count and to remember some counters.

Definition

An indentation sensitive grammar is defined by

• V: finite set of variables
• Sigma: finite set of terminals
• R: finite set of rules. Each rule starts with a string of exactly one variable and 0 or 1 counter and yields a string of variables, terminals, and counters.
• C: finite set of counters. C = { C_tⁿ | t in Sigma and n is a natural number}
• S: start variable

where

C_t⁰ := epsilon
C_tⁿ⁺¹ := C_tⁿ t

Example

Let's consider a simplified language that has a statement requiring nesting a (e.g. a while-statement), a simple statement b (e.g. assignment), and a symbol for indentation t (e.g. \t). We may generate a program by the following grammar:

S -> C_t⁰ E

C_tⁿ E -> C_tⁿ E C_tⁿ E | C_tⁿ N | C_tⁿ b | epsilon

C_tⁿ N -> C_tⁿ a C_tⁿ⁺¹ E