Статьи

Учебник Pyleri: разбор с легкостью

Добро пожаловать в учебник по Pyleri, он же Python Left-Right Parser , простой инструмент разбора. Чтобы использовать его, когда вам нужно нечто большее, чем регулярное выражение, но меньше, чем полный генератор парсера. В этом уроке мы собираемся показать вам, как использовать инструмент и основы синтаксического анализа.

Зачем учить Пылери?

Мы написали очень популярную серию публикаций о разборе библиотек и инструментов: Java , C # , Python , JavaScript . Мы также написали много любимых руководств по использованию ANTLR . Отличный промышленный инструмент для разбора, который идеально подходит для разбора реальных, сложных языков. Однако мы считаем, что нам не хватало хорошего учебника по простому инструменту синтаксического анализа. Тот, который вы можете использовать, когда вам нужно нечто большее, чем регулярное выражение, но вы не готовы к полному анализатору. Вот где приходит Пайлери.

Мы выбираем Pyleri, потому что это хороший и эффективный инструмент. Это позволяет легко создавать парсеры, а также может быть быстрым способом поддержки таких функций, как автозаполнение. Кроме того, одна и та же грамматика может также генерировать парсеры для нескольких языков: JavaScript, C, Python, Go и Java. Он также хорошо протестирован, учитывая, что он был разработан для использования с SiriDB , надежной и надежной базой данных временных рядов .

Рабочий процесс

Грамматика для Pyleri должна быть определена в выражениях Python. Они должны быть частью класса, производного от Grammar базового класса. Как в следующем примере.

1
2
3
class BookGrammar(Grammar):   
    k_book = Keyword('book')
    r_title = Regex('[a-zA-Z 0-9\']+')

Как только это определено, грамматика может быть экспортирована как файл. Экспортируемый файл определяет грамматику в Python или любом другом поддерживаемом языке. Существует несколько методов, по одному для каждого языка (например, export_java , export_js ).

Например, вы можете определить грамматику в Python, экспортировать ее в JavaScript, а затем использовать JavaScript-версию Pyleri (jsleri) для ее запуска.

1
2
3
4
5
grammarString = BookGrammar().export_js() # now grammarString contains the JS version of BookGrammar
# class BookGrammar extends Grammar {
#   static k_book = Keyword('book');
#   static r_title = Regex('^[a-zA-Z 0-9\']+');
#   etc.

Вы не можете сделать обратное, то есть вы не можете создать грамматику в jsleri и затем экспортировать ее в Python. Это потому, что jsleri или другие * leri не поддерживают эту функцию. Таким образом, Pyleri, несомненно, является основной версией семейства * leri. Поэтому лучше создать грамматику в Python, а затем экспортировать ее на этот язык.

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

Основы формата книги

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

1
2
3
4
5
# Create a Grammar Class to define the format
class BookGrammar(Grammar):   
    k_book = Keyword('book')
    r_title = Regex('[a-zA-Z 0-9\']+')
    START = Sequence(k_book, r_title)

Правило START всегда должно присутствовать. Вам нужно иметь правило с этим именем в вашей грамматике. Таким образом, Pyleri знает правило, с которого он должен начать анализ входных данных.

С практической точки зрения существует два вида правил синтаксического анализа: простой и комбинация других правил. Если у вас есть опыт разбора, вы можете подумать, что простые правила подобны правилам лексера, а сложные правила — правилам синтаксического анализа. Это не совсем так, поскольку между ними нет технических различий.

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

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

Тестирование грамматики

1
2
3
4
5
6
# Compile your grammar by creating an instance of the Grammar Class.
book_grammar = BookGrammar()
 
# Use the compiled grammar to parse 'strings'
print(book_grammar.parse('book The fall of Rome').is_valid) # => True
print(book_grammar.parse('book The Karamazov Brothers').as_str()) # => parsed successfully

Затем мы создаем объект из нашей грамматики и тестируем несколько входных данных. Все отлично работает Объект, возвращаемый методом анализа, имеет тип Result и имеет несколько полезных свойств:

  • is_valid является логическим значением, которое сообщает, является ли is_valid действительным
  • метод as_str() возвращает сообщение о результате анализа
  • поле tree возвращает дерево синтаксического анализа

