Разбор абсолютно всего в JavaScript с использованием алгоритма Эрли

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

Знакомство с алгоритмами синтаксического анализа навсегда изменило это отношение.

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

Причина написания парсера

Я работаю над декларативным парсером HTML. Синтаксис парсера зависит от настраиваемого DSL, который является расширением спецификации селектора CSS3.

Вот пример манифеста парсера, используемого для объявления того, что нужно анализировать, и того, как проверять и форматировать полученные данные:

selector: body
properties:
  title: title
  articles:
    selector: article {0,}
    properties:
      body: .body::property(innerHTML)
      summary: .body p {0,}[0]
      imageUrl: img::attribute(src)
      title: .title::text()::test(/foo/)::format(upperCase)

Там происходит множество вещей, не относящихся к спецификации CSS:

Выражение квантификатора ({0,})
Выражение доступа ([0])
Вызов функции в стиле XPath (::test(/foo/)::format(upperCase))

Мне нужен был способ его разобрать.

Выбор подходящего инструмента для работы

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

Это не означает, что регулярное выражение нельзя использовать в качестве парсера. Регулярные выражения могут использоваться для синтаксического анализа регулярного языка; Селекторы CSS не зависят от контекста.

Кстати, если термины контекстно-свободный или обычный язык не имеют особого смысла, я рекомендую прочитать Истинная сила регулярных выражений (5 минут чтения).

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

Я начал искать парсеры в JavaScript и нашел Jison и PEG.js. Однако ни один из алгоритмов не поддерживает левую рекурсию. Мне нужен синтаксический анализатор, поддерживающий левую рекурсию!

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

Короче говоря, на второй странице поиска Google по запросу Анализатор JavaScript я нашел http://nearley.js.org/, реализацию алгоритма синтаксического анализа Эрли.

Автор описывает это так:

Парсеры Earley великолепны, потому что они будут разбирать все, что вы им дадите. В зависимости от указанного алгоритма популярные парсеры, такие как lex / yacc, flex / bison, Jison, PEGjs и Antlr, будут ломаться в зависимости от заданной вами грамматики. И под разрывом я подразумеваю бесконечные циклы, вызванные левой рекурсией, сбоями или упорным отказом от компиляции из-за «ошибки сдвига-уменьшения».

