Разбор кода и построение синтаксических деревьев с PLY. Основы

Что такое PLY?

PLY — это аббревиатура из первых букв выражения: Python Lex-Yacc.
Фактически, это порт утилит lex и yacc на python в красивой обертке.
Работать с ply очень просто и порог входа для начала использования практически нулевой.
Написан он на чистом питоне и представляет из себя LALR(1) парсер, но кому это интересно?
Я по натуре практик (как и большинсво из вас) поэтому пошли в бой!

Что будем делать?

На сайте есть пример написания очередного калькулятора, поэтому повторяться не будем. А сделаем что-то навроде парсера очень очень узкого подмножества PHP :)
Наша задача в конце статьи построить синтаксическое дерево для такого примера:

<?php
$val = 5;
$result = substr( "foobar", 2*(7-$val) );
echo "это наш результат: $result";

Пример очень маленький и взят с потолка. Но чтобы построить дерево кода нужно много и походу мы задействуем такой механизм PLY как state.

Lex

Lex — это штука, которая разбивает текст на базовые элементы языка. Ну или группирует текст в базовые элементы. Как-то так.

Что мы здесь видим, кроме бесполезного кода? Видим токены (базовые элементы):
PHP_START — '<?php'
PHP_VAR — '$result'
PHP_EQUAL — '='
PHP_NAME — 'substr'
PHP_OPEN — '('
PHP_STRING — «foobar», 'это наш результат: $result'
PHP_NUM — '2', '7'
PHP_CLOSE — ')'
PHP_ECHO — «echo»
PHP_COLON — ';'
PHP_COMA — ','
PHP_PLUSMINUS — '-'
PHP_DIVMUL — '*'

Для разбора текста на токены в PLY имеется ply.lex. И работает он с регулярными выражениями.
А еще он очень придирчивый к тому что мы пишем в коде. Он требует обязательного присутствия массива с именем tokens.
Для каждого элемента этого массива мы обязаны иметь в коде регулярку или функцию с именем t_ЭЛЕМЕНТ.
Почему он такой придирчивый? Потому что он не работает напрямую во время выполнения программы, а выполняется лишь единожды при первом запуске программы и создает файл lextab.py, в котором описаны таблицы переходов и регулярки. При следующем запуске программы он проверяет наличие этого файла и в случае его присутствия уже не пытается строить таблицы заново, а использует сгенерированные.
Назад к коду.
Если бы синтаксис PHP ограничивался тринадцатью выше перечисленными токенами, то мы бы написали следующее:

# coding=utf8
import ply.lex as lex

# без этой штуки ничего не сынтерпретируется, потому что этот массив шарится между лексером и парсером и кроме того используется внутренне библиотекой
tokens = (
    'PHPSTART', 'PHPVAR', 'PHPEQUAL', 'PHPFUNC',
    'PHPSTRING', 'PHPECHO', 'PHPCOLON', 'PHPCOMA',
    'PHPOPEN', 'PHPCLOSE', 'PHPNUM', 'PLUSMINUS', 'DIVMUL'
)

# определим регулярку для абстрактного идетификатора
ident = r'[a-z]\w*'

# для каждого токена из массива мы должны написать его определение вида t_ИМЯТОКЕНА = регулярка
t_PHPSTART = r'\<\?php'
t_PHPVAR = r'\$'+ident # очень удобно, правда?
t_PHPEQUAL = r'\='
t_PHPFUNC = ident
t_PHPSTRING = r'"(\\.|[^"])*"'
t_PHPECHO = r'echo'
t_PHPCOLON = r';'
t_PHPCOMA = r','
t_PHPOPEN = r'\('
t_PHPCLOSE = r'\)'
t_PHPNUM = r'\d+'
t_PLUSMINUS = r'\+|\-'
t_DIVMUL = r'/|\*'

# здесь мы игнорируем незначащие символы. Нам ведь все равно, написано $var=$value или $var   =  $value
t_ignore = ' \r\n\t\f'

# а здесь мы обрабатываем ошибки. Кстати заметьте формат названия функции
def t_error(t):
    print "Illegal character '%s'" % t.value[0]
    t.lexer.skip(1)

lexer = lex.lex(reflags=re.UNICODE | re.DOTALL)

