Обход дамп-схемы дерева (графа) с помощью C - PullRequest
Новая
       11

Обход дамп-схемы дерева (графа) с помощью C

1 голос
/ 07 сентября 2011

У меня есть Схемоподобное дерево график структура.Я хочу разобрать его, используя C, в какое-нибудь представление в памяти и пройтись по нему.

Есть ли какая-нибудь библиотека или интерфейс синтаксического анализатора для этого?1008 * Я разобрал следующее выражение 

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

в следующее (Это мой дамп дерева, похожий на схему) 

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

К которому я хочу перейти, используя C (я должен датьэто кому-то еще, кто работает только с C).PROG - это этикетка;AndExp, OrExp и т. Д. Являются токенами для &&, ||и т.д ..

Ответы [ 2 ]

1 голос
/ 07 сентября 2011

Похоже, что это форма S-Expression .Возможно Этот анализатор S-Expression можно изменить для ваших нужд.

1 голос
/ 07 сентября 2011

Я думаю, что понял ваше требование, но не совсем уверен.

У вас есть выражения в префиксной нотации, поэтому это в основном загрузка префиксного выражения, которое есть в вашем файле дампа, в двоичном дереве.

Вот псевдокод, описывающий процесс загрузки выражений в дерево. 

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 делает новый узел1

    tok2 = TVal

    tok3 = (OrExp FValTVal)

  • Рекурсивный вызов 2 с TVal возвращает node2 к вызову 1 , который связывает его с левым указателем node1.

  • Рекурсивный вызов 3 с (OrExp FValTVal) из вызова 1.

    tok1 = ORExp делает новый узел3

    tok2 = FVal

    tok3 = TVal

  • Рекурсивный вызов 3 с FVal и вызов 4 с TVal соответственно возвращает node4 и node5 со значениями операндов, которые связаны слева и справа ссылки узла 3 из звонка 3.

Больше не нужно рассматривать подвыражение, рекурсия возвращается к исходной точке. У вас есть корень дерева. 

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

Если имеется более двух операндов, обработку можно выполнить аналогичным образом, добавив дополнительные ссылки на узлы дерева.

Для каждого выражения в вашем файле дампа, которые разделены запятыми, будут иметь отдельные деревья, которые после создания могут быть пройдены.

...