Rekursiv descendant parser
From Wikipedia, the free encyclopedia
Remove ads
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.
 | 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. |
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.
Denne artikkelen er en spire. Du kan hjelpe Wikipedia ved å utvide den.
Autoritetsdata
Remove ads
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads