Дизайн компилятора - семантический анализ

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

Например

E → E + T

Вышеупомянутое производство CFG не имеет семантического правила, связанного с ним, и оно не может помочь в понимании производства.

Семантика

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

CFG + semantic rules = Syntax Directed Definitions

Например:

int a = “value”;

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

  • Разрешение области
  • Проверка типа
  • Проверка массива

Семантические ошибки

Мы упомянули некоторые из ошибок семантики, которые, как ожидают, распознает семантический анализатор:

  • Несоответствие типов
  • Необъявленная переменная
  • Использование зарезервированного идентификатора.
  • Многократное объявление переменной в области видимости.
  • Доступ к переменной вне области.
  • Фактическое и формальное несоответствие параметров.

Атрибут Грамматика

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

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

Пример:

E → E + T { E.value = E.value + T.value }

Правая часть CFG содержит семантические правила, которые определяют, как следует интерпретировать грамматику. Здесь значения нетерминалов E и T складываются вместе, и результат копируется в нетерминал E.

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

Синтезированные атрибуты

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

S → ABC

Если S принимает значения из своих дочерних узлов (A, B, C), то он называется синтезированным атрибутом, поскольку значения ABC синтезируются в S.

Как и в нашем предыдущем примере (E → E + T), родительский узел E получает свое значение от своего дочернего узла. Синтезированные атрибуты никогда не принимают значения от своих родительских узлов или любых дочерних узлов.

Унаследованные атрибуты

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

S → ABC

A может получать значения из S, B и C. B может принимать значения из S, A и C. Аналогично, C может принимать значения из S, A и B.

Расширение : когда нетерминал расширяется до терминалов согласно грамматическому правилу

Унаследованные атрибуты

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

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

Семантический анализатор получает AST (Абстрактное синтаксическое дерево) со своей предыдущей стадии (синтаксический анализ).

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

Атрибутами являются два значения кортежа, <имя атрибута, значение атрибута>

Например:

int value  = 5;
<type, “integer”>
<presentvalue, “5”>

Для каждого производства мы прилагаем семантическое правило.

S-атрибут SDT

Если SDT использует только синтезированные атрибуты, он называется S-атрибутным SDT. Эти атрибуты оцениваются с использованием S-атрибутов SDT, семантические действия которых записаны после производства (правая часть).

S-атрибут SDT

Как показано выше, атрибуты в S-атрибутных SDT оцениваются при анализе снизу вверх, поскольку значения родительских узлов зависят от значений дочерних узлов.

L-атрибут SDT

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

В LT-атрибутах SD нетерминал может получать значения из родительских, дочерних и дочерних узлов. Как в следующем производстве

S → ABC

S может принимать значения из A, B и C (синтезировано). A может принимать значения только из S. B может принимать значения от S и A. C может получать значения от S, A и B. Ни один нетерминал не может получить значения от родного брата справа от него.

Атрибуты в L-атрибутных SDT оцениваются методом разбора по глубине и слева направо.

L-атрибут SDT

Мы можем заключить, что если определение S-атрибутировано, то оно также L-атрибутировано, поскольку L-атрибутированное определение включает S-атрибутированные определения.