Отладка абстрактного синтаксического дерева (AST)

Sep 16, 2007 · Comments
Win32.Utf8

Во время работы над парсером постоянно возникала необходимость посмотреть как выглядит тот или иной кусок дерева или все дерево целиком. Недолго думая, я попробовал выводить его в виде XML, - получилось довольно неплохо.

Исходный код на C:

typedef void *LPVOID;

Дерево, полученное после синтаксического разбора:

<translation_unit>
 <external_declaration>
  <declaration>
   <init_list_declaration>
    <declaration_specifiers>
     <declaration_specifier>
      <storage_class_specifier>
       typedef
      </storage_class_specifier>
     </declaration_specifier>
     <declaration_specifier>
      <type_specifier>
       <builtin_type>
        void
       </builtin_type>
      </type_specifier>
     </declaration_specifier>
    </declaration_specifiers>
    <init_declarator>
     <declarator>
      <pointer>
       *
      </pointer>
      <direct_declarator>
       LPVOID
      </direct_declarator>
     </declarator>
    </init_declarator>
   </init_list_declaration>
   ;
  </declaration>
 </external_declaration>
</translation_unit>

Что особенно приятно, так это то, что на Python такие вещи делаются одной левой. Исходный класс Node, представляющий узел дерева, дополняется методом “str”:

exclude_attrs = set(['type', 'children'])

class Node:
    def __init__(self, type, children):
        self.type = type
        self.children = children

    def __str__(self):
        s = '<%s' % self.type

        # Представляем переменные объекта как XML аттрибуты
        for attr in self.__dict__:
            if not attr in exclude_attrs:
                s += ' %s="%s"' % (attr, self.__dict__[attr])

        # Рекурсивно генерируем все подузлы, не забывая про отступы
        if len(self.children):
            s += '>\n'
            for i in self.children:
                s += ' %s\n' % str(i).replace('\n', '\n ')
            s += '</%s>' % self.type
        else:
            s += '/>'

        return s

# Получаем AST
node = parse_source()

# Выводим его в stdout
print node

Небольшого пояснения требует комментарий про то, что переменные объекта выводятся в виде XML атрибутов, поскольку в примере выше никаких атрибутов нет. Каждый из узлов дерева, использованного в примере, содержит только две переменные: “type” – тип узла и “children” – список всех детей. Поскольку и то и другое включаются в XML “естественным” путем, то и показывать их как атрибуты не следует. Для их исключения используется список “exclude_attrs”. А вот, например, такой объект будет показан по-другому:

node = Node(“test”, [])
node.value = “FooBar”
print node

<test value="FooBar"/>

Эта возможность будет очень полезна позднее, когда в AST будут включаться не только экземпляры класса Node, но и более сложные классы.

Алексей Пахунов

Отладка абстрактного синтаксического дерева (AST)