Как написать универсальный парсер

Учимся писать парсер сайта своими руками

Сегодня я приведу вам в пример, который возможно понадобиться начинающим парсерам и возможно вы найдете в нем ценную информацию. В комментариях очень хотелось бы увидеть возможные изменения для упрощения задачи, так что всегда рад услышать ваши мнения.
Передо мной стояла задача заполнить интернет магазин товарами в количестве свыше 50 тыс наименований. Оригиналы товаров лежали на сайтах поставщиков.
Особо заморачиваться с кодом и решением я не стал, поэтому сделал все максимально просто и быстро.
Прикрепленные файлы буду выкладывать на проекте моих друзей и партнеров 2file.ru Будьте уверены что все ссылки всегда будут действующими и вы всегда сможете скачать любой файл из данной инструкции. +размер файлов не ограничен, нет времени ожидания и нет рекламмы.

Первым делом я решил скачать полностью сайт себе чтобы в дальнейшем было проще работать с ним.
Для Windows нам потребуется программа wget (КАЧАЕМ)
Распаковываем например на диск С и для удобства переименовываем в wget.
Далее нажимаем пуск-выполнить-cmd и там вводим CD C:\wget\. Далее нам нужно запустить команду wget.exe -c -p -r -l0 -np -N -k -nv АДРЕС САЙТА 2>wget.log. Описание команд -c -p -r -l0 -np -N -k -nv можно подробно почитать ТУТ. Нажимаем enter и начинается скачивание. В папке wget появляется папка с названием сайта, куда сливается сайт. ВНИМАНИЕ, при больших объемах, сайт может скачиваться даже несколько дней.
. Прошло несколько дней…
Вот мы и дождались загрузки сайта на наш компьютер. В моем случаи в корне находились страницы с подробным описанием товаров, так что буду следовать отсюда.
Нам понадобится установленный на компьютере сервер apache+php. Для удобства и быстроты настройки можно использовать например xampp, который можно взять бесплатно на ЭТОМ сайте, где так-же приведен процесс инсталяции.

Ок, теперь у нас стоит апач, есть скачанный сайт. Далее для удобства я перенес все скачанные странички в папку xampp для дальнейшей работы с ними. Чтобы не усложнять код, я переименовал все страницы в порядковые номера чтобы получилось 1.html, 2.html… и так далее. Сделать это очень просто. Например через total commender в меню файлы-групповое переименование. Далее в папке с переименованными страницами я создал index.php файл. Теперь начнем разбираться в коде:

(.+?.) #is’, $html, $matches );
foreach ( $matches[1] as $value ) echo $value.’&ltbr>’;
?>

Первой строчкой я указываю на открытие 132.html, в котором будет осуществляться выборка данных.

Открыв любую скачанную страницу, мы видим что интересующая нас информация находится между тегами.
Один из моих примеров это