Давайте попробуем неверный ввод, чтобы лучше увидеть, что as_str() метод as_str() .

1
2
print(book_grammar.parse('story Farewell to Arms').is_valid) # => False
print(book_grammar.parse('story Farewell to Arms').as_str()) # => error at position 0, expecting: book

Как вы можете видеть, когда ввод недопустим, вышеупомянутый метод возвращает сообщение об ошибке, которое объясняет, что пошло не так. Если синтаксический анализ не выполняется, вы также можете посмотреть в поле pos чтобы точно определить, где анализ был остановлен.

Дерево разбора

Наконец мы увидим дерево разбора.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Returns properties of a node object as a dictionary:
def node_props(node, children):
    return {
        'start': node.start,
        'end': node.end,
        'name': node.element.name if hasattr(node.element, 'name') else None,
        'element': node.element.__class__.__name__,
        'string': node.string,
        'children': children}
 
 
# Recursive method to get the children of a node object:
def get_children(children):
    return [node_props(c, get_children(c.children)) for c in children]
 
# View the parse tree:
def view_parse_tree(res):
    start = res.tree.children[0] \
        if res.tree.children else res.tree
    return node_props(start, get_children(start.children))
 
# let's print the parse tree
pp = pprint.PrettyPrinter()
pp.pprint(view_parse_tree(book_grammar.parse('book The Karamazov Brothers')))

Функции для навигации разбора взяты из документации Pyleri.

Это выход из предыдущего ввода разговорника book The Karamazov Brothers .

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
{'children': [{'children': [],
               'element': 'Keyword',
               'end': 4,
               'name': 'k_book',
               'start': 0,
               'string': 'book'},
              {'children': [],
               'element': 'Regex',
               'end': 27,
               'name': 'r_title',
               'start': 5,
               'string': 'The Karamazov Brothers'}],
 'element': 'Sequence',
 'end': 27,
 'name': 'START',
 'start': 0,
 'string': 'book The Karamazov Brothers'}

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

Описание книги

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
class BookGrammar(Grammar):   
    k_book = Keyword('book')
    r_title = Regex('[a-zA-Z 0-9\']+')
    k_author = Keyword('authors')
    r_author = Regex('[a-zA-Z 0-9\']+')
    k_publication = Keyword('publication_date')
    k_pub = Keyword('pub_date')
    k_pub_date = Choice(k_publication, k_pub)
    r_pub_date = Regex('0-9]+')
    k_description = Keyword('description')
    r_description = Regex('"([^"]*)"')
    DESCRIPTION = Sequence(k_description, r_description)
    AUTHORS = Sequence(k_author, List(r_author, delimiter=',', mi=1, ma=None))
    PUB_DATE = Sequence(k_pub_date, r_pub_date)
    TITLE = Sequence(k_book, r_title)       
    START = Sequence(TITLE, Optional(AUTHORS), Optional(PUB_DATE), Optional(DESCRIPTION))

Формат нашей книги показывает лишь некоторые элементы, которые можно использовать для создания правил.

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

Элемент List представляет собой серию, по крайней мере, от mi элементов до ma элементов. В нашем случае мы используем его, чтобы указать, что нам нужен как минимум 1 автор и до бесконечного числа авторов.

Наконец, Optional элемент указывает элемент, который может присутствовать, если он присутствует не всегда. Мы используем его для составления последнего элемента: всегда есть TITLE, но остальные метаданные являются опциональными.

Этот простой пример показывает, как создать грамматику с помощью Pyleri или любого комбинатора синтаксического анализа. Сначала вы разрабатываете отдельные правила, а затем объединяете их вместе, чтобы сформировать правило, которое описывает весь документ. Это довольно легко, когда вы получите мышление.

Это пример ввода, который может проанализировать наша грамматика.

1
2
3
4
book 1984
 authors George Orwell
 pub_date 1949
 description "A dystopian novel by English writer George Orwell published in June 1949, whose themes center on the risks of government overreach, totalitarianism and repressive regimentation of all persons and behaviors within society"

