SlideShare a Scribd company logo
Recursion
Index
Definition for Recursion
Classification of Recursion
About Left Recursion
Elimination of Left Recursion and
Example
Definition
• Recursion is the process a procedure goes through when one of the
steps of the procedure involves invoking the procedure itself
Classification
Recursion
Left recursion Right recursion
Left Recursion
A→A𝛼/𝛽
A
A
A
A
𝛼
𝛼
𝛼
𝛽
A
𝛽
Top down parser doesn’t allow in
Left Recursion bcz of it’s infinite problem.
So… we need to eliminate this problem.
Infinite problem
Elimination of Left Recursion
A→A𝛼/𝛽
A
A
A
A
𝛼
𝛼
𝛼
𝛽
A
𝛽
𝛽 𝛼*
Elimination of Left Recursion
𝐴 → 𝛽 𝛼*
𝐴 → 𝛽𝐴′
𝐴′
→ 𝛼𝐴′
/∈
𝐴 → 𝛽𝐴′
𝐴′
→ 𝛼𝐴′
/∈
A→A𝛼/𝛽
Example
E →E +T / T
𝐴 → 𝛽𝐴′
𝐴′
→ 𝛼𝐴′
/∈
A→A𝛼/𝛽
A A 𝛼 𝛽
E→ 𝑇𝐸′
𝐸′
→ +𝑇 𝐸′
/∈
Thanks for your attention!
Any Question??...
Ad

More Related Content

What's hot (20)

Compiler design syntax analysis
Compiler design syntax analysisCompiler design syntax analysis
Compiler design syntax analysis
Richa Sharma
 
Function overloading and overriding
Function overloading and overridingFunction overloading and overriding
Function overloading and overriding
Rajab Ali
 
Circular link list.ppt
Circular link list.pptCircular link list.ppt
Circular link list.ppt
Tirthika Bandi
 
Operator precedance parsing
Operator precedance parsingOperator precedance parsing
Operator precedance parsing
sanchi29
 
Heuristc Search Techniques
Heuristc Search TechniquesHeuristc Search Techniques
Heuristc Search Techniques
Jismy .K.Jose
 
Kleene's theorem
Kleene's theoremKleene's theorem
Kleene's theorem
Mobeen Mustafa
 
Unit iv(simple code generator)
Unit iv(simple code generator)Unit iv(simple code generator)
Unit iv(simple code generator)
Kalaimathi Vijayakumar
 
Bottom up parser
Bottom up parserBottom up parser
Bottom up parser
Akshaya Arunan
 
closure properties of regular language.pptx
closure properties of regular language.pptxclosure properties of regular language.pptx
closure properties of regular language.pptx
Thirumoorthy64
 
Inline function in C++
Inline function in C++Inline function in C++
Inline function in C++
Jenish Patel
 
Parsing
ParsingParsing
Parsing
khush_boo31
 
Recursive Descent Parsing
Recursive Descent Parsing  Recursive Descent Parsing
Recursive Descent Parsing
Md Tajul Islam
 
Top down parsing
Top down parsingTop down parsing
Top down parsing
ASHOK KUMAR REDDY
 
Topological sort
Topological sortTopological sort
Topological sort
Burhan Ahmed
 
Data Hazard and Solution for Data Hazard
Data Hazard and Solution for Data HazardData Hazard and Solution for Data Hazard
Data Hazard and Solution for Data Hazard
COMSATS Institute of Information Technology
 
Phases of Compiler
Phases of CompilerPhases of Compiler
Phases of Compiler
Tanzeela_Hussain
 
Polymorphism
PolymorphismPolymorphism
Polymorphism
Nochiketa Chakraborty
 
Lexical analysis - Compiler Design
Lexical analysis - Compiler DesignLexical analysis - Compiler Design
Lexical analysis - Compiler Design
Muhammed Afsal Villan
 
Syntax Directed Definition and its applications
Syntax Directed Definition and its applicationsSyntax Directed Definition and its applications
Syntax Directed Definition and its applications
ShivanandManjaragi2
 
