Добавление интерпретатора дерева синтаксического анализа Python

dobavlenie interpretatora dereva sintaksicheskogo analiza python

Текст и язык

Одна из слабостей программы parser1 состоит в том, что она встраивает логику вычисления выражений в логику синтаксического анализа: результат вычисляется во время грамматического разбора строки. Это ускоряет вычисление, но может затруднить модификацию программного кода, особенно при росте системы. Проще говоря, можно изменить организацию программы с тем, чтобы отделить синтаксический анализ от вычисления. Вместо вычисления строки парсер может построить промежуточное представление, которое будет вычислено позднее. Дополнительным стимулом к созданию такого отдельного представления является возможность подвергнуть его анализу другими средствами (например, оптимизаторами, инструментами просмотра и так далее) — они могут запускаться в отдельных проходах по дереву.

В примере 19.16 показана версия parser1, реализующая эту идею. Парсер анализирует строку и строит дере во син так си че ско го ана ли за, то есть дерево экземпляров классов, которое представляет выражение и может быть вычислено на отдельной стадии. Дерево синтаксического анализа строится из классов, которые «умеют» вычислять себя: чтобы вычислить выражение, мы просто предложим дереву вычислить себя. Корневые узлы дерева просят своих потомков вычислить себя, а затем объединяют результаты, применяя единственный оператор. Фактически вычисление в этой версии является рекурсивным обходом дерева вложенных экземпляров классов, построенного парсером.

Пример 19.16. PP4E\Lang\Parser\parser2.py

Синтаксический анализ, выполняемый отдельно от вычисления, конструирующий дерево синтаксического анализа

TraceDefault = False

class UndefinedError(Exception): pass

if __name__ == ‘__main__’:

from scanner import Scanner, SyntaxError, LexicalError # запускается здесь else:

from .scanner import Scanner, SyntaxError, LexicalError # из PyTree

############################################################################ # интерпретатор (дерево умных объектов)

############################################################################

class TreeNode:

def validate(self, dict): # проверка ошибок по умолчанию

pass

def apply(self, dict): # механизм вычисления по умолчанию

pass

def trace(self, level): # механизм анализа дерева по умолчанию

print(‘.’ * level + ‘<empty>’)

# КЛАССЫ КОРНЕВЫХ ОБЪЕКТОВ

class BinaryNode(TreeNode):

def __init__(self, left, right): # наследуемые методы

self.left, self.right = left, right # левая/правая ветви

def validate(self, dict):

self.left.validate(dict) # ветви рекурсивного спуска

self.right.validate(dict)

def trace(self, level):

print(‘.’ * level + ‘[‘ + self.label + ‘]’)

self.left.trace(level+3)

self.right.trace(level+3)

class TimesNode(BinaryNode):

label = ‘*’

def apply(self, dict):

return self.left.apply(dict) * self.right.apply(dict)

class DivideNode(BinaryNode):

label = ‘/’

def apply(self, dict):

return self.left.apply(dict) / self.right.apply(dict)

class PlusNode(BinaryNode):

label = ‘+’

def apply(self, dict):

return self.left.apply(dict) + self.right.apply(dict)

class MinusNode(BinaryNode): label = ‘-‘

def apply(self, dict):

return self.left.apply(dict) — self.right.apply(dict)

# КЛАССЫ ОБЪЕКТОВ-ЛИСТЬЕВ

class NumNode(TreeNode):

def __init__(self, num):

self.num = num # уже число

def apply(self, dict): # проверка по умолчанию

return self.num

def trace(self, level):

print(‘.’ * level + repr(self.num)) # как прогр. код, было ‘self.num’

class VarNode(TreeNode):

def __init__(self, text, start):

self.name = text # имя переменной

self.column = start # номер позиции для ошибок

def validate(self, dict):

if not self.name in dict.keys():

raise UndefinedError(self.name, self.column)

def apply(self, dict):

return dict[self.name] # сначала проверить

def assign(self, value, dict):

dict[self.name] = value # локальное расширение

def trace(self, level):

print(‘.’ * level + self.name)

# КЛАССЫ КОМПОЗИТНЫХ ОБЪЕКТОВ

class AssignNode(TreeNode):

def __init__(self, var, val): self.var, self.val = var, val

def validate(self, dict):

self.val.validate(dict) # не проверять переменные

def apply(self, dict):

self.var.assign( self.val.apply(dict), dict )

def trace(self, level):

print(‘.’ * level + ‘set ‘)

self.var.trace(level + 3)

self.val.trace(level + 3)

############################################################################ # парсер (синтаксический анализатор, построитель дерева)

############################################################################

class Parser:

def __init__(self, text=»):

self.lex = Scanner(text) # создать сканер

self.vars = {‘pi’:3.14159} # добавить константы

self.traceme = TraceDefault

return self.Goal()

except SyntaxError:

