Analizatorul recursiv descent este un algoritm de parsare de sus în jos implementat prin proceduri de apelare reciprocă , în care fiecare procedură corespunde uneia dintre regulile gramaticii fără context sau BNF . Aplicarea regulilor secvenţial, de la stânga la dreapta, consumă jetoanele primite de la analizatorul lexical . Este unul dintre cei mai simpli algoritmi de analiză, potrivit pentru o implementare complet manuală.
Pentru analizatorii de acest tip, este necesară o gramatică COP adecvată , în special, o gramatică LL (k) care să permită una dintre opțiunile alternative pentru extinderea fiecărui non-terminal să fie selectată (prevăzută) fără ambiguitate pentru următorul simbol sau simboluri.
Un astfel de parser rulează în timp liniar.
O variantă este LL-parser , o implementare a unui parser predictiv cu construcția automată a unui „tabel de predicție” care determină regula potrivită pentru extinderea nonterminalului pe baza nonterminalului dat și a următorului simbol.
În loc să facă o predicție, analizatorul încearcă pur și simplu să aplice toate alegerile alternative de reguli în ordine, până când una dintre încercări reușește.
Un astfel de parser poate necesita un timp de rulare exponențial și nu este întotdeauna garantat să se completeze, în funcție de gramatică. Vulnerabil la recursiunea stângă .
| Limbi formale și gramatici formale | |
|---|---|
| Concepte generale | |
| Tip 0 | |
| Tipul 1 |
|
| Tip 2 | |
| Tip 3 | |
| analizare | |