Leftmost Derivation Simulator

Grammar rules are applied left-to-right. Each step replaces the leftmost nonterminal with one of its production rules, until only terminals remain.

Current sentential form: Step 0 / 0
Select an example and press Next โ†’
๐Ÿ“‹ Show all derivation steps

Grammar Used in This Example

Legend

<nonterminal> โ€” can still be replaced by a rule
terminal โ€” final symbol, cannot be replaced
<highlighted> โ€” the nonterminal being replaced this step

What is Leftmost Derivation?

Start from <program>. Always replace the leftmost nonterminal first. Keep applying rules until the string contains only terminals. This is exactly what a parser does when it validates your code against a grammar.

๐Ÿ“– Deep Explanation โ€” Leftmost Derivation

Key Definitions

Grammar
A set of rules (productions) that describe what sentences a language allows. Written in BNF. Like a recipe book โ€” each rule says "this thing can be made from these ingredients."
Nonterminal
Written as <name>. A placeholder that must still be expanded. Think of it as a category: <var> means "some variable", not a specific one yet.
Terminal
An actual token โ€” a real symbol in the final code. begin, A, =, ; are all terminals. They cannot be expanded further. Terminal = the end of the road.
Sentential Form
Any string produced during a derivation. It can contain both nonterminals and terminals. The start symbol is a sentential form; the final sentence (all terminals) is one too.
Production Rule
Written as <X> โ†’ something. It says: "nonterminal X can become this." Multiple alternatives are separated by | (OR).
Derivation
The sequence of steps from start symbol to a final sentence. Each step applies exactly one production rule to replace one nonterminal. Denoted โ‡’ (derives).

The Algorithm โ€” Step by Step

1
Start with the grammar's start symbol (usually <program>). This is your first sentential form.
2
Find the leftmost nonterminal in the current sentential form โ€” scan left to right, take the first <angle bracket> you encounter.
3
Choose a production rule for that nonterminal (e.g. <exp> โ†’ <var> * <exp>). Replace the nonterminal with the rule's right-hand side.
4
Repeat steps 2โ€“3 until no nonterminals remain. The result is a valid sentence in the language.
โœ“
Done when all symbols are terminals. The string is in the language defined by the grammar.

Mnemonics โ€” How to Remember

๐ŸŒ… "Sun rises in the East"
Just like you read โ€” left to right. Always expand the first (leftmost) unexpanded symbol you see. Never skip ahead.
๐Ÿง… "Peeling an Onion"
Each derivation step peels one layer. The outer structure comes first (<program> โ†’ beginโ€ฆend), then inner details fill in one by one.
๐ŸŽญ "Nonterminals are Actors, Terminals are Stage Props"
<nonterminal> = still in costume, playing a role, will be replaced. terminal = a real object on stage, final, cannot change.
๐Ÿ“‹ "To-Do List"
A sentential form is a to-do list. <nonterminals> are unchecked tasks. Each derivation step checks off exactly one item โ€” always the leftmost unchecked one.
๐Ÿ”ค "NT = Not Terminal = Not done yet"
NT = NonTerminal = Not Terminated = still needs work. Terminal = terminated = finished = leaf of the parse tree.
โ‡’ "Arrow = Becomes"
Read A โ‡’ B as "A becomes B in one step." Read A โ‡’* B as "A eventually becomes B in zero or more steps."

Leftmost vs Rightmost Derivation

Leftmost Derivation (LMD)
  • Always expand the leftmost nonterminal
  • Reads like how you parse text: left โ†’ right
  • Used by top-down parsers (LL parsers)
  • Example: LL(1) parsers, recursive descent parsers
<S> โ‡’ <A> + <B> โ† expand leftmost
    โ‡’ x + <B> โ† expand leftmost
    โ‡’ x + y
Rightmost Derivation (RMD)
  • Always expand the rightmost nonterminal
  • Constructs the parse tree from right to left
  • Used by bottom-up parsers (LR parsers)
  • Example: LALR(1) parsers, yacc/bison tools
<S> โ‡’ <A> + <B> โ† expand rightmost
    โ‡’ <A> + y โ† expand rightmost
    โ‡’ x + y
Key insight: Both LMD and RMD produce the same parse tree for an unambiguous grammar โ€” they just build it in a different order. An ambiguous grammar is one where the same string has more than one parse tree (different derivation orders lead to structurally different trees).

Notation Quick Reference

Symbol Read as Meaning
โ†’ "can be replaced by" Production rule. <A> โ†’ xyz means nonterminal A can become xyz.
โ‡’ "directly derives" One derivation step. ฮฑ โ‡’ ฮฒ means ฮฒ is obtained from ฮฑ by applying one production.
โ‡’* "derives (in 0+ steps)" Zero or more derivation steps. Used to say "this sentence is in the language."
| "or" Separates alternatives. <A> โ†’ x | y means A can become x OR y.
<name> "nonterminal name" Angle brackets signal a nonterminal โ€” a placeholder not yet resolved to real code.
word "terminal / token" A literal symbol in the final program. Cannot be expanded. Leaf of the parse tree.

BNF Grammar โ€” Interactive Reference

BNF defines a language's syntax. Click any rule to see what it means and example sentences it generates.

Production Rules

Click a rule to explore it

Select any production rule on the left to see its explanation, alternatives, and example strings it can generate.

BNF Notation Cheatsheet

Symbols
<name> = nonterminal
word = terminal
โ†’ = "can be replaced by"
| = OR (alternative)
Example Rule
<stmt> โ†’ <var> = <exp>

A statement can be: a variable, then =, then an expression.

Recursion
<stmt_list> โ†’ <stmt> ; <stmt_list> | <stmt>

Rules can refer to themselves โ€” this is how grammar generates infinite sentences.

Parse Tree Builder

A parse tree shows the hierarchical structure of a derived sentence. Step forward to watch it grow.

Step 0
Parse Tree vs Derivation: Both represent the same process. A derivation is a flat sequence of sentential forms; a parse tree is the 2D hierarchical view. Each inner node is a nonterminal; each leaf is a terminal.

Programming Paradigms

Click any paradigm to see its characteristics and a code example.

Type System Explorer

See how different type systems handle the same operations. Click "Run" to check what happens.

Type Dimension 1: Checking Time

Static Typing

Type known at compile time. Errors caught early.

Languages: C C++ Java Rust
Dynamic Typing

Type known at runtime. More flexible, errors at runtime.

Languages: Python JS Ruby

Type Dimension 2: Conversion Rules

Strong Typing

Illegal conversions cause an error. No implicit coercion.

Weak Typing

Types are coerced silently. Can lead to surprising behavior.

Click a type system to see an example

Each card will show a code snippet and explain what happens.

Error Type Detector

Which kind of error is each snippet?

Memory Model โ€” Stack & Heap Simulator

Watch memory regions fill and empty as functions are called. Click each cell for details.

Step 0

๐Ÿ“š Stack (LIFO)

โ† grows upward

๐Ÿ—ƒ Heap (Dynamic)

๐Ÿ“Œ Registers / Other

Stack Facts

  • Stores local variables and function call frames
  • Uses LIFO โ€” Last In, First Out
  • Fixed max size โ€” overflow โ†’ Stack Overflow!
  • Automatically managed (push on call, pop on return)
  • Very fast โ€” just a pointer increment

Heap Facts

  • Used for dynamic allocation (new, malloc)
  • No fixed order โ€” allocated and freed anywhere
  • Manual management in C/C++ โ†’ risk of memory leak
  • Automatic in Java/Python (garbage collector)
  • Slower than stack access

Practice Quiz

Based on your course material and exam questions. Click an answer to reveal explanation.

Score: 0 / 0