Синтакси́ческий ана́лиз (или разбор, жарг. па́рсинг ← англ. parsing) в лингвистике и информатике — процесс сопоставления линейной последовательности лексем (слов, токенов) естественного или формального языка с его формальной грамматикой. Результатом обычно является дерево разбора (синтаксическое дерево). Обычно применяется совместно с лексическим анализом.
Синтаксический анализатор (жарг. па́рсер ← англ. parser) — это программа или часть программы, выполняющая синтаксический анализ.
В ходе синтаксического анализа исходный текст преобразуется в структуру данных, обычно — в дерево, которое отражает синтаксическую структуру входной последовательности и хорошо подходит для дальнейшей обработки.
Как правило, результатом синтаксического анализа является синтаксическое строение предложения, представленное либо в виде дерева зависимостей, либо в виде дерева составляющих, либо в виде некоторого сочетания первого и второго способов представления.
1 Область применения
2 Типы алгоритмов
3 Восстановление после ошибок
3.1 Восстановление в режиме паники
3.2 Восстановление на уровне фразы
3.3 Продукции ошибок
4 Средства разработки анализаторов
5 См. также
6 Примечания
7 Литература
8 Ссылки
Область применения[править | править код]
Всё что угодно, имеющее «синтаксис», поддается автоматическому анализу.
Структурированные данные — данные, языки их описания, оформления и т. д. Например, XML, HTML, CSS, JSON, ini-файлы, специализированные конфигурационные файлы и т. п.;
Построение индекса в поисковой системе;
SQL-запросы (DSL-язык);
Математические выражения;
Регулярные выражения (которые, в свою очередь, могут использоваться для автоматизации лексического анализа);
Формальные грамматики;
Лингвистика — естественные языки. Например, машинный перевод и другие генераторы текстов.
Извлечение данных веб-страниц — веб-скрейпинг, является частным случаем парсинга[1].
Типы алгоритмов[править | править код]
Нисходящий парсер (англ. top-down parser) — продукции грамматики раскрываются, начиная со стартового символа, до получения требуемой последовательности токенов.
Метод рекурсивного спуска
LL-анализатор
Восходящий парсер[en] (англ. bottom-up parser) — продукции восстанавливаются из правых частей, начиная с токенов и заканчивая стартовым символом.
LR-анализатор
GLR-парсер
Восстановление после ошибок[править | править код]
Простейший способ реагирования на некорректную входную цепочку лексем — завершить синтаксический анализ и вывести сообщение об ошибке. Однако часто оказывается полезным найти за одну попытку синтаксического анализа как можно больше ошибок. Именно так ведут себя трансляторы большинства распространённых языков программирования.
Таким образом перед обработчиком ошибок синтаксического анализатора стоят следующие задачи:
он должен обеспечивать быстрое восстановление после ошибки, чтобы продолжать поиск других ошибок;
он не должен существенно замедлять обработку корректной входной цепочки.
Ниже описаны наиболее известные стратегии восстановления после ошибок.
При обнаружении ошибки синтаксический анализатор пропускает входные лексемы по одной, пока не будет найдена одна из специально определённого множества синхронизирующих лексем. Обычно такими лексемами являются разделители, например: ;, ) или }. Набор синхронизирующих лексем должен определять разработчик анализируемого языка. При такой стратегии восстановления может оказаться, что значительное количество символов будут пропущены без проверки на наличие дополнительных ошибок. Данная стратегия восстановления наиболее проста в реализации.
Иногда при обнаружении ошибки синтаксический анализатор может выполнить локальную коррекцию входного потока так, чтобы это позволило ему продолжать работу. Например, перед точкой с запятой, отделяющей различные операторы в языке программирования, синтаксический анализатор может закрыть все ещё не закрытые круглые скобки. Это более сложный в проектировании и реализации способ, однако в некоторых ситуациях, он может работать значительно лучше восстановления в режиме паники. Естественно, данная стратегия бессильна, если настоящая ошибка произошла до точки обнаружения ошибки синтаксическим анализатором.
Знание наиболее распространённых ошибок позволяет расширить грамматику языка продукциями, порождающими ошибочные конструкции. При срабатывании таких продукций регистрируется ошибка, но синтаксический анализатор продолжает работать в обычном режиме.
Отдельные этапы разработки и построения трансляторов могут быть автоматизированы и выполнены компьютером.
Вот некоторые из наиболее известных средств разработки анализаторов[2]:
Bison — генератор парсеров
Coco/R — генератор сканера и парсера
GOLD — парсер
JavaCC — генератор парсеров для языка Java
Lemon Parser — генератор парсеров
Lex — генератор сканеров
Ragel — генератор встраиваемых парсеров
Spirit Parser Framework — генератор парсеров
SYNTAX
Syntax Definition Formalism[en]
UltraGram
VivaCore
Yacc — генератор парсеров
См. также сравнение генераторов парсеров[en].
Компилятор компиляторов
Синтаксически управляемая трансляция
Регулярные выражения
Примечания[править | править код]
↑ Тим Джонс М. Извлечение информация из Интернета при использовании языка Ruby. (неопр.) (22.05.2014).
↑ Ela Kumar. Natural Language Processing. — I. K. International Pvt Ltd, 2011. — P. 100. — ISBN 978-93-80578-77-4.
Литература[править | править код]
А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. Т. 1. Пер. с англ. В. Н. Агафонова под ред. В. М. Курочкина. М.: Мир, 1978. 614 с.
А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. Т. 2. Пер. с англ. А. Н. Бирюкова и В. А. Серебрякова под ред. В. М. Курочкина. М.: Мир, 1978. 487 с.
Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. — 2-е изд. — М.: Вильямс, 2008. — ISBN 978-5-8459-1349-4.
Робин Хантер. Основные концепции компиляторов = The Essence of Compilers. — М.: «Вильямс», 2002. — С. 256. — ISBN 5-8459-0360-2.
Ссылки[править | править код]
Трансляция кода (рус.)
Для улучшения этой статьи желательно: Проверить достоверность указанной в статье информации. Исправить статью согласно стилистическим правилам Википедии. Проставив сноски, внести более точные указания на источники. Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником. Нужен парсинг данных?Собираем открытые данные с любых веб-сайтов: цены, названия, артикулы, описания, свойства, категории, фото, отзывы, ссылки, тел.номера, e-mail и многое другое. Написать |
