Разработка языка программирования, являющегося подмножеством заданного языка

Нетерминалы :

  Def = *БлокОпис        8 ;

Правила :

   1)  Def  ->  DfL Def

   2)  Def  ->  DfL

   3)  Def  ->  DfC Def

   4)  Def  ->  DfC

   5)  Def ->  DfT Def

   6)  Def  ->  DfT

   7)  Def  ->  DfV Def

   8)  Def  ->  DfV

 

3. Грамматика описания меток GR3 (Начальный символ DfL)

Терминалы :

  lab = label      ;  ;   = ;          ;  ,   = ,          ;

  id  = идент      ;  nat = ЦелБезЗнак ;

Нетерминалы :

  DfL = *ОписМеток     1 ;  M = Метка              2 ;

  LLb = СписокМеток      2 ;

Правила :

   1)  DfL  ->  lab LLb

   2)  LLb  ->  M   ; 

   3)  LLb  ->  M   ,   LLb

   4)  M    ->  id

   5)  M    ->  nat

 

4. Грамматика описания констант GR4 (Начальный символ DfC)

Терминалы :

  con = const      ;  ;   = ;          ;  =   = =          ;

  id  = идент      ;  Pex = *выражение ;

Нетерминалы :

  DfC = *ОписКонстант    1 ;  LCn = СписокКонстант   2 ;

  Cn1 = ОписКонстанты    1 ;

Правила :

   1)  DfC  ->  con LCn

   2)  LCn  ->  Cn1 ;   LCn

   3)  LCn  ->  Cn1 ; 

   4)  Cn1  ->  id  =   Pex

 

5. Грамматика описания типов GR5 (Начальный символ DfT)

Терминалы :

  typ = type       ;  ;   = ;          ;  =   = =          ;

  id  = идент      ;  Сid = *КонстИден ;  int = integer    ;

  chr = char       ;  ..  = ..         ;  str = string     ;

Нетерминалы :

  DfT = *ОписТипов       1 ;  LTp = СписокТипов      2 ;

  Tp1 = ОписТипа         2 ;  Typ = Тип              4 ;

Правила :

   1)  DfT  ->  typ LTp

   2)  LTp  ->  Tp1 ;   LTp

   3)  LTp  ->  Tp1 ; 

   4)  Tp1  ->  id  =   Typ

   5)  Tp1  ->  id  =   id

   6)  Typ  ->  Cid ..  Cid

   7)  Typ  ->  int

   8)  Typ  ->  chr

   9)  Typ  ->  str

 

6. Грамматика описания переменных GR6 (Начальный символ DfV)

Терминалы :

  var = var        ;  ;   = ;          ;  ,   = ,          ;

  :   = :          ;  id  = идент      ;  int = integer    ;

  chr = char       ;  str = string     ;

Нетерминалы :

  DfV = *ОписПеременных  1 ;  LVr = СписокОписПерем  2 ;

  Vr1 = Перемен          2 ;  Vrs = СписокПеременных 1 ;

  DV1 = 1ОписПеремен    4 ;

Правила :

   1)  DfV  ->  var LVr

   2)  LVr  ->  DV1 ; 

   3)  LVr  ->  DV1 ;   LVr

   4)  Vr1  ->  id

   5)  Vr1  ->  Vr1 ,   id

   6)  Vrs  ->  Vr1

   7)  DV1  ->  Vrs :   id

   8)  DV1  ->  Vrs :   int

   9)  DV1  ->  Vrs :   chr

  10)  DV1  ->  Vrs :   str

 

7. Грамматика меток GR7 (Начальный символ M)

Терминалы :

  id  = идент      ;  nat = ЦелБезЗнак ;

Нетерминалы :

  M   = *Метка           2 ;

Правила :

   1)  M    ->  id

   2)  M    ->  nat

 

8. Грамматика описания операторов GR8 (Начальный символ opl)

Терминалы :

  M   = *метка     ;  :   = :          ;  O:= = *ОпПрисв   ;

  OIO = *ОпВв/Выв  ;  OMn = *ОперУправ ;  BOp = *БлокОпер  ;

