Rekursiv descendant parser
 | Denne artikkelen mangler kildehenvisninger, og opplysningene i den kan dermed være vanskelige å verifisere. Kildeløst materiale kan bli fjernet. |
 | Språkvask: Denne artikkelen trenger språkvask og korrektur for å oppnå en høyere standard. Den som leser gjennom og bidrar med korrektur, må gjerne deretter fjerne denne malen. Når du åpner redigeringsfeltet, ser malen slik ut: {{Språkvask}} |
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.
