cを使用してスキームのようなツリー（グラフ）ダンプを横断する

StackOverflow https://stackoverflow.com/questions/7335275

  •  27-10-2019
  •  | 
  •  

質問

私はスキームのような木を持っています グラフ 構造。 Cを使用していくつかのメモリ表現に分析し、その上を歩きたいです。

これを行うためのパーサーのライブラリやフロントエンドはありますか？

編集：

次の式を解析しました

true && (false || true) ;
true ;
false || false

次のように（これは私のスキームのような木ダンプです） 

(PROG [(AndExp TVal(OrExp FValTVal)), TVal, (OrExp FValFVal)])

Cを使用してトラバースしたい（Cを使用するだけで作業する他の人にそれを与える必要があります）。 Progはラベルです。 andExp、orexpなどは&&のトークンです||など..

役に立ちましたか？

解決

これは一形態のようです S-Expression. 。多分 このS-Expressionパーサー ニーズに合わせて変更できます。

他のヒント

私はあなたの要件を理解したと思いますが、よくわかりません。

プレフィックス表記に式があります。したがって、これは基本的に、バイナリツリーのダンプファイルにあるプレフィックス式をロードすることです。

これは、式をツリーにロードするプロセスを説明する擬似コードです。

tree_node make_tree (string dump)
{
  tok1 = get_tok (dump);
  tok2 = get_tok (dump);
  tok3 = get_tok (dump);

  if (tok1 == operand)
  {
    node = make_new_node_with (tok1);
    return node;
  }

  node = make_new_node_with (tok1);
  node->left = make_tree (tok2);
  node->right = make_tree (tok3);
  return node;
}

  • 再帰 電話1に電話します と (AndExp TVal(OrExp FValTVal))

    tok1 = AndExp 新しいnode1を作成します

    tok2 = TVal

    tok3 = (OrExp FValTVal)

  • 再帰 2に電話してください と TVal node2をに返します 電話1に電話します Node1の左ポインターとリンクします。

  • 再帰 3に電話してください と (OrExp FValTVal) 通話1から。

    tok1 = ORExp 新しいnode3を作成します

    tok2 = FVal

    tok3 = TVal

  • 再帰 3に電話してください と FVal と 4に電話してください と TVal それぞれ、node4とnode5をオペランド値を返します。オペランド値は、コール3のnode3の左右のリンクにリンクされます。

考慮されるべきサブエグポンションはもうありませんが、再帰は出発点に戻ります。あなたは木の根を持っています。

                         ( node1 )
                         |AndExp |
                         +---+---+
                             |
                +------------+------------+
                |                         |
            ( node2 )                ( node3 )
            | TVal  |                | ORExp |
            +---+---+                +---+---+
                                         |
                             +-----------+-----------+
                             |                       |
                         ( node4 )               ( node5 )
                         |  FVal |               |  TVal |
                         +---+---+               +---+---+

2つ以上のオペランドがある場合、ツリーノードに追加のリンクを追加することにより、処理を同様に実行できます。

ダンプファイルの各式について、コンマで区切られているものには別々の木があり、作成後に移動できます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top