Нетерминалы :

  Opl = *Оператор       2 ;  Op  = НепомечОпер         4 ;

Правила :

   1)  Opl  ->  M   :   Op

   2)  Opl  ->  Op

   3)  Op   ->  BOp

   4)  Op   ->  O:=

   5)  Op   ->  OIO

   6)  Op   ->  OMn

 

9. Грамматика блока операторов GR9 (Начальный символ BOp)

Терминалы :

  beg = begin      ;  end = end        ;  ;   = ;          ;

  Opl = *Оператор  ;

Нетерминалы :

  BOp = *БлокОпер        1 ;  OPs = Набор операторов     1 ;

  Op1 = Оператор         2 ;

Правила :

   1)  BOp  ->  beg OPs end

   2)  OPs  ->  Op1

   3)  Op1  ->  Opl

   4) Op1  ->  Opl ;   Op1

 

10. Грамматика оператора присваивания GR10 (Начальный символ O:=)

Терминалы :

  id  = идент      ;  :=  =  :=        ;  Pex = *выражение ;

Нетерминалы :

  O:= = *ОпПрисв        1 ;

Правила :

   1)  O:=  ->  id  :=  Pex

 

11. Грамматика операторов ввода/вывода GR11 (Начальный символ OIO)

Терминалы :

  rd  = readln     ;  wr  = writeln    ;  (   = (          ;

  )   = )          ;  Pex = *выражение ;  ,   = ,          ;

  id  = идент      ;

Нетерминалы :

  OIO = *ОпВв/Выв       2 ;  OIn = ОперВвода            1 ;

  OOu = ОперВывода       1 ;  W1  = Аргумент вывода      2 ;

  LWr = СписВыраж        1 ;  Vrs = СписПерем            1 ;

  Vr1 = Перемен          2 ;

Правила :

   1)  OIO  ->  OIn

   2)  OIO  ->  OOu

   3)  OIn  ->  rd  (   Vrs ) 

   4)  OOu  ->  wr  (   LWr ) 

   5)  W1   ->  Pex

   6)  W1   ->  Pex ,   W1

   7)  LWr  ->  W1

   8)  Vrs  ->  Vr1

   9)  Vr1  ->  id

  10)  Vr1  ->  id  ,   Vr1

 

12. Грамматика операторов управления GR12 (Начальный символ OMn)

Терминалы :

  rpt = repeat     ;  unt = until      ;  Opl = *Оператор  ;

  Lex = *ЛогВыраж  ;  got = goto       ;  if  = if         ;

  thn = then       ;  els = else       ;  M   = *Метка     ;

  ;   =            ;

Нетерминалы :

  OMn = *ОперУправ      3 ;  ORu = ОперЦикла        1 ;

  OGo = ОперПерехода     1 ;  OIf = ОперУсловия      2 ;

  Ops = Операторы        1 ;  Op1 = Оператор         2 ;

Правила :

   1)  OMn  ->  ORu

   2)  OMn  ->  OGo

   3)  OMn  ->  OIf

   4)  ORu  ->  rpt Ops unt Lex

   5)  OGo  ->  got M 

  6)  OIf  ->  if  Lex thn Opl

   7)  OIf  ->  if  Lex thn Opl els Opl

   8)  Ops  ->  Op1

   9)  Op1  ->  Opl ; 

  10)  Op1  ->  Opl ;   Op1

 

13. Грамматика логических выражений GR13 (Начальный символ Lex)

Терминалы :

  >   = >          ;  <   = <          ;  =   = =          ;

  >=  = >=         ;  <=  = <=         ;  <>  = <>         ;

  (   = (          ;  )   = )          ;  or  = or         ;

  and = and        ;  not = not        ;  Pex = *выражение ;

  str = строка     ;  sme = Same       ;  ,   = ,          ;

Нетерминалы :

  Lex = *ЛогВыраж        2 ;  Z1  =                  2 ;

  Z2  =                  1 ;  Z3  =                  2 ;

  Z4  =                  3 ;  F1  =                  2 ;

  F2  =                  2 ;  Sgn = знак сравнения   6 ;

