Почему онлайн-парсеры останавливаются на регулярных выражениях?

StackOverflow https://stackoverflow.com/questions/803515

Вопрос

Я долго задавался вопросом, почему, скажем, нет никаких анализаторов, скажем, БНФ, которые ведут себя как регулярные выражения в различных библиотеках.

Конечно, есть такие вещи, как АНТЛР, Якк и многие другие, которые генерировать код который, в свою очередь, может анализировать КФГ, но, похоже, не существует библиотеки, которая могла бы сделать это без промежуточного шага.

Мне интересно написать Парсер 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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top