Что такое 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 # 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 = ' \r\t\f' 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 + ":\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 Он одновременно и хранит все нужное, и структурирует вывод, что чень удобно при отладке.
# 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 + ":\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 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 🙂
ссылка на оригинал статьи http://habrahabr.ru/post/191252/
Добавить комментарий