Семантика языков программирования

1. Семантика языков программирования

 

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

Семантика языков программирования изменяется в очень широких пределах. Они отличаются не только по особенностям реализации отдельных операций, но и по парадигмам программирования, определяющим принципиальные различия в методах разработки программ. Специфика реализации операций может касаться как структуры обрабатываемых данных, так и правил обработки одних и тех же типов данных. Такие языки, как PL/1 и APL поддерживают выполнение матричных и векторных операций. Большинство же языков работают в основном со скалярами, предоставляя для обработки массивов процедуры и функции, написанные программистами. Но даже при выполнении операции сложения двух целых чисел такие языки, как C и Паскаль могут вести себя по-разному.

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

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

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

1. Языки программирования предназначены для облегчения программирования. Поэтому их операторы и структуры данных более мощные, чем в машинных языках.

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

3. Для любого языка определяется:

– множество символов, которые можно использовать для записи правильных программ (алфавит), основные элементы;

– множество правильных программ (синтаксис);

– «смысл» каждой правильной программы (семантика).

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

 

Y = F(X)    (2.1)

 

Формально каждая правильная программа X - это цепочка символов из некоторого алфавита A, преобразуемая в соответствующую ей цепочку Y, составленную из символов алфавита B.

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

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

Связь структуры программы с  языком программирования называется синтаксическим отображением.

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

 

a + (b + c) · d    (1)

 

В большинстве языков программирования данное выражение определяет иерархию программных объектов, которую можно отобразить в виде дерева (см. Рисунок 1):

 

Рисунок 1 Синтаксическая структура выражения a + (b + c) · d,

построенная по первому  описанию

 

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

<выражение> ::= <слагаемое> | <выражение> + <слагаемое>;

<слагаемое> ::= <множитель> | <слагаемое> * <множитель>;

<множитель> ::= <буква> | ( <выражение> );

<буква> ::= a | b | c | d | i | f | g | h | i | j | k | l | m | n | o | p | q

| r | s | t | u | v | w | x | y | z.

Примечание. Знак «::=» читается как «это есть». Вертикальная черта «|» читается как «или».

 

Рисунок 2 Синтаксическая структура выражения a + (b + c) · d,

построенная по второму  описанию

 

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

<выражение> ::= <операнд> | <выражение> + < операнд >

| <выражение> * < операнд >;

<операнд> ::= <буква> | ( <выражение> );

<буква> ::= a | b | c | d | i | f | g | h | i | j | k | l | m | n | o | p | q

| r | s | t | u | v | w | x | y | z.

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

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

Процесс нахождения синтаксической структуры заданной программы называется синтаксическим разбором.

Синтаксическая структура, правильная для одного языка, может быть ошибочной  для другого. Например, в языке  Форт приведенной выражение не будет распознано. Однако для этого языка корректным будет являться постфиксное выражение:

 

a b c + d · +    (2)

 

Его синтаксическая структура описывается  правилами:

<выражение> ::= <буква> | <операнд> <операнд> <операция>;

< операнд > ::= < буква > | < выражение >;

< операция > ::= + | *;

<буква> ::= a | b | c | d | i | f | g | h | i | j | k | l | m | n | o | p | q

| r | s | t | u | v | w | x | y | z.

Иерархическое дерево, определяющее синтаксическую структуру, представлено на Рисунке 3.

Другой характерной особенностью всех языков является их семантика. Она определяет смысл операций языка, корректность операндов. Цепочки, имеющие одинаковую синтаксическую структуру в различных языках программирования, могут различаться по семантике (что, например, наблюдается в C++, Pascal, Basic для приведенного выше фрагмента арифметического выражения).

 

Рисунок 3 Синтаксическая структура выражения a b c + d · +,

построенная по постфиксным  правилам

 

Знание семантики языка позволяет  отделить ее от его синтаксиса и  использовать для преобразования в другой язык (осуществить генерацию кода).

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

 

 

Задание 2:

ПРАКТИЧЕСКАЯ РАБОТА ЛЕКСИЧЕСКИЙ  АНАЛИЗ

2

PROGRAM, INPUT, OUTPUT, VAR, INTEGER, BEGIN, FOR, TO, DO

«:», «,», «;», «:=», «.», «[», «]», «(», «)»

целые числа с количеством цифр не более 8

 

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

Таблица терминальных символов:

№ строки	Терминальный символ	Признак разделителя
01	PROGRAM	–
02	VAR	–
03	BEGIN	–
04	END	–
05	INTEGER	–
06	FOR	–
07	TO	–
08	DO	–
09	INPUT	–
10	OUTPUT	–

 

Таблица символических  имен:

№ строки	Символическое имя	Адрес	Тип	Другая информация
01	x		int
02	y		int
03	z		int

 

 

 

Текст программы:

var

  Form1: TForm1;

  Liksem:array of string;

  VARFLAG:BOOLEAN;

 

implementation

 

{$R *.dfm}

//иницилицизация массива разделителей

procedure TForm1.initArrLiksem();

var i,CountArr:integer;

begin

with GridTermin do

  begin

  CountArr:=0;

  for i:=1 to RowCount-1 do

   if  UpperCase(Cells[2,i])='+' then

      CountArr:=CountArr+1;

 

  SetLength(Liksem,CountArr);

  CountArr:=0;

   for i:=1 to RowCount-1 do

   if  UpperCase(Cells[2,i])='+' then

      begin

      Liksem[CountArr]:=Cells[1,i];

      CountArr:=CountArr+1;

      end;

  end;

end;

 

//получение первого слова

function getWord(st:string):integer;

var sttmp:string;

indx,i:integer;

begin

if st='' then exit;

for i:=0 to high(Liksem) do

  begin

         if indx>0 then

      begin

      Form1.ListBox1.Items.add('gWd>0 st:'+st+'ix'+inttostr(indx));

      if indx=1 then indx:=2;

      delete(st,indx,length(st));

      Form1.ListBox1.Items.add('gWd>0 st:'+st);

      getWord(st);

      end ;

 

  end;

    if (indx<=0) or (length(st)=1) then

      begin

      Form1.ListBox1.Items.add('gWd<=0 st:'+st+'ix'+inttostr(indx));

      getWord:=length(st);

      exit;

      end;

    indx:=pos(Liksem[i],st);

 

end;

 

//Удаляет пробелы с  начала и конца строки stTmp

function TForm1.DelStrBgEnSpace(stTmp:string):string;

begin

  if stTmp[1]=' ' then

    Delete(stTmp,1,1);

  if stTmp[Length(stTmp)]=' ' then

    Delete(stTmp,Length(stTmp),1);

  DelStrBgEnSpace:=stTmp;

end;

 

//Удаляет из строки stTmp все двойные пробелы

function TForm1.DelStrSpaceDouble(stTmp:string):string;

begin

while pos('  ',stTmp)>0 do

    delete(stTmp,pos('  ',stTmp),1);

  DelStrSpaceDouble:=stTmp;

end;

 

//заменяут разделители на значения

function TForm1.ReplaceLiksemToStr(stTmp:string):string;

VAR ST:INTEGER;

begin

if UpperCase(stTmp)='VAR' then

VARFLAG:=true;

if UpperCase(stTmp)='BEGIN' then

VARFLAG:=false;

 

ST :=StrInGrid(GridTermin, stTmp);

IF ST>0 THEN BEGIN  Result:='<1.'+INTTOSTR(ST)+'>'; EXIT; END;

 

ST :=StrInGrid(LitGrid, stTmp);

IF (ST<0) and VARFLAG THEN

      begin

      LitGrid.cells[1,LitGrid.RowCount-1]:=stTmp;

      ST:=LitGrid.RowCount-1;

      LitGrid.RowCount:=LitGrid.RowCount+1;     

      end;

 

IF ST>=0 THEN BEGIN  Result :='<2.'+INTTOSTR(ST)+'>'; EXIT; END;

ST :=StrInGrid(SimGrid, stTmp);

IF (ST<0) and not VARFLAG THEN

      begin

      SimGrid.cells[1,SimGrid.RowCount-1]:=stTmp;

      ST:=SimGrid.RowCount-1;

      SimGrid.RowCount:=SimGrid.RowCount+1;

      end;

 

IF ST>=0 THEN BEGIN  Result :='<3.'+INTTOSTR(ST)+'>'; EXIT; END;

Result :='';

end;

 

//поиск строки в таблице

function TForm1.StrInGrid(SG:TStringGrid; StrFind:string):INTEGER;

var I:integer;

begin

IF StrFind = ' ' THEN EXIT;

with SG do

  begin

  for i:=0 to RowCount-1 do

   begin

   if  UpperCase(Cells[1,i])=UpperCase(StrFind) then

      begin

     StrInGrid:=I;

      exit;

      end else StrInGrid:=-1;

   end;

  end;

end;

 

procedure TForm1.FormCreate(Sender: TObject);

var I,j:integer;

F: TextFile;

cnt:integer;

st:string;

begin

 

AssignFile(F, ExtractFilePath(Application.ExeName)+'GridTermin.txt');

Reset(F);

with GridTermin do

  begin

  readln(F,cnt);

  RowCount:=cnt;

    readln(F,cnt);

  ColCount:=cnt;

  for i:=1 to RowCount-1 do

  for j:=1 to ColCount-1 do

    begin

    readln(F,st);

    GridTermin.Cells[0,i]:=inttostr(i);

    GridTermin.Cells[j,i]:=st;

    end;

  end;

CloseFile(F);

initArrLiksem;

end;

 

procedure TForm1.Button1Click(Sender: TObject);

var I,j:integer;