Правила :

   1)  Lex  ->  Z1  F1

   2)  Lex  ->  Z1

   3)  Z1   ->  Z2  F2

   4)  Z1   ->  Z2

   5)  Z2   ->  Z3

   6)  Z3   ->  not Z3

   7)  Z3   ->  Z4

   8)  Z4   ->  sme (   str ,   str ) 

   9)  Z4   ->  Pex Sgn Pex

  10)  Z4   ->  (   Lex ) 

  11)  F1   ->  or  Z1  F1

  12)  F1   ->  or  Z1

  13)  F2   ->  and Z2  F2

  14)  F2   ->  and Z2

  15)  Sgn  ->  < 

  16)  Sgn  ->  > 

  17)  Sgn  ->  = 

  18)  Sgn  ->  <=

  19)  Sgn  ->  >=

  20)  Sgn  ->  <>

 

14. Грамматика простых выражений GR14 (Начальный символ Pex)

Терминалы :

  +   = +          ;  -   = -          ;  *   = *,/        ;

  (   = (          ;  /   = /          ;  )   = )          ;

  id  = идент      ;  Cid = *КонстИден ;  Scn = *СтрокКонст;

  Fun = *функция   ;

Нетерминалы :

  Pex = *выражение       2 ;  E1  =                  2 ;

  E2  =                  2 ;  T1  =                  2 ;

  T2  =                  5 ;

Правила :

   1)  Pex  ->  T1  E1

   2)  Pex  ->  T1

   3)  E1   ->  +   T1  E1

   4)  E1   ->  +   T1

   5)  E1   ->  -   T1  E1

   6)  E1   ->  -   T1

   7)  E2   ->  *   T2  E2

   8)  E2   ->  *   T2

   9)  E2   ->  /   T2  E2

  10)  E2  ->  /   T2

  11)  T1   ->  T2  E2

  12)  T1   ->  T2

  13)  T2   ->  id

  14)  T2   ->  Cid

  15)  T2   ->  Scn

  16)  T2   ->  Fun

  17)  T2   ->  (   Pex )

 

15. Грамматика вызова фукций GR15 (Начальный символ Fun)

Терминалы :

  int = integer    ;  str = string     ;  lng = length     ;

  cnc = concat     ;  pos = pos        ;  sym = StrChar    ;

  (   = (          ;  )   = )          ;  ,   = ,          ;

  Pex = *выражение ;

Нетерминалы :

  Fun = *функция         6 ;

Правила :

   1)  Fun  ->  int (   Pex ) 

   2)  Fun  ->  str (   Pex ) 

   3)  Fun  ->  lng (   Pex ) 

   4)  Fun  ->  cnc (   Pex ,   Pex ) 

   5)  Fun  ->  pos (   Pex ,   Pex ) 

   6)  Fun  ->  sym (   Pex ,   Pex ) 

 

16. Грамматика целых констант GR16 (Начальный символ Cid)

Терминалы :

  nat = ЦелБезЗнак ;  -   = -          ;

Нетерминалы :

  Cid = *КонстИден   2 ;

Правила :

   1)  Cid  ->  -   nat

   2)  Cid  ->  nat

 

17. Грамматика строковых констант GR17 (Начальный символ Scn)

Терминалы :

  Any = Любой символ ;  '   = '           ;

Нетерминалы :

  Scn = *СтрокКонст      2 ;  Sms = список символов     1 ;

  Sym = символ           2 ;

Правила :

   1)  Scn  ->  '   Sms ' 

   2)  Scn  ->  '   ' 

   3)  Sms  ->  Sym

   4)  Sym  ->  Any

   5)  Sym  ->  Any Sym

 

4.3. Описание промежуточного языка

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

Формат тетрад:

<код операции>, <операнд_1>, <операнд_2>, <результат>,

где <операнд_1> и <операнд_2> специфицируют  аргументы, а <результат> — временное имя для хранения результата выполнения операции (переменная из рабочей области).

В качестве операндов тетрад наряду с переменными и константами, определенными в исходной программе, могут выступать результаты ранее  выполненных тетрад. Например, выражение a* b + с* d представляется в виде последовательности следующих тетрад:

 

*  , a, b, t1

*  , c, d, t2

