Parse Tree Analyzer

Python Compiler Project

---

📁 Project Structure

parse_tree_analyzer/
├── main.py            ← GUI application (run this)
├── lexer.py           ← Tokenizer / Lexer
├── ast_nodes.py       ← AST node definitions
├── ll_parser.py       ← LL Recursive Descent parser (top-down)
├── lr_parser.py       ← LR Shift-Reduce parser (bottom-up)
├── tree_visualizer.py ← Matplotlib tree drawing engine
├── requirements.txt   ← Python dependencies
└── README.md          ← This file

---

🚀 How to Run

1. Install dependencies

pip install matplotlib

2. Run the application

python main.py

---

✨ Features

Feature	Description
Grammar Modes	Arithmetic, Programming Language, Custom
LL Parser	Recursive Descent — top-down, rule-by-rule derivation
LR Parser	Shift-Reduce (Pratt/precedence-climbing) — bottom-up
Tree Visualization	Side-by-side graphical parse trees (matplotlib)
LL Trace	Full step-by-step rule derivation log
LR Trace	Shift / Reduce action log
Token Inspector	Token stream table with type, value, line, column
Comparison Tab	Algorithm feature comparison + runtime stats

---

🧠 Supported Grammar

Arithmetic Mode

3 + 4 * 2 - 1;
(10 + 5) * (3 - 2);
2 ** 3 + 1;

Programming Language Mode

var x = 10;
var y = 20;
print(x + y);

function add(a, b) {
  return a + b;
}

if (x > 0) {
  print(x);
} else {
  print(-x);
}

while (i < 5) {
  i = i + 1;
}

for (var i = 0; i < 10; i = i + 1) {
  print(i * i);
}

---

🔍 Algorithms

LL (Recursive Descent) — Top-Down

• Starts from the root (Program) and expands rules recursively
• Each grammar rule = one Python method
• Uses 1-token lookahead to choose which rule to apply
• Steps shown: Rule predictions → Token matches

LR (Shift-Reduce / Pratt) — Bottom-Up

• Starts from tokens and reduces them into larger constructs
• Maintains an explicit operator-stack with precedence/associativity
• Steps shown: SHIFT (consume token) → REDUCE (apply rule)

---

📊 Complexity

	LL	LR
Time	O(n)	O(n)
Space	O(depth) — call stack	O(depth) — explicit stack
Grammar	LL(1)	LR(1) / stronger