Как написать парсер на perl

Парсим pod от Perl 5 при помощи Perl 6

Только что закончил разработку парсера pod (plain old documentation) для Perl 5, написанного на Perl 6. Грамматику сделать получилось на удивление легко – спасибо Perl 6, ведь я сам-то не особенно какой гений программирования. С помощью ребят из #perl6 я узнал много всего интересного по ходу дела, и хочу поделиться этим со всеми. Ну и код, конечно, тоже прилагается.

Кстати, рекомендую прочесть сначала моё введение в грамматики в Perl 6, и многое в этой статье станет более ясным.

Разработка грамматики

В Perl 6 грамматика – особый тип классов для разбора текстов. Идея в том, чтобы объявить последовательность регулярок и назначить им токены, которые затем можно использовать для разбора ввода. Для Pod::Perl5::Grammar я подробно проработал спецификацию perlpod, добавляя по мере исследования стандартов нужные токены.

Конечно, есть несколько проблем. Во-первых, как определить регулярку для списков? В pod списки могут содержать списки – может ли определение включать себя? Оказывается, что рекурсивные определения возможны, если только они не совпадают со строкой нулевой длины, что приведёт к бесконечному циклу. Вот определение:

Токен over_back описывает весь список с начала до конца. Проще говоря, там написано, что лист должен начинаться с =over и заканчиваться с =back, а посередине может быть много всякого, включая ещё один over_back!

Для простоты я обычно называл токены так, как они пишутся в pod, хотя иногда это не получалось из-за пересечений пространств имён.

Следующий шаблон мне особенно нравится, поэтому я часто к нему обращался:

Он полезен, если вам надо найти шаблон, но при этом игнорировать всё остальное, если он не найден. В нашем случае, pod_section – это токен, определяющий секцию в pod, но pod часто пишут прямо в коде Perl, и тогда всё лишнее должно быть проигнорировано. Поэтому, во второй части определения используется негативный lookahead ?!before для проверки того, что следующий отрывок текста не равен pod_section, и используется точка, чтобы зацепить «всё остальное», включая переводы строк. Оба условия сгруппированы в квадратных скобках со звёздочкой снаружи, чтобы проверять текст посимвольно.

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

Классы действий

Классы действий – это обычные классы Perl 6, которые можно передавать в грамматику во время разбора. Они позволяют назначать поведение (действия) токенам для работы в момент совпадения шаблона. Надо просто назвать методы в классе так же, как токен, над которым его необходимо выполнить. Я написал класс действий pod-to-HTML. Вот метод для преобразования =head1 в HTML:

Каждый раз, когда грамматика использует токен head1, выполняется этот метод. Ему передаётся переменная $/, содержащая найденную последовательность head1, из который и извлекается текстовая строка.

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

Это происходит оттого, что italics и bold находятся регулярками в первую очередь. Пришлось использовать буфер для хранения HTML из токенов второго уровня. Когда находится токен параграфа, парсер подставляет вместо текста содержимое этого буфера. Класс выглядит так:

Особое внимание нужно обратить на работу с регулярками. Каждый пример класса действий использует $/. Это ошибка – догадайтесь, что случится в результате:

Присвоение переменной только для чтения или значению.

Ядерный взрыв. Когда $/ передаётся в head1, оно служит только для чтения. Выполнение любой регулярки в той же лексической области видимости попытается перезаписать $/. На это я пару раз напарывался, и с помощью канала #perl6 я остановился на таком варианте:

Добавив is copy к параметрам, я делаю копию значения вместо указания на $/. Затем я копирую переменную match в $match, и тогда следующая регулярка может спокойно работать с $/. Думаю, что лучше вообще сделать так:

Просто не называть параметр $/, и всё сработает. Но всесторонне я это пока не проверял.

Для использования класса действий мы просто передаём его в грамматику:

В первом примере используется позиционный аргумент :$actions. Он обязательно должен называться actions. Во втором примере я назвал аргумент :actions($actions), и в этом случае объект класса действий может называться как угодно.

Улучшаем pod

Статьи на PerlTricks.com написаны в HTML, со своими именами классов и тегами span. Его сложно редактировать и сложно писать. Я хотел бы использовать для редактирования pod – он был бы проще для писателей и для редактора. Поэтому мне хочется расширить pod, добавив в него всякие полезные функции для блогов. Например, форматирование делается через B и тому подобные функции. Почему бы не добавить @ для ссылок на Twitter, или M для ссылок на MetaCPAN?

Поскольку грамматики в Perl 6 – это классы, их можно наследовать и переопределять. Поэтому я могу добавить свои собственные коды так:

Также нужно переопределить токен format_codes, чтобы включить в него новые:

Вот так всё просто. Новая грамматика сможет парсить pod и работать с моими новыми кодами форматирования. Конечно, класс Pod::Perl5::Pod тоже можно расширять и переопределять, и в результате получится что-то вроде:

Это ещё не всё

Существует более наглядный способ работы с группами токенов, multi-dispatch. Вместо определения format_codes как списка альтернативных токенов, мы объявляем метод-прототип, и объявляем каждый метод форматирования как вариант multi прототипа.

При наследовании грамматики нет необходимости переопределять format_codes. Можно добавить новые через multi:

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

Источник статьи: http://habr.com/ru/post/264225/

Написание парсера с нуля: так ли страшен черт?

В прошлом топике я рассказывал о том, как мы с другом решили ради развлечения написать свой встраиваемый язык программирования для платформы .NET. У первой версии был серьезный недостаток — парсер был реализован на F# с помощью сторонней библиотеки. Из-за этого требовалась куча зависимостей, парсер работал медленно, а поддержка его была крайне муторным занятием.

Очевидно, что парсер нужно было переписать на C#, но при мысли о написании парсера с нуля вдруг находилась дюжина других срочных дел. Таким образом таск перекидывался и откладывался практически полгода и казался непосильным, а в итоге был сделан за 4 дня. Под катом я расскажу об удобном способе, позволившим реализовать парсер достаточно сложной грамматики без использования сторонних библиотек и не тронуться умом, а также о том, как это позволило улучшить язык LENS.

Первый блин

Как было сказано выше, в качестве ядра парсера мы использовали библиотеку FParsec. Причины данного выбора скорее исторические, нежели объективные: понравился легковесный синтаксис, хотелось поупражняться в использовании F#, и автор библиотеки очень оперативно отвечал на несколько вопросов по email.

Главным недостатком этой библиотеки для нашего проекта оказались внешние зависимости:

• Примерно десятимегабайтный F# Runtime
• 450 кб сборок самого FParsec

Кроме того, сам компилятор разбился на 3 сборки: парсер, синтаксическое дерево и точку входа. Сборка парсера занимала внушительные 130 кб. Для встраиваемого языка это абсолютно неприлично.

Другой проблемой было отображение ошибок. Лаконичная запись грамматики на местном DSL при некорректно введенной программе выдавала нечитаемую ошибку c перечислением ожидаемых лексем:

Хотя кастомная обработка ошибок и возможна, DSL для нее явно не предназначен. Описание грамматики уродливо распухает и становится абсолютно неподдерживаемым.

Еще одним неприятным моментом была скорость работы. При «холодном старте» компиляция любого, даже самого простого скрипта занимала на моей машине примерно 350-380 миллисекунд. Судя по тому, что повторный запуск такого же скрипта занимал уже всего-то 5-10 миллисекунд, задержка была вызвана JIT-компиляцией.

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

Немного теории

Сферический парсер в вакууме представляет собой функцию, которая принимает исходный код, а возвращает некое промежуточное представление, по которому удобно будет сгенерировать код для используемой виртуальной машины или процессора. Чаще всего это представление имеет древовидную структуру и называется абстрактным синтаксическим деревом — АСД (в иностранной литературе — abstract syntactic tree, AST).

Древовидная структура особенно хороша тем, что ее обход в глубину отлично сочетается со стековой организацией, используемой во многих современных виртуальных машинах (например, JVM или .NET). Генерация кода в данной статье рассматриваться не будет, однако элементы синтаксического дерева, как результат работы парсера, будут время от времени упоминаться.

Итак, на входе мы имеем строку. Набор символов. Работать с ней в таком виде напрямую не слишком удобно — приходится учитывать пробелы, переносы строк и комментарии. Для упрощения себе жизни разработчики парсеров обычно разделяют разбор на несколько проходов, каждый из которых выполняет какую-то одну простую задачу и передает результат своей работы следующему:

1. Лексический анализатор: string -> IEnumerable
2. Синтаксический анализатор: IEnumerable -> IEnumerable
3. Семантический анализатор: IEnumerable -> ?

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

Лексический анализатор

• Скорость работы
• Легкость расширения
• Простота реализации
• Отслеживание положения в исходном тексте

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

Все лексемы изначально стоит поделить на 2 типа — статические и динамические. К первым относятся те лексемы, которые можно выразить обычной строкой — ключевые слова и операторы. Лексемы типа идентификаторов, чисел или строк проще описать регулярным выражением.

Статические лексемы, в свою очередь, есть резон поделить на операторы и ключевые слова. Ключевые слова сопоставляются только в том случае, если следующий за ними символ не является допустимым для идентификатора (или дальше — конец строки). В противном случае возникнут проблемы с идентификаторами, чье начало совпадает с ключевым словом: например, «information» -> keyword(in), keyword(for), identifier(mation) .

• Работает быстро
• Элементарное устройство, можно написать за полчаса
• Новые лексемы добавляются очень просто
• Способ подходит для множества грамматик

Недостатки:

• Танцы с бубном при разборе языка со значимыми пробелами
• Порядок объявления лексем важен: желательно сортировать по длине

Синтаксический анализатор

• Легкость расширения при изменении грамматики
• Возможность описывать подробные сообщения об ошибках
• Возможность заглядывать вперед на неограниченное количество позиций
• Автоматическое отслеживание положения в исходном коде
• Лаконичность, близость к исходной грамматике

Для того, чтобы упростить себе жизнь при написании парсера, следует оформить грамматику специальным образом. Никаких сложных конструкций! Все правила можно поделить на 3 типа:

• Описание — один конкретный узел:
  (var_expr = «var» identifier «=» expr)
• Повторение — один конкретный узел повторяется многократно, возможно с разделителем:
  main = < stmt ";" >
• Альтернатива — выбор из нескольких узлов
  (stmt = var_expr | print_expr | assign_expr | other)

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

Правило-перечисление — это цикл. Чтобы вернуть последовательность значений, в C# есть очень удобный функционал для создания генераторов с помощью yield return .

Правило-альтернатива по очереди вызывает правила-варианты с помощью специальной обертки, которая позволяет откатиться в исходное состояние. Правила просто вызываются по порядку, пока хотя бы одно из них не совпадет, связанные оператором coalesce ( ?? ).

Тут пытливый читатель спросит:
— Как это, просто вызываются по порядку? А как же опережающие проверки? Например, так:

Признаюсь, свой первый серьезный парсер я написал именно так. Однако это плохая идея!

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

Если с id_assign еще все понятно, то оба других правила начинаются с нетерминала lvalue , под которым может скрываться километровое выражение. Очевидно, что никаких опережающих проверок тут не напасешься.

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

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

Рассмотрим на примере выше. Допустим, у нас есть текст: a.1 = 2 :

1. Первой вызывается альтернатива id_assign .
2. Идентификатор a успешно совпадает.
3. Дальше идет точка, а ожидается знак «равно». Однако с идентификатора могут начинаться и другие правила, поэтому ошибка не выбрасывается.
4. Правило assign откатывает состояние назад и пробует дальше.
5. Вызывается альтернатива member_assign .
6. Идентификатор и точка успешно совпадают. В грамматике нет других правил, которые начинаются с идентификатора и точки, поэтому дальнейшие ошибки не имеет смысл пытаться обработать откатыванием состояния.
7. Число 1 не является идентификатором, поэтому выкидывается ошибка.

Сначала напишем несколько полезных методов:

С их помощью реализация приведенной выше грамматики становится практически тривиальной:

Атрибут DebuggerStepThrough сильно помогает при отладке. Поскольку все вызовы вложенных правил так или иначе проходят через Attempt и Ensure, без этого атрибута они будут постоянно бросаться в глаза при Step Into и забивать стек вызовов.

Преимущества данного метода:

• Откат состояния — очень дешевая операция
• Легко управлять тем, до куда можно откатываться
• Легко отображать детальные сообщения об ошибках
• Не требуются никакие внешние библиотеки
• Небольшой объем генерируемого кода

Недостатки:

• Реализация парсера вручную занимает время
• Сложность написания и оптимальность работы зависят от качества грамматики
• Леворекурсивные грамматики следует разруливать самостоятельно

Операторы и приоритеты

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

Теперь представим, что у нас есть еще булевы операторы, операторы сравнения, операторы сдвига, бинарные операторы, или какие-нибудь собственные. Сколько правил получается, и сколько всего придется поменять, если вдруг придется добавить новый оператор с приоритетом где-то в середине?

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

Теперь для добавления нового оператора необходимо лишь дописать соответствующую строчку в инициализацию списка приоритетов.

Добавление поддержки унарных префиксных операторов оставляю в качестве тренировки для особо любопытных.

Что нам это дало?

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

Итого, сравнительная таблица результатов:

Скорее всего, возможно провести оптимизации и выжать из синтаксического анализатора больше производительности, но пока и этот результат вполне устраивает.

Избавившись от головной боли с изменениями в грамматике, мы смогли запилить в LENS несколько приятных вещей:

Цикл for

Используется как для обхода последовательностей, так и для диапазонов:

Композиция функций

С помощью оператора :> можно создавать новые функции, «нанизывая» существующие:

Частичное применение возможно с помощью анонимных функций:

Улучшения синтаксиса

Скобки вокруг единственного аргумента лямбды опциональны:

Скобки в управляющих конструкциях убраны:

Появился блок try/finally

Скобки при передаче индекса или поля в функцию опциональны:

Проект хоть и медленно, но развивается. Осталось еще много интересных задач. На следующую версию планируется:

• Объявление generic-типов и функций
• Возможность пометить функции или типы атрибутами
• Поддержку событий

Также можно скачать собранные демки под Windows.

Источник статьи: http://habr.com/ru/post/202622/