data = '''
<?php
$result = substr("foobar", "bar");
echo $result;
'''

lexer.input(data)

while True:
    tok = lexer.token() # читаем следующий токен
    if not tok: break      # закончились печеньки
    print tok

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

def t_PHPVAR(t):
    r'\$[a-zA-Z]\w*'
    print 'Урра, мы распарсили переменную ' + t.value # value - это то что нашлось регуляркой
    return t

Кстати вывод примера, что написан выше будет таким:

LexToken(PHPSTART,'<?php',1,1)
LexToken(PHPVAR,'$val',1,7)
LexToken(PHPEQUAL,'=',1,12)
LexToken(PHPNUM,'5',1,14)
LexToken(PHPCOLON,';',1,15)
LexToken(PHPVAR,'$result',1,17)
LexToken(PHPEQUAL,'=',1,25)
LexToken(PHPFUNC,'substr',1,27)
LexToken(PHPOPEN,'(',1,33)
LexToken(PHPSTRING,'"foobar"',1,35)
LexToken(PHPCOMA,',',1,43)
LexToken(PHPNUM,'2',1,45)
LexToken(DIVMUL,'*',1,46)
LexToken(PHPOPEN,'(',1,47)
LexToken(PHPNUM,'7',1,48)
LexToken(PLUSMINUS,'-',1,49)
LexToken(PHPVAR,'$val',1,50)
LexToken(PHPCLOSE,')',1,54)
LexToken(PHPCLOSE,')',1,56)
LexToken(PHPCOLON,';',1,57)
LexToken(PHPFUNC,'echo',1,59)
LexToken(PHPSTRING,'"\xd1\x8d\xd1\x82\xd0\xbe \xd0\xbd\xd0\xb0\xd1\x88 \xd1\x80\xd0\xb5\xd0\xb7\xd1\x83\xd0\xbb\xd1\x8c\xd1\x82\xd0\xb0\xd1\x82: $result"',1,64)
LexToken(PHPCOLON,';',1,107)

Числа в конце — это номер строки и номер символа. Как видите, номер строки не изменяется. Его нужно менять самим. Как? При проходе токена с переходом на новую строку. Для этого уберем символ новой строки из игнорируемых токенов и добавим новую функцию t_newline:

t_ignore = ' \r\t\f'

def t_newline(t):
    r'\n+'
    t.lexer.lineno += len(t.value)

Вот теперь у нас все работает:

LexToken(PHPSTART,'<?php',2,1)
LexToken(PHPVAR,'$val',3,7)
LexToken(PHPEQUAL,'=',3,12)
LexToken(PHPNUM,'5',3,14)
LexToken(PHPCOLON,';',3,15)
LexToken(PHPVAR,'$result',4,17)
LexToken(PHPEQUAL,'=',4,25)
LexToken(PHPFUNC,'substr',4,27)
LexToken(PHPOPEN,'(',4,33)
LexToken(PHPSTRING,'"foobar"',4,35)
LexToken(PHPCOMA,',',4,43)
LexToken(PHPNUM,'2',4,45)
LexToken(DIVMUL,'*',4,46)
LexToken(PHPOPEN,'(',4,47)
LexToken(PHPNUM,'7',4,48)
LexToken(PLUSMINUS,'-',4,49)
LexToken(PHPVAR,'$val',4,50)
LexToken(PHPCLOSE,')',4,54)
LexToken(PHPCLOSE,')',4,56)
LexToken(PHPCOLON,';',4,57)
LexToken(PHPFUNC,'echo',5,59)
LexToken(PHPSTRING,'"\xd1\x8d\xd1\x82\xd0\xbe \xd0\xbd\xd0\xb0\xd1\x88 \xd1\x80\xd0\xb5\xd0\xb7\xd1\x83\xd0\xbb\xd1\x8c\xd1\x82\xd0\xb0\xd1\x82: $result"',5,64)
LexToken(PHPCOLON,';',5,107)

Работает, но не полностью. Наша строка «это наш результат: $result» возвращается лексером как есть. А как парсить её будем? Создавать отдельный лексер? Неа. В PLY (да и в сишном lex) есть поддержка такой штуки как state. State — это переключалка на другой тип токенов. Вот это мы и будем использовать.

State

Итак, для того чтобы создать новый state нам нужно его предварительно объявить:

