parser-comparison Goto Github PK

Для сравнения выбранных генераторов рассматривалась следующая неоднозначная грамматика:

S -> SSS | SS | a    # задается регулярным выражением 'a+'

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

P.S. Та же грамматика может быть описана так:

S -> aS | a

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

• antlr4 (Adaptive LL(*))
• lark (Earley)
• parglare (GLR)
• yacc (LALR(1))

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

Для реализации генераторов использовались языки программирования Python3 и Java (визуализация деревьев в ANTLR)

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

Результаты сравнения времен работы генераторов на неоднозначной грамматике S -> SSS | SS | a приведены в таблице:

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

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

При выборе генератора парсеров пользователю стоит ориентироваться на ситуацию и свои цели. Как видно из анализа двух рассмотренных выше таблиц, генератор Yacc не строит деревья разбора, соответственно, это отражается на времени работы программы -- Yacc отрабатывает быстрее других генераторов. ANTLR4 на строке длиной больше 20-ти символов уже работает слишком долго, однако строит подробные деревья разбора; Parglare ведет себя похожим образом, но умеет не слишком долго обрабатывать строки длиной уже до 90 символов. Если хочется и относительно небольшое время работы, и наглядное представление парсинга -- наверное, предпочтение следует отдать генератору Lark.

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

В частности, сравнительно небольшое время разбора неоднозначной грамматики Lark на Earley и CYK и Yacc показывали за счет четко зафиксированных на уровне языка правил, в какую ветку спускаться и какой случай как интерпретировать.