Описание заданного множества конструкций языка программирования с помощью формальной грамматики

где вх — цепочка, полученная из путем удаления из нее всех выходных символов.

*(S, «», ) = (S, # #, $)

*(S, «», ) = (S, # #, $)

*(S, a,) = (S,, $)

*(S, b,) = (S,, $)

*(S, c,) = (S,, $)

*(S, d,) = (S,, $)

*(S, e,) = (S,, $)

*(S, a,) = (S,, $)

*(S, b,) = (S,, $)

*(S, c,) = (S,, $)

*(S, d,) = (S,, $)

*(S, e,) = (S,, $)

*(S, 0,) = (S,, $)

*(S, 1,) = (S,, $)

*(S, 2,) = (S,, $)

*(S, 3,) = (S,, $)

*(S, 4,) = (S,, $)

*(S, 5,) = (S,, $)

*(S, 6,) = (S,, $)

*(S, 7,) = (S,, $)

*(S, 8,) = (S,, $)

*(S, 9,) = (S,, $)

*(S, 0,) = (S,, $)

*(S, 1,) = (S,, $)

*(S, 2,) = (S,, $)

*(S, 3,) = (S,, $)

*(S, 4,) = (S,, $)

*(S, 5,) = (S,, $)

*(S, 6,) = (S,, $)

*(S, 7,) = (S,, $)

*(S, 8,) = (S,, $)

*(S, 9,) = (S,, $)

*(S, 0,) = (S,, $)

*(S, 1,) = (S,, $)

*(S, 2,) = (S,, $)

*(S, 3,) = (S,, $)

*(S, 4,) = (S,, $)

*(S, 5,) = (S,, $)

*(S, 6,) = (S,, $)

*(S, 7,) = (S,, $)

*(S, 8,) = (S,, $)

*(S, 9,) = (S,, $)

*(S, «» ,) = (S, # #, $)

*(S, «» ,) = (S, # #, $)

*(S, a,) = (S, #bool# # #, $)

*(S, b,) = (S, #bool# # #, $)

*(S, c,) = (S, #bool# # #, $)

*(S, d,) = (S, #bool# # #, $)

*(S, e,) = (S, #bool# # #, $)

*(S, «» ,) = (S,, $)

*(S, a,) = (S, #char# # #, $)

*(S, b,) = (S, #char# # #, $)

*(S, c,) = (S, #char# # #, $)

*(S, d,) = (S, #char# # #, $)

*(S, e,) = (S, #char# # #, $)

*(S, «» ,) = (S,, $)

*(S, a,) = (S,, $)

*(S, b,) = (S,, $)

*(S, c,) = (S,, $)

*(S, d,) = (S,, $)

*(S, e,) = (S,, $)

*(S, «» ,) = (S,, $)

*(S, «'true'» ,) = (S,, $)

*(S, «'false'» ,) = (S,, $)

*(S, «'a'» ,) = (S,, $)

*(S, «'b'» ,) = (S,, $)

*(S, «'c'» ,) = (S,, $)

*(S, «'d'» ,) = (S,, $)

*(S, «'e'» ,) = (S,, $)

*(S, a,) = (S,, $)

*(S, b,) = (S,, $)

*(S, c,) = (S,, $)

*(S, d,) = (S,, $)

*(S, e,) = (S,, $)

*(S, «» ,) = (S,, $)

*(S, «» ,) = (S,, $)

*(S, «» ,) = (S,, $)

*(S, «» ,) = (S,, $)

*(S, «» ,) = (S,, $)

*(S, «» ,) = (S,, $)

*(S, «» ,) = (S,, $)

*(S, a,) = (S,, $)

*(S, b,) = (S,, $)

*(S, c,) = (S,, $)

*(S, d,) = (S,, $)

*(S, e,) = (S,, $)

*(S, «» ,) = (S,, $)

*(S, «'true'» ,) = (S,, $)

*(S, «'false'» ,) = (S,, $)

*(S, «» ,) = (S, # #, $)

3. Для всех правил вида

*(S, «,» ,) = (S, $, $)

*(S, «» ,) = (S, $, $)

*(S, «» ,) = (S, $, $)

*(S, «» ,) = (S, $, $)

*(S, «» ,) = (S, $, $)

*(S, «» ,) = (S, $, $)

*(S, «» ,) = (S, $, $)

*(S, «» ,) = (S, $, $)

*(S, «» ,) = (S, $, $)

*(S, «» ,) = (S, $, $)

*(S, «» ,) = (S, $, $)

*(S, «» ,) = (S, $, $)

*(S, -|,) = (S, $, $)

4. Для каждого bОVтвх, не стоящего на первом месте в правой части правил транслирующей грамматики, строим функции вида: f (S, b, b) = (S, $, $).

(S, «,», «,») = (S, $, $)

(S, «», «») = (S, $, $)

(S, «», «») = (S, $, $)

(S, «», «») = (S, $, $)

(S, «», «») = (S, $, $)

(S, «», «») = (S, $, $)

(S, «», «») = (S, $, $)

(S, «», «») = (S, $, $)

(S, «», «») = (S, $, $)

5. Для каждого wОVтвых, записываемого в магазин, строим функции вида: f *(S, $, w) = (S, $, w).

*(S, $, #bool#) = (S, $, #bool#)

*(S, $, #char#) = (S, $, #char#)

*(S, $, #a#) = (S, $, #a#)

*(S, $, #b#) = (S, $, #b#)

*(S, $, #c#) = (S, $, #c#)

*(S, $, #d#) = (S, $, #d#)

*(S, $, #e#) = (S, $, #e#)

*(S, $, #0#) = (S, $, #0#)

*(S, $, #1#) = (S, $, #1#)

*(S, $, #2#) = (S, $, #2#)

*(S, $, #3#) = (S, $, #3#)

*(S, $, #4#) = (S, $, #4#)

*(S, $, #5#) = (S, $, #5#)

*(S, $, #6#) = (S, $, #6#)

*(S, $, #7#) = (S, $, #7#)

*(S, $, #8#) = (S, $, #8#)

*(S, $, #9#) = (S, $, #9#)

*(S, $, # #) = (S, $, # #)

*(S, $, #RM#) = (S, $, #RM#)

*(S, $, #EM#) = (S, $, #EM#)

*(S, $, #=#) = (S, $, #=#)

*(S, $, #&#) = (S, $, #&#)

*(S, $, #V#) = (S, $, #V#)

*(S, $, #!#) = (S, $, #!#)

*(S, $, #'true'#) = (S, $, #'true'#)

*(S, $, #'false'#) = (S, $, #'false'#)

*(S, $, #'a'#) = (S, $, #'a'#)

*(S, $, #'b'#) = (S, $, #'b'#)

*(S, $, #'c'#) = (S, $, #'c'#)

*(S, $, #'d'#) = (S, $, #'d'#)

*(S, $, #'e'#) = (S, $, #'e'#)

6. Строим функцию перехода в заключительное состояние:

(S, -|, []) = (S, $, $)

Пример работы магазинного преобразователя:

Подадим на вход цепочку:

b1b1',''false'

На выходе магазинного преобразователя получим цепочку:

b1 bool b1 'false' ! =

ТАКТ 0

состояниеS

входная цепочка" «b1 «» «» b1, «» «'false'» «» «»

магазин[]

выходная цепочка функция перехода*(S," «,)=(S,# #,$)

ТАКТ 1

состояниеS

входная цепочка" «b1 «» «» b1, «» «'false'» «» «»

магазин# #[]

выходная цепочка функция перехода (S," «,)=(S,» «,$)

ТАКТ 2

состояниеS

входная цепочкаb1 «» «» b1, «» «'false'» «» «» -|

магазин" «# #[]

выходная цепочка функция перехода*(S, B,)=(S,#BOOL## #,$)

ТАКТ 3

состояние S

входная цепочкаb1 «» «» b1, «» «'false'» «» «» -|

магазин# ##BOOL#" «# #[]

выходная цепочка функция перехода*(S, B,)=(S,$)

ТАКТ 4

состояние S

входная цепочкаb1 «» «» b1, «» «'false'» «» «» -|

магазин# ##BOOL#" «# #[]

выходная цепочка функция перехода (S, B,)=(S,#B#,$)

ТАКТ 5

состояние S

входная цепочка1 «» «» b1, «» «'false'» «» «» -|

магазин#B## ##BOOL#" «# #[]

выходная цепочка функция перехода*(S,$,#B#)=(S,$,#B#)

ТАКТ 6

состояние S

входная цепочка1 «» «» b1, «» «'false'» «» «» -|

магазин# ##BOOL#" «# #[]

выходная цепочкаB

функция перехода*(S, 1,)=(S,$)

ТАКТ 7

состояние S

входная цепочка1 «» «» b1, «» «'false'» «» «» -|

магазин# ##BOOL#" «# #[]

выходная цепочкаB

функция перехода (S, 1,)=(S,#1#,$)

ТАКТ 8

состояние S

входная цепочка" «» «b1, «» «'false'» «» «» -|

магазин#1## ##BOOL#" «# #[]

выходная цепочкаB

функция перехода*(S,$,#1#)=(S,$,#1#)

ТАКТ 9

состояние S

входная цепочка" «» «b1, «» «'false'» «» «» -|

магазин# ##BOOL#" «# #[]

выходная цепочкаB1

функция перехода*(S," «,)=(S,$,$)

ТАКТ 10

состояние S

входная цепочка" «» «b1, «» «'false'» «» «» -|

магазин# ##BOOL#" «# #[]

выходная цепочкаB1

функция перехода*(S,$,# #)=(S,$,# #)

ТАКТ 11

состояние S

входная цепочка" «» «b1, «» «'false'» «» «» -|

магазин#BOOL#" «# #[]

выходная цепочкаB1″ ««»

функция перехода*(S,$,#BOOL#)=(S,$,#BOOL#)

ТАКТ 12

состояние S

входная цепочка" «» «b1, «» «'false'» «» «» -|

магазин" «# #[]

выходная цепочкаB1″ ««» «BOOL»

функция перехода*(S," «,)=(S,$,$)

ТАКТ 13

состояние S

входная цепочка" «» «b1, «» «'false'» «» «» -|

магазин" «# #[]

выходная цепочкаB1″ ««» «BOOL»

функция перехода (S," «,» «)=(S,$,$)

ТАКТ 14

состояние S

входная цепочка" «b1, «» «'false'» «» «» -|

магазин# #[]

выходная цепочкаB1″ ««» «BOOL»

функция перехода*(S," «,)=(S,$,$)

ТАКТ 15

состояние S

входная цепочка" «b1, «» «'false'» «» «» -|

магазин# #[]

выходная цепочкаB1″ ««» «BOOL»

функция перехода*(S,$,# #)=(S,$,# #)

ТАКТ 16

состояние S

входная цепочка" «b1, «» «'false'» «» «» -|

магазин[]

выходная цепочкаB1″ ««» «BOOL» «» «»

функция перехода (S," «,)=(S,#=#» «# #» ," ,$)

ТАКТ 17

состояние S

входная цепочкаb1, «» «'false'» «» «» -|

магазин" ," # #" «#=#[]

выходная цепочкаB1″ ««» «BOOL» «» «»

функция перехода*(S, B,)=(S,$)

ТАКТ 18

состояние S

входная цепочкаb1, «» «'false'» «» «» -|

магазин" ," # #" «#=#[]

выходная цепочкаB1″ ««» «BOOL» «» «»

функция перехода*(S, B,)=(S,$)

ТАКТ 19

состояние S

входная цепочкаb1, «» «'false'» «» «» -|

магазин" ," # #" «#=#[]

выходная цепочкаB1″ ««» «BOOL» «» «»

функция перехода (S, B,)=(S,#B#,$)

ТАКТ 20

состояние S

входная цепочка1, «» «'false'» «» «» -|

магазин#B#" ," # #" «#=#[]

выходная цепочкаB1″ ««» «BOOL» «» «»

функция перехода*(S,$,#B#)=(S,$,#B#)

ТАКТ 21

состояние S

входная цепочка1, «» «'false'» «» «» -|

магазин" ," # #" «#=#[]

выходная цепочкаB1″ ««» «BOOL» «» «» B

функция перехода*(S, 1,)=(S,$)

ТАКТ 22

состояние S

входная цепочка1, «» «'false'» «» «» -|

магазин" ," # #" «#=#[]

выходная цепочкаB1″ ««» «BOOL» «» «» B

функция перехода (S, 1,)=(S,#1#,$)

ТАКТ 23

состояние S

входная цепочка, «» «'false'» «» «» -|

магазин#1#" ," # #" «#=#[]

выходная цепочкаB1″ ««» «BOOL» «» «» B

функция перехода*(S,$,#1#)=(S,$,#1#)

ТАКТ 24

состояние S

входная цепочка, «» «'false'» «» «» -|

магазин" ," # #" «#=#[]

выходная цепочкаB1″ ««» «BOOL» «» «» B1

функция перехода*(S," ," ,)=(S,$,$)

ТАКТ 25

состояние S

входная цепочка, «» «'false'» «» «» -|

магазин" ," # #" «#=#[]

выходная цепочкаB1″ ««» «BOOL» «» «» B1

функция перехода (S," ," ," ,")=(S,$,$)

ТАКТ 26

состояние S

входная цепочка" ««'false'» «» «» -|

магазин# #" «#=#[]

выходная цепочкаB1″ ««» «BOOL» «» «» B1

функция перехода*(S,$,# #)=(S,$,# #)

ТАКТ 27

состояние S

входная цепочка" ««'false'» «» «» -|

магазин" «#=#[]

выходная цепочкаB1″ «„“ „BOOL“ „“ „“ B1» ««»

функция перехода*(S," «,)=(S,$)

ТАКТ 28

состояние S

входная цепочка" ««'false'» «» «» -|

магазин" «#=#[]

выходная цепочкаB1″ «„“ „BOOL“ „“ „“ B1» ««»

функция перехода (S," «,)=(S,#!#» «,$)

ТАКТ 29

состояние S

входная цепочка" 'false'" «» «» -|

магазин" «#!#» «#=#[]

выходная цепочкаB1″ «„“ „BOOL“ „“ „“ B1» ««»

функция перехода*(S," 'FALSE'" ,)=(S,$)

ТАКТ 30

состояние S

входная цепочка" 'false'" «» «» -|

магазин" «#!#» «#=#[]

выходная цепочкаB1″ «„“ „BOOL“ „“ „“ B1» ««»

функция перехода (S," 'FALSE'" ,)=(S,#'FALSE'#,$)

ТАКТ 31

состояние S

входная цепочка" ««» -|

магазин#'FALSE'#" «#!#» «#=#[]

выходная цепочкаB1″ «„“ „BOOL“ „“ „“ B1» ««»

функция перехода*(S,$,#'FALSE'#)=(S,$,#'FALSE'#)

ТАКТ 32

состояние S

входная цепочка" ««» -|

магазин" «#!#» «#=#[]

выходная цепочкаB1″ «„“ „BOOL“ „“ „“ B1» ««» «'FALSE'»

функция перехода (S," «,» «)=(S,$,$)

ТАКТ 33

состояние S

входная цепочка" «-|

магазин#!#" «#=#[]

выходная цепочкаB1″ «„“ „BOOL“ „“ „“ B1» ««» «'FALSE'»

функция перехода*(S,$,#!#)=(S,$,#!#)

ТАКТ 34

состояние S

входная цепочка" «-|

магазин" «#=#[]

выходная цепочкаB1″ «„“ „BOOL“ „“ „“ B1» ««» «'FALSE'» !

функция перехода (S," «,» «)=(S,$,$)

ТАКТ 35

состояние S

входная цепочка-|

магазин#=#[]

выходная цепочкаB1″ «„“ „BOOL“ „“ „“ B1» ««» «'FALSE'» !

функция перехода*(S,$,#=#)=(S,$,#=#)

ТАКТ 36

состояние S

входная цепочка-|

магазин[]

выходная цепочкаB1″ «„“ „BOOL“ „“ „“ B1» ««» «'FALSE'» ≠

функция перехода*(S,-|,)=(S,$,$)

ТАКТ 37

состояние S

входная цепочка-|

магазин[]

выходная цепочкаB1″ «„“ „BOOL“ „“ „“ B1» ««» «'FALSE'» ≠

функция перехода (S,-|,[])=(S,$,$)

ТАКТ 38

состояние S

входная цепочка-|

магазин[]

выходная цепочкаB1″ «„“ „BOOL“ „“ „“ B1» ««» «'FALSE'» ≠

Магазинный автомат успешно завершил работу

3. Лексический анализатор

3.1 Грамматика лексических единиц и структура лексем

1. Грамматика идентификатора

I cA

A cA

A dA

A rI

c — буква

d — цифра

r — разделитель (`,', ' `, '<')

2. Грамматика числа

I dB

B dB

B rB

d — цифра

r — разделитель (`,', ' `, '<')

3. Грамматика служебного слова

I

C /E

E cD

C cD

D cD

D >I

c — буква

4. Грамматика констант

I 'F

F cG

G cG

G 'I

c — буква

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

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

Структуры данных:

{ Таблица служебных слов }

TSSl: array[1.16] of StrType = ('char','/char','boolean','/boolean',

'arr','/arr','earr','/earr','ass','/ass',

'and','/and','or','/or','not','/not');

{ Таблица логических констант }

TLog: array[1.2] of StrType = ('true','false');

{ Таблица символьных констант }

TChr: array[1.36] of Char =('a','b','c','d','e','f','g','h','i','j','k','l',

'm','n','o','p','q','r','s','t','u','v','w','x',

'y','z','0','1','2','3','4','5','6','7','8','9');

{ Таблица разделителей }

TRzd = ',';

type

TPerem=(TChar, TBool); { - Возможный тип переменной }

TIdent=string[16]; { - Макс. длина идентификатора }

TypeLx=(Idt, Num, SSl, Log, Chr, Rzd);

{ - Типы лексем:

Idt — идентификатор — a, b[2] Num — целое число (б/зн) — 12, 2341

Rzd — разделитель — «,» SSl — служебное слово — ,

Log — логическая константа — true, false Chr — символьная константа — 'a', 'c' }

{ Типы, определяющие: }

TAdrTP =^TElTP; { - таблицу переменных — ТП }

TAdrTSP =^TElTSP; { - таблицу симв. представления — ТСП }

TAdrTZ =^TElTZ; { - таблицу значений — ТЗ (ячейки памяти)}

TAdrTN =^TElTN; { - таблицу чисел — ТЧ }

TAdrTL =^TElTL; { - таблицу лексем — ТЛ }

TElTP= record { Тип эл-та ТП: }

TypeP :TPerem; { - тип переменной (TBool, TChar) }

PointTSP:TAdrTSP; { - указатель на эл-т ТСП }

PointTZ :TAdrTZ; { - указатель на эл-т ТЗ }

Dim :Word; { - кол-во эл-тов (+1) в ТЗ если Dim > 0, то это — массив }

NextP :TAdrTP; { - указатель на след. эл-т ТП }

end;

TElTSP= record { Тип эл-та ТСП: }

SimvP :TIdent; { - идентификатор (симв. представление) }

NextS :TAdrTSP; { - указатель на след. эл-т ТСП }

end;

TElTN= record { Тип эл-та ТЧ: }

Numer :Word; { - значение: 0.65 535 }

NextN :TAdrTN; { - указатель на след. эл-т ТЧ }

end;

TElTZ= record { Тип эл-та ТЗ: (ячейки памяти) }

TypeZ :TPerem; { - тип хранимого значения }

Value :Byte; { - значение — 1 байт (char, bool) }

NextZ :TAdrTZ; { - указатель на след. эл-т ТЗ }

end;

TElTL= record { Тип эл-та ТЛ: }

LenL :Byte; { - длина лексемы }

NextL :TAdrTL; { - указатель на след. эл-т ТЛ }

case TypeL: TypeLx of

{ варианты }

Idt: (PointPer :TAdrTP); { - для ид-ра }

Num: (PointNum :TAdrTN); { - для числа }

SSl, Log, Chr: (Index :Byte); { - для служ. слов, констант}

Rzd: (); { - для разделителя «,» }

end;

Количество таблиц определено количеством типов лексем. В нашем случае их шесть — четыре заранее известных и две формируемых в процессе работы лексического анализатора.

Заранее известные таблицы:

1. Таблица служебных слов

2. Таблица разделителей

3. Таблица констант типа Boolean

4. Таблица констант типа Char

Формируемые таблицы:

1. Таблица идентификаторов

2. Таблица чисел Пример работы лексического анализатора:

Подадим на вход лексического анализатора цепочку:

ch, ac1, 5 b7

b7, `true'

ac1, 3, `C'

В результате работы лексического анализатора получим таблицы:

Таблица служебных слов:

1 char9 ass

2/char10/ass

3 boolean11 and

4/boolean12/and

5 arr13 or

6/arr14/or

7 earr15 not

8/earr16/not

Таблица разделителей:

17`,'

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

18`a'

19`b'

…

43`z'

44`0'

45`1'

…

53`9'

Таблица логических констант:

54`true'

55`false'

Таблица идентификаторов:

56ch

57ac1

58b7

Таблица чисел:

Таблица лексем:

Символы действия (семантика анализа):

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

1. Для идентификатора Идентификатор должен начинаться с буквы и не должен иметь длину более 16 символов.

{НИ} - Начало идентификатора

— подготовка буфера для записи (очистка)

— установка длины = 1

{ФИ} - Формирование идентификатора

— запись очередного входного символа в буфер

— увеличение длины на 1

— проверка счетчика длины на допустимое значение (? 16)

{КИ} - Конец идентификатора

— поиск идентификатора в таблице идентификаторов (если его нет, то добавляем)

— добавляем лексему типа Idt с длиной идентификатора

— указатель лексемы ставим на соответствующую ячейку таблицы идентификаторов

2. Для числа Число должно принадлежать диапазону от 0 до 65 535 (word).

Следовательно, его длина не может быть больше, чем 5.

{НЧ} - Начало числа

— подготовка буфера для записи (очистка)

— установка длины = 1

{ФЧ} - Формирование числа

— запись очередного входного символа в буфер

— увеличение длины на 1

— проверка счетчика длины на допустимое значение (? 16)

{КЧ} - Конец числа

— поиск числа в таблице чисел (если его нет, то добавляем)

— добавляем лексему типа Num с длиной числа

— указатель лексемы ставим на соответствующую ячейку таблицы чисел

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

{НС} - Начало служебного слова

— подготовка буфера для записи (очистка)

— установка длины = 1

{ФС} - Формирование служебного слова

— запись очередного входного символа в буфер

— увеличение длины на 1

{КС} - Конец служебного слова

— поиск служебного слова в таблице служебных слов (если его нет, то ошибка)

— добавляем лексему типа SSl с длиной служебного слова

— указатель лексемы ставим на соответствующую ячейку таблицы служебных слов

4. Для константы (char, boolean)

Константы должны быть точно описаны в соответствии с языком.

{НК} - Начало константы

— подготовка буфера для записи (очистка)

— установка длины = 1

{ФК} - Формирование константы

— запись очередного входного символа в буфер

— увеличение длины на 1

{КК} - Конец константы

— поиск константы в таблицах констант (char, boolean) (если ее нет, то ошибка)

— добавляем лексему типа Log или Chr с длиной константы

— указатель лексемы ставим на соответствующую ячейку соответствующей таблицы

5. Для разделителя Разделители должны быть точно описаны в соответствии с языком.

{ФР} - Формирование разделителя

— поиск разделителя в таблице разделителей (если его нет, то ошибка)

— добавляем лексему типа Rzd с длиной = 1

— указатель лексемы ставим на соответствующую ячейку таблицы разделителей

6. Дополнительные символы действия

{ФО} - Формирование ошибки

— вывод информации об ошибке

{ЧС} - Чтение символа

— чтение очередного входного символа из файла

3.4 Структура программы лексического анализатора Спецификация процедур:

BeginIdt (Ch)

Процедура формирования идентификатора и лексемы типа Idt

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

BeginNum (Ch)

Процедура формирования числа и лексемы типа Num

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

BeginSSl

Процедура распознавания служебного слова и формирование лексемы типа SSl

BeginConst

Процедура распознавания константы (симв. или лог.) и формирование лексемы типа Chr или Log

FormirRzd

Процедура формирования лексемы типа Rzd (разделитель)

4. Семантика перевода Синтаксически-управляемые схемы и транслирующие грамматики позволяют задавать соответствия между цепочками входного и выходного языков, называемые переводом. Такие соответствия отражают структурные или синтаксические свойства входных и выходных цепочек, но возникают значительные трудности при попытках их использования для описания контекстно-зависимых условий или смысла конструкций — семантики языков программирования.

Для задания семантики применяются различные приемы: W-грамматики, венский метаязык, аксиоматический и денотационный методы, а также атрибутные транслирующие грамматики (АТ — грамматики).

Рассматриваемые в настоящем разделе АТ — грамматики отличаются от транслирующих грамматик тем, что символам грамматики приписываются атрибуты, отражающие семантическую информацию, а правилам грамматики сопоставляются правила вычисления значений атрибутов.

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

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

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

Если мы описываем массив, то мы в структуру переменной в ТП заносим информацию о массиве (количество элементов). После этого выделяем память в ТЗ, состоящей из N элементов (N — количество элементов в массиве). И далее записываем указатель в ТП на начало этого поля памяти (первый элемент массива).

Операции могут выполняться с двумя типами данных Boolean и Char. Операции не могут выполняться, если в них используются операнды различного типа. Чтобы это учесть, введем в структуру ячейки памяти поле TypeZ (TChar, TBool), которое и будет указывать нам тип переменной, значение которой хранится в данной ячейке. Также в выполнении операции не могут участвовать переменные и элементы массива, которые не имеют значения (не инициализированы).

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

4.2 Атрибутная грамматика

Ѓ"a1 ЃЄb1 := Ѓ"a2 ЃЄb2 Ѓ"a3 ЃЄb3

_{a2=a1; a3=b2; b1=b3;}

_{Ѓ"a4 ЃЄb4 ЃЄx1} :='' _ЃЄx2 ',' _ЃЄy1 {WrRM}_{Ѓ"x3 Ѓ"y2} {FMB}_{Ѓ"a5 ЃЄb5 Ѓ"x4} ''

_{a5=a4; b4=b5; (x1, x3, x4)=x2; y2=y1;}

< MasChar>_{Ѓ"a6 ЃЄb6 ЃЄx5} :='' _ЃЄx6 ',' _ЃЄy3 {WrRM}_{Ѓ"x7 Ѓ"y4} {FMC}_{Ѓ"a7 ЃЄb7 Ѓ"x8} ''

_{a7=a6; b6=b7; (x5, x7, x8)=x6; y4=y3;}

_^t1 :=''_ЃЄx9 ',' _ЃЄy5 {FUkTZEM}_{Ѓ"x10 Ѓ"y6 ЃЄt2} ''

_{t1=t2; x10=x9; y6=y5;}

_{Ѓ"a8 ЃЄb8} :=''_{Ѓ"a9 ЃЄb9} ''_{Ѓ"a10 ЃЄb10}

_{b8=b10; a9=a8; a10=b9;}

_{Ѓ"a11 ЃЄb11} :=''_{Ѓ"a12 ЃЄb12} ''_{Ѓ"a13 ЃЄb13}

_{b11=b13; a12=a11; a13=b12;}

_{Ѓ"a14 ЃЄb14} :=_{Ѓ"a15 ЃЄb15}