Лeкcичecкий и cинтaкcичecкий aнaлизaтop нa Питoнe

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мпилятop ), т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)

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

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

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

    def t_space(self, token):
        r'\s+' # Для любых символов пропуска
        # Пропускаем их
        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 для создание парсеров, и мы допишем свой интерпретатор.
До скорой встречи!