Синтаксический анализ: типы анализа компилятором сверху вниз и снизу вверх

Что такое синтаксический анализ?

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

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

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

Зачем вам нужен синтаксический анализатор?

  • Проверьте, верен ли код грамматически
  • Синтаксический анализатор помогает применять правила к коду.
  • Помогает вам убедиться, что каждая открывающая скобка имеет соответствующий закрывающий баланс.
  • Каждое объявление имеет тип, и этот тип должен существовать.

Важная терминология синтаксического анализатора

Важные термины, используемые в процессе синтаксического анализа:

  • Предложение: Предложение — это группа символов в некотором алфавите.
  • Лексема: Лексема – это синтаксическая единица языка самого низкого уровня (например, итог, начало).
  • Маркеров: Токен — это всего лишь категория лексем.
  • Ключевые слова и зарезервированные слова – Это идентификатор, который используется как фиксированная часть синтаксиса оператора. Это зарезервированное слово, которое нельзя использовать в качестве имени или идентификатора переменной.
  • Шумовые слова – Шумовые слова необязательны, они вставляются в высказывание для повышения читабельности предложения.
  • Комментарии – Это очень важная часть документации. Обычно оно отображается с помощью /* */ или //Blank (пробелов).
  • Разделители – Это синтаксический элемент, обозначающий начало или конец некоторой синтаксической единицы. Подобно утверждению или выражению, «начало»… «конец» или {}.
  • Набор символов — ASCII, Юникод
  • Идентификаторы – Это ограничение на длину, которое помогает снизить читабельность предложения.
  • Символы оператора – + и – выполняет две основные арифметические операции.
  • Синтаксические элементы языка

Зачем нам нужен парсинг?

анализ

Синтаксический анализ также проверяет правильность формата входной строки и, если нет, отклоняет ее.

анализ

Фоллоwing Это важные задачи, выполняемые синтаксическим анализатором при разработке компилятора:

  • Помогает вам обнаружить все типы синтаксических ошибок.
  • Найдите позицию, в которой произошла ошибка
  • Четкое и точное описание ошибки.
  • Восстановление после ошибки, чтобы продолжить и найти дальнейшие ошибки в коде.
  • Не должно влиять на компиляцию «правильных» программ.
  • Анализ должен отклонять недопустимые тексты, сообщая о синтаксических ошибках.

Методы синтаксического анализа

Техники синтаксического анализа делятся на две группы:

  • Нисходящий анализ,
  • Анализ снизу вверх

Анализ сверху вниз

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

Два типа анализа сверху вниз:

  1. Прогнозирующий анализ:

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

  1. Рекурсивный анализ спуска:

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

Анализ снизу вверх

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

Ошибка — методы восстановления

Распространенные ошибки, возникающие при анализе системного программного обеспечения

  • лексический: Имя неверно введенного идентификатора.
  • синтаксический: несбалансированная скобка или отсутствующая точка с запятой
  • Семантический: несовместимое присвоение значения
  • логический: бесконечный цикл и недостижимый код

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

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

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

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

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

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

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

Ошибка производства

  • Восстановление выдачи ошибок расширяет грамматику языка, который генерирует ошибку.neoмы конструируем. Затем анализатор выполняет диагностику ошибок этой конструкции.

Глобальная коррекция

  • Компилятору следует вносить как можно меньше изменений при обработке неправильной входной строки. Учитывая неправильную входную строку a и грамматику c, алгоритмы будут искать дерево разбора для связанной строки b. Как и в случае некоторых вставок, удалений и модификаций токенов, необходимых для преобразования a в b, минимально возможное количество.

Grammar

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

Правила грамматики формы

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

Условные обозначения

Символ условных обозначений может быть указан путем заключения элемента в квадрат. brackets. Это произвольная последовательность экземпляров элемента, которую можно указать, заключив элемент в фигурные скобки, за которыми следует символ звездочки {… }*.

Это выбор альтернативы, которая может использовать символ в рамках одного правила. При необходимости его можно заключить в круглые скобки ([,] ).

Два типа области условных обозначений Терминальные и нетерминальные

1. Терминалы:

  • Строчные буквы алфавита, такие как a, b, c,
  • Символы операторов, такие как +,-, * и т. д.
  • Символы пунктуации, такие как круглые скобки, решетка, запятая.
  • 0, 1, …, 9 цифр
  • Строки, выделенные жирным шрифтом, такие как id или if, все, что представляет собой один символ терминала.

2. Нетерминалы:

  • Заглавные буквы, такие как A, B, C.
  • Названия, выделенные строчными буквами курсивом: выражение или некоторые

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

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

expression -> expression -+ term
expression -> expression – term 
expression-> term
term  -> term * factor
term -> expression/ factor
term  -> factor factor
factor ->  ( expression )
factor -> id

Грамматический вывод

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

Крайний левый вывод

Когда вводная форма предложения сканируется и заменяется в последовательности слева направо, это называется крайним левым выводом. Форма предложения, полученная путем крайнего левого вывода, называется формой предложения слева.

Самый правый вывод

Крайний правый вывод сканирует и заменяет входные данные продукционными правилами, справа налево, последовательность. Это известно как самый правый вывод. Форма предложения, полученная из крайнего правого вывода, известна как форма предложения справа.

Синтаксис против лексического анализатора

Синтаксический анализатор Лексический анализатор
Синтаксический анализатор в основном имеет дело с рекурсивными конструкциями языка. Лексический анализатор облегчает задачу синтаксического анализатора.
Синтаксический анализатор работает с токенами исходной программы, чтобы распознавать значимые структуры языка программирования. Лексический анализатор распознает токен в исходной программе.
Он получает входные данные в виде токенов от лексических анализаторов. Он отвечает за достоверность токена, предоставленного

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

Недостатки использования синтаксических анализаторов

  • Он никогда не определит, действителен токен или нет.
  • Not помогает определить, действительна или нет операция, выполненная с типом токена.
  • Вы не можете решить, что токен объявлен и инициализирован до его использования.

Итоги

  • Синтаксический анализ — это второй этап процесса разработки компилятора, который следует после лексического анализа.
  • Синтаксический анализатор помогает применять правила к коду.
  • Предложение, лексема, токен, ключевые слова и зарезервированные слова, шумовые слова, комментарии, разделители, набор символов, идентификаторы — вот некоторые важные термины, используемые при синтаксическом анализе при построении компилятора.
  • Анализатор проверяет, что входная строка имеет правильный формат, и если нет, отклоняет ее.
  • Методы синтаксического анализа делятся на две разные группы: синтаксический анализ сверху вниз и синтаксический анализ снизу вверх.
  • Лексические, синтаксические, семантические и логические — вот некоторые распространенные ошибки, возникающие во время метода синтаксического анализа.
  • Грамматика – это набор структурных правил, описывающих язык.
  • Символ условных обозначений может быть указан путем заключения элемента в квадрат. brackets
  • CFG — это леворекурсивная грамматика, имеющая хотя бы одно произведение типа
  • Грамматическое происхождение — это последовательность грамматических правил, которая преобразует начальный символ в строку.
  • Синтаксический анализатор в основном имеет дело с рекурсивными конструкциями языка, тогда как лексический анализатор облегчает задачу синтаксического анализатора в СУБД
  • Недостаток метода синтаксического анализатора заключается в том, что он никогда не определит, действителен токен или нет.