print('Syntax Error at column:

self.lex.showerror()

except LexicalError:

print('Lexical Error at column self.lex.showerror()

$подпись: def errorcheck(self, tree): try: tree.validate(self.vars) # проверка ошибок return 'ok' except undefinederror as instance: # args - кортеж varinfo = instance.args print("'%s' is undefined at column: %d" % varinfo) self.lex.start = varinfo[1] self.lex.showerror() # вернет none def interpret(self, tree): result = tree.apply(self.vars) # дерево вычисляет себя само if result != none: # игнорировать результат 'set' print(result) # игнорировать ошибки def goal(self): if self.lex.token in ['num', 'var', '(']: tree = self.expr() self.lex.match('\0') return tree elif self.lex.token == 'set': tree = self.assign() self.lex.match('\0') return tree else:$

raise SyntaxError()

def Assign(self):

self.lex.match(‘set’)

vartree = VarNode(self.lex.value, self.lex.start) self.lex.match(‘var’)

valtree = self.Expr()

return AssignNode(vartree, valtree) # два поддерева

def Expr(self):

left = self.Factor() # левое поддерево

while True:

if self.lex.token in [‘\0’, ‘)’]: return left

elif self.lex.token == ‘+’:

self.lex.scan()

left = PlusNode(left, self.Factor()) # добавить корневой узел elif self.lex.token == ‘-‘:

self.lex.scan()

left = MinusNode(left, self.Factor()) # растет вверх/вправо else:

raise SyntaxError()

def Factor(self):

left = self.Term()

while True:

if self.lex.token in [‘+’, ‘-‘, ‘\0’, ‘)’]: return left

elif self.lex.token == ‘*’:

self.lex.scan()

left = TimesNode(left, self.Term())

elif self.lex.token == ‘/’:

self.lex.scan()

left = DivideNode(left, self.Term())

else:

raise SyntaxError()

def Term(self): if self.lex.token == ‘num’:

leaf = NumNode(self.lex.match(‘num’)) return leaf elif self.lex.token == ‘var’:

leaf = VarNode(self.lex.value, self.lex.start)

self.lex.scan() return leaf

elif self.lex.token == ‘(‘:

self.lex.scan()

tree = self.Expr()

self.lex.match(‘)’) return tree

else:

raise SyntaxError()

############################################################################ # программный код самотестирования: использует свой парсер, тест для parser1 ############################################################################

if __name__ == ‘__main__’: import testparser testparser.test(Parser, ‘parser2’) # выполнить с классом Parser

Обратите внимание на способ обработки исключения обнаружения неопределенного имени в errorCheck. Когда классы исключений наследуют встроенный класс Exception, их экземпляры автоматически возвращают аргументы, переданные в вызов конструктора исключения в виде кортежа в своем атрибуте args, что удобно использовать для форматирования строк.

Отметьте также, что новый парсер повторно использует тот же самый модуль сканера. Чтобы перехватывать ошибки, возбуждаемые сканером, он также импортирует классы, идентифицирующие исключения сканера. И сканер, и парсер могут возбуждать исключения при ошибках (лексические ошибки, синтаксические ошибки и ошибки неопределенных имен). Они перехватываются на верхнем уровне парсера и завершают текущий разбор. При этом нет надобности устанавливать и проверять флаги состояния, чтобы завершить рекурсию. Поскольку математические действия выполняются с использованием целых чисел, чисел с плавающей точкой и операторов Python, обычно не требуется перехватывать ошибки переполнения или потери значимости. Но в данной реализации парсер не обрабатывает такие ошибки, как деление на ноль; они приводят к системному выходу из парсера с выводом содержимого стека Python и сообщения об ошибке. Выяснение причины и исправление этого оставляются в качестве упражнения.

Когда модуль parser2 запускается как программа верхнего уровня, мы получаем тот же результат, что и при запуске модуля parser1. Фактически они совместно используют один и тот же программный код тестирования — оба парсера передают свои объекты классов Parser функции testparser.test. А поскольку классы также являются объектами, мы точно так же можем передать эту версию парсера в интерактивный цикл модуля testparser: testparser.interact(parser2.Parser).

Внешне новый парсер ведет себя точно так же, как и оригинал, поэтому я не буду приводить его вывод здесь (запустите пример у себя, чтобы самим увидеть результаты). Следует, однако, отметить, что этот парсер поддерживает возможность использования его как в виде самостоятельного сценария, так и в виде пакета, доступного для импортирования из других программ, таких как PyTree, которой мы воспользуемся чуть ниже. Однако Python 3.X больше не включает собственный каталог модуля в путь поиска, поэтому в последнем случае мы вынуждены использовать синтаксис импорта по относительному пути в пакете и импортировать из другого каталога при тестировании в интерактивном режиме:

C:\…\PP4E\Lang\Parser> parser2.py

parser2 <class ‘__main__.Parser’>

5.0

…остальная часть вывода такая же, как в parser1…

C:\…PP4E\Lang\Parser> python

>>> import parser2

from .scanner import Scanner, SyntaxError, LexicalError # из PyTree ValueError: Attempted relative import in non-package

(ValueError: Попытка импорта по относительному пути отсутствующего пакета)

C:\…\PP4E\Lang\Parser> cd ..

C:\…\PP4E\Lang> Parser\parser2.py

parser2 <class ‘__main__.Parser’>

5.0

…остальная часть вывода такая же, как в parser1…

C:\…\PP4E\Lang> python

> >> from Parser import parser2

> >> x = parser2.Parser()

> >> x.parse(‘1 + 2 * 3 + 4′)

> >> import Parser.testparser

> >> Parser.testparser.interact(parser2.Parser)

Enter=> 4 * 3 + 5

Enter=> stop

>>>

Использования в parser2 синтаксиса импорта пакета по полному пути вместо импорта по относительному пути или неквалифицированного импорта:

from PP4E.Lang.Parser import scanner

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

Использованная литература:

Марк Лутц — Программирование на Python, 4-е издание, II том, 2011

Каталог сайтов Всего.ру