Построение абстрактного синтаксического дерева

Алгоритм работы Win32.Utf8 состоит из трех основных шагов:

1. Исходные заголовки пропускаются через стандартный препроцессор;

2. Полученный код парсится и трансформируется в дерево объектов, описывающее функции, типы и связи между ними;

3. Полученное дерево используется для генерации кода по заданным шаблонам.

На данный момент я работаю над вторым этапом. Цель – построенное дерево должно быть компактным, его структура должна облегчать последующий анализ во время генерации кода. В тоже время дерево должно включать всю информацию необходимую для генерации корректного кода.

DParser позволяет задавать правила следующим образом:

def d_rule(t):
    ''' production : foo '+' bar '''
    return t[0] + t[2]

def d_terminals(t):
    '''
        foo : 'foo' ;
        bar : 'bar'
    '''
    pass

Правило “d_rule” будет вызвано каждый раз , когда парсер обнаружит в анализируемом тексте последовательность “foo + bar”. В качестве параметр правила “t” будет передан список значений, соответствующих обнаруженным символам. Поскольку правило для “foo” и “bar” не выполняет никаких действий, то в “d_rule” всегда будет передаваться список из трех строк: [ ‘foo’, ‘+’, ‘bar’ ]. Значение, возвращаемое из “d_rule”, будет присвоено нетерминалу “production” и будет передано в любое правило, включающее этот символ.

Как видно из примера выше, один и тот же обработчик может вызываться для нескольких (или всех) правил. Используя эту возможность можно полное генерировать дерево разбора с помощью всего нескольких строк кода.

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

def create_node(type, children):
    return Node(type, children)

def d_grammar(t, this):
    '''
        production : foo '+' bar ;
        foo : 'foo' ;
        bar : 'bar'
    '''
    return create_node(this.symbol, t)

Дополнительный параметр “this” позволяет получить доступ к имени нетерминала, т.е. имени слева от “:” - “this.symbol”.

Это работает доя простых грамматик, однако грамматика C к таковым не относится. Немного уменьшить глубину дерева можно если отказаться от создания узлов дерева с единственным ребенком:

def create_node(type, children):
        if len(children) > 1:
            return Node(type, children)
        else:
            return children[0]

Некоторые узлы, возможно, будут важны при последующем анализе дерева. Для них можно завести список исключений:

key_nodes = set([ 'foo' ])

def create_node(type, children):
    if len(children) > 1 or type in key_nodes:
        return Node(type, children)
    else:
        return children[0]

DParser позволяет использовать в правилах операторы повторения ‘*’, ‘+’ и ‘?’, а также группировать символы, заключая их в скобки:

def d_grammar(t, this):
    '''
        start : production+ ;
        production : foo* ( '+' bar )+ ;
        foo : 'foo' ;
        bar : 'bar'
    '''
    pass

В этом случае в соответствующей позиции списка “t” вместо единичного значения, будет передан список значений. Например в случае правила “start : production+ ” “t” будет состоять из одного элемента, однако значен7ие этого элемента будет списком значений для символа “production”. Функция создания узла дерева должна это учитывать, разворачивая вложенные списки на лету:

key_nodes = set([ 'foo' ])

def unwrap(children):
    nodes = []

    for c in children:
        if isinstance(c, list):
            nodes.extend(unwrap(c))
        else:
            nodes.append(c)

    return nodes

def create_node(type, children):
    nodes = unwrap(children)

    if len(nodes) > 1 or type in key_nodes:
        return Node(type, nodes)
    else:
        return nodes[0]

Стоит также учесть, что грамматика может использовать правую/левую рекурсию, вместо операторов повторения:

def d_grammar(t, this):
    '''
        production_list 
            : production
            | production_list production
    '''
    pass

Об этом также стоит позаботиться:

def create_node(type, children):
    nodes = unwrap(children)

    left = nodes[0]
    if isinstance(left, Node) and type == left.type:
        left.children.extend(nodes[1:])
        return left

    right = nodes[-1]
    if isinstance(right, Node) and type == right.type:
        nodes.pop(-1)
        nodes.extend(right.children)
        right.children = nodes
        return right

    if len(nodes) > 1 or type in key_nodes:
        return Node(type, nodes)
    else:
        return nodes[0]

В результате получаем дерево почти пригодное для анализа. Я говорю “почти”, потому как его можно упростить еще больше. Об этом - в следующем посте.

Примечание: код набирался прямо в браузере и приведён только в качестве иллюстрации. Он даже может не компилироваться, не говоря уже о том, чтобы работать.