Недавно я начал делать серьезные попытки изучить Haskell (любой, кто пробовал раньше, вероятно, посочувствует, что обычно требуется пара попыток, чтобы взломать его). Среди множества интересных вещей, которые может предложить Haskell, есть потрясающая библиотека синтаксического анализа, которая поставляется со стандартным набором пакетов под названием Parsec, который позволяет вам описывать, как анализировать сложные грамматики на том, что по сути выглядит как естественный язык. .
Вот как реализован парсер CSV с использованием Parsec. Не волнуйтесь, если вы не понимаете весь синтаксис, дело в том, что весь синтаксический анализатор указан всего в четырех строках.
Однако этот пост не о Haskell, а скорее о библиотеке, которую я написал под названием arcsecond, которая основана на Parsec, с целью придать такую же выразительность JavaScript.
Комбинаторы парсеров
arcsecond - это библиотека комбинаторов синтаксических анализаторов, в которой сложные синтаксические анализаторы могут быть построены путем составления простых синтаксических анализаторов. Самые простые парсеры просто сопоставляют определенные строки или символы:
Затем их можно объединить вместе с комбинаторами в библиотеке.
Затем новые парсеры можно использовать с текстом:
Комбинаторы
Комбинаторы - вот где становится круто. В arcsecond комбинатор - это синтаксический анализатор более высокого порядка, который принимает один или несколько синтаксических анализаторов в качестве входных данных и возвращает новый синтаксический анализатор, который объединяет их каким-либо образом. Если вы использовали компоненты более высокого порядка, например, connect, withRouter, или withStyles, значит, вы уже знакомы с этой идеей.
Как показано выше, sequenceOf - это комбинатор, который будет анализировать текст, используя каждый из анализаторов по порядку, собирая их результаты в массив.
choice, с другой стороны, будет пробовать каждый из своих синтаксических анализаторов по порядку и использовать первый, который соответствует. Библиотека содержит больше, например many, которое принимает синтаксический анализатор в качестве аргумента и сопоставляет столько, сколько может, используя этот синтаксический анализатор, собирая результаты в массиве:
Вы можете использовать sepBy для создания синтаксического анализатора, который сопоставляет элементы, разделенные чем-то, совпадающим с другим синтаксическим анализатором.
между позволит вам сопоставить элементы, которые встречаются между двумя другими синтаксическими анализаторами.
Карри-функции
arcsecond использует каррированные функции. Если вы не знаете, что такое каррированная функция, прочтите мою статью Создание щелчка при функциональном программировании. Если вы действительно не можете беспокоиться прямо сейчас, откройте это на другой вкладке и прочтите это резюме.
Каррированная функция - это функция, которая, если она принимает более одного аргумента, вместо этого возвращает новую функцию, которая принимает следующий аргумент. Это легче увидеть с помощью кода:
Как вы можете видеть выше, curriedAdd сначала вызывается с 1. Поскольку он затем возвращает функцию, мы можем продолжить и вызвать ее с 2, что, наконец, возвращает фактический результат. .
Мы можем использовать curriedAdd для создания новой функции, вызывая ее только с одним аргументом, а затем присваивая результат переменной. Как язык, JavaScript рассматривает функции как первоклассный гражданин, то есть их можно передавать и присваивать переменным.
Этот принцип лежит в основе arcsecond, и каждая функция в библиотеке определяется таким образом. sepBy возьмем два парсера - первый парсер разделителя, а второй парсер значения. Поскольку он каррирован, легко создать более конкретный комбинатор, например commaSeparated, указав только первый аргумент.
Если вы к этому не привыкли, это может показаться странным. Но хороший урок, который следует усвоить разработчику программного обеспечения, - это не резко реагировать на вещи, которые вы не сразу понимаете. Обычно причина есть, и вы найдете гораздо больше пользы, обнаружив эту причину, а не отвергнув ее.
Обработка ошибок
Если вы попытаетесь разобрать строку, которая неправильно отформатирована, вы ожидаете получить какое-то сообщение об ошибке. arcsecond использует специальный тип данных, называемый Either, который является либо значением, либо ошибкой. Это похоже на обещание, которое можно либо отклонить, либо выполнить, но без асинхронности. Однако в Either тип «разрешенный» называется Right, а тип «отклоненный» - называется Left.
Тип возврата синтаксического анализа - Either. Вы можете получить значение или ошибку следующим образом:
Однако это может не вписаться в вашу кодовую базу, если у вас нет более функционального кода. По этой причине есть два других варианта. Первый - преобразовать Either в Promise:
Или вы можете использовать toValue, который должен быть заключен в блок try / catch:
Что-то более сложное: JSON
Давайте рассмотрим arcsecond, используя его для создания синтаксического анализатора JSON.
Нажмите здесь, чтобы пропустить вперед и увидеть полный анализатор JSON в одном файле
Ценности
JSON имеет только 7 возможных значений:
- Нить
- Число
- правда
- ложный
- нулевой
- Множество
- Объект
Итак, чтобы написать парсер JSON, нам просто нужно написать парсеры для всех этих значений.
Типы
Чтобы наш синтаксический анализатор был полезен, нам нужно иметь возможность идентифицировать то, что мы проанализировали, и лучший способ сделать это - поместить результаты в тип данных, который предоставит нам общий интерфейс для взаимодействия с Дерево JSON. У каждого типа есть имя типа, значение и функция toString для красивой печати структуры.
Имея в руках наши типы, давайте начнем с самых простых парсеров: true, false и null. Это просто буквальные строки:
Синтаксические анализаторы в arcsecond имеют метод map, как и массивы, который позволяет преобразовывать значение, сопоставленное синтаксическому анализатору. С помощью map мы можем поместить совпадающие значения в типы данных, определенные выше.
Числа немного сложнее. В спецификации JSON есть эта железнодорожная диаграмма, показывающая, как можно проанализировать число:
Вилки на железных дорогах имеют возможность выбора, поэтому простейшее число, которое можно сопоставить, - это просто 0.
В основном такие числа, как:
- 1
- -0.2
- 3.42e2
- -0.4352E-235
Все допустимы в JSON, а что-то вроде 03.46 - нет, потому что ни один путь на железной дороге не допускает этого.
Если вы потратите время на то, чтобы прочитать numberParser, вы увидите, что он примерно 1: 1 совпадает с диаграммой выше.
Давайте теперь попробуем струны. Строка - это что угодно, заключенное в двойные кавычки, но она также может содержать экранированные кавычки.
Парсер somethingExcept здесь очень удобен и особенно выразителен по сравнению с изображением на веб-сайте спецификации JSON.
Остается только массив и объект, которые могут быть ловушками, потому что они в основном просто контейнеры для jsonValue. Чтобы проиллюстрировать, как это может пойти не так, мы можем сначала написать «неправильный» способ синтаксического анализа массива, а затем посмотреть, как с этим бороться.
Мы можем использовать синтаксический анализатор пробелов, который соответствует нулю или более пробелам, чтобы гарантировать, что скобки массива и оператор запятой допускают любые (необязательные) пробелы, которые могут там присутствовать.
Поскольку arrayParser определяется в терминах jsonParser и jsonParser определяется в терминах arrayParser, мы сталкиваемся с ReferenceError. Если мы переместим определение arrayParser ниже jsonParser, у нас все равно будет та же проблема. Мы можем исправить это, заключив jsonParser в специальный синтаксический анализатор с метко названным recursiveParser. Аргументом для recursiveParser является преобразователь, который позволит нам ссылаться на переменные, которые еще не входят в область видимости.
Реализация arrayParser на самом деле довольно тривиальна - так же просто, как значения JSON, разделенные запятыми, в квадратных скобках.
Объект лишь немного сложнее. Значения в объекте представляют собой пары строк и некоторые другие значения JSON с двоеточием в качестве разделителя.
Вот и все. jsonValue можно использовать для анализа всего документа JSON. Полный синтаксический анализатор можно найти здесь в кратком виде.
Бонусный парсер: CSV
Поскольку я начал с парсера CSV в Haskell, давайте посмотрим, как это будет выглядеть в угловых секундах. Я сохраню его минимальным и откажусь от создания типов данных для хранения значений, а также некоторых дополнительных усилений, которых также нет в версии Parsec.
Результатом должен быть массив массивов - внешний массив содержит «строки», а внутренние массивы содержат элементы строки.
Заключение
Есть немало ключевых особенностей arcsecond, о которых не упоминалось в этой статье, в том числе тот факт, что он может анализировать контекстно-зависимые языки, а модель анализа основана на Fantasy Land. -соответствующая Монада ». Моей главной целью в этом проекте было привнести такой же уровень выразительности, который Parsec имеет в JavaScript, и я надеюсь, что мне это удалось.
Пожалуйста, ознакомьтесь с проектом на github вместе со всеми документами и примерами API и подумайте о arcsecond, когда в следующий раз обнаружите, что пишете непонятное регулярное выражение для спагетти - возможно, вы используете не тот инструмент для работы! Вы можете установить последнюю версию с помощью:
npm i arcsecond
Напишите мне в твиттере @fstokesman и поставьте этой статье, если она вам показалась интересной! Я мог бы написать продолжение о том, как arcsecond работает внутри, так что следите за обновлениями.
