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

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

Например

E → E + T

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

Семантика

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

CFG + semantic rules = Syntax Directed Definitions

Например:

int a = “value”;

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

Разрешение прицела
Проверка типа
Проверка с привязкой к массиву

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

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

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

Грамматика атрибутов

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

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

Example:

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.

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

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

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

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

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

Атрибуты - это два значения кортежа, <имя атрибута, значение атрибута>

Например:

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

К каждой постановке мы прилагаем семантическое правило.

S-атрибутное SDT

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

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

L-атрибутированное SDT

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

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

S → ABC

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

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

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