Den rekursive descent-parser er en top- down parsing - algoritme implementeret af gensidigt kaldende procedurer, hvor hver procedure svarer til en af reglerne for kontekstfri grammatik eller BNF . Anvendelser af reglerne sekventielt, fra venstre mod højre, bruger de tokens , der modtages fra den leksikalske analysator . Det er en af de enkleste parsingalgoritmer, velegnet til en fuldstændig manuel implementering.
For parsere af denne type er der behov for en passende COP-grammatik , specifikt en LL (k) grammatik, der tillader en af de alternative muligheder for at udvide hver ikke-terminal entydigt at blive valgt (forudsagt) for det næste token eller tokens.
En sådan parser kører i lineær tid.
En variant er LL-parseren , en implementering af en forudsigende parser med automatisk konstruktion af en "forudsigelsestabel", der bestemmer den passende regel for udvidelse af den ikke-terminale base baseret på den givne ikke-terminale og det næste token.
I stedet for at lave en forudsigelse, forsøger parseren blot at anvende alle alternative regelvalg i rækkefølge, indtil et af forsøgene lykkes.
En sådan parser kan kræve eksponentiel køretid og er ikke altid garanteret at fuldføre, afhængigt af grammatikken. Sårbar over for venstre rekursion .
| Formelle sprog og formelle grammatikker | |
|---|---|
| Generelle begreber | |
| Type 0 | |
| Type 1 |
|
| Type 2 | |
| Type 3 |
|
| parsing | |