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

12

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

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

Фил Райт
источник
1
Что вы имеете в виду именно под "разбором"? Вы имеете в виду проверку, является ли ввод действительно регулярным выражением, или вы имеете в виду более сложную вещь, например, машину, выводящую описание соответствующего NFA? (если вы не уверены, является ли ввод действительно регулярным выражением, и вам нужно проверить его, тогда вы должны быть в состоянии проверить правильность круглых скобок и это обычно означает использование стека.)
Kaveh
Для практического ответа, вы можете посмотреть на источник Plan 9 Grep для grep.y .
Брюс Эдигер

Ответы:

8

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

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

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

Рафаэль
источник
Благодарю. Написание кода для этих задач создает лучшее понимание и не должно быть таким же эффективным, как у существующих утилит, таких как lex, yacc, bison и т. д.
Фил Райт,
@PhilWright: Понятно! Я редактировал дальнейшие указатели для этого случая.
Рафаэль
Я бы предпочел для этого кодер парсера рекурсивного спуска.
Дейв Кларк
Если для этого нужно написать парсер вручную, то можно использовать рекурсивное снижение (после факторинга и массирования), парсер LCC для C < sites.google.com/site/lccretargetablecompiler > имеет интересный подход для обработки большого количества операторов. Но, пожалуй, самым простым для создания вручную является разбор приоритетов.
vonbrand
3

Я предлагаю вам прочитать хороший ответ Юкки на вопрос " Сопоставление регулярных выражений с использованием регулярных выражений " также на 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-регулярное-выражение-парсер ».

Вор
источник
Юкка по существу снимает требование, чтобы круглые скобки были сбалансированы. Я не знаю ни одного случая, когда это на самом деле делается, но стоит отметить, что, изменяя семантику, вы можете «упростить» синтаксис.
Рафаэль
4
Вы (и Юкка) не разбираете регулярные выражения, а только узнаете их. «Да, это (сжатое) регулярное выражение».
Жиль "ТАК - перестань быть злым"