Terminals and Non-Terminals

Understand the two kinds of symbols every grammar uses: terminals (the actual output characters) and non-terminals (the placeholder rules), and how derivations use them to build strings.

Terminals — The Real Output

Terminals are the actual symbols that appear in the final string generated by a grammar. They cannot be replaced further — they are the end of the road.

Think of terminals as the words in a sentence. Once a non-terminal is replaced by a terminal, that terminal stays fixed forever.

Notation conventions:

Lowercase letters: a, b, c, x, y
Digits: 0, 1, 2
Operator symbols: +, -, *, /
Keywords in a language: if, while, int

Example Grammars and Their Terminals

Grammar 1 — Balanced parentheses

Example

G: S → (S) | SS | ε

Terminals: { ( , ) }

Grammar 2 — Simple arithmetic expressions

Example

G: E → E + T | T

T → T * F | F

F → ( E ) | id | num

Terminals: { +, *, (, ), id, num }

In the final generated string, you will only ever see terminals. A string like id + num * id is a valid sentence because it contains only terminals.

Non-Terminals — The Placeholders

Non-terminals (also called variables) are placeholder symbols that represent a class of strings. They act as intermediate building blocks during derivation and must eventually be replaced — either by terminals or by other non-terminals that will themselves be replaced.

Non-terminals are the structural rules of the grammar. They give the language its shape.

Notation conventions:

Uppercase letters: A, B, C, S, E, T, F
Angle-bracket names: <expression>, <statement>, <digit>

What Non-Terminals Represent

Non-Terminal	What it Represents
S	Start — the whole program or sentence
E	Expression
T	Term
F	Factor
A	Some intermediate structure

A Grammar Dissected

Example

G: S → aAb

A → cAd | ε

Non-Terminals: { S, A }

Terminals: { a, b, c, d }

Start Symbol: S

Here, A represents "any number of c's on the left and d's on the right". The non-terminal A is a placeholder for that whole family of strings.

Derivation — Using the Rules

A derivation is the step-by-step process of applying production rules, starting from the start symbol S, until no non-terminals remain. Each step replaces exactly one non-terminal.

Two Strategies

Leftmost Derivation (LMD): Always replace the leftmost non-terminal first. Rightmost Derivation (RMD): Always replace the rightmost non-terminal first.

Example — Deriving "aaccddb" step by step

Grammar:

Example

S → aAb

A → cAd | ε

Leftmost Derivation of "aaccddb":

Example

Step Sentential Form Rule Applied

────── ───────────────── ──────────────────────

0 S (start)

1 aAb S → aAb

2 acAdb A → cAd (leftmost A)

3 accAdd b A → cAd (leftmost A)

4 accddb A → ε

Wait — let me trace more carefully with the grammar S → aAb, A → cAd | ε:

Example

Deriving "acdb":

S → aAb → acAdb → acdb (A → ε in step 2)

Deriving "accdb": ← Not in L(G), since each c needs a matching d

Deriving "acddb": ← Not in L(G), since d's come from inside A

Deriving "accdd b":

S → aAb → acAdb → accAdd b → accddb

The language generated is:

Example

L(G) = { a cⁿ dⁿ b | n ≥ 0 }

= { ab, acdb, accdb, accddb, ... }

Wait — L(G) = { acⁿdⁿb | n ≥ 0 }:

n=0 → ab

n=1 → acdb

n=2 → accddb

n=3 → acccdddb

Each application of A → cAd adds one c on the inside-left and one d on the inside-right, surrounding the current A. When we finally apply A → ε, no more substitutions happen.

Parse Tree — Visualising a Derivation

A parse tree (also called a derivation tree) is a graphical representation of a derivation. It shows which rule was applied at each step, branching from the start symbol down to the terminals.

Rules for building a parse tree:

The root is always the start symbol S
Each interior node is a non-terminal
Each leaf is a terminal (or ε)
If you apply rule A → XYZ, then A is a node with three children X, Y, Z

Example

Grammar:

Example

E → E + T | T

T → T * F | F

F → ( E ) | id

Derivation of id + id * id:

Example

→ E + T

→ T + T

→ F + T

→ id + T

→ id + T * F

→ id + F * F

→ id + id * F

→ id + id * id

Parse Tree:

Example

/ | \

E + T

| / | \

T T * F

| | |

F F id

| |

id id

Key insight: The parse tree captures the operator precedence and associativity of the expression. id * id forms a subtree under T, meaning multiplication is done before addition — exactly as expected.

The leaves read left-to-right spell out the original string: id + id * id.

Side-by-Side Comparison

Property	Terminal	Non-Terminal
Symbol convention	Lowercase: a, b, 0, +, id	Uppercase: A, B, S, E, T
Role	Actual output character	Placeholder / structural rule
Can be replaced?	No — fixed forever	Yes — must be replaced
Appears in final string?	Yes	No
Appears in parse tree as	Leaf node	Interior node
Examples	`a`, `+`, `if`, `42`	`S`, `E`, `Term`, `Stmt`

Quick Rule to Spot Them

Look at the right-hand side of a production after derivation ends:

