📘 1. Grammar (Formal Grammar)

✅ Definition

A Grammar is a set of rules (productions) used to generate strings in a language.

👉 In compiler design, grammar defines the syntax of programming languages.

---

🧠 Components of a Grammar

A grammar is written as:

G = (V, T, P, S)

Where:

Symbol	Meaning
V	Variables (Non-terminals)
T	Terminals
P	Production Rules
S	Start Symbol

---

📌 Example Grammar

E → E + T | T
T → id

• E, T → Non-terminals
• +, id → Terminals
• E → E + T → Production rule
• E → Start symbol

---

⭐ Key Points (Exam)

👉 Grammar defines structure of language 👉 Uses production rules 👉 Start symbol is very important

---

🧠 2. Types of Symbols

🔹 1. Terminals

• Actual symbols in the language
• Cannot be replaced

👉 Example: id, +, *, ( )

---

🔹 2. Non-Terminals

• Variables used to generate strings
• Can be replaced

👉 Example: E, T

---

---

🔍 3. Derivation

✅ Definition

A Derivation is the process of generating a string from the start symbol using production rules.

---

🔄 Types of Derivations

---

🔹 1. Leftmost Derivation (LMD)

👉 Always replace the leftmost non-terminal first

---

🔹 2. Rightmost Derivation (RMD)

👉 Always replace the rightmost non-terminal first

---

📌 Example Grammar

E → E + T | T
T → id

---

🎯 Derive String: id + id

---

🔹 Leftmost Derivation

E ⇒ E + T
  ⇒ T + T
  ⇒ id + T
  ⇒ id + id

---

🔹 Rightmost Derivation

E ⇒ E + T
  ⇒ E + id
  ⇒ T + id
  ⇒ id + id

---

⭐ Key Points (Exam)

👉 LMD → Leftmost first 👉 RMD → Rightmost first 👉 Both produce same string

---

🌳 4. Parse Tree (Very Important)

✅ Definition

A Parse Tree is a tree representation of a derivation showing how a string is generated from the grammar.

---

📊 Structure

• Root → Start symbol
• Internal nodes → Non-terminals
• Leaves → Terminals

---

📌 Example: id + id

Grammar:

E → E + T
E → T
T → id

---

🌳 Parse Tree

        E
      / | \
     E  +  T
     |     |
     T     id
     |
     id

---

🧠 Explanation

• Root = E
• Leaves = id + id
• Shows structure clearly

---

⭐ Key Points (Exam)

👉 Parse tree shows hierarchical structure 👉 Same parse tree for both LMD & RMD 👉 Used in syntax analysis

---

🔄 5. Relationship Between Concepts

Grammar → Derivation → Parse Tree

• Grammar defines rules
• Derivation generates string
• Parse tree shows structure

---

⚠️ 6. Ambiguity (Important Concept)

✅ Definition

A grammar is ambiguous if it has more than one parse tree for the same string.

---

📌 Example

E → E + E | id

String: id + id + id

👉 Can have multiple parse trees ❌

---

⭐ Exam Point

👉 Ambiguity is undesirable in compilers

---

🎯 7. Important Exam Concepts

👉 Frequently asked:

• Define grammar with components
• Define derivation
• Difference between LMD and RMD
• Construct parse tree
• What is ambiguity?
• Draw parse tree for given string

---

📝 8. Short Notes (Quick Revision)

Grammar

• Set of rules
• Defines syntax

Derivation

• Step-by-step string generation
• LMD & RMD

Parse Tree

• Tree representation
• Shows structure

---

📊 9. Final Summary Table

Aspect	Grammar	Derivation	Parse Tree
Definition	Set of rules	Process of generating string	Tree representation
Purpose	Define syntax	Generate strings	Show structure
Form	Rules	Steps	Tree
Components	V, T, P, S	Production steps	Nodes & edges
Types	—	LMD, RMD	—
Output	Language	String	Tree
Importance	Very High	High	Very High

---

✅ Final Conclusion

• Grammar defines the structure of a language
• Derivation shows how strings are formed
• Parse Tree visually represents the structure
• All three are core concepts in syntax analysis

---