У меня больше одной книги

Эта грамматика прекрасно работает, когда у вас есть только одна книга, но обычно у вас больше; это если вы не очень медленный читатель. Итак, мы должны изменить грамматику, чтобы поддержать коллекцию книг. На самом деле мы хотим также поддерживать несколько коллекций книг, на случай, если мы хотим разделить наши книги на разные группы.

Например, мы хотим поддержать что-то вроде этого ввода.

1
2
3
4
5
6
7
8
collection 1 = [
   // book 1
   // book 2
   collection 2 = [
    // book 3
    // book 4
   ]
]

Поддерживать такую ​​структуру на самом деле довольно просто, нам просто нужно несколько модификаций.

1
2
3
4
5
6
7
8
9
r_name = Regex('[a-zA-Z 0-9]+')
    t_equals = Token('=')
     
    [..]
 
    START = Ref()
    BOOK = Sequence(TITLE, Optional(AUTHORS), Optional(PUB_DATE), Optional(DESCRIPTION))
    ELEM = Choice(BOOK, START)
    START = Sequence(r_name, t_equals, '[', List(ELEM, delimiter=k_end_book), ']')

Первое, что мы делаем, — это создаем пару правил для поддержки именования коллекций. Мы используем новый тип Token правила для анализа знака равенства. Это правило используется для операторов и тому подобного. Существует также версия, которая принимает несколько токенов.

1
Tokens('+ / )')

Вам просто нужно отделить каждого из них пробелом.

Большое изменение, однако, касается правила START . Мы используем специальное правило Ref , чтобы указать прямую ссылку. Вы можете использовать его для создания рекурсивных правил. Сначала вы указываете прямую ссылку с помощью Ref , затем вы определяете реальное правило как нормальное. В нашем примере начальное правило содержит коллекцию элементов с потенциальным именем. В свою очередь, каждый элемент может быть отдельной книгой или начальным элементом. Поскольку начальный элемент представляет собой набор элементов, вы видите, как все это является рекурсивным.

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

Использование грамматики

Теперь, когда у нас есть окончательная версия нашей грамматики, мы можем ее использовать. Проблема в том, что Pyleri не предлагает никаких готовых к использованию методов навигации по дереву разбора, как это делают более сложные инструменты, такие как ANTLR. Это означает, что нет простого способа создать посетителя или слушателя для выполнения какой-либо операции с деревом. К счастью, это не сложно сделать вручную.

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

Мы можем начать с повторного использования функций для навигации по дереву и помещения их в класс с именем VisitTree .

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Returns properties of a node object as a dictionary:
    def node_props(self, node, children):
        self.read_info(node)
        return {
            'start': node.start,
            'end': node.end,
            'name': node.element.name if hasattr(node.element, 'name') else None,
            'element': node.element.__class__.__name__,
            'string': node.string,
            'children': children
        }
 
    # Recursive method to get the children of a node object:
    def get_children(self, children):
        return [self.node_props(c, self.get_children(c.children)) for c in children]
 
    # The main function that we all visit all the leaves of the tree
    def navigate_parse_tree(self, res):
        # store the names of the collections
        self.names_collections = []   
        start = res.tree.children[0] \
            if res.tree.children else res.tree
        return self.node_props(start, self.get_children(start.children))

Как вы можете видеть, эти функции в основном одинаковы, мы просто сделали несколько вещей:

  • мы модифицируем их, чтобы стать частью класса
  • мы добавили вызов функции read_info внутри node_props и добавили поле names_collections в начале посещения

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

Посмотрим, где происходит волшебство.

Получение данных, которые нам нужны

На самом деле мы разделили функцию на две функции: одну, которая собирает информацию о книге, и другую, которая управляет коллекцией.

1
2
3
def read_info(self, node):       
        self.add_book(node)
        self.manage_collection(node)

