категории | RSS
  

Ecли в Baшeм пpилoжeнии вдpyг пoнaдoбитcя cкaнep и пapcep (к пpимepy, Bы пишитe интepпpeтaтop кaкoгo тo выcoкoypoвнeвoгo языкa, или вooбщe, цeлый кoмпилятopsmile ), тo пepвoe, чтo пpийдeт Baм в гoлoвy пocлe изyчeния cyти вoпpoca - мeтoд peкypcивнoгo cпycкa. Этoт мeтoд, дeйcтвитeльнo, oтнocитeльнo лeгкий к peaлизaции, и мы бы имeннo им и вocпoльзoвaлиcь, ecли бы пиcaли нa кaкoм нибyдь Пacкaлe. Ho, тaк кaк мы пoльзyeмcя Питoнoм, ecть бoлee пpocтoй cпocoб - мoдyль spark.

Moдyль пpeдcтaвляeт в нaшe pacпopяжeниe нecкoлькo клaccoв - для лeкcичecкoгo и cинтaкcичecкoгo aнaлизa (GenericScanner, GenericParser), для построения дерева синтаксического разбора (GenericASTBuilder), для обхода этого дерева (GenericASTTraversal), и для поиска узлов в синтаксическом дереве (GenericASTMatcher).
Автор модуля (John Aycock) предлагает для обработки данных использовать четыре прохода - лексический анализ, синтаксический анализ, семантический анализ и генерация кода. Но, по моему мнению, это излишне. Притом что модуль этот оперативу жрет безбожно, так и еще четыре прохода на наших смартах - смерти подобно. Поэтому мы изберем другой подход - на первом проходе лексический анализ с помощью GenericScanner, на втором - все остальное на основе GenericParser.
В данной статье мы будем разрабатывать интерпретатор целочисленных математических выражений. Конечно, это не очень впечатляюще, но достаточно просто в реализации, и поможет понять основные принципы работы с модулем.
И так, поехали! Что у нас там по списку - лексический анализ? Ну тогда начнем с него.
Суть лексического анализа в разборе входящего текста на последовательность элементарных составляющих - токенов. Это может быть оператор (к примеру + или -), идентификатор (имя переменной, метода, класса и т.д.) разделитель (запятая, двуеточие...) и прочие.
В этом деле нам поможет класс GenericScanner. Для начала нужно наследовать наш сканер от этого класса:


from spark import GenericScanner

class Scanner(GenericScanner):

def __init__(self):
# Инициализировать нужно обязательно!
GenericScanner.__init__(self)
# Создаем список, в котором будут сохранятся токены
self.tokens = []

Да, чуть не забыл - токены будут сохранятся в виде простого класса-контейнера. Вот его код:


class Token:

def __init__(self, type, value):
""" type - тип токена (оператор, идентификатор и т.д.)
value - его значение
"""
self.type = type
self.value = value

""" Нужно реализовать еще пару методов для сравнения токенов и для строкового представления
"""

def __eq__(self, other):
return self.type == other

def __ne__(self, other):
return not self == other

def __repr__(self):
return '%s(%r)' %(self.type, self.value)


Возвращаемся к нашему сканеру. Далее нужно создавать методы, в которых будут обрабатываться токены. Эти методы должны удовлетворять некоторым условиям - во первых, имя метода должно начинаться с "t_", во вторых, метод должен принимать один аргумент - собственно, токен. И в третьих - первая строка метода должна быть строкой документации, которая содержит в себе регулярное выражение с описанием данного токена. Напишем метод для распознавания целых чисел:

def t_integer(self, token):
r'\d+' # Только целые десятичные числа
# Добавляем токен в список
self.tokens.append(Token('INTEGER', int(token)

Вот и все! Просто, не так ли?smile
Далее методы для распознавания операторов:

def t_operator(self, token):
r'[\+\-\*\/]' # только плюс, минус, умножение и деление
self.tokens.append(Token('OPERATOR', token))

Теперь нужен метод для обработки пробелов:

def t_space(self, token):
r'\s+' # Для любых символов пропуска
# Пропускаем ихsmile
pass

И, наконец, желательно перегрузить метод t_default - он вызывается в случае, если встреченный символ не описывается никаким предыдущим методом:

def t_default(self, token):
r'[\s\S]+' # Для любых символов
# Синтаксическая ошибка!
raise SyntaxError, str(token)

Наш простой сканер готов. И не так много усилий мы затратили на его создание. Пользоваться им можно следующим образом:

scanner = Scanner()
scanner.tokenize(data)
tokens = scanner.tokens

Где data - сканируемый текст.

Итак, мы имеем сканнер, который обрабатывает текст, и на выходе выдает поток токенов (или ошибку в случае встречи незнакомого символа)
На этом данная статья заканчивается, а в следующей я напишу как пользоваться классом GenericParser для создание парсеров, и мы допишем свой интерпретатор.
До скорой встречи!


Pythoner
2011-01-11T15:54:01Z
Здесь находятся
всего 0. За сутки здесь было 0 человек

Комментарии 13

#13   Virtuos86    

Как-то мимо меня проскользнуло несколько зачётных статей, в том числе и эта.
Кстати, кажется обещанное продолжение так и не появилось fellow?


0 ответить

#13   Pythoner    

Полный не обещаю, но есть модули, портированые под компьютерный Python + wxPython. e32, appuifw, keypress, key_codes - необходимый минимум, но что там под виндой слегка тупит, лень было разбираться. Или качать SDK (посмотри здесь) и запускать скрипты из под него. Это я не пробовал - пишу по старинке, на смарте.


0 ответить

#13   Canth    

Хм, отличная штука надо поюзать. А вот то что оперативу хавает очень плохо на моем 7610 это ж на вес золота. питонер к тебе вопрос, есть ли что то чтобы писать проги на смарт на питоне на компе? чтоб там и appuifw был короче полный набор.


0 ответить

#13   Pythoner    

Будет. Если честно, мне просто лень ее дописыватьsmile но как то соберусь с духом, и все таки закончуsmile))


0 ответить

#13   ffffh    

Отличная статья!!! Я бы, на твоём месте, добавил бы еще сюда такую инфу, как эта же статья, но без использования модуля spark. Хотя это ИМХО, но всё же было бы весьма познавательно! С нетерпением жду следующей статьи!


0 ответить

#13   dj-avtosh    

Рекурсия сама по себе не есть легко.


0 ответить

#13   Pythoner    

Не понял вопроса. Весь код в статье дан с помощью тега code.


0 ответить

#13   Besplotnyi    

Pythoner, разве в статьях нет тега [code] ? Все же нагляднее было бы.


0 ответить

#13   akaSMIT    

отлично))


0 ответить

#13   Angel-iz-Ada    

Цитата: Pythoner
В свое время мне пришлось много литературы полистать

я вижу feel


0 ответить

Напомнить пароль