17.1: Написание синтаксических анализаторов с помощью PetitParser

1. Последнее обновление

2. Сохранить как PDF

Идентификатор страницы

43764

• Александр Бергель, Дамьен Кассу, Стефан Дюкасс, Янник Лаваль
• Square Bracket Associates

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

Кроме того, PetitParser не основан на таких таблицах, как SmaCC и ANTLR. Вместо этого он использует комбинацию четырех альтернативных методологий синтаксического анализа: синтаксические анализаторы без сканирования, комбинаторы синтаксических анализаторов, синтаксические грамматики синтаксического анализа и синтаксические анализаторы Packrat. Таким образом, PetitParser более мощен в том, что он может анализировать. Давайте кратко рассмотрим эти четыре методологии синтаксического анализатора:

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

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

Грамматики синтаксического анализа выражений (PEG) предоставляют понятие упорядоченного выбора. В отличие от комбинаторов синтаксических анализаторов, упорядоченный выбор PEG всегда следует за первой подходящей альтернативой и игнорирует другие альтернативы. Действительный ввод всегда приводит только к одному дереву синтаксического анализа, результат синтаксического анализа никогда не бывает неоднозначным.

Парсеры Packrat гарантируют линейное время анализа и позволяют избежать распространенных проблем с левой рекурсией в PEG.

Загрузка PetitParser

Хватит болтать, приступим. PetitParser разработан в Pharo, также доступны версии для Java и Dart. Готовый образ можно скачать по телефону ¹ . Чтобы загрузить PetitParser в существующий образ, выполните следующее выражение Gofer:

Код \(\PageIndex{1}\) (Pharo): Установка PetitParser

 Гофер новый
    smalltalkhubUser: проект «Лось»: «PetitParser»;
    пакет: 'ConfigurationOfPetitParser';
    нагрузка. 
