Loading article…
コンピュータサイエンスにおいて、末尾再帰パーサーは、より一般的な再帰下降パーサーから派生したものです。末尾再帰パーサーは、左再帰文法を解析するためによく使用されます。ランタイムまたはコンパイルツールが末尾呼び出しをジャンプに最適化する方法を備えている場合、通常の再帰下降パーサーよりもスタック領域の使用量が少なくなります。また、記述も容易です。典型的な再帰下降パーサーでは、左再帰文法の解析は不可能です（無限ループの問題のため）。末尾再帰パーサーは、ノードの再親付け技術を使用することで、これを可能にします。
以下のようなEBNF文法が与えられた場合：
E : T T : T { '+' F } | F F : F { '*' I } | I I : <識別子>単純な末尾再帰構文解析器は、再帰下降構文解析器とほぼ同じように記述できます。抽象構文木を使用してこのような文法を解析する典型的なアルゴリズムは次のとおりです。
この種のパーサーの基本的なC言語の例を以下に示します。簡略化のため、実装の詳細は省略しています。
typedef struct _exptree exptree ; struct _exptree { char token ; exptree * left ; exptree * right ; };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 ; next_token (); replace_tree -> right = parse_f (); first_f = replace_tree ; }return 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 ; next_token (); replace_tree -> right = parse_i (); first_i = replace_tree ; } return first_i ; }exptree * parse_i ( void ) { exptree * i = alloc_tree (); i -> left = i -> right = NULL ; i -> token = cur_token (); next_token (); return i ; }