Комментарии 39
Огромное спасибо за статью, по рекурсивным шаблонам например вообще очень мало информации, я собирал по крупицам, чтобы построить регуляркой разбор плейсходеров для бд и html для парсинга — отлично работает, но понимал я их на уровне магии, а после этой статьи все более-менее упорядочилоась.
В иллюстрации вложенностей классов грамматик по Хомскому есть одна мелкая неточность — пустая строка является валидной контекстно-свободной грамматикой, однако не входит ни в одну из других категорий. Хотя это, конечно, вопрос не к переводчику, а к автору.
Регулярки сильны конечно, но все же для большинства задаx связынных с парсингом HTML phpQuery или какого-нибудь Simple HTML DOM хватит выше крыши, и производитльность выше.
Для подавляющего большинства задач, связанных с каждодневной человеческой деятельностью хватит четырех арифметических действий, так нет же — напридумывали дифференциалов, интегралов, комплескных чисел и прочих непонятностей.
Здесь тоже выполняеется «правило 80/20» — есть 20% задач (меньшинство), где можно и регулярки применить.
Здесь тоже выполняеется «правило 80/20» — есть 20% задач (меньшинство), где можно и регулярки применить.
напридумывали дифференциалов, интегралов
интегралы и дифференциалы IRL встречаются не реже сложения и вычитания, не говоря уж об умножении и делении
Я имел ввиду что для людей которые справшивают
В подавляющем большинстве случаев все же более правильное решение XML парсер, и правильно что советуют именно его, а не регулярки, т.к. это проще и быстрее, а если бы говорили «пиши регулярки» — ответ тоже был бы правильным но не рациональным. К регуляркам стоит прибегать только в случае если XML парсер не в силах решить проблему, либо это будет сложнее чем при использовании регулярок. Но в любом случае порядок должен быть такой.
как распарсить какие-то конкретные аспекты HTML
В подавляющем большинстве случаев все же более правильное решение XML парсер, и правильно что советуют именно его, а не регулярки, т.к. это проще и быстрее, а если бы говорили «пиши регулярки» — ответ тоже был бы правильным но не рациональным. К регуляркам стоит прибегать только в случае если XML парсер не в силах решить проблему, либо это будет сложнее чем при использовании регулярок. Но в любом случае порядок должен быть такой.
if($i_can_use_xmlParser){
//parse xml
}else{
//parse regex
}
Боюсь, что вы очень сильно лукавите, заявляя, что библиотеки, работающие с DOMDocument в php будут быстрее, чем регулярные выражения. Производительность и потребление памяти у этого интерфейса практически катастрофическая. В Simple HTML DOM дело обстоит получше, поскольку там сделан свой автомат для парсинга, но и его скорость для многих задач будет ниже, чем у регулярных выражений (если задача не подразумевает полного парсинга дерева документа, или фрагмента документа).
Боюсь вы сильно ошибаетесь на счет Simple HTML DOM вот тесты человек делал habrahabr.ru/post/114323/. На счет того что регулярки медленне много где читал, хотя соглашусь что вырезать содержимое тега title регулярками по идее быстрее получится. Но удобнее это сделать все-же XML парсером
Самый лучший ответ на SO на эту тему, если кто не видел) stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags/1732454#1732454
Удел регексов — быстро высечь какой-нибудь там кусок текста по паре признаков. Хоть из html, хоть из чего.
Для полноценного парсинга формально описанных языков есть всякие парсер-комбинаторы и парсер-генераторы.
Для полноценного парсинга формально описанных языков есть всякие парсер-комбинаторы и парсер-генераторы.
НЛО прилетело и опубликовало эту надпись здесь
Не хочется придираться к хорошей статье, но «0005» — это не натуральное число.
Согласен. N -> 0N не правильно.
А как правильно?
Круто. Про DEFINE не знал. Оказывается, для полноценной валидации email существует более читаемый регэксп, чем этот:
(соус: StackOverflow: Using a regular expression to validate an email address)
(?:(?:\r\n)?[ \t])*(?:(?:(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*|(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)*\<(?:(?:\r\n)?[ \t])*(?:@(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*(?:,@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*)*:(?:(?:\r\n)?[ \t])*)?(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*\>(?:(?:\r\n)?[ \t])*)|(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)*:(?:(?:\r\n)?[ \t])*(?:(?:(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*|(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)*\<(?:(?:\r\n)?[ \t])*(?:@(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*(?:,@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*)*:(?:(?:\r\n)?[ \t])*)?(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*\>(?:(?:\r\n)?[ \t])*)(?:,\s*(?:(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*|(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)*\<(?:(?:\r\n)?[ \t])*(?:@(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*(?:,@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*)*:(?:(?:\r\n)?[ \t])*)?(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*\>(?:(
?:\r\n)?[ \t])*))*)?;\s*)
(соус: StackOverflow: Using a regular expression to validate an email address)
Пример бы какой-нибудь живой.
Так можно таки вытащить из html нужный div со всеми вложенными?
Так можно таки вытащить из html нужный div со всеми вложенными?
так это и обычной регуляркой можно, просто вставить кусок спереди побольше для уникальности :)
я так объявления на авто.ру отслеживал когда машину покупал, через сервис, который делает рсс из любого сайта по регулярке
я так объявления на авто.ру отслеживал когда машину покупал, через сервис, который делает рсс из любого сайта по регулярке
то есть одной регуляркой можно найти определённый тег, допустим и найти закрывающий к нему, с учётом того, что внутри может быть любое количество вложенных дивов?
Надо писать не просто тег, а кусок html, однозначно определяющий фрагмент. И в конце так же. Метод тупой, но прекрасно подходит для парсинга сайтов.
Кусок, однозначно определяющий конец —
</div>на реальном сайте если такой див один, то после него есть кусок, однозначно его идентифицирующий
если несколько, то сначала отделяем блок с этими дивами как в первом случае, а потом разбиваем: если вложенности нет, то концом будет , если есть, то например .
если несколько, то сначала отделяем блок с этими дивами как в первом случае, а потом разбиваем: если вложенности нет, то концом будет , если есть, то например .
НЛО прилетело и опубликовало эту надпись здесь
А поделитесь ссылкой на этот сервис, пожалуйста. Мне раз нужен был такой функционал — ничего путного не нагуглил, пришлось долго мучить Yahoo Pipes.
Я использовал feed43.com
Пример бы какой-нибудь живой.
Так можно таки вытащить из html нужный div со всеми вложенными?
Можно. Например, вытаскиваем div с id=«1» + все вложенные:
(?sxi) (?(DEFINE) (?<balanced_expr> (?:(?&no_div_expr) (?&div_expr) )* (?&no_div_expr) ) (?<no_div_expr> (?:(?!<div[^>]*>)(?!</div>).)* ) (?<div_expr> <div[^>]*> (?&balanced_expr) </div> ) ) <div \s id="1">(?&balanced_expr)</div>
Давно хотел перевести эту статью, да всё руки не доходили—спасибо!
Совершенно замечательная статья, не хватает только списка литературы на тему матлогики для интересующихся.
Спасибо большое за статью, расширила мой кругозор.
В части теории формальных грамматик статья безграмотная. Такого понятия, как «регулярная грамматика» в иерархии Хомского вообще нет, это автор сам придумал. Есть определение грамматики типа 3. Это грамматика с правилами вида
Есть понятие «регулярный язык» — язык, который задается регулярным выражением. Есть также теорема Клини, которая говорит о том, что каждый регулярный язык можно также задать и конечным автоматом и, наоборот, каждый язык, заданный конечным автоматом, можно задать также и регулярным выражением. С другой стороны, есть связь между иерархией Хомского и иерархией вычислительных автоматов. Это соответствие было обнаружено и доказано задолго до того, как регулярные выражения стали использоваться как способ задания формального языка. С методической точки зрения намного проще и понятнее связать регулярные выражения с автоматами.
Для выражений с группированием и обратными ссылками вполне себе подходит модель автомата с магазинной памятью (стеком). Это мощный формализм. Различают детерминированные и недетеминированные автоматы с магазинной памятью. Не так сложно, как мне кажется, построить магазинный автомат для регулярного выражения с обратными ссылками. Автомат с магазинной памятью эквивалентен (в том смысле, что задает тот же язык) контекстно-свободной грамматике. Для контекстно-зависимых грамматик имеется соответствие с т.н. линейно-ограниченными автоматами. Такие автоматы и грамматики могут задавать сложные языки, например, язык
Вообще, задавать сложный язык регуляркой не хорошо с точки зрения возможности отладки и последующей поддержки. Язык РВ для таких вещей явно не предназначен, получаются монстрообразные выражения, которые трудно даже просто прочитать. Конечно, форматирование помогает, но и оно не всегда является панацеей. Мне кажется, человеческому уму больше подходят иерархические структуры, в этом, видимо, и состоит секрет популярности контекстно-свободных грамматик. Они сейчас используются совсем не в том смысле, который задавал им Хомский изначально (как методы порождения цепочек языка), а скорее как категориальные грамматики, в которых нетерминальные символы обозначают категории, а стрелочка в правиле грамматики — иерархическую связь между категориями.
A --> aB, A --> Ba и A --> a. Заметим, что правила с пустой правой частью здесь нет, это правило автор также придумал. Здесь главное, что порождение цепочек языка производится добавлением символа спереди или сзади. Вообще, необязательно даже, чтобы один символ добавлялся, можно сразу несколько, т.е. правила можно и такие сделать: A --> Bw, где w — цепочка из терминальных символов. Это правило легко преобразовать в эквивалентные (с точки зрения порождающей мощности) классического вида для типа 3.Есть понятие «регулярный язык» — язык, который задается регулярным выражением. Есть также теорема Клини, которая говорит о том, что каждый регулярный язык можно также задать и конечным автоматом и, наоборот, каждый язык, заданный конечным автоматом, можно задать также и регулярным выражением. С другой стороны, есть связь между иерархией Хомского и иерархией вычислительных автоматов. Это соответствие было обнаружено и доказано задолго до того, как регулярные выражения стали использоваться как способ задания формального языка. С методической точки зрения намного проще и понятнее связать регулярные выражения с автоматами.
Для выражений с группированием и обратными ссылками вполне себе подходит модель автомата с магазинной памятью (стеком). Это мощный формализм. Различают детерминированные и недетеминированные автоматы с магазинной памятью. Не так сложно, как мне кажется, построить магазинный автомат для регулярного выражения с обратными ссылками. Автомат с магазинной памятью эквивалентен (в том смысле, что задает тот же язык) контекстно-свободной грамматике. Для контекстно-зависимых грамматик имеется соответствие с т.н. линейно-ограниченными автоматами. Такие автоматы и грамматики могут задавать сложные языки, например, язык
L = {(a^n)^2}, т.е. все цепочки этого языка состоят из символов a, число которых равно квадрату чисел натурального ряда: a, aaaa, aaaaaaaaa, .... Попробуйте придумать регулярное выражение для этого языка, мне кажется, довольно трудно.Вообще, задавать сложный язык регуляркой не хорошо с точки зрения возможности отладки и последующей поддержки. Язык РВ для таких вещей явно не предназначен, получаются монстрообразные выражения, которые трудно даже просто прочитать. Конечно, форматирование помогает, но и оно не всегда является панацеей. Мне кажется, человеческому уму больше подходят иерархические структуры, в этом, видимо, и состоит секрет популярности контекстно-свободных грамматик. Они сейчас используются совсем не в том смысле, который задавал им Хомский изначально (как методы порождения цепочек языка), а скорее как категориальные грамматики, в которых нетерминальные символы обозначают категории, а стрелочка в правиле грамматики — иерархическую связь между категориями.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Истинное могущество регулярных выражений