- Лучше Эрли, чем никогда (http://hardmath123.github.io/earley.html)

Это походило на навык, которому я хочу научиться.

Я продолжил читать.

Настраивать

Установите пакет nearley.

$ npm install nearley

nearley состоит из основного пакета (API парсера) и нескольких программ CLI:

$ ls -1 ./node_modules/.bin
nearley-railroad
nearley-test
nearley-unparse
nearleyc

Эти программы:

nearley-railroad используется для создания железнодорожных схем.
nearley-test используется для проверки произвольного ввода на соответствие скомпилированной грамматике.
nearley-unparse используется для генерации случайных строк, удовлетворяющих грамматике.
nearleyc используется для компиляции грамматики Неарли в сценарий JavaScript.

Чтобы сделать эти программы доступными для вашей оболочки, добавьте ./node_modules/.bin в свой $PATH (export PATH=./node_modules/.bin:$PATH) или установите nearley с опцией --global.

Мы будем использовать только nearleyc и nearley-test.

Разбор «1 + 2 + 3»

Парсеру нужна грамматика для анализа ввода.

Алгоритм Эрли анализирует строку на основе грамматики в форме Бэкуса-Наура (BNF). Грамматика BNF состоит из набора производственных правил, которые являются расширением нетерминалов.

Грамматика для синтаксического анализа ввода «1 + 2 + 3»:

expression -> "1+2+3"

Говоря языком непрофессионала, эта грамматика гласит: сопоставьте «1 + 2 + 3» как «выражение».

Нетерминал - это конструкция языка. Нетерминал имеет имя (expression) и список производственных правил . производственное правило определяет, чему соответствовать. Производственное правило состоит из серии других нетерминалов или строк (1+2+3 - производственное правило, состоящее из одного терминала).

Примечание: expression - произвольное имя. Не имеет смыслового значения.

Проверка грамматики

Чтобы проверить это, скомпилируйте грамматику, используя nearleyc:

$ cat <<'EOF' > ./grammar.ne
expression -> "1+2+3"
EOF
$ nearleyc ./grammar.ne --out ./grammar.js

Укажите nearley-test на использование полученного ./grammar.js для анализа ввода:

nearley-test ./grammar.js --input '1+2+3'
Table length: 6
Number of parses: 1
Parse Charts
Chart: 0
0: {expression →  ● expression$string$1}, from: 0
1: {expression$string$1 →  ● "1" "+" "2" "+" "3"}, from: 0
Chart: 1
0: {expression$string$1 → "1" ● "+" "2" "+" "3"}, from: 0
Chart: 2
0: {expression$string$1 → "1" "+" ● "2" "+" "3"}, from: 0
Chart: 3
0: {expression$string$1 → "1" "+" "2" ● "+" "3"}, from: 0
Chart: 4
0: {expression$string$1 → "1" "+" "2" "+" ● "3"}, from: 0
Chart: 5
0: {expression$string$1 → "1" "+" "2" "+" "3" ● }, from: 0
1: {expression → expression$string$1 ● }, from: 0
Parse results:
[ [ '1+2+3' ] ]

Ура! наша программа проанализировала строковый литерал «1 + 2 + 3».

Таблица частичного синтаксического анализа

Важно понимать вывод nearley-test, потому что это инструмент, который вы будете использовать для отладки грамматик.

Эрли работает, создавая таблицу частичного синтаксического анализа, то есть n-й столбец таблицы содержит все возможные способы синтаксического анализа s[:n], первых n символов s.

Chart: 0
0: {expression →  ● expression$string$1}, from: 0
1: {expression$string$1 →  ● "1" "+" "2" "+" "3"}, from: 0

В приведенном выше примере «Диаграмма: 0» - это первый столбец. Это показывает, что у нас есть единственный нетерминал expression, который может быть равен expression$string$1.

Насколько я понимаю, expression$string$1 - это просто временная переменная, используемая для представления терминальных структур, чтобы избежать их повторения. Подробнее об этом позже.

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

По мере продвижения мы продолжаем сопоставлять терминальный символ за символом.

Chart: 1
0: {expression$string$1 → "1" ● "+" "2" "+" "3"}, from: 0
Chart: 2
0: {expression$string$1 → "1" "+" ● "2" "+" "3"}, from: 0
Chart: 3
0: {expression$string$1 → "1" "+" "2" ● "+" "3"}, from: 0
Chart: 4
0: {expression$string$1 → "1" "+" "2" "+" ● "3"}, from: 0
Chart: 5
0: {expression$string$1 → "1" "+" "2" "+" "3" ● }, from: 0

Если совпадает весь терминал, программа выдает токен для совпадения.

1: {expression → expression$string$1 ● }, from: 0
Parse results:
[ [ '1+2+3' ] ]

Чтобы расширить свое понимание, добавьте еще один терминал в expression производственное правило и используйте nearley-test для проверки различных входных данных, например

expression ->
    "1+2+0"
  | "1+2+3"

Несколько производственных правил (нетерминальные расширения) разделяются символом вертикальной черты (|).

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

Постпроцессоры

Если вы внимательно следите, то заметили, что результат программы («1 + 2 + 3») содержится в массиве, который сам содержится в массиве.

[
  [
    '1+2+3'
  ]
]

На это есть две причины.

Первая причина заключается в том, что каждое производственное правило нетерминала - это сам список. В исходном примере этот список содержит одну клемму «1 + 2 + 3». Мы могли бы записать это как:

expression ->
  "1" "+" "2" "+" "3"

Примечание: пробелы вокруг нетерминалов и терминалов не имеют значения в объявлении грамматики.

Эта грамматика эквивалентна исходному примеру. Однако результат другой:

[
  [
    '1',
    '+',
    '2',
    '+',
    '3'
  ]
]

Это потому, что алгоритм Эрли работает с символами. Внутренне nearley преобразует строки длиной более одного символа в правило синтаксического анализатора, объявленное как последовательность символов (строковых литералов), составляющих исходную строку. Если это правило синтаксического анализатора совпадает, результирующая серия символов объединяется обратно в исходную строку.

Совет: посмотрите скомпилированный файл грамматики (grammar.js), чтобы лучше понять внутренний формат правил синтаксического анализатора.

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

Серьезно, а что такое постпроцессор?

Постпроцессор - это функция JavaScript, которая используется для обработки результата производственного правила. Постпроцессор может отформатировать результат или отклонить совпадение. Правило постпроцессора объявляется после производственного правила в окружении {% … %}, например

expression ->
  "1" "+" "2" "+" "3" {% d => d.join('') %}
EOF

Постпроцессор вызывается с 3 параметрами. Первый параметр - это список всех совпадений. В приведенном выше примере это: 1, +, 2, +, 3.

Результат постпроцессора становится значением производственного правила. В приведенном выше примере синтаксический анализатор, выполняемый с вводом «1 + 2 + 3», выдаст:

[
  '1+2+3'
]

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

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

Вернемся к определению нетерминального, которое я дал ранее:

Нетерминал - это конструкция языка. Нетерминал имеет имя и список производственных правил . производственное правило определяет, чему соответствовать. Производственное правило состоит из ряда других нетерминалов или строк.

Это означает, что мы можем объявить нетерминал для сопоставления чисел и нетерминал для сопоставления математических символов.

expression ->
  N MS N MS N  {% d => d.join('') %}
MS ->
    "+" {% d => d[0] %}
  | "-" {% d => d[0] %}
N ->
    "1" {% d => d[0] %}
  | "2" {% d => d[0] %}
  | "3" {% d => d[0] %}
  | "4" {% d => d[0] %}
  | "5" {% d => d[0] %}
  | "6" {% d => d[0] %}
  | "7" {% d => d[0] %}
  | "8" {% d => d[0] %}
  | "9" {% d => d[0] %}
  | "0" {% d => d[0] %}

Надеюсь, это не требует пояснений.

Рекурсивные шаблоны

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

Один или несколько раз

N ->
    "0" {% d => d[0] %}
  | "1" {% d => d[0] %}
  | "2" {% d => d[0] %}
  | "3" {% d => d[0] %}
  | "4" {% d => d[0] %}
  | "5" {% d => d[0] %}
  | "6" {% d => d[0] %}
  | "7" {% d => d[0] %}
  | "8" {% d => d[0] %}
  | "9" {% d => d[0] %}
  | "0" N {% d => d[0] + d[1] %}
  | "1" N {% d => d[0] + d[1] %}
  | "2" N {% d => d[0] + d[1] %}
  | "3" N {% d => d[0] + d[1] %}
  | "4" N {% d => d[0] + d[1] %}
  | "5" N {% d => d[0] + d[1] %}
  | "6" N {% d => d[0] + d[1] %}
  | "7" N {% d => d[0] + d[1] %}
  | "8" N {% d => d[0] + d[1] %}
  | "9" N {% d => d[0] + d[1] %}

Это просто сообщает синтаксическому анализатору, что N является одним из [0–9] или N является одним из [0–9], за которым следует N.

Ноль или больше

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

Чтобы соответствовать ничему, мы используем правило эпсилона. Правило эпсилона обозначается с помощью null.

N ->
    null
  | "0" N {% d => d[0] + d[1] %}
  | "1" N {% d => d[0] + d[1] %}
  | "2" N {% d => d[0] + d[1] %}
  | "3" N {% d => d[0] + d[1] %}
  | "4" N {% d => d[0] + d[1] %}
  | "5" N {% d => d[0] + d[1] %}
  | "6" N {% d => d[0] + d[1] %}
  | "7" N {% d => d[0] + d[1] %}
  | "8" N {% d => d[0] + d[1] %}
  | "9" N {% d => d[0] + d[1] %}

Это сообщает синтаксическому анализатору, что N - это ничто или одно из [0-9], за которым следует N.

Это примеры конструкции рекурсивного повторения BNF.

Наборы символов и квантификаторы

Если вы думаете о [0–9] и квантификаторах, то вам повезло: nearley поддерживает наборы символов и квантификаторы (+*?).

Примечание. Это nearley особенность. nearley компилирует наборы символов и квантификаторы в BNF.

Следовательно, приведенный выше пример один или несколько можно переписать как:

N ->
  [0-9]:+ {% d => d[0].join('') %}

Приведенный выше пример ноль или более можно переписать как:

N ->
  [0-9]:* {% d => d[0].join('') %}

Резюме

Анализ буквального «1 + 2 + 3» научил нас:

что такое нетерминальный
что такое терминал
что такое производственное правило
как отлаживать грамматику
что такое постпроцессор nearley
что такое наборы символов
что такое кванторы
что такое конструкция рекурсивного повтора BNF

Я знаю, о чем вы думаете: все это для разбора буквальной строки «1 + 2 + 3»? Я могу разобрать его с помощью регулярного выражения (\d+\+?).

Разбор (и оценка) математических выражений

Вот грамматика для анализа любого допустимого математического выражения, которое состоит из действий сложения, вычитания, умножения и деления.

main -> AS {% d => d[0] %}
# Parentheses
P -> "(" AS ")" {% d => d[1] %}
    | N {% d => d[0] %}
# Multiplication and division
MD -> MD "*" P {% d => d[0]*d[2] %}
    | MD "/" P {% d => d[0]/d[2] %}
    | P {% d => d[0] %}
# Addition and subtraction
AS ->
    AS "+" MD {% d => d[0]+d[2] %}
  | AS "-" MD {% d => d[0]-d[2] %}
  | MD {% d => d[0] %}
N ->
    [0-9]:+ {% d => parseInt(d[0].join(''), 10) %}

Вы уже знаете все компоненты, составляющие эту грамматику. Понять, что это просто вопрос компиляции грамматики и использования nearley-test для отладки нескольких выражений, например 10/((1+4)*8)*4 дает 1.

Двусмысленность

Когда я представил постпроцессоры, я рассказал о том, как результат содержится в массиве массивов.

[
  [
    '1+2+3'
  ]
]

Я объяснил один уровень вложенности - это потому, что производственное правило - это список.

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

[
  '1+2+3'
]

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

Неоднозначность представит проблемы с производительностью (для завершения синтаксического анализа необходимо проанализировать несколько маршрутов). Это также приведет к затруднению обнаружения ошибок - разные маршруты могут давать разные результаты синтаксического анализа.

Вот пример неоднозначной грамматики:

attributeName ->
  [_a-zA-Z]:* [_a-zA-Z0-9-]:* {% d => d[0].join('') + d[1].join('') %}

Если входные данные совпадают с первым и вторым наборами символов, на выходе парсера будут:

[
  'foobar',
  'foobar'
]

Это потому, что и [_a-zA-Z]:*, и [_a-zA-Z0–9-]:* соответствуют строке «foobar» до завершения.

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

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

attributeName ->
  [_a-zA-Z] [_a-zA-Z0-9-]:* {% d => d[0] + d[1].join('') %}

Отклонение совпадения

Когда я действительно представил функции постпроцессора, я сказал, что функция постпроцессора вызывается с тремя параметрами:

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

Когда я впервые прочитал документацию nearley, это оставило меня озадаченным - когда я хочу отклонить действительное совпадение? Я столкнулся по крайней мере с одним сценарием при работе с синтаксическим анализатором CSS, о котором я упоминал ранее.

Рассмотрим этот пример:

selectorBody ->
  typeSelector:?
  idSelector:?
  classSelector:*
  attributeValueSelector:*
  attributePresenceSelector:*
  pseudoClassSelector:* {%d flatten %d}

Примечание: это единое производственное правило. Нет |.

Селектор CSS может состоять из:

селектор типа (необязательно)
селектор идентификатора (необязательно)
несколько селекторов классов (необязательно)
несколько селекторов значений атрибутов (необязательно)
несколько селекторов присутствия и (необязательно)
несколько выборщиков псевдокласса (необязательно)

Заметили закономерность? Все они необязательны. Это означает, что селектор CSS должен иметь хотя бы один из перечисленных выше компонентов, но ни один из них не требуется.

Моя первая и наивная попытка была:

Примечание. Сокращения используются только в целях форматирования.

selectorBody ->
    TS   IS:? CS:* AVS:* APS:* PCS:* {% flatten %}
  | TS:? IS   CS:* AVS:* APS:* PCS:* {% flatten %}
  | TS:? IS:? CS   AVS:* APS:* PCS:* {% flatten %}
  | TS:? IS:? CS:* AVS   APS:* PCS:* {% flatten %}
  | TS:? IS:? CS:* AVS:* APS   PCS:* {% flatten %}
  | TS:? IS:? CS:* AVS:* APS:* PCS   {% flatten %}

Это гарантирует наличие хотя бы одного селектора. Проблема в том, что (как вы уже догадались!) Это может дать более одного результата (неоднозначная грамматика).

Вот тут и появляется страж отказа.

Мы можем отфильтровать null результатов (когда квантификатор ничего не соответствует, он дает null; помните, как мы писали квантификаторы с использованием BNF). И если совпадений нет, мы возвращаем дозор отклонения, чтобы отклонить совпадение.

selectorBody ->
    TS:? IS:? CS:* AVS:* APS:* PCS:* {% (d, i, reject) => { const tokens = d.filter((token) => { return token !== null; }); if (!tokens.length) return reject; return flatten(tokens); } %}

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

Вспомогательные функции

Написание функций постпроцессора после каждого производственного правила не очень хорошо для читабельности кода. Используйте синтаксис @{% … %} для объявления вспомогательных функций. Фактически, в приведенном выше примере кода уже используется предопределенная функция flatten.

@{%
  const flatten = d => {
    return d.reduce(
      (a, b) => {
        return a.concat(b);
      },
      []
    );
  };
const filter = d => {
    return d.filter((token) => {
      return token !== null;
    });
  };
const selectorBody = (d, i, reject) => {
    const tokens = filter(d);
if (!tokens.length) {
      return reject;
    }
return flatten(tokens);
  }
%}
selectorBody ->
    TS:? IS:? CS:* AVS:* APS:* PCS:* {% selectorBody %}

Примечание. Весь код, написанный между @{% … %}, поднимается в начало сгенерированного файла грамматики. Следовательно, где вы их напишете, значения не имеет. Однако я предпочитаю определять всех помощников в верхней части файла.

Парсинг и токенизация

Теперь, когда вы знаете, как разбирать строку, как ее токенизировать?

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

N ->
    [0-9]:+ {% d => {type: 'NUMBER', value: parseInt(d[0].join(''), 10)} %}

Бонус: грамматика IDE

Существуют плагины для разных IDE, которые включают подсветку синтаксиса Nearley:

Пользователи Atom могут писать почти целые грамматики с помощью этого плагина Божидара Маринова.
Пользователи Sublime Text могут писать почти грамматики с этим синтаксисом от liam4.
Пользователи Vim могут использовать этот плагин Андреса Арана.

Всемогущее оружие!

Я обещал тебе всемогущее оружие: оно у тебя! Теперь у вас есть умение разбирать абсолютно любую строку!

Парсер селектора CSS

Вначале я сказал, что начал изучать синтаксический анализ, потому что мне нужно было создать синтаксический анализатор селектора CSS. Я построил его с использованием nearley, и я почти уверен, что это самый тщательный синтаксический анализатор селекторов CSS, доступный для JavaScript.

Встречайте Scalpel, синтаксический анализатор селекторов CSS.

Если вы ищете больше примеров использования алгоритма Эрли для разбора контекстно-свободной грамматики, я рекомендую вам взглянуть на исходный код Scalpel.

Удачи! :-)