Ocasní rekurzivní analyzátor - Tail recursive parser

v počítačová věda, rekurzivní analyzátory ocasu jsou odvozením od běžnějších analyzátory rekurzivního sestupu. Ocasní rekurzivní analyzátory se běžně používají k analýze vlevo rekurzivní gramatiky. Využívají menší množství místa v zásobníku než běžné analyzátory rekurzivního sestupu. Jsou také snadno psatelné. Typické analyzátory rekurzivního sestupu znemožňují syntézu levé rekurzivní gramatiky (kvůli problému s nekonečnou smyčkou). Ocasní rekurzivní analyzátory používají techniku ​​opětovného vytváření uzlů, díky níž je to možné.

Příklad

Vzhledem k EBNF Gramatika, například následující:

 E: T T: T { '+' F } | F F: F { '*' Já } | Já Já: <identifikátor>

Jednoduchý rekurzivní analyzátor ocasu lze napsat podobně jako analyzátor rekurzivního sestupu. Typický algoritmus pro analýzu takové gramatiky pomocí abstraktní syntaxový strom je:

  1. Analyzujte další úroveň gramatiky a získejte její výstupní strom, označte jej jako první strom, F
  2. Zatímco existuje koncový token, T, které lze vložit jako nadřazenou položku tohoto uzlu:
    1. Přidělit nový uzel, N
    2. Soubor Naktuální operátor jako aktuální vstupní token
    3. Posuňte vstup o jeden token předem
    4. Soubor Nlevý podstrom jako F
    5. Opět analyzujte další úroveň a uložte ji jako další strom, X
    6. Soubor Npravý podstrom jako X
    7. Soubor F na N
  3. Vrátit se N

Základní příklad tohoto druhu analyzátoru v C je zde zobrazen. Podrobnosti implementace byly pro jednoduchost vynechány.

typedef struktur _exptree exptree;struktur _exptree {	char žeton;	exptree *vlevo, odjet;	exptree *že jo;};exptree *parse_e(prázdnota){	vrátit se parse_t();}exptree *parse_t(prázdnota){	exptree *first_f = parse_f();		zatímco (cur_token() == '+') {		exptree *replace_tree = alloc_tree();		replace_tree->žeton = cur_token();		replace_tree->vlevo, odjet = first_f;		next_token();		replace_tree->že jo = parse_f();		first_f = replace_tree;	}	vrátit se first_f;}exptree *parse_f(prázdnota){	exptree *first_i = parse_i();		zatímco (cur_token() == '*') {		exptree *replace_tree = alloc_tree();		replace_tree->žeton = cur_token();		replace_tree->vlevo, odjet = first_i;		next_token();		replace_tree->že jo = parse_i();		first_i = replace_tree;	}		vrátit se first_i;}exptree *parse_i(prázdnota){	exptree *i = alloc_tree();	i->vlevo, odjet = i->že jo = NULA;	i->žeton = cur_token();	next_token();	vrátit se i;}

Viz také

Další čtení