preg_match_all( ‘#(.+?.)#is’, $html, $matches );

Далее осуществляется вывод полученных данных на экран и спуск на строчку вниз br.

Для выдирания нескольких результатов из одной страницы, можно использовать код на подобии:

(.+?.) #is’, $html, $matches );
preg_match_all( ‘# (.+?.) #is’, $html, $matches1 );
preg_match_all( ‘# (.+?.) #is’, $html, $matches2 );

foreach ( $matches[1] as $value ) echo $value.’ ‘;
foreach ( $matches1[1] as $value ) echo $value.’ ‘;
foreach ( $matches2[1] as $value ) echo $value.’&ltbr>’;
?>

Должно получится что-то вроде (значение1, значение2, значение3 &ltbr>)

Теперь немного дополним наш код чтобы прогнать все наши скачанные страницы. Решил сделать с помощью цикла и получилось что-то вроде этого:

(.+?.) #is’, $html, $matches );
preg_match_all( ‘# (.+?.) #is’, $html, $matches1 );
preg_match_all( ‘# (.+?.) #is’, $html, $matches2 );

foreach ( $matches[1] as $value ) echo $value.’ ‘;
foreach ( $matches1[1] as $value ) echo $value.’ ‘;
foreach ( $matches2[1] as $value ) echo $value.’&ltbr>’;

Отлично, теперь мы видим что-то вроде этого:
значение#значение#значение
значение#значение#значение

Для удобства дальнейшей работы я использовал #. Теперь копируем все что получилось, загоняем в excel, нажимаем данные-текст по столбцам и ставим # в качестве разделителя столбцов. Отлично, мы получили таблицу с результатами нашего парсинга. УРА

Дальнейшая работа зависит от вашей фантазии и цели. Спасибо за внимания, надеюсь на инвайт.

Данная статья не подлежит комментированию, поскольку её автор ещё не является полноправным участником сообщества. Вы сможете связаться с автором только после того, как он получит приглашение от кого-либо из участников сообщества. До этого момента его username будет скрыт псевдонимом.

Источник статьи: http://habr.com/ru/sandbox/30536/

Написание парсера с нуля: так ли страшен черт?

В прошлом топике я рассказывал о том, как мы с другом решили ради развлечения написать свой встраиваемый язык программирования для платформы .NET. У первой версии был серьезный недостаток — парсер был реализован на F# с помощью сторонней библиотеки. Из-за этого требовалась куча зависимостей, парсер работал медленно, а поддержка его была крайне муторным занятием.

Очевидно, что парсер нужно было переписать на C#, но при мысли о написании парсера с нуля вдруг находилась дюжина других срочных дел. Таким образом таск перекидывался и откладывался практически полгода и казался непосильным, а в итоге был сделан за 4 дня. Под катом я расскажу об удобном способе, позволившим реализовать парсер достаточно сложной грамматики без использования сторонних библиотек и не тронуться умом, а также о том, как это позволило улучшить язык LENS.

Первый блин

Как было сказано выше, в качестве ядра парсера мы использовали библиотеку FParsec. Причины данного выбора скорее исторические, нежели объективные: понравился легковесный синтаксис, хотелось поупражняться в использовании F#, и автор библиотеки очень оперативно отвечал на несколько вопросов по email.

Главным недостатком этой библиотеки для нашего проекта оказались внешние зависимости:

• Примерно десятимегабайтный F# Runtime
• 450 кб сборок самого FParsec

Кроме того, сам компилятор разбился на 3 сборки: парсер, синтаксическое дерево и точку входа. Сборка парсера занимала внушительные 130 кб. Для встраиваемого языка это абсолютно неприлично.

Другой проблемой было отображение ошибок. Лаконичная запись грамматики на местном DSL при некорректно введенной программе выдавала нечитаемую ошибку c перечислением ожидаемых лексем:

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

Еще одним неприятным моментом была скорость работы. При «холодном старте» компиляция любого, даже самого простого скрипта занимала на моей машине примерно 350-380 миллисекунд. Судя по тому, что повторный запуск такого же скрипта занимал уже всего-то 5-10 миллисекунд, задержка была вызвана JIT-компиляцией.

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

Немного теории

Сферический парсер в вакууме представляет собой функцию, которая принимает исходный код, а возвращает некое промежуточное представление, по которому удобно будет сгенерировать код для используемой виртуальной машины или процессора. Чаще всего это представление имеет древовидную структуру и называется абстрактным синтаксическим деревом — АСД (в иностранной литературе — abstract syntactic tree, AST).

Древовидная структура особенно хороша тем, что ее обход в глубину отлично сочетается со стековой организацией, используемой во многих современных виртуальных машинах (например, JVM или .NET). Генерация кода в данной статье рассматриваться не будет, однако элементы синтаксического дерева, как результат работы парсера, будут время от времени упоминаться.

Итак, на входе мы имеем строку. Набор символов. Работать с ней в таком виде напрямую не слишком удобно — приходится учитывать пробелы, переносы строк и комментарии. Для упрощения себе жизни разработчики парсеров обычно разделяют разбор на несколько проходов, каждый из которых выполняет какую-то одну простую задачу и передает результат своей работы следующему:

1. Лексический анализатор: string -> IEnumerable
2. Синтаксический анализатор: IEnumerable -> IEnumerable
3. Семантический анализатор: IEnumerable -> ?

Поскольку семантический анализатор — штука сугубо индивидуальная, ее описание в данную статью не входит. Тем не менее, я поделюсь некоторыми полезными приемами для первых двух анализаторов.

Лексический анализатор

• Скорость работы
• Легкость расширения
• Простота реализации
• Отслеживание положения в исходном тексте

Алгоритм лексера прост: он сканирует строку слева направо, пытаясь сопоставить текущее положение в строке с каждой известной ему лексемой. При удачном сопоставлении лексер сдвигается по строке направо на столько символов, сколько заняла предыдущая лексема, и продолжает поиск по новой до конца строки. Пробелы, табуляции и переводы строки для большинства грамматик можно просто игнорировать.

Все лексемы изначально стоит поделить на 2 типа — статические и динамические. К первым относятся те лексемы, которые можно выразить обычной строкой — ключевые слова и операторы. Лексемы типа идентификаторов, чисел или строк проще описать регулярным выражением.

Статические лексемы, в свою очередь, есть резон поделить на операторы и ключевые слова. Ключевые слова сопоставляются только в том случае, если следующий за ними символ не является допустимым для идентификатора (или дальше — конец строки). В противном случае возникнут проблемы с идентификаторами, чье начало совпадает с ключевым словом: например, «information» -> keyword(in), keyword(for), identifier(mation) .

• Работает быстро
• Элементарное устройство, можно написать за полчаса
• Новые лексемы добавляются очень просто
• Способ подходит для множества грамматик

Недостатки:

• Танцы с бубном при разборе языка со значимыми пробелами
• Порядок объявления лексем важен: желательно сортировать по длине

Синтаксический анализатор

• Легкость расширения при изменении грамматики
• Возможность описывать подробные сообщения об ошибках
• Возможность заглядывать вперед на неограниченное количество позиций
• Автоматическое отслеживание положения в исходном коде
• Лаконичность, близость к исходной грамматике

Для того, чтобы упростить себе жизнь при написании парсера, следует оформить грамматику специальным образом. Никаких сложных конструкций! Все правила можно поделить на 3 типа:

• Описание — один конкретный узел:
  (var_expr = «var» identifier «=» expr)
• Повторение — один конкретный узел повторяется многократно, возможно с разделителем:
  main = < stmt ";" >
• Альтернатива — выбор из нескольких узлов
  (stmt = var_expr | print_expr | assign_expr | other)

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

Правило-перечисление — это цикл. Чтобы вернуть последовательность значений, в C# есть очень удобный функционал для создания генераторов с помощью yield return .

Правило-альтернатива по очереди вызывает правила-варианты с помощью специальной обертки, которая позволяет откатиться в исходное состояние. Правила просто вызываются по порядку, пока хотя бы одно из них не совпадет, связанные оператором coalesce ( ?? ).

Тут пытливый читатель спросит:
— Как это, просто вызываются по порядку? А как же опережающие проверки? Например, так:

Признаюсь, свой первый серьезный парсер я написал именно так. Однако это плохая идея!

Во-первых, заглянуть можно только на фиксированное число символов. Для всяких for или var , конечно, подойдет. Но, допустим, у нас есть такие правила в грамматике:

Если с id_assign еще все понятно, то оба других правила начинаются с нетерминала lvalue , под которым может скрываться километровое выражение. Очевидно, что никаких опережающих проверок тут не напасешься.

Другая проблема — смешение зон ответственности. Чтобы грамматика была расширяемой, правила должны быть как можно более независимы друг от друга. Данный подход требует, чтобы внешнее правило знало о составе внутренних, что увеличивает связность и осложняет поддержку при изменении грамматики.

Так зачем нам вообще опережающие проверки? Пусть каждое правило само знает о том, насколько далеко нужно заглянуть вперед, чтобы убедиться, что именно оно наиболее подходящее.

Рассмотрим на примере выше. Допустим, у нас есть текст: a.1 = 2 :

1. Первой вызывается альтернатива id_assign .
2. Идентификатор a успешно совпадает.
3. Дальше идет точка, а ожидается знак «равно». Однако с идентификатора могут начинаться и другие правила, поэтому ошибка не выбрасывается.
4. Правило assign откатывает состояние назад и пробует дальше.
5. Вызывается альтернатива member_assign .
6. Идентификатор и точка успешно совпадают. В грамматике нет других правил, которые начинаются с идентификатора и точки, поэтому дальнейшие ошибки не имеет смысл пытаться обработать откатыванием состояния.
7. Число 1 не является идентификатором, поэтому выкидывается ошибка.

Сначала напишем несколько полезных методов:

С их помощью реализация приведенной выше грамматики становится практически тривиальной:

Атрибут DebuggerStepThrough сильно помогает при отладке. Поскольку все вызовы вложенных правил так или иначе проходят через Attempt и Ensure, без этого атрибута они будут постоянно бросаться в глаза при Step Into и забивать стек вызовов.

Преимущества данного метода:

• Откат состояния — очень дешевая операция
• Легко управлять тем, до куда можно откатываться
• Легко отображать детальные сообщения об ошибках
• Не требуются никакие внешние библиотеки
• Небольшой объем генерируемого кода

Недостатки:

• Реализация парсера вручную занимает время
• Сложность написания и оптимальность работы зависят от качества грамматики
• Леворекурсивные грамматики следует разруливать самостоятельно

Операторы и приоритеты

Неоднократно я видел в описаниях грамматик примерно следующие правила, показывающие приоритет операций:

Теперь представим, что у нас есть еще булевы операторы, операторы сравнения, операторы сдвига, бинарные операторы, или какие-нибудь собственные. Сколько правил получается, и сколько всего придется поменять, если вдруг придется добавить новый оператор с приоритетом где-то в середине?

Вместо этого, можно убрать из грамматики вообще все описание приоритетов и закодить его декларативно.

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

Добавление поддержки унарных префиксных операторов оставляю в качестве тренировки для особо любопытных.

Что нам это дало?

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

Итого, сравнительная таблица результатов:

Скорее всего, возможно провести оптимизации и выжать из синтаксического анализатора больше производительности, но пока и этот результат вполне устраивает.

Избавившись от головной боли с изменениями в грамматике, мы смогли запилить в LENS несколько приятных вещей:

Цикл for

Используется как для обхода последовательностей, так и для диапазонов:

Композиция функций

С помощью оператора :> можно создавать новые функции, «нанизывая» существующие:

Частичное применение возможно с помощью анонимных функций:

Улучшения синтаксиса

Скобки вокруг единственного аргумента лямбды опциональны:

Скобки в управляющих конструкциях убраны:

Появился блок try/finally

Скобки при передаче индекса или поля в функцию опциональны:

Проект хоть и медленно, но развивается. Осталось еще много интересных задач. На следующую версию планируется:

• Объявление generic-типов и функций
• Возможность пометить функции или типы атрибутами
• Поддержку событий

Также можно скачать собранные демки под Windows.

Источник статьи: http://habr.com/ru/post/202622/