Parsing
ParsingParsing
Parsing
ShrikantSharma86
 

More from Shamsul Huda (6)

Error Recovery strategies and yacc | Compiler Design
Error Recovery strategies and yacc | Compiler DesignError Recovery strategies and yacc | Compiler Design
Error Recovery strategies and yacc | Compiler Design
Shamsul Huda
 
Postfix Notation | Compiler design
Postfix Notation | Compiler designPostfix Notation | Compiler design
Postfix Notation | Compiler design
Shamsul Huda
 
Economics problems and prospects of Bangladesh
Economics problems and prospects of BangladeshEconomics problems and prospects of Bangladesh
Economics problems and prospects of Bangladesh
Shamsul Huda
 
Learning Objectives of (Management Information System)MIS
Learning Objectives of (Management Information System)MISLearning Objectives of (Management Information System)MIS
Learning Objectives of (Management Information System)MIS
Shamsul Huda
 
Global impact of greenhouse effect
Global impact of greenhouse effectGlobal impact of greenhouse effect
Global impact of greenhouse effect
Shamsul Huda
 
architecture memory interfacing
architecture memory interfacingarchitecture memory interfacing
architecture memory interfacing
Shamsul Huda
 
Error Recovery strategies and yacc | Compiler Design
Error Recovery strategies and yacc | Compiler DesignError Recovery strategies and yacc | Compiler Design
Error Recovery strategies and yacc | Compiler Design
Shamsul Huda
 
Postfix Notation | Compiler design
Postfix Notation | Compiler designPostfix Notation | Compiler design
Postfix Notation | Compiler design
Shamsul Huda
 
Economics problems and prospects of Bangladesh
Economics problems and prospects of BangladeshEconomics problems and prospects of Bangladesh
Economics problems and prospects of Bangladesh
Shamsul Huda
 
Learning Objectives of (Management Information System)MIS
Learning Objectives of (Management Information System)MISLearning Objectives of (Management Information System)MIS
Learning Objectives of (Management Information System)MIS
Shamsul Huda
 
Global impact of greenhouse effect
Global impact of greenhouse effectGlobal impact of greenhouse effect
Global impact of greenhouse effect
Shamsul Huda
 
architecture memory interfacing
architecture memory interfacingarchitecture memory interfacing
architecture memory interfacing
Shamsul Huda
 
Ad

Recently uploaded (20)

Chemotherapy of Malignancy -Anticancer.pptx
Chemotherapy of Malignancy -Anticancer.pptxChemotherapy of Malignancy -Anticancer.pptx
Chemotherapy of Malignancy -Anticancer.pptx
Mayuri Chavan
 
