Hvad er Lookahead i parsing?

Lookahead er en funktion i nogle programmeringssprog, der gør det muligt for parseren at kigge fremad på det n
ste token eller tokens i inputstrømmen og bruge denne information til at bestemme programmets struktur.

Med andre ord giver lookahead parseren mulighed for at se, hvad der kommer op. n
ste i inputstrømmen, før den rent faktisk analyserer den. Dette kan v
re nyttigt til at løse uklarheder i grammatikken, som f.eks. når en s
tning kan parses på flere måder.

Overvej f.eks. følgende s
tning:

"Katten jagtede musen."

Denne s
tning er grammatisk tvetydig, fordi den kunne parses. som enten "Katten jagtede musen" eller "Jagtede musen katten." For at løse denne tvetydighed kan en parser bruge lookahead til at kigge fremad på det n
ste token og bestemme, hvilken parsing der er korrekt. Hvis den n
ste token er "the", så er den første parsing korrekt, men hvis den n
ste token er "chased", så er den anden parsing korrekt.

Lookahead kan implementeres på forskellige måder afh
ngigt af sproget og den parser, der bruges. Nogle almindelige teknikker til implementering af lookahead omfatter:

1. Venstre rekursion: I denne teknik kalder parseren rekursivt sig selv for at parse resten af inputstrømmen ved at bruge informationen, den indsamler fra det aktuelle token til at bestemme, hvordan det n
ste token skal analyseres.
2. Højre rekursion: I denne teknik kalder parseren rekursivt sig selv for at parse det forrige token ved at bruge informationen, den indsamler fra det aktuelle token til at bestemme, hvordan det n
ste token skal analyseres.
3. Prediktiv parsing: I denne teknik bruger parseren en statistisk model til at forudsige det n
ste token i inputstrømmen og bruger denne forudsigelse til at guide sin parsing.
4. CYK-parsing: I denne teknik bruger parseren en tabel med v
rdier til at holde styr på de mulige parse-tr
er for inputstrømmen og bruger lookahead-information til at besk
re søgerummet og finde det korrekte parse-tr
.

Overordnet set er lookahead en kraftfuld funktion, der kan hj
lpe parsere med at håndtere tvetydighed i naturlige sprogbehandlingsopgaver, men det kan også v
re beregningsm
ssigt dyrt og er muligvis ikke altid nødvendigt afh
ngigt af den specifikke brugssag.