Yacc（BISON）でパーサーツリーを印刷するには

Question

BISONとFlEXを使用してC言語のパーサを作成しました。与えられたc-入力コードが構文的に間違っている場合、それは動作し、 "syntax error"を出力します。そうでなければ何も出力しません。

しかし、パーサーツリーは、パーサーの出力として特定のc-入力コードに関連して印刷します。それ、どうやったら出来るの？ BISONにはパーサーツリーを印刷するための関数がありますか？

Answer 1

TXR言語（http://www.nongnu.org/txr）は、入力を解析するためにFlexとYaccを使用しています。 -vオプションを指定すると、解析ツリーが表示されます。

例えば：

$ ./txr -v -c "@/[a-z]*|foo/" 
spec: 
(((text (#<sys:regex: 9d99268> or (0+ (set (#\a . #\z))) (compound #\f #\o #\o))))) 

あなたはパーサアクションのツリーを構築し、ツリーの印刷ルーチンでそれを自分で印刷します。人生を楽にするために、私はLispのようなオブジェクト表現を使用しました。 これを書くことは、すべての可能なオブジェクトタイプを認識し、それらを表記法にレンダリングする再帰的な印刷機能によって処理されます。たとえば上の例では、文字タイプのオブジェクトがハッシュバックスラッシュで表記されており、印刷できない不透明なコンパイル済みの正規表現は、#<...>と表記されています。ここで

は、文法の一部です：

regexpr : regbranch      { $$ = if3(cdr($1), 
                cons(compound_s, $1), 
                car($1)); } 
     | regexpr '|' regexpr   { $$ = list(or_s, $1, $3, nao); } 
     | regexpr '&' regexpr   { $$ = list(and_s, $1, $3, nao); } 
     | '~' regexpr     { $$ = list(compl_s, $2, nao); } 
     | /* empty */ %prec LOW   { $$ = nil; } 
     ; 

あなたが見ることができるように、ASTを構築することは、ネストされたリストの大部分は単純な構造です。 このフォームはコンパイルに非常に便利です。 NFAベースの正規表現コンパイラのトップレベル関数は、非常に読みやすいです。

/* 
* Input is the items from a regex form, 
* not including the regex symbol. 
* I.e. (rest '(regex ...)) not '(regex ...). 
*/ 
static nfa_t nfa_compile_regex(val exp) 
{ 
    if (nullp(exp)) { 
    nfa_state_t *acc = nfa_state_accept(); 
    nfa_state_t *s = nfa_state_empty(acc, 0); 
    return nfa_make(s, acc); 
    } else if (typeof(exp) == chr_s) { 
    nfa_state_t *acc = nfa_state_accept(); 
    nfa_state_t *s = nfa_state_single(acc, c_chr(exp)); 
    return nfa_make(s, acc); 
    } else if (exp == wild_s) { 
    nfa_state_t *acc = nfa_state_accept(); 
    nfa_state_t *s = nfa_state_wild(acc); 
    return nfa_make(s, acc); 
    } else { 
    val sym = first(exp), args = rest(exp); 

    if (sym == set_s) { 
     return nfa_compile_set(args, nil); 
    } else if (sym == cset_s) { 
     return nfa_compile_set(args, t); 
    } else if (sym == compound_s) { 
     return nfa_compile_list(args); 
    } else if (sym == zeroplus_s) { 
     nfa_t nfa_arg = nfa_compile_regex(first(args)); 
     nfa_state_t *acc = nfa_state_accept(); 
     /* New start state has empty transitions going through 
     the inner NFA, or skipping it right to the new acceptance state. */ 
     nfa_state_t *s = nfa_state_empty(nfa_arg.start, acc); 
     /* Convert acceptance state of inner NFA to one which has 
     an empty transition back to the start state, and 
     an empty transition to the new acceptance state. */ 
     nfa_state_empty_convert(nfa_arg.accept, nfa_arg.start, acc); 
     return nfa_make(s, acc); 
    } else if (sym == oneplus_s) { 
     /* One-plus case differs from zero-plus in that the new start state 
     does not have an empty transition to the acceptance state. 
     So the inner NFA must be traversed once. */ 
     nfa_t nfa_arg = nfa_compile_regex(first(args)); 
     nfa_state_t *acc = nfa_state_accept(); 
     nfa_state_t *s = nfa_state_empty(nfa_arg.start, 0); /* <-- diff */ 
     nfa_state_empty_convert(nfa_arg.accept, nfa_arg.start, acc); 
     return nfa_make(s, acc); 
    } else if (sym == optional_s) { 
     /* In this case, we can keep the acceptance state of the inner 
     NFA as the acceptance state of the new NFA. We simply add 
     a new start state which can short-circuit to it via an empty 
     transition. */ 
     nfa_t nfa_arg = nfa_compile_regex(first(args)); 
     nfa_state_t *s = nfa_state_empty(nfa_arg.start, nfa_arg.accept); 
     return nfa_make(s, nfa_arg.accept); 
    } else if (sym == or_s) { 
     /* Simple: make a new start and acceptance state, which form 
     the ends of a spindle that goes through two branches. */ 
     nfa_t nfa_first = nfa_compile_regex(first(args)); 
     nfa_t nfa_second = nfa_compile_regex(second(args)); 
     nfa_state_t *acc = nfa_state_accept(); 
     /* New state s has empty transitions into each inner NFA. */ 
     nfa_state_t *s = nfa_state_empty(nfa_first.start, nfa_second.start); 
     /* Acceptance state of each inner NFA converted to empty 
     transition to new combined acceptance state. */ 
     nfa_state_empty_convert(nfa_first.accept, acc, 0); 
     nfa_state_empty_convert(nfa_second.accept, acc, 0); 
     return nfa_make(s, acc); 
    } else { 
     internal_error("bad operator in regex"); 
    } 
    } 
}