Формальные методы описания синтаксиса.

Формальные методы описания синтаксиса.

Для описания синтаксических конструкций языка программирования в настоящее время наиболее распространены два формальных метода. Первый использует форму записи, предложенную Джоном Бэкусом и Питером Нау-ром, когда они описывали синтаксис языка Алгол-60. С тех пор эта форма называется Backus Naur Form, или сокращенно BNF.

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

Чтобы получить правильные грамматические конструкции языка, используя синтаксические диаграммы, нужно идти по путям, указанным стрелками, от одного четырехугольника к другому до тех пор, пока не встретится выход. Там, где предусмотрено более одного направления движения, можно выбирать любое. Если по пути встречается ссылка к другой синтаксической диаграмме, то следует войти в эту новую диаграмму, пройти по ней, выйти из нее и возвратиться на старое место в первоначальной диаграмме. Если по пути движения встречается точка, то это означает, что данный путь характерен только для Turbo Pascal и является расширением стандарта языка. Варианты представления синтаксических конструкций языка программирования методом BNF или методом синтаксических диаграмм являются тождественными.

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

1) ориентированные на компиляцию (семантика – множество преобразований над синтаксической моделью);

2) ориентированные на интерпретацию (семантика – множество описанных на метаязыке преобразований синтаксически правильных языковых конструкций).

Виды семантик, ориентированные на интерпретацию:

1) Операционные (смысл конструкций языка в терминах переходов абстрактной машины из одного состояния в другое), например, SECD-машина П. Лендина;

2) Пропозиционные (смысл конструкций языка в терминах множества формул, описывающих состояния объектов программы), например, подходы Хоара и Флойда;

3) Денотационные (смысл конструкций языка в терминах абстракции функций на состояниях программы), например, теория семантических доменов Д. Скотта.

Вопрос 4. Деревья синтаксического анализа.

Дерево синтаксического анализа арифметического выражения - это бинарное дерево, листьями которого служат операнды, а остальными вершинами - операции, причем уровень вершины соответствует приоритету выполнения операции: чем ближе к листьям, тем приоритет выше.

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

((a / (b + c)) + (x * (y — z))).

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

Генерация дерева синтаксического анализа

Одно и то же арифметическое выражение может быть записано тремя способами:

1. Инфиксный способ записи (знак операции находится между операндами):

((a / (b + c)) + (x * (y - z)))

Все арифметические операции, привычные нам со школьных лет, записываются именно таким образом.

2. Префиксный способ записи (знак операции находится перед операндами):

+( /(a, +(b, c)), *(x, -(y, z)))

Из знакомых всем нам функций префиксный способ записи используется, например, для sin(x), tg(x), f(x, y, z) и т.п.

3. Постфиксный способ записи (знак операции находится после операндов):

((a, (b, c)+ )/, (x, (y, z)- )* )+

Арифметические выражения

Арифметическое выражение является аналогом обычной алгебраической формулы, оно задает правило и определяет порядок выполнения операций при вычислении по формуле. Арифметическое выражение состоит из следующих элементов: числовых констант, переменных, указателей функции, знаков арифметических операций и круглых скобок. Частным случаем арифметического выражения является числовая константа, переменная, указатель функции. Константы, переменные и функции должны быть либо описаны в программе, либо иметь стандартные имена. В арифметическом выражении используются следующие знаки арифметических операций: + (сложение), - (вычитание), * (умножение), / (деление), div(деление нацело с отбрасыванием остатка), mod(нахождение целого остатка при делении нацело).

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

При записи арифметических выражений следует выполнять следующие правила:

- выражение записывают в строку без надстрочных или подстрочных символов;

- использовать только круглые скобки, число открывающихся скобок всегда должно равняться числу закрывающихся скобок, «лишние» круглые скобки, если они использованы без нарушения правил, не играют никакой роли, поэтому, когда возникает сомнения в последовательности выполнения операций, можно поставить «лишние» скобки;

- нельзя записывать подряд два знака арифметических операций, нельзя опускать знак умножения между сомножителями;

- необходимо помнить, что порядок выполнения арифметического выражения определяется скобками, в их отсутствие операции выполняются согласно старшинству (приоритету) операций в следующем порядке: вычисление значения функции; операции умножения, деления, divилиmod; операции сложения или вычитания. Операции одинакового приоритета выполняются последовательно слева направо.

Тип результата арифметического выражения зависит от типов операндов, участвующих в операции. Тип результата операций «+», «-«, «*» будет Integer, если оба операнда имеют типInteger, в противном случае результат будет типа Real. Результат операции «/» всегда имеет типReal. Операции div и mod допустимы только при целочисленных операндах и дают результат типа Integer. Результаты вычисления арифметических выражений (в том числе промежуточные) не должны выходить из допустимой области значений целых и вещественных величин.

Пример

Then

Begin

операторы;

End

Else

Begin

операторы;

end;

Ада

if условие1 then команды1

else if условие2 then команды2

...

else командыN

end if;

Вариант 1 Вариант 2

If < условие 1> Then < Операторы 1> Elself < условие 2> Then < Операторы 2> End If

if< условие 1> then < Операторы 1> elseif< условие 2> then < Операторы 2> ... elseif< условие n-1> then < Операторы n-1> else < Операторы n> endif

Оператор работает следующим образом:

если (If) выполняется < условие 1>, то ( Then) будет выполнена последовательность операторов < Блок 1>,
иначеесли ( ElseIf ) выполняется < условие 2>, то ( Then) будет выполнен < Блок 2> ,

и т.д.,

иначе ( Else ) - < Блок N>

Begin

if count = 0 then result: = 0

else result: = 1

End

Если оператор else следовало связать с первым оператором then, то это можно было записать так:

if sum = 0 then

Begin

if count = 0 then result: = 0

End

elseresult: = 1

Формальные методы описания синтаксиса.

1) ориентированные на компиляцию (семантика – множество преобразований над синтаксической моделью);

Виды семантик, ориентированные на интерпретацию:

12 3 4 5 Следующая ⇒