Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

Anna | 16.06.2014 | нет комментариев

Что такое 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'

# а тут мы обрабатываем ошибки. Кстати подметьте формат нmark!    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 :)

Источник: programmingmaster.ru
Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB