1

スキームのようなツリーグラフ構造を持っています。Cを使用してそれを解析してメモリ内の表現にし、その上を歩きたい。

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

編集：

次の式を解析しました

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

以下に（これは私のスキームのようなツリーダンプです）

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

これをCを使用してトラバースしたい（Cでのみ動作する他の誰かにそれを渡さなければならない）。PROGはラベルです。AndExp、OrExpなどは&&、||のトークンです。など..

4

2 に答える 2

1

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

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

これは、式をツリーにロードするプロセスを記述した擬似コードです。

tree_node make_tree（文字列ダンプ）
{{
  tok1 = get_tok（ダンプ）;
  tok2 = get_tok（ダンプ）;
  tok3 = get_tok（ダンプ）;

  if（tok1 ==オペランド）
  {{
    node = make_new_node_with（tok1）;
    リターンノード;
  }

  node = make_new_node_with（tok1）;
  node-> left = make_tree（tok2）;
  node-> right = make_tree（tok3）;
  リターンノード;
}

  • 再帰呼び出し1(AndExp TVal(OrExp FValTVal))

    tok1=AndExp 新しいノード1を作成します

    tok2 =TVal

    tok3 =(OrExp FValTVal)

  • 再帰呼び出し2TValは、 node2を呼び出し1に返します。呼び出し1は、node1の左側のポインターにリンクします。

  • from呼び出し1を使用した再帰呼び出し3 。(OrExp FValTVal)

    tok1=ORExp新しいノードを作成します3

    tok2 =FVal

    tok3 =TVal

  • withとcall4withの再帰呼び出しは、それぞれオペランド値を持つnode4とnode5を返します。これらは、呼び出し3からのnode3の左右のリンクにリンクされています。FValTVal

考慮すべき部分式はもうありません。再帰は開始点に戻ります。あなたは木の根を持っています。

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

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

カンマで区切られたダンプファイル内の式ごとに、作成後にトラバースできる個別のツリーがあります。

于 2011-09-07T16:26:31.833 に答える
1

これはS-Expressionの一形態のようです。おそらく、このS-Expressionパーサーは必要に応じて変更できます。

于 2011-09-07T16:39:32.637 に答える