states = (
   ('string','exclusive'),
)

'string' — это название нового состояния, а exclusive — это тип. Вообще, может быть два типа состояний: exclusive и inclusive. Exclusive — общих токенов не видно (общие, это те которые мы писали до этого, они по умолчанию находятся в состоянии INITIAL). Inclusive — видны общие токены и в текущем состоянии мы просто добавляем к ним дополнительные.
В случае нашей строки нам не нужны другие токены, так как внутри у нас там все по другому. Впрочем парочку мы позаимствуем. Нам нужен токен PHPVAR, потому что переменная у нас выглядит одинаково и снаружи и внутри строки, и нужен будет еще один токен, который вы увидите походу ниже.
Чтобы сделать токен общим мы должны присвоить ему префикс ANY_, ну а чтобы сделать токен видимым только для какого-то определенного состояния — <состояние>_. Ниже приведены измененные токены.

# для каждого токена из массива мы должны написать его определение вида t_ИМЯТОКЕНА = регулярка
t_PHPSTART = r'\<\?php'
t_ANY_PHPVAR = r'\$'+ident # очень удобно, правда?
t_PHPEQUAL = r'\='
t_PHPFUNC = ident
t_PHPECHO = r'echo'
t_PHPCOLON = r';'
t_PHPCOMA = r','
t_PHPOPEN = r'\('
t_PHPCLOSE = r'\)'
t_PHPNUM = r'\d+'
t_PLUSMINUS = r'\+|\-'
t_DIVMUL = r'/|\*'

# изменили токен PHPSTRING и сделали из него функцию, добавили его во все состояния
def t_ANY_PHPSTRING(t): # нужен в обоих состояниях, потому что двойные кавычки матчатся и там и там.
    r'"'
    if t.lexer.current_state() == 'string':
        t.lexer.begin('INITIAL') # переходим в начальное состояние
    else:
        t.lexer.begin('string') # парсим строку
    return t

t_string_STR = r'(\\.|[^$"])+' # парсим пока не дойдем до переменной или до кавычки, попутно игнорируем экранки

# говорим что ничего не будем игнорировать
t_string_ignore = '' # это кстати обязательная переменная, без неё нельзя создать новый state

# ну и куда же мы без обработки ошибок
def t_string_error(t):
    print "Illegal character '%s'" % t.value[0]
    t.lexer.skip(1)

Кстати, заметили это: LexToken(PHPFUNC,'echo',5,59)?
PLY перед построением таблицы сортирует регулярные выражения по возрастанию и в процессе парсинга побеждает длиннейшее. Вот поэтому echo и не парсится как PHPECHO. Как это обойти? Легко. Просто изменим тип возвращаемого токена в функции.
Вот так:

@TOKEN(ident)
def t_PHPFUNC(t):
    if t.value.lower() == 'echo':
        t.type = 'PHPECHO'
    return t

Теперь echo возвращается как нужно. Кстати о декораторе TOKEN: вместо того, чтобы писать регулярку в начале тела функции, можно просто поместить её в переменную и применить к функции как декоратор. Что мы и сделали.

Вот. Теперь вроде все. Да не все.
Неплохо бы игнорировать комментарии.
Что же, добавим еще одну маленькую функцию в лексер:

def t_comment(t):
    r'(/\*(.|\n)*?\*/)|(//.*)'
    pass

Вот теперь переходим к парсеру (parser.py).

Yacc

Yacc — это штука (парсер), в которую мы передаем токены и описываем правила их соединения (грамматику). Походу работы этой программы мы можем создать абстрактное дерево или же сразу выполнять программу (как это сделано в примере с калькулятором на сайте).
В PLY для описания грамматики существует класс ply.yacc.
Описывать граматику в ply очень просто и это доставляет даже некоторое наслаждение. Для описания у нас снова существуют специальные функции p_имяфункции, где в doc-строках мы и описываем эту самую грамматику.
Давайте попробуем написать очень простую грамматику для нашего абстрактного примера с php:

php -> [PHPSTART phpbody]?
phpbody -> [phpline phpcolons]*
phpcolons -> [ PHPCOLON ]+
phpline -> assign | func | [PHPECHO args]
assign -> PHPVAR PHPEQUAL expr
expr -> [fact | expr PLUSMINUS fact]
fact -> [term | fact DIVMUL term]
term -> [arg | PHPOPEN expr PHPCLOSE]
func -> PHPFUNC PHPOPEN args PHPCLOSE
args -> [ expr [PHPCOMA expr]* ]?
arg -> string | phpvar | PHPNUM | func
string -> PHPSTRING str PHPSTRING
str -> [STR | str phpvar]?
phpvar -> PHPVAR

Текста написано уже много, и рассказывать еще можно очень долго. Но для понимания основ ply.yacc достаточно разобрать один пример. А дальше я уже выложу исходник парсера.

Итак, выдранный кусок из парсера:

def p_str(p):
    '''str :
           | STR
           | str phpvar'''
    if len(p) == 1:
        p[0] = Node('str', [''])
    elif len(p) == 2:
        p[0] = Node('str', [p[1]])
    else:
        p[0] = p[1].add_parts([p[2]])

По порядку. Парсинг начинается с первой сверху функции с шаблоном p_<функция>. Т.е. у меня например первой в исходнике стоит p_php, поэтому парсер начнет работу именно с неё (сверху вниз). Парсер работает с правилами в doc-строках, и после их матчинга возвращает управление в функцию с правилами и при этом передает переменную p. В переменной p хранится результат парсинга. Причем после обработки мы должны засунуть наши результаты в p[0]. Элементы, начиная с p[1], это правая часть наших правил — отматченные токены и правила.

    '''str :
           | STR
           | str phpvar'''

По сути правило выше — это скомбинированное (слитое) правило. '|' как несложно догадаться — это ИЛИ, ну или различные варианты токена.
Между двоеточием и левой/правой частью обязателен пробел. Так любит ply. Если правая часть может быть пустой, то после двоеточия ничего не пишем. Токены должны быть написаны большими буквами, а правила маленькими, без префикса p_. Т.е. в примере выше использовались правила p_str и p_phpvar.

Например, если мы имеем "" (пустую строку), то в p у нас будет только одно значение — p[0], причем оно не определно и мы должны его заполнить.
Если у нас строка «привет $vasya пупкин», то эта функция выполнится три раза. Первый раз для значения STR, и мы вернем это значение обратно в p[0], второй раз для $vasya, и добавим это к предыдущему значению (p[1] будет содержать ноду, которую мы вернули в p[0] на прошлой итерации), а третий раз добавим на выход «пупкин». Наверное я сумбурно описал, но это надо просто потрогать. Открыть среду исполнения и поиграться :)

Кстати, иногда более удобен вариант с разделенными вариантами (тафтология, простите):

def p_str_empty(p):
    '''str :'''
    p[0] = Node('str', [''])


def p_str_raw(p):
    '''str : STR'''
    p[0] = Node('str', [p[1]])

def p_str_var(p):
    '''str : str phpvar'''
    p[0] = p[1].add_parts([p[2]])

Он абсолютно идентичен предыдущему варианту кода. Просто фломастеры другие. Функции имеют разные названия (потому что разделять их надо в питоне), но префиксы идентичные (str), что и заставляет ply группировать их вместе как варианты одного правила.

Для удобства построения дерева я использовал такой простенький и эффективный класс:

class Node:
    def parts_str(self):
        st = []
        for part in self.parts:
            st.append( str( part ) )
        return "\n".join(st)

    def __repr__(self):
        return self.type + ":\n\t" + self.parts_str().replace("\n", "\n\t")

    def add_parts(self, parts):
        self.parts += parts
        return self

    def __init__(self, type, parts):
        self.type = type
        self.parts = parts

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

Заключение

Если есть какие-то замечания или пожелания, с удовольствием допишу/изменю пост.

Код статьи здесь

Ну и если интересно с чего я вдруг про ply решил написать — pyfox. Делаю потихонечьку обработку css на python. Вернее парсер css написан, но вот прогулка по dom еще полностью не реализована (не все псевдоселекторы работают). Сейчас конкретно проблема с nth-child. Не на уровне css а на уровне эффективного матчинга — в dom нету такого свойства как номер среди соседей, а считать предыдущих соседей не хочется. Видимо придется HTMLParser кастомизировать. Может кто решит присоединитсья ко мне? Всех welcome :)