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

Содержание:

Anonim

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

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

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

Процесс анализатора синтаксиса

В этом руководстве вы узнаете

  • Зачем вам нужен анализатор синтаксиса?
  • Важная терминология анализатора синтаксиса
  • Зачем нужен парсинг?
  • Методы синтаксического анализа
  • Ошибка - методы восстановления
  • Грамматика:
  • Условные обозначения
  • Грамматика без контекста
  • Грамматика
  • Синтаксис против лексического анализатора
  • Недостатки использования синтаксических анализаторов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. Предиктивный синтаксический анализ:

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

  1. Парсинг с рекурсивным спуском:

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

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

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

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

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

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

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

Заявление режима восстановления

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

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

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

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

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

Произведения с ошибками

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

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

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

Грамматика:

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

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

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

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

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

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

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

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

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

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

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

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

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

expression -> expression -+ termexpression -> expression - termexpression-> termterm -> term * factorterm -> expression/ factorterm -> factor factorfactor -> ( expression )factor -> id

Грамматика

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

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

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

Самая правая производная

Самая правая деривация просматривает и заменяет ввод производственными правилами, справа налево, последовательность. Это называется крайним правым выводом. Смысловая форма, образованная от самого правого слова, известна как правая-сентенциальная форма.

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

Анализатор синтаксиса

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

Анализатор синтаксиса в основном имеет дело с рекурсивными конструкциями языка.

Лексический анализатор упрощает задачу синтаксического анализатора.

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

Лексический анализатор распознает токен в исходной программе.

Он получает входные данные в виде токенов от лексических анализаторов.

Он отвечает за действительность токена, предоставленного

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

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

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

Резюме

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