Система организована в виде двух модулей, содержащих два класса:
• Сканер производит посимвольный анализ нижнего уровня.
• Парсер содержит в себе сканер и производит грамматический анализ высокого уровня.
Парсер отвечает также за вычисление значения выражения и тестирование системы. В данной версии парсер вычисляет выражение во время его грамматического разбора. Чтобы использовать систему, следует создать парсер, передать ему входную строку и вызвать метод parse. Впоследствии можно снова вызвать parse с новой строкой выражения.
Здесь намеренно произведено разделение труда. Сканер извлекает из строки лексемы, но ему ничего не известно о грамматике. Парсер обрабатывает грамматику, но находится в неведении относительно самой строки. Благодаря такой модульной организации программный код сохраняет относительную простоту. И это еще один пример отношения композиции объектно-ориентированного программирования в действии: парсеры содержат сканеры и делегируют им выполнение некоторых операций.
Модуль в примере 19.13 реализует задачу лексического анализа — обнаружения в выражении базовых лексем путем сканирования строки текста слева направо. Обратите внимание на простоту используемой здесь логики; такой анализ иногда можно выполнить с помощью регулярных выражений (описанных раньше), но, на мой взгляд, шаблон, необходимый для обнаружения и извлечения лексем в этом примере, окажется слишком сложным и хрупким. Если вам так не кажется, попробуйте переписать этот модуль с применением модуля re.
Пример 19.13. PP4E\Lang\Parser\scanner.py
############################################################################ сканнер (лексический анализатор)
############################################################################
import string
class SyntaxError(Exception): pass # локальные ошибки
class LexicalError(Exception): pass # бывшие строки
def __init__(self, text): self.next = 0 self.text = text + ‘\0’
def newtext(self, text): Scanner.__init__(self, text)
def showerror(self): print(‘=> ‘, self.text) print(‘=> ‘, (‘ ‘ * self.start) + ‘"’)
def match(self, token): if self.token != token: raise SyntaxError(token) else: value = self.value if self.token != ‘\0’:
self.scan() # очередная лексема/значение
return value # вернуть предыдущее значение
def scan(self): self.value = None ix = self.next while self.text[ix] in string.whitespace: ix += 1 self.start = ix
if self.text[ix] in [‘(‘, ‘)’, ‘-‘, ‘+’, ‘/’, ‘*’, ‘\0’]: self.token = self.text[ix] ix += 1
elif self.text[ix] in string.digits: str = »
while self.text[ix] in string.digits: str += self.text[ix] ix += 1
if self.text[ix] == ‘.’: str += ‘.’ ix += 1
while self.text[ix] in string.digits: str += self.text[ix] ix += 1
self.token = ‘num’ self.value = float(str) else:
self.token = ‘num’
self.value = int(str) # соответствует long() в 3.x
elif self.text[ix] in string.ascii_letters: str = »
while self.text[ix] in (string.digits + string.ascii_letters) str += self.text[ix] ix += 1
if str.lower() == ‘set’: self.token = ‘set’
else:
self.token = ‘var’ self.value = str
else:
raise LexicalError() self.next = ix
Класс модуля парсера создает и встраивает сканер для выполнения задач лексического анализа, занимается интерпретацией грамматических правил и вычислением результата выражения, как показано в примере 19.14.
Пример 19.14. PP4E\Lang\Parser\parser1.py
############################################################################ парсер (синтаксический анализатор, вычисляет выражение в процессе анализа) ############################################################################ class UndefinedError(Exception): pass from scanner import Scanner, LexicalError, SyntaxError
class Parser:
def __init__(self, text=»):
self.lex = Scanner(text) # встроить сканер
self.vars = {‘pi’: 3.14159} # добавить переменную
def parse(self, *text):
if text: # главная точка входа
self.lex.newtext(text[0]) # использовать парсер повторно?
try:
self.lex.scan() # получить первую лексему
self.Goal() # разобрать предложение
except SyntaxError:
print(‘Syntax Error at column:’, self.lex.start)
self.lex.showerror()
except LexicalError:
print(‘Lexical Error at column:’, self.lex.start)
self.lex.showerror()
except UndefinedError as E:
name = E.args[0]
print("’%s’ is undefined at column:" % name, self.lex.start)
self.lex.showerror()
def Goal(self):
if self.lex.token in [‘num’, ‘var’, ‘(‘] val = self.Expr()
self.lex.match(‘\0’) # выражение?
print(val)
elif self.lex.token == ‘set’: # команда set?
self.Assign()
self.lex.match(‘\0’)
else:
raise SyntaxError()
def Assign(self):
self.lex.match(‘set’)
var = self.lex.match(‘var’)
val = self.Expr()
self.vars[var] = val # присвоить имени в словаре
def Expr(self):
left = self.Factor()
while True:
if self.lex.token in [‘\0’, ‘)’]: return left
elif self.lex.token == ‘+’:
self.lex.scan()
left = left + self.Factor()
elif self.lex.token == ‘-‘:
self.lex.scan()
left = 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 = left * self.Term()
elif self.lex.token == ‘/’:
self.lex.scan()
left = left / self.Term()
else:
raise SyntaxError()
def Term(self):
if self.lex.token == ‘num’:
val = self.lex.match(‘num’) # числа
return val
elif self.lex.token == ‘var’:
if self.lex.value in self.vars.keys(): # keys(): EIBTI! val = self.vars[self.lex.value] # найти значение имени self.lex.scan() return val
else:
raise UndefinedError(self.lex.value)
elif self.lex.token == ‘(‘:
self.lex.scan()
val = self.Expr() # подвыражение
self.lex.match(‘)’)
return val
else:
raise SyntaxError()
if __name__ == ‘__main__’:
import testparser # программный код самотестирования
testparser.test(Parser, ‘parser1’) # тест локального объекта Parser
Если внимательно изучить этот пример, можно заметить, что парсер ведет словарь (self.vars) имен переменных: они сохраняются в словаре командой set и выбираются из него при появлении в выражении. Лексемы представляются строками с возможными ассоциированными значениями (числовое значение для чисел и строки для имен переменных). Для обработки правил expr-tail и factor-tail в этом парсере используются итерации (циклы while) вместо рекурсии. За исключением этой оптимизации правила грамматики непосредственно отображаются в методы парсера: лексемы становятся обращениями к сканеру, а ссылки на вложенные правила становятся обращениями к другим методам.
При выполнении файла parser1.py как программы верхнего уровня выполняется его программный код самотестирования, который, в свою очередь, просто выполняет готовый тест, показанный в примере 19.15. Обратите внимание, что строки преобразуются в числа с помощью функции int, это гарантирует поддержку целых чисел неограниченной точности в целочисленных вычислениях, потому что сканер использует целые числа Python, которые всегда обеспечивают дополнительную точность по мере необходимости (отдельный синтаксис long, имевшийся в Python 2.X, использовать более не требуется).
Заметьте также, что смешанные операции над целыми числами и числами с плавающей точкой приводятся к операциям над числами с плавающей точкой, так как для фактических вычислений используются операторы Python. Кроме того, оператор деления / также унаследовал модель истинного деления от Python 3.X, которая сохраняет остаток от деления и возвращает результат с плавающей точкой, независимо от типов операндов. Мы могли бы просто использовать // в логике вычислений, чтобы сохранить прежнее поведение (или включить в грамматику оба оператора, / и //), но здесь мы будем следовать основным тенденциям Python 3.X.
Пример 19.15. PP4E\Lang\Parser\testparser.py
############################################################################ контрольный пример парсера
############################################################################