Реализация парсера Python

realizaciya parsera python Текст и язык

Система организована в виде двух модулей, содержащих два класса:

     Сканер производит посимвольный анализ нижнего уровня.

     Парсер содержит в себе сканер и производит грамматический анализ высокого уровня.

Парсер отвечает также за вычисление значения выражения и тестирование системы. В данной версии парсер вычисляет выражение во время его грамматического разбора. Чтобы использовать систему, следует создать парсер, передать ему входную строку и вызвать метод parse. Впоследствии можно снова вызвать parse с новой строкой выражения.

Здесь намеренно произведено разделение труда. Сканер извлекает из строки лексемы, но ему ничего не известно о грамматике. Парсер обрабатывает грамматику, но находится в неведении относительно самой строки. Благодаря такой модульной организации программный код сохраняет относительную простоту. И это еще один пример отношения композиции объектно-ориентированного программирования в действии: парсеры содержат сканеры и делегируют им выполнение некоторых операций.

Модуль в примере 19.13 реализует задачу лексического анализа — обнаружения в выражении базовых лексем путем сканирования строки текста слева направо. Обратите внимание на простоту используемой здесь логики; такой анализ иногда можно выполнить с помощью регулярных выражений (описанных раньше), но, на мой взгляд, шаблон, необходимый для обнаружения и извлечения лексем в этом примере, окажется слишком сложным и хрупким. Если вам так не кажется, попробуйте переписать этот модуль с применением модуля re.

Пример 19.13. PP4E\Lang\Parser\scanner.py

############################################################################ сканнер (лексический анализатор)

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

import string

class SyntaxError(Exception): pass # локальные ошибки

class LexicalError(Exception): pass # бывшие строки

class Scanner

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

############################################################################ контрольный пример парсера

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

подпись: def test(parserclass, msg): print(msg, parserclass)
x = parserclass('4 / 2 + 3') x.parse()
x.parse('3 + 4 / 2') x.parse('(3 + 4) / 2') x.parse('4 / (2 + 3)') x.parse('4.0 / (2 + 3)') x.parse('4 / (2.0 + 3)') x.parse('4.0 / 2 * 3') x.parse('(4.0 / 2) * 3')
x.parse('4.0 / (2 * 3)') x.parse('(((3))) + 1')
y = parserclass() y.parse('set a 4 / 2 + 1') y.parse('a * 3') y.parse('set b 12 / a') y.parse('b')
подпись: # допускаются различные парсеры
# аналог eval('3 + 4 / 2')...
# 3.x: / - истинное деление
# // не поддерживается (пока)



 


z = ParserClass() z.parse(‘set a 99′) z.parse(‘set a a + 1′) z.parse(‘a’)

подпись: # ввод из командной строкиz = ParserClass() z.parse(‘pi’) z.parse(‘2 * pi’) z.parse(‘1.234 + 2.1′)

def interact(ParserClass):
print(ParserClass)

x = ParserClass()

while True:

cmd = input(‘Enter=> ‘) if cmd == ‘stop’: break

x.parse(cmd)

Сопоставьте следующие результаты с вызовами функции print в модуле самотестирования:

C:\\PP4E\Lang\Parser> python parser1.py

parser1 <class ‘__main__.Parser’>

5.0

5.0

3.5

0.8

0.8

0.8

6.0

6.0

0.666666666667

4

9.0

4.0

100

3.14159

6.28318

3.334

Как обычно, парсер можно тестировать также в интерактивной оболочке, чтобы опробовать все его возможности:

C:\\PP4E\Lang\Parser> python

>   >> import parser1

>   >> x = parser1.Parser()

>   >> x.parse(‘1 + 2′)

3

Ошибки перехватываются и описываются достаточно дружественным способом (предполагается, что счет начинается с нуля):

>>> x.parse(‘1 + a’)

‘a’ is undefined at column: 4

=> 1 + a

=> "

>>> x.parse(‘1+a+2’)

‘a’ is undefined at column: 2

=> 1+a+2

=> "

>>> x.parse(‘1 * 2 $’)

Lexical Error at column: 6

=> 1 * 2 $

=> "

>>> x.parse(‘1 * — 1′)

Syntax Error at column: 4

=> 1 * — 1

=> "

>>> x.parse(‘1 * (9′)

Syntax Error at column: 6

=> 1 * (9

=> "

подпись: # в 3.x поведение операции деления изменилось>>> x.parse(‘1 + 2 / 3′)

1.66666666667

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

Syntax Error at column: 7

=> 1 + 2 // 3

=> "

Чрезвычайно большие числа также с успехом обрабатываются парсером, потому что в процессе используются встроенные объекты и операторы Python:

>>> x.parse(‘888888888888888888888888888888888888888888888.9999999’)

8.88888888889e+44

>>> x.parse(‘99999999999999999999999999999999999999999 + 2′)

100000000000000000000000000000000000000001

>>> x.parse(‘999999999999999999999999999999.88888888888 + 1.1′)

1e+30

Кроме того, в модуле testparser реализована также возможность интерактивного вычисления выражений, если вам вздумается использовать парсер как простой калькулятор командной строки (или если вам надоест вводить вызовы методов). Передайте класс Parser, чтобы модуль testparser мог создать собственный экземпляр парсера:

>>> import testparser

>>> testparser.interact(parser1.Parser)

<class ‘parser1.Parser’>

Enter=> 4 * 3 + 5

17

Enter=> 5 + 4 * 3

17

Enter=> (5 + 4) * 3

27

Enter=> set a 99

Enter=> set b 66

Enter=> a + b

165

Enter=> # + 1

Lexical Error at column: 0

=> # + 1

=> "

Enter=> a * b + c

‘c’ is undefined at column: 8

=> a * b + c

=> "

Enter=> a * b * + c

Syntax Error at column: 8 => a * b * + c => "

Enter=> a

99

Enter=> a * a * a

970299

Enter=> stop

>>> 

Урок 3: разделяй и властвуй

Как демонстрирует система синтаксического анализа, модульная конструкция программы почти всегда приносит значительный выигрыш. С помощью средств структурирования программ на языке Python (функций, модулей, классов и так далее) большие задачи могут быть разбиты на маленькие контролируемые части, которые можно создавать и тестировать независимо друг от друга. Например, сканер можно протестировать без парсера, создав его экземпляр с помощью входной строки и вызывая его методы scan или match. Можно даже проверить его в интерактивном режиме, из командной строки Python. Когда используется разделение программ на логические составляющие, становится проще понять их и модифицировать. Представьте себе, как бы выглядел парсер, если бы логика сканера была вложена в него, а не вызывалась.

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

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

Каталог сайтов Всего.ру
Оцените статью
Секреты программирования
Добавить комментарий