---

Jeg er (for første gang) igang med at udvikle en krydscompiler (i C++)
og er stødt i begreberne lookahead og backtracking i forbindelse med
parsing. Litteraturen forvirrer mig og er nu i tvivl om hvilke
parsingtyper der benytter sig af lookahead og backtracking samt hvilke
fordele og ulemper der er ved henholdsvis Top-down parsing og
Buttom-up parsing?

---

Viktoria Runge wrote:
> Jeg er (for første gang) igang med at udvikle en krydscompiler (i C++)
> og er stødt i begreberne lookahead og backtracking i forbindelse med
> parsing. Litteraturen forvirrer mig og er nu i tvivl om hvilke
> parsingtyper der benytter sig af lookahead og backtracking samt hvilke
> fordele og ulemper der er ved henholdsvis Top-down parsing og
> Buttom-up parsing?

Jeg vil vædde med, at du får flere svar i dk.edb.programmering.

--
Jens Axel Søgaard

---

Viktoria Runge <viktoria@ofir.dk> writes:

> Jeg er (for første gang) igang med at udvikle en krydscompiler (i C++)
> og er stødt i begreberne lookahead og backtracking i forbindelse med
> parsing. Litteraturen forvirrer mig og er nu i tvivl om hvilke
> parsingtyper der benytter sig af lookahead og backtracking samt hvilke
> fordele og ulemper der er ved henholdsvis Top-down parsing og
> Buttom-up parsing?

Jeg tror de klogeste hoveder i den slags spørgsmål holder til
dk.edb.programmering, xfut dertil.

Lookahead betyder at du kigge flere tokens fram før du beslutter dig
til hvad slags udtryk det er du skal parse. Eksempel

a + b

her er du nødt til til at kigge to tokens frem før du kan beslutte dig
til at det er et "plus" udtryk du er i gang med.

Backtracking betyder at du først prøver at parse et udtryk på en måde,
og hvis det ikke fungere laver du en "undo" og prøver igen på en ny
måde. F.eks. kunne du parse ovenstående med noget i stil med

void read_expression (Expression& expr)
{
save_state state;
if (read_multiply_expression (expr))
return;
backtrack (state);
if (read_addition_expression (expr))
return;
backtrack (state);
if (read_subtraction_expression (expr))
return;
// ...
}

En recursive-descent (top-down) parser for et ikke-trivielt sprog
bruger normalt både lookahead og backtracking. Men backtracking kan
være dyr så man prøver at undgå det.

Bottom-up parsere har jeg aldrig rigtig forstået.

Der er teorier der siger bottom-up parsere hurtigere, og de er ofte
genereret automatisk med tools som yacc. I praksis foretrækker jeg
dog en håndskrevet recusive descent parser fordi de er så dejligt
simple, jeg kan forstå hvad der foregår. Nogen påstår også r-d
parsere er hurtigere i praksis.