Что такое 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 = ' rntf'
# а здесь мы обрабатываем ошибки. Кстати заметьте формат названия функции
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,'"xd1x8dxd1x82xd0xbe xd0xbdxd0xb0xd1x88 xd1x80xd0xb5xd0xb7xd1x83xd0xbbxd1x8cxd1x82xd0xb0xd1x82: $result"',1,64)
LexToken(PHPCOLON,';',1,107)
Числа в конце — это номер строки и номер символа. Как видите, номер строки не изменяется. Его нужно менять самим. Как? При проходе токена с переходом на новую строку. Для этого уберем символ новой строки из игнорируемых токенов и добавим новую функцию t_newline:
t_ignore = ' rtf'
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,'"xd1x8dxd1x82xd0xbe xd0xbdxd0xb0xd1x88 xd1x80xd0xb5xd0xb7xd1x83xd0xbbxd1x8cxd1x82xd0xb0xd1x82: $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
# coding=utf8
import ply.lex as lex
from ply.lex import TOKEN
import re
states = (
('string','exclusive'),
)
# без этой штуки ничего не съинтерпретируется, потому что этот массив шарится между лексером и парсером и кроме того используется внутренне библиотекой
tokens = (
'PHPSTART', 'PHPVAR', 'PHPEQUAL', 'PHPFUNC',
'PHPSTRING', 'PHPECHO', 'PHPCOLON', 'PHPCOMA',
'PHPOPEN', 'PHPCLOSE', 'PHPNUM', 'PLUSMINUS', 'DIVMUL',
'STR'
)
# определим регулярку для абстрактного идетификатора
ident = r'[a-z]w*'
# для каждого токена из массива мы должны написать его определение вида t_ИМЯТОКЕНА = регулярка
t_PHPSTART = r'<?php'
t_ANY_PHPVAR = r'$'+ident # очень удобно, правда?
t_PHPEQUAL = r'='
t_PHPCOLON = r';'
t_PHPCOMA = r','
t_PHPOPEN = r'('
t_PHPCLOSE = r')'
t_PHPNUM = r'd+'
t_PLUSMINUS = r'+|-'
t_DIVMUL = r'/|*'
@TOKEN(ident)
def t_PHPFUNC(t):
if t.value.lower() == 'echo':
t.type = 'PHPECHO'
return t
# игнорируем комментарии
def t_comment(t):
r'(/*(.|n)*?*/)|(//.*)'
pass
# изменили токен 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)
# здесь мы игнорируем незначащие символы. Нам ведь все равно, написано $var=$value или $var = $value
t_ignore = ' rtf'
def t_newline(t):
r'n+'
t.lexer.lineno += len(t.value)
# а здесь мы обрабатываем ошибки. Кстати заметьте формат названия функции
def t_error(t):
print "Illegal character '%s'" % t.value[0]
t.lexer.skip(1)
lexer = lex.lex(reflags=re.UNICODE | re.DOTALL | re.IGNORECASE)
if __name__=="__main__":
data = '''
<?php
$val = 5;
$result = substr( "foobar", 2*(7-$val) );
echo "это наш результат: $result";
'''
lexer.input(data)
while True:
tok = lexer.token() # читаем следующий токен
if not tok: break # закончились печеньки
print tok
Вот теперь переходим к парсеру (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 + ":nt" + self.parts_str().replace("n", "nt")
def add_parts(self, parts):
self.parts += parts
return self
def __init__(self, type, parts):
self.type = type
self.parts = parts
Он одновременно и хранит все нужное, и структурирует вывод, что чень удобно при отладке.
# coding=utf8
from lexer import tokens
import ply.yacc as yacc
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 + ":nt" + self.parts_str().replace("n", "nt")
def add_parts(self, parts):
self.parts += parts
return self
def __init__(self, type, parts):
self.type = type
self.parts = parts
def p_php(p):
'''php :
| PHPSTART phpbody'''
if len(p) == 1:
p[0] = None
else:
p[0] = p[2]
def p_phpbody(p):
'''phpbody :
| phpbody phpline phpcolons'''
if len(p) > 1:
if p[1] is None:
p[1] = Node('body', [])
p[0] = p[1].add_parts([p[2]])
else:
p[0] = Node('body', [])
def p_phpcolons(p):
'''phpcolons : PHPCOLON
| phpcolons PHPCOLON'''
def p_phpline(p):
'''phpline : assign
| func
| PHPECHO args'''
if len(p) == 2:
p[0] = p[1]
else:
p[0] = Node('echo', [p[2]])
def p_assign(p):
'''assign : PHPVAR PHPEQUAL expr'''
p[0] = Node('assign', [p[1], p[3]])
def p_expr(p):
'''expr : fact
| expr PLUSMINUS fact'''
if len(p) == 2:
p[0] = p[1]
else:
p[0] = Node(p[2], [p[1], p[3]])
def p_fact(p):
'''fact : term
| fact DIVMUL term'''
if len(p) == 2:
p[0] = p[1]
else:
p[0] = Node(p[2], [p[1], p[3]])
def p_term(p):
'''term : arg
| PHPOPEN expr PHPCLOSE'''
if len(p) == 2:
p[0] = p[1]
else:
p[0] = p[2]
def p_func(p):
'''func : PHPFUNC PHPOPEN args PHPCLOSE'''
p[0] = Node('func', [p[1], p[3]])
def p_args(p):
'''args :
| expr
| args PHPCOMA expr'''
if len(p) == 1:
p[0] = Node('args', [])
elif len(p) == 2:
p[0] = Node('args', [p[1]])
else:
p[0] = p[1].add_parts([p[3]])
def p_arg(p):
'''arg : string
| phpvar
| PHPNUM
| func'''
p[0] = Node('arg', [p[1]])
def p_phpvar(p):
'''phpvar : PHPVAR'''
p[0] = Node('var', [p[1]])
def p_string(p):
'''string : PHPSTRING str PHPSTRING'''
p[0] = p[2]
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]])
def p_error(p):
print 'Unexpected token:', p
parser = yacc.yacc()
def build_tree(code):
return parser.parse(code)
# coding=utf8
from parser import build_tree
data = '''
<?php
$val = 5;
$result = substr( "foobar", 2*(7-$val) ); /* comment */
echo "это наш результат: ", $result;
'''
result = build_tree(data)
print result
line: assign: $val arg: 5 assign: $result arg: func: substr args: arg: str: foobar *: arg: 2 -: arg: 7 arg: var: $val echo: args: arg: str: это наш результат: arg: var: $result
Заключение
Если есть какие-то замечания или пожелания, с удовольствием допишу/изменю пост.
Ну и если интересно с чего я вдруг про ply решил написать — pyfox. Делаю потихонечьку обработку css на python. Вернее парсер css написан, но вот прогулка по dom еще полностью не реализована (не все псевдоселекторы работают). Сейчас конкретно проблема с nth-child. Не на уровне css а на уровне эффективного матчинга — в dom нету такого свойства как номер среди соседей, а считать предыдущих соседей не хочется. Видимо придется HTMLParser кастомизировать. Может кто решит присоединитсья ко мне? Всех welcome :)
Автор: xytop
