Rekursiv descendant parser
 | Kildeløs: Denne artikkelen mangler kildehenvisninger, og opplysningene i den kan dermed være vanskelige å verifisere. Kildeløst materiale kan bli fjernet. |
 | Språkvask: Teksten i denne artikkelen kan ha behov for språkvask for å oppnå en høyere standard. Om du leser gjennom og korrigerer der nødvendig, kan du gjerne deretter fjerne denne malen. |
Innenfor informatikken er en rekursiv descendant parser en form for top-down parser som bygges fra et sett gjensidig rekursive prosedyrer, eller en ikke-rekursiv ekvivalent, hvor hver av prosedyrene implementerer en av produksjonene av grammatikken. Strukturen av det resulterende programmet speiler således grammatikken den anerkjenner.
En prediktv parser er en rekursiv descendant parser som ikke trenger backtracking. Prediktiv parsing er bare mulig for en LL(k)-grammatikk, som er en kontekstfri grammatikk for hvilken det eksisterer et positivt heltall k som tillater parseren å bestemme hvilken produksjon den skal bruke ved å undersøke bare de neste k token av innmatning. LL(k) grammatikken kan derfor ikke være tvetydig eller inneholde venstrerekursjon. Enhver kontekstfri grammatikk kan omdannes til en ekvivalent grammatikk uten venstrerekursjon, men å fjerne venstrerekursjon fører ikke alltid til en LL(k)-grammatikk. En prediktiv parser kjøres i lineær tid.