/
Forside
/
Teknologi
/
Udvikling
/
C/C++
/
Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn
*
Kodeord
*
Husk mig
Brugerservice
Kom godt i gang
Bliv medlem
Seneste indlæg
Find en bruger
Stil et spørgsmål
Skriv et tip
Fortæl en ven
Pointsystemet
Kontakt Kandu.dk
Emnevisning
Kategorier
Alfabetisk
Karriere
Interesser
Teknologi
Reklame
Top 10 brugere
C/C++
#
Navn
Point
1
BertelBra..
2425
2
pmbruun
695
3
Master_of..
501
4
jdjespers..
500
5
kyllekylle
500
6
Bech_bb
500
7
scootergr..
300
8
gibson
300
9
molokyle
287
10
strarup
270
måske OT: parserspørgsmål
Fra :
Viktoria Runge
Dato :
21-02-03 14:40
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?
Jens Axel Søgaard (
21-02-2003
)
Kommentar
Fra :
Jens Axel Søgaard
Dato :
21-02-03 16:13
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
Per Abrahamsen (
21-02-2003
)
Kommentar
Fra :
Per Abrahamsen
Dato :
21-02-03 16:18
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.
Søg
Alle emner
Teknologi
Udvikling
C/C++
Indstillinger
Spørgsmål
Tips
Usenet
Reklame
Statistik
Spørgsmål :
177491
Tips :
31966
Nyheder :
719565
Indlæg :
6408458
Brugere :
218886
Månedens bedste
Årets bedste
Sidste års bedste
Copyright © 2000-2024 kandu.dk. Alle rettigheder forbeholdes.