Redigerer Rekursiv descendant parser

{{kildeløs}}
{{språkvask}}
Innenfor [[informatikk]]en er en '''rekursiv descendant parser''' en form for top-down [[parsing|parser]] som bygges fra et sett [[gjensidig rekursjon|gjensidig rekursive]] prosedyrer, eller en ikke-rekursiv ekvivalent, hvor hver av prosedyrene implementerer en av [[Produksjon (informatikk)|produksjonene]] av [[grammatikk]]en. 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-parser|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]].

{{stubb}}
{{Autoritetsdata}}

[[Kategori:Parsingalgoritmer]]