Почему повторяющиеся строки, такие как [wcw | w - строка из a и b's] не могут быть обозначены регулярными выражениями? pls. дайте мне подробный ответ, как новый для лексического анализа. Благодаря ...Регулярные выражения Лексический анализ
Регулярные выражения в их первоначальном виде описывают обычные языки/грамматики. Они не могут содержать вложенные структуры, поскольку эти языки могут быть описаны простым конечным автоматом. Упрощенный, вы можете представить, что, как если бы каждое слово языка строго возрастало слева направо (или справа налево), где повторяющиеся структуры должны быть явно определены и статичны.
Это означает, что никакая информация из предыдущих состояний не может переноситься на более поздние состояния (несколько символов на входе). Поэтому, если у вас есть свой символ w, вы не можете указать, что вход должен иметь точно такую же строку w позже в последовательности. Точно так же вы не можете гарантировать, что каждая открывающая паратеха нуждается в ближайшем паране (так что сами регулярные выражения даже не являются обычным языком и поэтому не могут быть описаны регулярными выражениями :-)).
В теоретическом информатике мы работали с очень ограниченным набором операторов регулярных выражений, в основном состоящих только из последовательности, альтернативы (|) и повторения (*), все остальное можно описать с помощью этих операций.
Однако обычно двигатели регулярных выражений позволяют группировать определенные подматрицы в совпадения, которые затем можно ссылаться или извлекать позже. Некоторые движки даже позволяют использовать такую обратную ссылку в самой строке выражения поиска, тем самым позволяя выражению описывать больше, чем просто обычный язык. Если я правильно помню, такое использование обратных ссылок может даже дать языки, которые не являются контекстно-свободными.
Дополнительные указатели:
Вправо. Приведенный выше пример wcw не может быть выполнен с использованием контекстно-свободной грамматики, насколько я могу видеть (конечно, нет, если это wcwcw), но это легко проверить на Perl. –
Это может быть, вы просто не можете гарантировать, что это же строки «а» с и «Ъ» s, потому что нет никакого способа, чтобы сохранить информацию, полученную при прохождении первой половины для использования при обходе второго.
Имейте в виду, что синтаксический анализ является основным предметом одной из самых сложных курсов я взял в аспирантуре (Составители I). Уже есть довольно хороший ответ, но у вас может не быть фона, чтобы использовать его. –
Ну, это было нелегко. Но по крайней мере иногда это было весело. Хотя здесь он включал оптимизацию, а также несколько алгоритмов без синтаксического анализа. Любые идеи, как сделать этот пост более понятным для кого-то без особого фона? -.- – Joey