Почему онлайн-парсеры останавливаются на регулярных выражениях?
-
03-07-2019 - |
Вопрос
Я долго задавался вопросом, почему, скажем, нет никаких анализаторов, скажем, БНФ, которые ведут себя как регулярные выражения в различных библиотеках.
Конечно, есть такие вещи, как АНТЛР, Якк и многие другие, которые генерировать код который, в свою очередь, может анализировать КФГ, но, похоже, не существует библиотеки, которая могла бы сделать это без промежуточного шага.
Мне интересно написать Парсер Packrat, вдобавок ко всем этим странностям с вложенными скобками, связанными с регулярными выражениями (и, возможно, даже в большей степени, ради развлечения), но почему-то у меня такое ощущение, что я просто вступаю в еще одну проблему остановки - например, в класс болот.
Есть ли технические/теоретические ограничения для этих парсеров или я просто что-то упускаю?
Решение
Я думаю, это скорее культурная вещь.Использование контекстно-свободных грамматик в основном ограничивается компиляторами, которые обычно имеют код, связанный с каждым продукционным правилом.В некоторых языках проще вывести код, чем имитировать обратные вызовы.В других вы увидите библиотеки парсеров:Например, комбинаторы парсеров в Haskell.С другой стороны, регулярные выражения широко используются в таких инструментах, как grep, где неудобно запускать компилятор C каждый раз, когда пользователь вводит новое регулярное выражение.
Другие советы
Повышение.Дух похоже на то, что вам нужно.
Если вы хотите сделать свой собственный, я использовал БНФК для моего последнего проекта компилятора, и он предоставляет грамматика, используемая в ее собственной реализации.Это может быть хорошей отправной точкой...
Никаких технических/теоретических ограничений, скрывающихся в тени, не существует.Я не могу сказать, почему они не пользуются большей популярностью, но я знаю по крайней мере одну библиотеку, которая обеспечивает тот вид «онлайнового» анализа, который вам нужен.
SimpleParse — это библиотека Python, которая позволяет вам просто вставить свою запутанную EBNF-грамматику в вашу программу и использовать ее для немедленного анализа, без каких-либо промежуточных шагов.Я использовал его в нескольких проектах, где мне нужен был собственный язык ввода, но на самом деле я не хотел связываться с каким-либо формальным процессом сборки.
Вот небольшой пример, который пришел мне в голову:
decl = r"""
root := expr
expr := term, ("|", term)*
term := factor+
factor := ("(" expr ")") / [a-z]
"""
parser = Parser(decl)
success, trees, next = parser.parse("(a(b|def)|c)def")
Библиотеки комбинаторов парсеров для Haskell и Scala также позволяют выразить грамматику вашего парсера в том же фрагменте кода, который его использует.Однако вы не можете, скажем, позволить пользователю вводить грамматику во время выполнения (что в любом случае может представлять интерес только для людей, создающих программное обеспечение, помогающее людям понимать грамматику).
Пипарсинг (http://pyparsing.wikispaces.com) имеет встроенную поддержку синтаксического анализа Packrat и является чистым Python, поэтому вы можете увидеть фактическую реализацию.
Потому что полноценные контекстно-свободные грамматики достаточно запутаны, поскольку в них отсутствует какой-то загадочно-плотный и непонятный синтаксис, который делал бы их еще более запутанными?
Трудно понять, о чем вы спрашиваете.Вы пытаетесь создать что-то вроде регулярного выражения, но для контекстно-свободных грамматик?Например, используя $var =~ /expr = expr + expr/
(в Perl) и наличие этого совпадения "1 + 1"
или "1 + 1 + 1"
или "1 + 1 + 1 + 1 + 1 + ..."
?Я думаю, что одним из ограничений этого будет синтаксис:Наличие более трех правил сделает ваше «грамматическое выражение» еще более нечитаемым, чем любое современное регулярное выражение.
Побочные эффекты — это единственное, что я вижу, что вас доставит.Большинство генераторов синтаксических анализаторов включают встроенный код для обработки, и для того, чтобы это работало, вам понадобится оценка.
Одним из способов решения этой проблемы было бы назвать действия, а затем создать функцию «действия», которая принимает имя действия, которое нужно выполнить, и аргументы, с которыми оно должно быть выполнено.
Теоретически это можно сделать с помощью Повышение духа на C++, но в основном он создан для статических грамматик.Я думаю, что причина, по которой это не распространено, заключается в том, что CFG не так часто используются, как регулярные выражения.Мне никогда не приходилось использовать грамматику, за исключением конструкции компилятора, но регулярные выражения я использовал много раз.CFG, как правило, намного сложнее регулярных выражений, поэтому имеет смысл генерировать код статически с помощью такого инструмента, как YACC или ANTLR.
tcllib есть что-то подобное, если ты можешь с этим смириться Разбор грамматик выражений а также TCL.Если вам нравится Perl, у CPAN есть Разбор::Эрли. Здесьэто чистый вариант Perl, который выглядит многообещающе. ПЛИ кажется правдоподобным решением для Python