Мы сделали это, чтобы было проще понять, как работать с деревом разбора.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
def add_book(self, node):
        if hasattr(node.element, 'name'):
            if node.element.name == 'r_title':
                self.book = {}
                self.book['title'] = node.string
            if node.element.name == 'r_pub_date':
                self.book['publication_date'] = node.string
            # we create the authors collection when we find the author keyword
            if node.element.name == 'k_author':
                self.book['authors'] = []
            # we then add each author to the collection
            if node.element.name == 'r_author':
                self.book['authors'].append(node.string)
            if node.element.name == 'r_description':
                # we remove the delimiting double quotes
                self.book['description'] = node.string[1:-1]

Все, что делает эта функция, проверяет имя элемента / узла дерева и добавляет информацию в поле book .

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

Единственное исключение для ключевого слова автора. Ключевое слово per se также не содержит никакой информации. Однако, поскольку может быть более одного автора, значение book['authors'] является списком. Поэтому мы инициализируем список, если найдем ключевое слово author. Затем мы добавляем в список значение для каждого r_author .

Управление коллекциями

Функция для управления коллекциями технически разделена на две части: одна смотрит на имя узлов, а другая ищет разделитель коллекции (то есть, [ и ] ).

Начнем с первой части.

01
02
03
04
05
06
07
08
09
10
def manage_collection(self, node):
        if hasattr(node.element, 'name'):
            # we have found the end of a book         
            if node.element.name == 'k_end_book':               
                self.books[self.name_collection].append(self.book)
                del self.book
            # set the name of the collection
            if node.element.name == 'r_name':
                # set the current name of the collection
                self.name_collection = str.strip(node.string)

Первая часть делает две вещи: ищет конец книги, чтобы добавить ее в текущую коллекцию, и ищет узел, содержащий имя коллекции.

Вторая часть ищет разделители коллекции.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
[..]
 
        # start of the collection
        if not hasattr(node.element, 'name') and node.string == '[':           
            # let's check whether this is the first collection
            if not hasattr(self, 'books'):
                self.books = {}       
 
            # let's store the name of the collection, in case of nested collections 
            self.names_collections.append(self.name_collection)
                 
            # create the new collection           
            self.books[self.name_collection] = []
 
        # end of the collection
        if not hasattr(node.element, 'name') and node.string == ']':
            # let's check whether the last book was added to the collection
            if hasattr(self, 'book'):
                self.books[self.name_collection].append(self.book)
                del self.book
             
            # let's delete the name of the current collection
            del self.name_collection
             
            # let's recover the name of the parent collection, if any
            if(len(self.names_collections) > 0):
                self.name_collection = self.names_collections.pop()

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

Собираем все вместе

Теперь нам просто нужно собрать все воедино.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
def main():
    # Compile your grammar by creating an instance of the Grammar Class.
    book_grammar = BookGrammar()
 
    # read the data from a file
    in_file = open("data.books","r")       
    text = in_file.read()       
    in_file.close()   
    # if the file is valid we navigate the parse tree
    if book_grammar.parse(text).is_valid:
        tree = VisitTree()
        tree.navigate_parse_tree(book_grammar.parse(text))   
         
        # print the resulting tree
        print(tree.get_collections())

В основной функции мы устанавливаем грамматику, анализируем файл примера и печатаем результаты.

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

Это пример различия между синтаксисом и семантикой. Парсер просто читает данные в четко определенном формате. Не существует жестких правил использования данных, описанных в формате.

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

Вы ожидали чего-то большего?

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

1
2
3
4
5
if book_grammar.parse(text).is_valid:
        tree = VisitTree()
        tree.navigate_parse_tree(book_grammar.parse(text))   
    else:
        print(book_grammar.parse(text).expecting)

Давайте представим, что мы забыли добавить закрывающую квадратную скобку. Это был бы выход.

1
{end_book, ]}

Набор end_book слова end_book и закрывающей квадратной скобки.

Это свойство может быть непустым набором, даже если синтаксический анализ является допустимым, в случае наличия дополнительных элементов, которые можно добавить. Таким образом, это не всегда признак ошибки, но он может быть полезен в случае ошибок, то есть когда свойство is_valid имеет значение False .

Резюме

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

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

Вы можете прочитать больше о Pyleri в официальном репозитории GitHub .

Смотрите оригинальную статью здесь: Учебник Pyleri: Разбор с легкостью

Мнения, высказанные участниками Java Code Geeks, являются их собственными.