Грамматический разбор

Грамматический разбор

В информатике, синтакси́ческий ана́лиз (па́рсинг) — это процесс сопоставления линейной последовательности лексем (слов, токенов) языка с его формальной грамматикой. Результатом обычно является дерево разбора. Обычно применяется совместно с лексическим анализом. Синтаксический анализатор (парсер) — это программа или часть программы, выполняющая синтаксический анализ.

Пример разбора выражения в дерево

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

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

Содержание

Область применения

Все что угодно, имеющее «синтаксис», поддающийся автоматическому анализу.

Типы алгоритмов

  • Нисходящий парсер (англ. top-down parser) — продукции грамматики раскрываются, начиная со стартового символа, до получения требуемой последовательности токенов.
  • Восходящий парсер (англ. bottom-up parser) — продукции восстанавливаются из правых частей, начиная с токенов и кончая стартовым символом.

Восстановление после ошибок

Простейший способ реагирования на некорректную входную цепочку лексем — завершить синтаксический анализ и вывести сообщение об ошибке. Однако часто оказывается полезным найти за одну попытку синтаксического анализа как можно больше ошибок. Именно так ведут себя трансляторы большинства распространённых языков программирования.

Таким образом перед обработчиком ошибок синтаксического анализатора стоят следующие задачи:

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

Ниже описаны наиболее известные стратегии восстановления после ошибок.

Восстановление в режиме паники

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

Восстановление на уровне фразы

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

Продукции ошибок

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

См. также

ПО для разработки анализаторов

Литература

  • Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. — 2-е изд. — М.: Вильямс, 2008. — ISBN 978-5-8459-1349-4
  • Робин Хантер Основные концепции компиляторов = The Essence of Compilers. — М.: «Вильямс», 2002. — С. 256. — ISBN 5-8459-0360-2

Ссылки



Wikimedia Foundation. 2010.

Поможем сделать НИР

Полезное


Смотреть что такое "Грамматический разбор" в других словарях:

  • грамматический разбор — синтаксический (анализ, разбор) Словарь русских синонимов …   Словарь синонимов

  • грамматический разбор — Syn: синтаксический анализ, синтаксический разбор …   Тезаурус русской деловой лексики

  • РАЗБОР — РАЗБОР, разбора, муж. 1. только ед. Действие по гл. разобрать во всех знач., кроме 11, 12 и 13 разбирать. Разбор дела. Разбоор товаров. Детальный разбор содержания книги. Грамматический разбор. Разбор частей предложения. 2. Статья, посвященная… …   Толковый словарь Ушакова

  • Грамматический анализ — В информатике, синтаксический анализ (парсинг) это процесс сопоставления линейной последовательности лексем (слов, токенов) языка с его формальной грамматикой. Результатом обычно является дерево разбора. Обычно применяется совместно с лексическим …   Википедия

  • разбор — а ( у); м. 1. к Разобрать разбирать (1 3, 5 8 зн.). Заняться разбором вещей. Р. дела. Детальный р. содержания книги. Р. частей предложения. Грамматический р. 2. Выбор, отбор; разборчивое отношение к кому , чему л. Брать всё без разбора. * С… …   Энциклопедический словарь

  • грамматический — см. грамматика; ая, ое. Граммати/ческий строй языка. Г ие правила. Граммати/ческий разбор предложения. Г ая ошибка (ошибка в правописании) …   Словарь многих выражений

  • разбор — а ( у); м. 1) к разобрать разбирать 1), 3), 5), 8) Заняться разбором вещей. Разбо/р дела. Детальный разбо/р содержания книги. Разбо/р частей предложения …   Словарь многих выражений

  • синтаксический разбор — ‘грамматический разбор’ Syn: синтаксический анализ …   Тезаурус русской деловой лексики

  • синтаксический анализ — ‘грамматический разбор’ Syn: синтаксический разбор …   Тезаурус русской деловой лексики

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

Книги

Другие книги по запросу «Грамматический разбор» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»