+  ,t1,t2,t3

 

Последовательность тетрад представляет собой программу, инструкции которой  обрабатываются последовательно. Операнды одной тетрады должны быть одинакового типа. Для преобразования типа операнда можно использовать тетрады преобразования типа с кодами операций ITOS (целый — в строкоый) и STOI (строковый — в целый). Поскольку операция преобразования типа одноместная, она записывается с пустым вторым операндом, например,

 

STOI, а,   , t

 

Для представления унарного минуса в тетрадах также можно не использовать второй операнд. Тетрада – , а,  , t интерпретируется как присвоение временной переменной t значения -а.

 

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

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

 

Описание тетрад
Синтаксис				Семантика
Коп	Оп1	Оп2	Рез
BRL	L			Безусловный переход на метку L
BF	L	R		Переход на метку L, если R = “Ложь”
DEFL	L			Определение метки L
WRT	A			Вывод значения А на экран
RED			A	Запрос на ввод с клавиатуры значения переменной A
CRLF				Возврат каретки и перевод строки
SET	A		R	Назначает тип A для переменной R
CHTP	A	B	R	Преобразует тип выражения  A к типу B
=I	A	B	R	операция «равно» для целых  значений A и B
=C	A	B	R	операция «равно» для символьных значений A и B
<I	A	B	R	операция «меньше» для целых значений A и B
>I	A	B	R	операция «больше» для целых значений A и B
<=I	A	B	R	операция «меньше равно» для целых значений A и B
>=I	A	B	R	операция «больше равно» для целых значений A и B
<>I	A	B	R	операция «неравно» для целых значений A и B
<>C	A	B	R	операция «неравно» для символьных значений A и B
:=	B		A	A := B
+I	A	B	R	R := A + B
-I	A	B	R	R := A - B
*I	A	B	R	R := A * B
/I	A	B	R	R := A / B
OR	A	B	R	R := A or B
AND	A	B	R	R := A and B
–I	A		R	R := – A
NOT	A		R	R := not A
LEN	A		R	Определение длины строки
CNC	A	B	R	Конкатенация строк
POS	A	B	R	Поиск подстроки в строке
STCH	A	B	R	Возврат из строки A символа с номером B
STOI	A		R	Преобразует строку A в целое число
ITOS	A		R	Преобразует целое число A в строку
SME	A	B	R	Сравнение двух строк

 

 

4.4. Неформальное описание перевода

1. Перевод условного оператора  IF (Полная форма)

Входная конструкция:

 IF <Выражение> THEN <Оператор1> ELSE <Оператор2>

Последовательность тетрад:

КОП	Оп1	Оп2	Рез
<Выражение> (R - результат)
BF	Lelse	R
<Оператор1>
BRL	Lend
DEFL	Lelse
<Оператор2>
DEFL	Lend

 

2. Перевод условного оператора IF (Сокращённая форма)

Входная конструкция:

 IF <Выражение> THEN <Оператор(ы)>

Последовательность тетрад:

КОП	Оп1	Оп2	Рез
<Выражение> (R - результат)
BF	Lend	R
<Оператор(ы)>
DEFL	Lend

 

3. Перевод оператора цикла  REPEAT - UNTIL

Входная конструкция:

REPEAT <Оператор(ы)> UNTIL <Выражение>

Последовательность тетрад:

КОП	Оп1	Оп2	Рез
DEFL	Lbegin
<Оператор(ы)>
<Выражение> (R - результат)
BF	Lbegin	R

 

4. Перевод оператора вывода WRITELN

Входная конструкция:

WRITELN(<Выражение1>, <Выражение2>, … ,<ВыражениеN>)

Последовательность тетрад:

КОП	Оп1	Оп2	Рез
<Выражение1> (R1 - результат)
WRT	R1
<Выражение2> (R2 - результат)
WRT	R2
…
…
<ВыражениеN> (RN - результат)
WRT	RN
CRLF

5. Перевод оператора вывода READLN

Входная конструкция:

READLN(A1, A2, … ,AN)

Последовательность тетрад:

КОП	Оп1	Оп2	Рез
RED			A1
RED			A2
…
RED			AN
CRLF