Может кто-нибудь объяснить мне, почему вы не можете использовать регулярное выражение для описания рекурсивной структуры.Почему regex не может использоваться для описания рекурсивной структуры?
Например
- А = * А? Б
Может кто-нибудь объяснить мне, почему вы не можете использовать регулярное выражение для описания рекурсивной структуры.Почему regex не может использоваться для описания рекурсивной структуры?
Например
Поскольку регулярное выражение (в смысле регулярных языков, по крайней мере) соответствует конечному автомату. Вам понадобится бесконечное количество состояний для отслеживания произвольных уровней вложенности.
«regex» больше не означает «конечный автомат», если вы не хотите вдаваться в длинную и бесплодную терминологию flamewar с половиной программирования. Даже обратное отслеживание нарушает этот изоморфизм, не говоря уже о других расширениях. – delnan
@ delnan: Я понимаю, что;), но если не квалифицировано дальше, я предполагаю, что «регулярное выражение» означает «обычный язык» ... –
Это предположение, с которым я столкнулся. По моему опыту, большинство использует «регулярное выражение» для обозначения «независимо от моего языка (ов)», который в большинстве случаев, по крайней мере, отступает. – delnan
Хотя регулярные выражения не могут выразить рекурсию формальным определением, для некоторых языков, таких как Perl и Ruby, существует «regex» implementations that support recursion.
Также для python существует alternative regex implementation поддержка рекурсии, которая не входит в стандартную библиотеку lib.
Но опять же, regular languages не имеют рекурсивных структур, поэтому формально регулярные выражения не могут выразить рекурсивные структуры по определению.
Это следствие формального определения обычного языка. См. Http://en.wikipedia.org/wiki/Regular_language –
@ p.s.w.g Осторожно! Не все, что работает под ярлыком «regex», эквивалентно обычным языкам, многие из них являются более мощными. – delnan
@delnann, в то время как вопрос помечен как «regex» и не имеет специфического для языка вопроса, утверждение 'p.s.w.g' применимо (и в любом случае совершенно точно). –