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

Question

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

Проблема здесь в том, что автор объясняет, что, учитывая строку символов, вы сначала конвертируете ее в постфикс. Он упоминает, что в режиме реального времени было бы лучше нарисовать NFA при разборе R.E, но не дал такого метода для этого .....

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

PS: - Я на самом деле не уверен, какие другие теги должны быть размещены в этом .... Кроме того, это не домашнее задание

Answer 1

Вот комбинированный парсер, компоновщик NFA и интерпретатор NFA на одной странице Python. Надеюсь, я не испорчу удовольствие от выяснения этого для себя - вы можете подождать и продолжить взлом, прежде чем перейти по ссылке.

Это похоже на предложение Дейнста, но «назад». Как говорит deinst, вы можете заставить анализатор создавать NFA для каждого подвыражения регулярного выражения, а затем подключать их по ходу работы. Например, для (a|b)*c сначала нужно проанализировать (a|b)*, чтобы получить NFA # 1, затем проанализировать c, чтобы получить NFA # 2, а затем завершить конечное состояние NFA # 1, изменив его на начальное состояние # 2. И так далее рекурсивно. Это обычный ответ.

Мой код вместо этого сначала создает тривиальный NFA с просто принимающим состоянием и ничего более. Затем он анализирует c, расширяя NFA: теперь у нас есть NFA, который проверяет на c, а затем принимает. Затем он рекурсивно анализирует (a|b)*, продолжая расширять NFA. Контракт синтаксического анализатора, заданный строкой re и NFA k, состоит в том, чтобы проанализировать строку для получения результирующего NFA, который заканчивается в начале k, когда re совпадает. Этот подход избавляет от необходимости разбивать биты частичных NFA, чтобы соединить их вместе.

Answer 2

Регулярное выражение в скобках можно рассматривать как отдельный NFA. Все, что вас волнует, - это то, что у него есть состояние ввода и состояние принятия. Вы просто рекурсивно разбираете вещи в скобках в NFA и вставляете их входные данные и принимаете состояния в соответствующие места в NFA, которые вы создаете. Сложная часть синтаксического анализа выражения инфикса заключается в правильном определении приоритетов операторов, что потребует столько же усилий, сколько и преобразование в постфикс.

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