(Светская беседа по адресу: #ConfigurationOfPetitParser) выполнить: #loadDefault.
 

Дополнительную информацию о том, как получить PetitParser, можно найти в главе о petit parser в книге Moose. ²

Написание простой грамматики

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

Код \(\PageIndex{2}\) (Pharo): Создание нашего первого анализатора для разбора идентификаторов

 |identifier|
идентификатор := #буква asParser , #слово asParser звездочка.
анализ идентификатора: 'a987jlkj' −→ #($a #($9 $8 $7 $j $l $k $j))
 

Рисунок \(\PageIndex{1}\): Представление синтаксической диаграммы для синтаксического анализатора идентификатора, определенного в коде \(\PageIndex{2}\).

Графическое обозначение

На рисунке \(\PageIndex{1}\) представлена ​​синтаксическая диаграмма анализатора идентификаторов. Каждое поле представляет парсер. Стрелки между прямоугольниками представляют собой поток, в котором потребляются входные данные. Круглые прямоугольники — это элементарные парсеры (терминалы). Квадраты (не показаны на этом рисунке) — это синтаксические анализаторы, состоящие из других синтаксических анализаторов (не терминалов).

Если вы проверите идентификатор объекта предыдущего скрипта, вы заметите, что это экземпляр

PPSequenceParser . Если вы углубитесь в объект, вы заметите следующее дерево различных объектов парсера:

Код \(\PageIndex{3}\) (Pharo): Состав парсеров, используемых для парсера идентификатора

 PPSequenceParser (принимает последовательность парсеров)
    PPPredicateObjectParser (принимает одну букву)
    PPPossessiveRepeatingParser (принимает ноль или более экземпляров другого парсера)
        PPPredicateObjectParser (принимает символ из одного слова)
 

Корневой синтаксический анализатор является синтаксическим анализатором последовательности, поскольку оператор , (запятая) создает последовательность из (1) синтаксического анализатора букв и (2) синтаксического анализа символов из нуля или более слов. Первый потомок корневого синтаксического анализатора — это синтаксический анализатор объектов предикатов, созданный выражением

#letter asParser . Этот синтаксический анализатор способен анализировать одну букву, как определено методом Character»isLetter . Второй потомок — повторяющийся синтаксический анализатор, созданный вызовом star . Этот синтаксический анализатор максимально использует свой дочерний синтаксический анализатор (другой синтаксический анализатор объектов-предикатов) на входе ( т.е. , это жадный парсер ). Его дочерний синтаксический анализатор — это синтаксический анализатор объектов предикатов, созданный выражением #word asParser . Этот синтаксический анализатор способен анализировать одну цифру или букву, как определено методами Character»isDigit и Character»isLetter .

Разбор некоторых входных данных

Для фактического анализа строки (или потока) мы используем метод PPParser»parse: следующим образом:

Код \(\PageIndex{4}\) (Pharo): Разбор некоторых входных строк с помощью анализатора идентификатора

 разбор идентификатора: 'да'.  → #($y #($e $a $h))
разбор идентификатора: 'f123'. → #($f #($1 $2 $3))
 

Хотя получение этих вложенных массивов с символами в качестве возвращаемого значения кажется странным, это декомпозиция ввода по умолчанию в дерево синтаксического анализа. Через некоторое время мы увидим, как это можно настроить.

Если мы попытаемся проанализировать что-то недопустимое, мы получим экземпляр PPFailure в качестве ответа:

Код \(\PageIndex{5}\) (Pharo): Анализ неверных входных данных приводит к ошибке

 разбор идентификатора: '123'. → буква ожидается в 0
 

Этот синтаксический анализ приводит к ошибке, поскольку первый символ (1) не является буквой. Экземпляры PPFailure — это единственные объекты в системе, которые отвечают true при отправке сообщения

#isPetitFailure . В качестве альтернативы вы также можете использовать PPParser»parse:onError: для создания исключения в случае ошибки:

 идентификатор
    разбор: '123'
    onError: [ :msg :pos | собственная ошибка: сообщение ]. 
 

Если вас интересует только совпадение данной строки (или потока), вы можете использовать следующие конструкции:

Код \(\PageIndex{6}\) (Pharo): Проверка того, что некоторые входные данные являются идентификаторами

Идентификатор

 соответствует: 'foo'. → правда
идентификатор соответствует: '123'. → ложь
идентификатор соответствует: 'foo()'. → правда
 

Последний результат может удивить: действительно, скобка не является ни цифрой, ни буквой, как было указано #word asParser выражение. На самом деле парсеру

идентификатор соответствует «foo» и этого достаточно, чтобы вызов PPParser»matches: вернул true . Результат будет аналогичен использованию parse : который вернет #($f #($o $o)) .

Если вы хотите убедиться, что все входные данные совпадают, используйте сообщение PPParser»end следующим образом:

Код \(\PageIndex{7}\) (Pharo): Проверка совпадения всего ввода используя PPParser»end

 конец идентификатора соответствует: 'foo()'.  → ложь
 

Сообщение PPParser»end создает новый синтаксический анализатор, соответствующий концу ввода. Чтобы иметь возможность легко создавать синтаксические анализаторы, важно, чтобы синтаксические анализаторы не совпадали с концом ввода по умолчанию. Из-за этого вам может быть интересно найти все места, которые парсер может сопоставить, используя сообщение

PPParser»matchesSkipIn: и PPParser»matchesIn: .

Код \(\PageIndex{8}\) (Pharo): Поиск всех совпадений во входных данных

 идентификатор matchesSkipIn: 'foo 123 bar12'.
    → упорядоченная коллекция(#($f #($o $o)) #($b #($a $r $1 $2)))
идентификатор соответствует In: 'foo 123 bar12'.
    → упорядоченная коллекция(#($f #($o $o)) #($o #($o)) #($o #()) #($b #($a $r $1 $2))
        #($a #($r $1 $2)) #($r #($1 $2)))
 

Метод PPParser»matchesSkipIn: возвращает набор массивов, содержащих то, что было сопоставлено. Эта функция позволяет избежать повторного анализа одного и того же символа. Способ PPParser»matchesIn: выполняет аналогичную работу, но возвращает коллекцию со всеми возможными проанализированными элементами: например, оценка

идентификатораmatchIn: 'foo 123 bar12' возвращает коллекцию из 6 элементов.

Аналогичным образом, чтобы найти все совпадающие диапазоны (индекс первого символа и индекс последнего символа) в данном вводе, можно использовать либо PPParser»matchingSkipRangesIn: , либо PPParser»matchingRangesIn: , как показано в приведенном ниже сценарии:

Код \(\PageIndex{9}\) (Pharo): Поиск всех совпадающих диапазонов во входных данных

 идентификатор соответствияSkipRangesIn: 'foo 123 bar12'.
    → упорядоченная коллекция ((от 1 до: 3) (от 9 до: 13))
идентификатор соответствияRangesIn: 'foo 123 bar12'.
    → упорядоченная коллекция ((от 1 до: 3) (от 2 до: 3) (от 3 до: 3) (от 9 до: 13) (от 10 до: 13) (от 11 до: 13))
 

Различные виды синтаксических анализаторов

PetitParser предоставляет большой набор готовых синтаксических анализаторов, которые можно составить для использования и преобразования произвольно сложных языков. Терминальные парсеры самые простые. Мы уже видели некоторые из них, еще несколько определены в таблице протокола \(\PageIndex{1}\).

Таблица \(\PageIndex{1}\): PetitParser предварительно определяет множество терминальных синтаксических анализаторов.

Анализаторы терминалов	Описание
$a asParser	Разбирает символ $a.
‘abc’ asParser	Разбирает строку ‘abc’.
#любой asParser	Разбирает любой символ.
#digit asParser	Разбирает одну цифру (0. .9).
#letter asParser	Разбирает одну букву (a..z и A..Z).
#word asParser	Разбирает цифру или букву.
#blank asParser	Разбирает пробел или табуляцию.
#newline asParser	Разбирает символы возврата каретки или перевода строки.
#space asParser	Разбирает любой символ пробела, включая новую строку.
# вкладка asParser	Анализирует символ табуляции.
#нижний регистр asParser	Разбирает символ нижнего регистра.
#uppercase asParser	Разбирает символ верхнего регистра.
ноль asParser	Ничего не анализирует.

Сторона класса PPPredicateObjectParser предоставляет множество других фабричных методов, которые можно использовать для создания более сложных анализаторов терминала. Чтобы их использовать, отправьте сообщение PPParser»asParser символу, содержащему имя фабричного метода (например, #punctuation asParser ).

Следующий набор синтаксических анализаторов используется для объединения других синтаксических анализаторов и определяется в таблице протокола \(\PageIndex{2}\).

Таблица \(\PageIndex{2}\): PetitParser предварительно определяет множество комбинаторов парсеров.

Комбинация парсеров	Описание
стр. 1, стр.2	Разбирает p1, за которым следует p2 (последовательность).
стр.1 / стр.2	Разбирает p1, если это не работает, разбирает p2.
р-звезда	Разбирает ноль или более p.
р плюс	Разбирает один или несколько p.
р опционально	Разбирает p, если это возможно.
р и	Разбирает p, но не использует его ввод.
р отрицать	Разбирает p и завершается успешно, если p терпит неудачу.
р не	Разбирает p и завершается успешно, если p не удается, но не потребляет входные данные.
конец	Разбирает p и завершается успешно только в конце ввода.
п раз: п	Разбирает p ровно n раз.
p мин.: n макс.: m	Разбирает p не менее n раз до m раз
р starLazy: q	Как звезда, но прекращает потреблять, когда q завершается успешно

В качестве простого примера комбинации синтаксических анализаторов следующее определение идентификатор2 синтаксический анализатор эквивалентен нашему предыдущему определению идентификатора :

Код \(\PageIndex{10}\) (Pharo): Другой способ выражения идентификатора синтаксического анализатора

 идентификатор2 := #letter asParser , (#буква в качестве парсера / #цифра в качестве парсера) звездочка. 
 

Рисунок \(\PageIndex{2}\): Представление синтаксической диаграммы для синтаксического анализатора идентификатора2, определенного в коде \(\PageIndex{10}\).

Действие синтаксического анализатора

Чтобы определить действие или преобразование синтаксического анализатора, мы можем использовать одно из сообщений PPParser»==> , PPParser»flatten , PPParser»token и PPParser»trim , определенные в таблице протокола \(\PageIndex{3}\).

Таблица \(\PageIndex{3}\): PetitParser заранее определяет множество парсеров действий.

Анализаторы действий	Описание
р плоский	Создает строку из результата p.
токен p	Аналогичен сглаживанию , но возвращает PPToken с подробностями.
р отделка	Обрезает пробелы до и после стр.
p отделка: trimParser	Обрезает все, что trimParser может разобрать (например, комментарии).
р ==> блок	Выполняет преобразование, указанное в аБлок .

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

Код \(\PageIndex{11}\) (Pharo): Использование flatten, чтобы результатом синтаксического анализа была строка

 |identifier|
идентификатор := (#буква asParser , (#буква asParser / #цифра asParser) звездочка).
разбор идентификатора: 'ajka0' → #($a #($j $k $a $0))
анализ сглаживания идентификатора: 'ajka0' → 'ajka0'
 

Сообщение PPParser»token аналогично flatten , но возвращает PPToken , который предоставляет гораздо больше контекстной информации, такой как коллекция, в которой находится токен, и его положение в коллекции.

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

Рисунок \(\PageIndex{3}\): Представление синтаксической диаграммы для синтаксического анализатора чисел, определенного в коде \(\PageIndex{14}\).

Код \(\PageIndex{12}\) (Pharo): Использование PPParser»trim для игнорирования пробелов

 |identifier|
идентификатор := (#letter asParser , #word asParser star) сгладить.
разбор идентификатора: 'ajka' → ожидается буква 0
Анализ обрезки идентификатора: 'ajka' → 'ajka'
 

Отправка обрезки сообщения эквивалентна вызову PPParser»trim: с #space asParser в качестве параметра. Это означает, что trim: может быть полезен для игнорирования других входных данных, комментариев исходного кода, например:

Код \(\PageIndex{13}\) (Pharo): Использование PPParser»trim: для игнорирования комментариев

 | идентификатор комментария игнорируемая строка |
идентификатор := (#letter asParser , #word asParser star) сгладить. 
комментарий := '//' asParser, #newline asParser отрицает звездочку.
игнорируемый := комментарий / #space asParser.
строка := идентификатор обрезка: игнорируется.
разбор строки: '// Это комментарий
oneIdentifier // другой комментарий' → 'oneIdentifier'
 

Сообщение PPParser»==> позволяет вам указать блок, который будет выполняться, когда синтаксический анализатор соответствует вводу. В следующем разделе представлены несколько примеров. Вот простой способ получить число из его строкового представления.

Код \(\PageIndex{14}\) (Pharo): Разбор целых чисел

 number := #digit asParser plus flatten ==> [ :str | строка как число].
разбор числа: '123' → 123
 

В таблице \(\PageIndex{3}\) показаны основные элементы для построения синтаксических анализаторов. Есть еще несколько хорошо задокументированных и проверенных фабричных методов в протоколах операторов ППпарсер . Если вы хотите узнать больше об этих фабричных методах, просмотрите эти протоколы. Интересным является SeparateBy: , который отвечает новому синтаксическому анализатору, который анализирует ввод один или несколько раз с разделением, указанным другим синтаксическим анализатором.

Написание более сложной грамматики

Теперь мы напишем более сложную грамматику для вычисления простых арифметических выражений. С грамматикой для числа (фактически целого числа), определенной выше, следующим шагом будет определение продукции для сложения и умножения в порядке старшинства. Обратите внимание, что мы создаем экземпляры продукции как PPDelegateParser заранее, потому что они рекурсивно ссылаются друг на друга. Затем метод #setParser: разрешает эту рекурсию. Следующий сценарий определяет три синтаксических анализатора для сложения, умножения и скобок (см. рисунок \(\PageIndex{4}\) для соответствующей синтаксической диаграммы):

Код \(\PageIndex{15}\) (Pharo): Анализ арифметические выражения

 term := PPDelegateParser new. 
prod := PPDelegateParser новый.
prim := PPDelegateParser новый.
term setParser: (prod , $+ asParser trim , term ==> [ :nodes | узлы первые + узлы последние ])
            / изд.
prod setParser: (prim , $* asParser trim , prod ==> [ :nodes | узлы первые * узлы последние ])
            / прим.
prim setParser: ($( asParser trim , term , $) asParser trim ==> [ :nodes | nodes second ])
            / число.
 

Термин «парсер» определяется как (1) произведение, за которым следует «+», за которым следует другой термин, или (2) произведение. В случае (1) блок действий просит синтаксический анализатор вычислить арифметическое сложение значений первого узла (продукта) и последнего узла (терма). Синтаксический анализатор prod аналогичен термину парсер. Парсер prim интересен тем, что он принимает левые и правые скобки до и после терма и имеет блок действий, который их просто игнорирует.

Чтобы понять приоритет продукции, см. рисунок \(\PageIndex{5}\). Корень дерева на этом рисунке ( термин ), это продукция, которая пробуется в первую очередь. Терм представляет собой + или prod . Термин производства стоит первым, потому что + как самый низкий приоритет в математике.

Чтобы убедиться, что наш синтаксический анализатор потребляет все входные данные, мы заключаем его с парсером end в start production:

 start := term end.
 

Вот и все, теперь мы можем протестировать наш парсер:

Код \(\PageIndex{16}\) (Pharo): Пробуем наш оценщик арифметических выражений

 начать синтаксический анализ: '1 + 2 * 3'. → 7
начать синтаксический анализ: '(1 + 2) * 3'. → 9
 

Рисунок \(\PageIndex{4}\): Представление синтаксической диаграммы для парсеров term , prod и prim , определенных в коде \(\PageIndex{15}\). Рисунок \(\PageIndex{5}\): Объясняет, как понять приоритет продукции. Выражение — это терм, который является либо суммой, либо произведением. Сначала необходимо распознавать суммы, так как они имеют самый низкий приоритет.