Может ли алгоритм маневрового двора анализировать регулярные выражения POSIX?

Question

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

Возможно, более сложная версия вопроса такова: к какому хорошему формальному утверждению класса задач можно применить алгоритм маневрового двора?

Пояснение: Этот вопрос о том, можете ли вы анализировать синтаксис POSIX re в абстрактное синтаксическое дерево, используя основные принципы алгоритма шунтирования, а не можете ли вы использовать регулярные выражения для реализации алгоритма шунтирования.Извините, я не был достаточно ясно, чтобы заявить, что для начала!

Answer 1

Я вполне уверен, что может. Если вы посмотрите на пакет регулярных выражений Генри Спенсера:

regexp.shar.Z

, который был основой для регулярных выражений Perl, вы заметите, что он описывает программу как "обычную железную дорогу".

Answer 2

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

^[^a-z][asd-]

^ имеет два разных значения, как и -. Я думаю, что выбрал бы парсер рекурсивного спуска.

Answer 3

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

Answer 4

Я скажу, что ответ на ваш вопрос «нет, вы не можете реализовать алгоритм маневрового двора с помощью регулярного выражения».Это по той же причине, по которой вы не можете анализировать произвольный HTML с помощью регулярных выражений.Что сводится к следующему:

Регулярные выражения не имеют стека.Поскольку алгоритм шунтирующего двора опирается на стек (для извлечения и извлечения операндов при преобразовании из инфикса в RPN), то регулярные выражения не обладают вычислительной «мощью» для выполнения этой задачи.

Это затушевывает многиедетали, но «регулярное выражение» является одним из способов определения регулярного языка.Когда вы «используете» регулярное выражение, вы просите компьютер сказать: «Посмотрите на текст и скажите, есть ли какая-либо из этих строк на моем языке. Язык, который я определил с помощью регулярного выражения».Я укажу на этот самый превосходный ответ, который вы и все, кто читает это, должны набрать для получения дополнительной информации по обычным языкам.

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

Если вы плохо знакомы с теорией автоматов и классами сложности, то эти статьи в Википедии, вероятно, не так уж полезны, если не объяснить их с нуля.

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