close

Разбор

Перейти к навигации Перейти к поиску

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

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

Парсеры обычно не пишутся вручную, а строятся через генераторы парсеров .

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

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

Описание

Пример

В следующем примере показан распространенный случай разбора языка для калькулятора (или калькулятора) с двумя уровнями грамматики: лексическим и синтаксическим.

Как уже упоминалось, первым шагом является генерация токенов или лексический анализ . Например, ввод может быть следующим «12 * (3 + 4) ^ 2», в этом случае синтаксический анализатор разбивает ввод на токены следующим образом: 12, *, (, 3, +, 4,) , ^ и 2, каждый из которых представляет собой символ со значением в математическом выражении. Синтаксический анализатор может содержать правила, которые сообщают ему, что символы *, +, ^, (и) вызывают запуск новой лексемы, поэтому лексемы типа «12 *» или «(3» не будут генерироваться.

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

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

Типы парсеров

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

  • Анализ сверху вниз — парсер может начать с ведущего символа и попытаться преобразовать его во входные данные. Интуитивно понятно, что синтаксический анализатор начинает с самого большого элемента и делит его на все более мелкие части. Парсеры LL являются примерами нисходящих парсеров.
  • Анализ снизу вверх — парсер может начать с ввода и попытаться переписать его до исходного символа. Интуитивно синтаксический анализатор пытается найти самый простой символ, затем обрабатывает содержащие его элементы и так далее. Парсеры LR являются примерами восходящих парсеров.

Еще одно важное различие заключается в том, что между синтаксическими анализаторами, которые генерируют по крайнему левому производному или по самому правому производному . Парсеры LL генерируют крайнее левое производное, а синтаксические анализаторы LR — крайнее правое производное.

Языки программирования

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

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

Однако использование более мощных грамматик, таких как контекстно- зависимые грамматики , означает потерю эффективности. Следовательно, общепринятой стратегией является использование контекстно-свободных грамматик для «расслабленной» (с меньшим количеством ограничений) версии языка. Эти грамматики будут принимать все допустимые конструкции рассматриваемого языка, а также другие недопустимые конструкции, которые отбрасываются во время семантического разбора входных данных. Например, грамматика может принять программу, использующую ранее не объявленную переменную.

Библиография

Связанные элементы

Нисходящий парсер

  • Парсер ЛЛ
    • Рекурсивный синтаксический анализатор
  • Парсер пакрат
  • метод Унгера

Восходящий анализатор

Генераторы парсеров

Внешние ссылки

Получено с " https://it.wikipedia.org/w/index.php?title=Parsing&oldid=125018236 "