Svans rekursiv parser
Inom datavetenskap är svansrekursiva parsers en härledning från de vanligare rekursiva descentparsarna . Tail rekursiva parsers används vanligtvis för att analysera vänster rekursiva grammatiker. De använder en mindre mängd stackutrymme än vanliga rekursiva descentparsers. De är också lätta att skriva. Typiska rekursiva descent-parsers gör det omöjligt att tolka vänster rekursiva grammatiker (på grund av ett problem med oändlig loop). Tail rekursiva parsers använder en nod reparenting-teknik som gör detta tillåtet.
Exempel
Med tanke på en EBNF- grammatik som följande:
E : T T : T { '+' F } | F F : F { '*' I } | I I : < identifierare >
En enkel rekursiv svanstolkare kan skrivas ungefär som en rekursiv descentparser. Den typiska algoritmen för att analysera en grammatik som denna med ett abstrakt syntaxträd är:
- Analysera nästa nivå av grammatiken och få dess utdataträd, utse det till det första trädet, F
- Medan det finns terminerande token, T , som kan sättas som förälder till denna nod:
- Tilldela en ny nod, N
- Ställ in N :s nuvarande operatör som aktuell inmatningstoken
- Förflytta inmatningen en token
- Ställ in N :s vänstra underträd som F
- Analysera en annan nivå ner igen och lagra detta som nästa träd, X
- Ställ in N :s högra underträd som X
- Ställ in F till N
- Retur N
Ett grundläggande exempel på denna typ av parser i C visas här. Implementeringsdetaljer har utelämnats för enkelhets skull.
typedef struct _exptree exptree ; struct _exptree { char token ; exptree * vänster ; exptree * höger ; }; exptree * parse_e ( void ) { return parse_t (); } exptree * parse_t ( void ) { exptree * first_f = parse_f (); while ( cur_token () == '+' ) { exptree * replace_tree = alloc_tree (); replace_tree -> token = cur_token (); replace_tree -> left = first_f ; nästa_token (); ersätt_träd -> höger = parse_f (); first_f = ersätt_träd ; } returnera first_f ; } exptree * parse_f ( void ) { exptree * first_i = parse_i (); while ( cur_token () == '*' ) { exptree * replace_tree = alloc_tree (); replace_tree -> token = cur_token (); replace_tree -> left = first_i ; nästa_token (); ersätt_träd -> höger = parse_i (); first_i = ersätt_träd ; } returnera first_i ; } exptree * parse_i ( void ) { exptree * i = alloc_tree (); i -> vänster = i -> höger = NULL ; i -> token = cur_token (); nästa_token (); returnera i ; }