Описание контекстных условий

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

Рассмотрим наиболее характерные типы контекстных условий:

1. Правила единственности именования различных объектов программы, таких, как переменные, подпрограммы, типы данных, константы, метки и т. п., устанавливаемые каждым языком программирования. Например:

• пространства имен различных объектов программы не должны попарно пересекаться;

• пространства имен различных объектов программы могут пересекаться.

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

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

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

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

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

Описание динамической семантики

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

Рассмотрим наиболее известные методы формального определения семантики.

Грамматические модели

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

Другой способ описания семантики языков программирования основан на использовании двухуровневых грамматик (W-грамматик), которые предложил Аад ван Вейнгаарден для описания языка ALGOL 68.

W-грамматика состоит из двух конечных множеств правил, называемых множествами метаправил и гиперправил. Метаправила – это БНФ, записываемые в несколько другой форме. Нетерминалы метаправил, называемые метапонятиями, записываются прописными буквами, например ЛИТЕРА. В каждом метаправиле определяются все альтернативы данного метапонятия. Символ '::' используется для разделения левой и правой частей метаправила, символ ';' разделяет альтернативы в правой части мета-правила, а символ '.' используется для определения конца метаправила. Например, следующие метаправила:

(1) ЛИТЕРА :: а; b; ... z;а; б; ... ; я.

(2) ПОНЯТИЕ :: ЛИТЕРА;

ПОНЯТИЕ ЛИТЕРА.

порождают либо метапонятие ЛИТЕРА, которое в свою очередь порождает протопонятие, представленное произвольной строчной буквой латинского или русского алфавита, либо метапонятие ПОНЯТИЕ, за которым следует ЛИТЕРА.

Гиперправило – это заготовка, из которой получаются синтаксические правила. Например, гиперправило:

ПОНЯТИЕ строка: ПОНЯТИЕ;

ПОНЯТИЕ строка, ПОНЯТИЕ.

является прототипом правил, описывающих строки. Оно содержит метапонятия (ПОНЯТИЕ) и протопонятия (строка).В гиперправилах для разделения левой и правой частей используется символ ':', а разные протопонятия внутри одной альтернативы разделяются символом ','. Металингвистические формы получаются после замены в гиперправиле всех метапонятий на протопонятия, выводимые из метапонятий с помощью метаправил.

Для рассмотренного ранее примера метаправила (1) и (2) позволяют вывести из метапонятия ПОНЯТИЕ такие протопонятия, как идентификатори значение.Заменяя в гиперправиле ПОНЯТИЕ этими протопонятиями, можно получить следующие БНФ:

значение последовательность: значение;