If the symbol still needs to be replaced → Non-terminal
If the symbol goes into the final string unchanged → Terminal

Example

S → aAb ← A is a non-terminal (will be replaced)

A → cd ← c and d are terminals (final output)

Full derivation:

S → aAb → acdb

Final string: a c d b ← all terminals, no non-terminals left

Terminals — The Real Output

Terminals are the actual symbols that appear in the final string generated by a grammar. They cannot be replaced further — they are the end of the road.

Think of terminals as the words in a sentence. Once a non-terminal is replaced by a terminal, that terminal stays fixed forever.

Notation conventions:

Lowercase letters: a, b, c, x, y
Digits: 0, 1, 2
Operator symbols: +, -, *, /
Keywords in a language: if, while, int

Example Grammars and Their Terminals

Grammar 1 — Balanced parentheses

Example

G: S → (S) | SS | ε

Terminals: { ( , ) }

Grammar 2 — Simple arithmetic expressions

Example

G: E → E + T | T

T → T * F | F

F → ( E ) | id | num

Terminals: { +, *, (, ), id, num }

In the final generated string, you will only ever see terminals. A string like id + num * id is a valid sentence because it contains only terminals.

Non-Terminals — The Placeholders

Non-terminals are the structural rules of the grammar. They give the language its shape.

Notation conventions:

Uppercase letters: A, B, C, S, E, T, F
Angle-bracket names: <expression>, <statement>, <digit>

What Non-Terminals Represent

Non-Terminal	What it Represents
S	Start — the whole program or sentence
E	Expression
T	Term
F	Factor
A	Some intermediate structure

A Grammar Dissected

Example

G: S → aAb

A → cAd | ε

Non-Terminals: { S, A }

Terminals: { a, b, c, d }

Start Symbol: S

Here, A represents "any number of c's on the left and d's on the right". The non-terminal A is a placeholder for that whole family of strings.

Derivation — Using the Rules

A derivation is the step-by-step process of applying production rules, starting from the start symbol S, until no non-terminals remain. Each step replaces exactly one non-terminal.

Two Strategies

Leftmost Derivation (LMD): Always replace the leftmost non-terminal first. Rightmost Derivation (RMD): Always replace the rightmost non-terminal first.

Example — Deriving "aaccddb" step by step

Grammar:

Example

S → aAb

A → cAd | ε

Leftmost Derivation of "aaccddb":

Example

Step Sentential Form Rule Applied

────── ───────────────── ──────────────────────

0 S (start)

1 aAb S → aAb

2 acAdb A → cAd (leftmost A)

3 accAdd b A → cAd (leftmost A)

4 accddb A → ε

Wait — let me trace more carefully with the grammar S → aAb, A → cAd | ε:

Example

Deriving "acdb":

S → aAb → acAdb → acdb (A → ε in step 2)

Deriving "accdb": ← Not in L(G), since each c needs a matching d

Deriving "acddb": ← Not in L(G), since d's come from inside A

Deriving "accdd b":

S → aAb → acAdb → accAdd b → accddb

The language generated is:

Example

L(G) = { a cⁿ dⁿ b | n ≥ 0 }

= { ab, acdb, accdb, accddb, ... }

Wait — L(G) = { acⁿdⁿb | n ≥ 0 }:

n=0 → ab

n=1 → acdb

n=2 → accddb

n=3 → acccdddb

Each application of A → cAd adds one c on the inside-left and one d on the inside-right, surrounding the current A. When we finally apply A → ε, no more substitutions happen.

Parse Tree — Visualising a Derivation

A parse tree (also called a derivation tree) is a graphical representation of a derivation. It shows which rule was applied at each step, branching from the start symbol down to the terminals.

Rules for building a parse tree:

The root is always the start symbol S
Each interior node is a non-terminal
Each leaf is a terminal (or ε)
If you apply rule A → XYZ, then A is a node with three children X, Y, Z

Example

Grammar:

Example

E → E + T | T

T → T * F | F

F → ( E ) | id

Derivation of id + id * id:

Example

→ E + T

→ T + T

→ F + T

→ id + T

→ id + T * F

→ id + F * F

→ id + id * F

→ id + id * id

Parse Tree:

Example

/ | \

E + T

| / | \

T T * F

| | |

F F id

| |

id id

The leaves read left-to-right spell out the original string: id + id * id.

Side-by-Side Comparison

Property	Terminal	Non-Terminal
Symbol convention	Lowercase: a, b, 0, +, id	Uppercase: A, B, S, E, T
Role	Actual output character	Placeholder / structural rule
Can be replaced?	No — fixed forever	Yes — must be replaced
Appears in final string?	Yes	No
Appears in parse tree as	Leaf node	Interior node
Examples	`a`, `+`, `if`, `42`	`S`, `E`, `Term`, `Stmt`

Quick Rule to Spot Them

Look at the right-hand side of a production after derivation ends:

If the symbol still needs to be replaced → Non-terminal
If the symbol goes into the final string unchanged → Terminal

Example

S → aAb ← A is a non-terminal (will be replaced)

A → cd ← c and d are terminals (final output)

Full derivation:

S → aAb → acdb

Final string: a c d b ← all terminals, no non-terminals left