Regexp parse type-3 грамматика

Question

Regexp parse type-3 грамматика

Чтение иерархии Хомского... ... я знаю, что регулярное выражение не может анализировать грамматики типа 2 (контекстно-свободные грамматики), а также типы 1 и тип 0. Могут ли регулярные выражения анализировать / перехватывать ВСЕ грамматики типа 3 ( регулярные грамматики)?

2

regex parsing grammar context-free-grammar chomsky-hierarchy

Источник

user954485 13 фев '12 в 14:11

1 ответ

Решение

Другие вопросы по тегам regex parsing grammar context-free-grammar chomsky-hierarchy

user978917 13 фев '12 в 14:33 2012-02-13 14:33 · Accepted Answer · 2012-02-13 14:33

Да, при условии, что они поддерживают чередование, объединение и звезду Клини. Это относится к регулярным выражениям типа PCRE (Perl/Java/JavaScript/PHP/...): чередование осуществляется ((...)|(...))конкатенация (...)(...)и звезда Клини (...)*, (Есть несколько других деталей - в большинстве этих языков вам нужно использовать что-то вроде \A а также \z для обозначения "начала строки" и "конца строки", что в обычной грамматике считается само собой разумеющимся - но это идея.)

Но не все, что называется "регулярным выражением" в контексте программирования, обязательно содержит все вышеперечисленное; например, POSIX Basic Regular Expressions поддерживает только очень ограниченную форму чередования, где все "ветви" чередования состоят из одного символа (например, в то время как PCREs имеют оба (a|b|c) и особый случай-эквивалент [abc], POSIX BREs имеют только [abc], так что не могу выразить что-то вроде (ab|c)).