Нужно ли языку регулярных выражений автомат для его анализа?

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

Я предполагаю, что это должен быть автомат с принудительной передачей, потому что наличие скобок означает необходимость подсчета, а DFA / NFA не может выполнить произвольный подсчет. Это предположение верно? Например, для выражения a (bc *) d потребуется PDA, чтобы подвыражение в скобках обрабатывалось правильно.

formal-languages parsers regular-expressions pushdown-automata Фил Райт
источник

Что вы имеете в виду именно под "разбором"? Вы имеете в виду проверку, является ли ввод действительно регулярным выражением, или вы имеете в виду более сложную вещь, например, машину, выводящую описание соответствующего NFA? (если вы не уверены, является ли ввод действительно регулярным выражением, и вам нужно проверить его, тогда вы должны быть в состоянии проверить правильность круглых скобок и это обычно означает использование стека.)

Kaveh

Для практического ответа, вы можете посмотреть на источник Plan 9 Grep для grep.y .

Брюс Эдигер

Ответы:

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

Одна возможность - использовать гомоморфизм ( против которого закрыт) избавиться от всех символов, кроме скобок, что оставляет вас с языком Дика, который, как известно, нерегулярен. Если сомневаетесь, используйте лемму прокачки на . $\mathrm{REG}$ $(^p)^p$

Тем не менее, вы, вероятно, не хотите кодировать КПК вручную. Подумайте об использовании генератора синтаксического анализатора, такого как ANTLR или byacc . С другой стороны, если вы хотите исследовать синтаксический анализ языков, программируя синтаксические анализаторы самостоятельно, вам следует продолжить работу с другими базовыми алгоритмами синтаксического анализа, такими как CYK , Earley , рекурсивное снижение и LR .

Рафаэль
источник

Благодарю. Написание кода для этих задач создает лучшее понимание и не должно быть таким же эффективным, как у существующих утилит, таких как lex, yacc, bison и т. д.

Фил Райт,

@PhilWright: Понятно! Я редактировал дальнейшие указатели для этого случая.

Рафаэль

Я бы предпочел для этого кодер парсера рекурсивного спуска.

Дейв Кларк

Если для этого нужно написать парсер вручную, то можно использовать рекурсивное снижение (после факторинга и массирования), парсер LCC для C < sites.google.com/site/lccretargetablecompiler > имеет интересный подход для обработки большого количества операторов. Но, пожалуй, самым простым для создания вручную является разбор приоритетов.

vonbrand

Я предлагаю вам прочитать хороший ответ Юкки на вопрос " Сопоставление регулярных выражений с использованием регулярных выражений " также на cstheory. Выдержка:

Например, мы можем изменить стандартную запись следующим образом, чтобы получить «сжатые» регулярные выражения :

Вы можете удалить любой префикс, который состоит из последовательности ('

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

То есть ((a|b)*c)de(f|g)может быть выражено в «сжатой» записи с использованием, например, любой из следующих форм: a|b)*c)de(f|gили ((a|b)*c)de(f|gили (a|b)*c)de(f|g).

[...]

«Сжатая» запись (регулярного выражения) является регулярным языком.

Это всего лишь ссылка на интересный (по моему мнению) «другой взгляд» на язык регулярных выражений; как подчеркнуто в комментариях ниже, это не полезно для построения синтаксического дерева. Если вы хотите написать код вашего парсера, я предложу вам эту простую статью о проекте кода « Writing-own-регулярное-выражение-парсер ».

Вор
источник

Юкка по существу снимает требование, чтобы круглые скобки были сбалансированы. Я не знаю ни одного случая, когда это на самом деле делается, но стоит отметить, что, изменяя семантику, вы можете «упростить» синтаксис.

Рафаэль

Вы (и Юкка) не разбираете регулярные выражения, а только узнаете их. «Да, это (сжатое) регулярное выражение».

Жиль "ТАК - перестань быть злым"