BÀI TẬP BỔ TRỢ TIẾNG ANH 9 THEO ĐƠN VỊ BÀI HỌC - GLOBAL SUCCESS - CẢ NĂM (TỪ...
BÀI TẬP BỔ TRỢ TIẾNG ANH 9 THEO ĐƠN VỊ BÀI HỌC - GLOBAL SUCCESS - CẢ NĂM (TỪ...BÀI TẬP BỔ TRỢ TIẾNG ANH 9 THEO ĐƠN VỊ BÀI HỌC - GLOBAL SUCCESS - CẢ NĂM (TỪ...
BÀI TẬP BỔ TRỢ TIẾNG ANH 9 THEO ĐƠN VỊ BÀI HỌC - GLOBAL SUCCESS - CẢ NĂM (TỪ...
Nguyen Thanh Tu Collection
 
spinal cord disorders (Myelopathies and radiculoapthies)
spinal cord disorders (Myelopathies and radiculoapthies)spinal cord disorders (Myelopathies and radiculoapthies)
spinal cord disorders (Myelopathies and radiculoapthies)
Mohamed Rizk Khodair
 
Rebuilding the library community in a post-Twitter world
Rebuilding the library community in a post-Twitter worldRebuilding the library community in a post-Twitter world
Rebuilding the library community in a post-Twitter world
Ned Potter
 
ANTI-VIRAL DRUGS unit 3 Pharmacology 3.pptx
ANTI-VIRAL DRUGS unit 3 Pharmacology 3.pptxANTI-VIRAL DRUGS unit 3 Pharmacology 3.pptx
ANTI-VIRAL DRUGS unit 3 Pharmacology 3.pptx
Mayuri Chavan
 
E-Filing_of_Income_Tax.pptx and concept of form 26AS
E-Filing_of_Income_Tax.pptx and concept of form 26ASE-Filing_of_Income_Tax.pptx and concept of form 26AS
E-Filing_of_Income_Tax.pptx and concept of form 26AS
Abinash Palangdar
 
puzzle Irregular Verbs- Simple Past Tense
puzzle Irregular Verbs- Simple Past Tensepuzzle Irregular Verbs- Simple Past Tense
puzzle Irregular Verbs- Simple Past Tense
OlgaLeonorTorresSnch
 
"Heraldry Detective Project"- Coats of Arms and Mottos of "Ivanhoe" in Ivanho...
"Heraldry Detective Project"- Coats of Arms and Mottos of "Ivanhoe" in Ivanho..."Heraldry Detective Project"- Coats of Arms and Mottos of "Ivanhoe" in Ivanho...
"Heraldry Detective Project"- Coats of Arms and Mottos of "Ivanhoe" in Ivanho...
ruslana1975
 
How to Manage Manual Reordering Rule in Odoo 18 Inventory
How to Manage Manual Reordering Rule in Odoo 18 InventoryHow to Manage Manual Reordering Rule in Odoo 18 Inventory
How to Manage Manual Reordering Rule in Odoo 18 Inventory
Celine George
 
2025 The Senior Landscape and SET plan preparations.pptx
2025 The Senior Landscape and SET plan preparations.pptx2025 The Senior Landscape and SET plan preparations.pptx
2025 The Senior Landscape and SET plan preparations.pptx
mansk2
 
Mental Health Assessment in 5th semester bsc. nursing and also used in 2nd ye...
Mental Health Assessment in 5th semester bsc. nursing and also used in 2nd ye...Mental Health Assessment in 5th semester bsc. nursing and also used in 2nd ye...
Mental Health Assessment in 5th semester bsc. nursing and also used in 2nd ye...
parmarjuli1412
 
TERMINOLOGIES,GRIEF PROCESS AND LOSS AMD ITS TYPES .pptx
TERMINOLOGIES,GRIEF PROCESS AND LOSS AMD ITS TYPES .pptxTERMINOLOGIES,GRIEF PROCESS AND LOSS AMD ITS TYPES .pptx
TERMINOLOGIES,GRIEF PROCESS AND LOSS AMD ITS TYPES .pptx
PoojaSen20
 
How to Manage Amounts in Local Currency in Odoo 18 Purchase
How to Manage Amounts in Local Currency in Odoo 18 PurchaseHow to Manage Amounts in Local Currency in Odoo 18 Purchase
How to Manage Amounts in Local Currency in Odoo 18 Purchase
Celine George
 
U3 ANTITUBERCULAR DRUGS Pharmacology 3.pptx
U3 ANTITUBERCULAR DRUGS Pharmacology 3.pptxU3 ANTITUBERCULAR DRUGS Pharmacology 3.pptx
U3 ANTITUBERCULAR DRUGS Pharmacology 3.pptx
Mayuri Chavan
 
CNS infections (encephalitis, meningitis & Brain abscess
CNS infections (encephalitis, meningitis & Brain abscessCNS infections (encephalitis, meningitis & Brain abscess
CNS infections (encephalitis, meningitis & Brain abscess
Mohamed Rizk Khodair
 
Cyber security COPA ITI MCQ Top Questions
Cyber security COPA ITI MCQ Top QuestionsCyber security COPA ITI MCQ Top Questions
Cyber security COPA ITI MCQ Top Questions
SONU HEETSON
 
COPA Apprentice exam Questions and answers PDF
COPA Apprentice exam Questions and answers PDFCOPA Apprentice exam Questions and answers PDF
COPA Apprentice exam Questions and answers PDF
SONU HEETSON
 
YSPH VMOC Special Report - Measles Outbreak Southwest US 5-14-2025 .pptx
YSPH VMOC Special Report - Measles Outbreak  Southwest US 5-14-2025  .pptxYSPH VMOC Special Report - Measles Outbreak  Southwest US 5-14-2025  .pptx
YSPH VMOC Special Report - Measles Outbreak Southwest US 5-14-2025 .pptx
Yale School of Public Health - The Virtual Medical Operations Center (VMOC)
 
Classification of mental disorder in 5th semester bsc. nursing and also used ...
Classification of mental disorder in 5th semester bsc. nursing and also used ...Classification of mental disorder in 5th semester bsc. nursing and also used ...
Classification of mental disorder in 5th semester bsc. nursing and also used ...
parmarjuli1412
 
How To Maximize Sales Performance using Odoo 18 Diverse views in sales module
How To Maximize Sales Performance using Odoo 18 Diverse views in sales moduleHow To Maximize Sales Performance using Odoo 18 Diverse views in sales module
How To Maximize Sales Performance using Odoo 18 Diverse views in sales module
Celine George
 
Chemotherapy of Malignancy -Anticancer.pptx
Chemotherapy of Malignancy -Anticancer.pptxChemotherapy of Malignancy -Anticancer.pptx
Chemotherapy of Malignancy -Anticancer.pptx
Mayuri Chavan
 
BÀI TẬP BỔ TRỢ TIẾNG ANH 9 THEO ĐƠN VỊ BÀI HỌC - GLOBAL SUCCESS - CẢ NĂM (TỪ...
BÀI TẬP BỔ TRỢ TIẾNG ANH 9 THEO ĐƠN VỊ BÀI HỌC - GLOBAL SUCCESS - CẢ NĂM (TỪ...BÀI TẬP BỔ TRỢ TIẾNG ANH 9 THEO ĐƠN VỊ BÀI HỌC - GLOBAL SUCCESS - CẢ NĂM (TỪ...
BÀI TẬP BỔ TRỢ TIẾNG ANH 9 THEO ĐƠN VỊ BÀI HỌC - GLOBAL SUCCESS - CẢ NĂM (TỪ...
Nguyen Thanh Tu Collection
 
spinal cord disorders (Myelopathies and radiculoapthies)
spinal cord disorders (Myelopathies and radiculoapthies)spinal cord disorders (Myelopathies and radiculoapthies)
spinal cord disorders (Myelopathies and radiculoapthies)
Mohamed Rizk Khodair
 
Rebuilding the library community in a post-Twitter world
Rebuilding the library community in a post-Twitter worldRebuilding the library community in a post-Twitter world
Rebuilding the library community in a post-Twitter world
Ned Potter
 
ANTI-VIRAL DRUGS unit 3 Pharmacology 3.pptx
ANTI-VIRAL DRUGS unit 3 Pharmacology 3.pptxANTI-VIRAL DRUGS unit 3 Pharmacology 3.pptx
ANTI-VIRAL DRUGS unit 3 Pharmacology 3.pptx
Mayuri Chavan
 
E-Filing_of_Income_Tax.pptx and concept of form 26AS
E-Filing_of_Income_Tax.pptx and concept of form 26ASE-Filing_of_Income_Tax.pptx and concept of form 26AS
E-Filing_of_Income_Tax.pptx and concept of form 26AS
Abinash Palangdar
 
puzzle Irregular Verbs- Simple Past Tense
puzzle Irregular Verbs- Simple Past Tensepuzzle Irregular Verbs- Simple Past Tense
puzzle Irregular Verbs- Simple Past Tense
OlgaLeonorTorresSnch
 
"Heraldry Detective Project"- Coats of Arms and Mottos of "Ivanhoe" in Ivanho...
"Heraldry Detective Project"- Coats of Arms and Mottos of "Ivanhoe" in Ivanho..."Heraldry Detective Project"- Coats of Arms and Mottos of "Ivanhoe" in Ivanho...
"Heraldry Detective Project"- Coats of Arms and Mottos of "Ivanhoe" in Ivanho...
ruslana1975
 
How to Manage Manual Reordering Rule in Odoo 18 Inventory
How to Manage Manual Reordering Rule in Odoo 18 InventoryHow to Manage Manual Reordering Rule in Odoo 18 Inventory
How to Manage Manual Reordering Rule in Odoo 18 Inventory
Celine George
 
2025 The Senior Landscape and SET plan preparations.pptx
2025 The Senior Landscape and SET plan preparations.pptx2025 The Senior Landscape and SET plan preparations.pptx
2025 The Senior Landscape and SET plan preparations.pptx
mansk2
 
Mental Health Assessment in 5th semester bsc. nursing and also used in 2nd ye...
Mental Health Assessment in 5th semester bsc. nursing and also used in 2nd ye...Mental Health Assessment in 5th semester bsc. nursing and also used in 2nd ye...
Mental Health Assessment in 5th semester bsc. nursing and also used in 2nd ye...
parmarjuli1412
 
TERMINOLOGIES,GRIEF PROCESS AND LOSS AMD ITS TYPES .pptx
TERMINOLOGIES,GRIEF PROCESS AND LOSS AMD ITS TYPES .pptxTERMINOLOGIES,GRIEF PROCESS AND LOSS AMD ITS TYPES .pptx
TERMINOLOGIES,GRIEF PROCESS AND LOSS AMD ITS TYPES .pptx
PoojaSen20
 
How to Manage Amounts in Local Currency in Odoo 18 Purchase
How to Manage Amounts in Local Currency in Odoo 18 PurchaseHow to Manage Amounts in Local Currency in Odoo 18 Purchase
How to Manage Amounts in Local Currency in Odoo 18 Purchase
Celine George
 
U3 ANTITUBERCULAR DRUGS Pharmacology 3.pptx
U3 ANTITUBERCULAR DRUGS Pharmacology 3.pptxU3 ANTITUBERCULAR DRUGS Pharmacology 3.pptx
U3 ANTITUBERCULAR DRUGS Pharmacology 3.pptx
Mayuri Chavan
 
CNS infections (encephalitis, meningitis & Brain abscess
CNS infections (encephalitis, meningitis & Brain abscessCNS infections (encephalitis, meningitis & Brain abscess
CNS infections (encephalitis, meningitis & Brain abscess
Mohamed Rizk Khodair
 
Cyber security COPA ITI MCQ Top Questions
Cyber security COPA ITI MCQ Top QuestionsCyber security COPA ITI MCQ Top Questions
Cyber security COPA ITI MCQ Top Questions
SONU HEETSON
 
COPA Apprentice exam Questions and answers PDF
COPA Apprentice exam Questions and answers PDFCOPA Apprentice exam Questions and answers PDF
COPA Apprentice exam Questions and answers PDF
SONU HEETSON
 
Classification of mental disorder in 5th semester bsc. nursing and also used ...
Classification of mental disorder in 5th semester bsc. nursing and also used ...Classification of mental disorder in 5th semester bsc. nursing and also used ...
Classification of mental disorder in 5th semester bsc. nursing and also used ...
parmarjuli1412
 
How To Maximize Sales Performance using Odoo 18 Diverse views in sales module
How To Maximize Sales Performance using Odoo 18 Diverse views in sales moduleHow To Maximize Sales Performance using Odoo 18 Diverse views in sales module
How To Maximize Sales Performance using Odoo 18 Diverse views in sales module
Celine George
 
Ad

Recursion (left recursion) | Compiler design

  翻译: