2. 3. 2. Построение диаграммы лексического анализатора.

S

F

Id

Буква, цифра

Буква

₁

Цифра

Цифра

., E+ E-

C

T

₃

L

Next1

E1

₃

:

=

₂

₃

Next2

E2

₃

<

=

₃

Next3

E3

₃

>

=

₃

Next4

E4

₃

<

>

Цифра

D

₂

Цифра

Идентификатор

Целое число без знака

Вещ. число без знака

Ошибка

Однолитерный разделитель

Двухлитерный разделитель

Двухлитерный разделитель

Двухлитерный разделитель

Двухлитерный разделитель

Однолитерный разделитель

Однолитерный разделитель

Однолитерный разделитель

Однолитерный разделитель

₂

Знак

₃

2. 3. 3. Спецификации функций лексического анализатора.

1. Процедура Find – записывает в выходной поток токенов ссылку на элемент в таблице лексем.

2. Процедура Cons – добавляет лексему в таблицу лексем заданного класса и записывает в выходной поток токенов ссылку на эту лексему.

3. Процедура Error – вставляет в поток токенов сообщение о лексической ошибке.

4. Процедура Id – распознает лексему «идентификатор», проверяет, не является ли идентификатор ключевым словом. Если да – то ищет данное ключевое слово в таблице ключевых слов; если нашел, то вызывается процедура Find, иначе процедура Cons. Если нет – то ищет данный идентификатор в таблице идентификаторов; если нашел, то вызывается процедура Find, иначе процедура Cons.

5. Процедура NatNum – распознает лексемы «целое число» и «вещественное число». После распознавания вызывается процедура Cons.

6. Процедура Rel – распознает лексемы «однолитерный разделитель» и «двухлитерный разделитель» (знаки отношения), ищет распознанную лексему в соответствующей таблице лексем; если нашел, то вызывается процедура Find, иначе процедура Cons.

7. Процедура Let – распознает лексемы «однолитерный разделитель» (двоеточие) и «двухлитерный разделитель» (знаки оператора присваивания), ищет распознанную лексему в соответствующей таблице лексем; если нашел, то вызывается процедура Find, иначе процедура Cons.

8. Процедура OneLiter – распознает лексему «однолитерный разделитель» (однолитерные разделители, кроме двоеточия и знаков отношения), ищет распознанную лексему в таблице однолитерных разделителей; если нашел, то вызывается процедура Find, иначе процедура Cons.

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

2. 4. Таблицы лексем.

1. Таблица ключевых слов.

Таблица ключевых слов

имя ключевого слова

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

Таблица идентификаторов
имя идентификатора	тип идентификатора	значение идентификатора	размерность вектора

Примечание: для переменных типа vector поле «значение идентификатора» не заполняется; для переменных типа real и integer значение размерности вектора считается равным 0. На этапе лексического анализа заполняется только поле «имя идентификатора».

3. Таблица целых констант.

Таблица целых констант
значение константы	метка

Примечание: значение поля «метка» - TRUE для меток, для обычных констант – не заполняется. На этапе лексического анализа заполняется только поле «значение константы».

4. Таблица вещественных констант.

Таблица вещественных констант

значение константы

5. Таблица однолитерных разделителей.

Таблица однолитерных разделителей

однолитерный разделитель

6. Таблица двухлитерных разделителей.

Таблица двухлитерных разделителей

двухлитерный разделитель

2. 5. Тестирование лексического анализатора.

Тестовая программа.

program Test;

var

i:integer;

r:real;

begin

i:=10;

r:=1E+7;

while i>0 do

begin

r:=r/10;

i:=i-1;

end;

write(r);

end.

Выходной поток токенов.

program 1 1

Id 2 1

; 5 1

var 1 2

Id 2 2

: 5 2

integer 1 3

; 5 1

Id 2 3

: 5 2

real 1 4

; 5 1

begin 1 5

Id 2 2

:= 6 1

Nat 3 1

; 5 1

Id 2 3

:= 6 1

Num 4 1

; 5 1

while 1 6

Id 2 2

rel 5 3

Nat 3 2

do 1 7

begin 1 5

Id 2 3

:= 6 1

Id 2 3

* 5 4

Nat 3 3

; 5 1

Id 2 2

:= 6 1

Id 2 2

+ 5 5

Nat 3 4

; 5 1

end 1 8

; 5 1

write 1 9

( 5 6

Id 2 3

) 5 7

; 5 1

end 1 8

. 5 8

Таблицы лексем («#» - символ конца таблицы лексем).

program

var

integer

real

begin

while

do

end

write

#

Test

i

r

#

10

0

10

1

#

1E+7

#

;

:

>

/

-

(

)

.

#

:=

#

3. Описание этапа синтаксического анализа.

3. 1. Построение КС-грамматики входного языка и разбиение полученной грамматики на подграмматики.

Подграмматики. Класс подграмматик – грамматики слабого предшествования.

1) Подграмматика G (основная грамматика).

Л А Б О Р А Т О Р Н А Я Р А Б О Т А # 2

" Ввод, преобразование и анализ КС-грамматик "

Студент : БЕЗРУКОВ , группа : 0352 .

Сеанс : 7.12.02 , 19:34 .

Файл : "G.TXT" .

ГРАММАТИКА G.

Терминалы :

Def = описания ; Ops = операторы ; pro = program ;

beg = begin ; end = ; ; = ;

. = ; Id = идент-р ;

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

S = 4 ;

Правила :

1) S -> pro Id ; Def beg Ops end .

2) S -> pro Id ; beg Ops end .

3) S -> pro Id ; Def beg end .

4) S -> pro Id ; beg end .

Обработка грамматики возможна;

Конец.

2) Подграмматика G1 (подграмматика раздела описаний).

Л А Б О Р А Т О Р Н А Я Р А Б О Т А # 2

" Ввод, преобразование и анализ КС-грамматик "

Студент : БЕЗРУКОВ , группа : 0352 .

Сеанс : 8.12.02 , 13:21 .

Файл : "G1.TXT" .

ГРАММАТИКА G1.

Терминалы :

lab = label ; con = const ; var = ;

; = ; , = ; : = ;

= = ; Cns = конст. ; Id = идент-р ;

Nat = целое ; [ = ; ] = ;

rea = real ; int = integer ; vec = vector ;

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

Def = 7 ; DL = 1 ;

Lbs = 2 ; L = 1 ;

DC = 2 ; DV = 2 ;

Ids = 2 ; I = 1 ;

Typ = 4 ;

Правила :

1) Def -> lab DL

2) Def -> con DC

3) Def -> var DV

4) Def -> lab DL con DC

5) Def -> lab DL var DV

6) Def -> con DC var DV

7) Def -> lab DL con DC var DV

8) DL -> Lbs ;

9) Lbs -> L

10) Lbs -> Lbs , L

11) L -> Nat

12) DC -> I = Cns ;

13) DC -> DC I = Cns ;

14) DV -> Ids : Typ ;

15) DV -> DV Ids : Typ ;

16) Ids -> I

17) Ids -> Ids , I

18) I -> Id

19) Typ -> rea

20) Typ -> int

21) Typ -> vec [ Id ]

22) Typ -> vec [ Nat ]

Обработка грамматики возможна;

Конец.

3) Подграмматика G2 (подграмматика операторов).

Л А Б О Р А Т О Р Н А Я Р А Б О Т А # 2

" Ввод, преобразование и анализ КС-грамматик "

Студент : БЕЗРУКОВ , группа : 0352 .

Сеанс : 9.12.02 , 9:30 .

Файл : "G2.TXT" .

ГРАММАТИКА G2.

Терминалы :

beg = begin ; end = ; rd = read ;

rdl = readln ; wr = write ; wrl = writeln ;

got = goto ; if = ; the = then ;

els = else ; whi = while ; do = ;

; = ; : = ; ( = ;

) = ; , = ; = = ;

:= = ; Id = идент-р ; Nat = целое ;

rel = отношения ; ArE = ар.выр-е ; CVe = комп.в-ра ;

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

Ops = 2 ; Op = 4 ;

Lab = 1 ; OpC = 2 ;

B = 1 ; E = 1 ;

OpE = 6 ; Op1 = 1 ;

I = 2 ; Op2 = 2 ;

Str = 2 ; Op3 = 2 ;

Out = 1 ; SO = 3 ;

Op4 = 1 ; Op5 = 2 ;

T1 = 1 ; T2 = 1 ;

THE = 1 ; ELS = 1 ;

Op6 = 1 ; WHI = 1 ;

DO = 1 ; Exp = 2 ;

Правила :

1) Ops -> Op

2) Ops -> Ops ; Op

3) Op -> Lab OpE

4) Op -> Lab OpC

5) Op -> OpE

6) Op -> OpC

7) Lab -> Nat :

8) OpC -> B Ops E

9) OpC -> beg end

10) B -> beg

11) E -> end

12) OpE -> Op1

13) OpE -> Op2

14) OpE -> Op3

15) OpE -> Op4

16) OpE -> Op5

17) OpE -> Op6

18) Op1 -> I := ArE

19) I -> Id

20) I -> CVe

21) Op2 -> rd ( Str )

22) Op2 -> rdl ( Str )

23) Str -> I

24) Str -> Str , I

25) Op3 -> wr ( Out )

26) Op3 -> wrl ( Out )

27) Out -> SO

28) SO -> ArE

29) SO -> ArE : ArE

30) SO -> ArE : ArE : ArE

31) Op4 -> got Nat

32) Op5 -> if Exp T1 T2

33) Op5 -> if Exp THE Op

34) T1 -> THE Op

35) T2 -> ELS Op

36) THE -> the

37) ELS -> els

38) Op6 -> WHI Exp DO Op

39) WHI -> whi

40) DO -> do

41) Exp -> ArE rel ArE

42) Exp -> ArE = ArE

Обработка грамматики возможна;

Конец.

4) Подграмматика G3 (подграмматика арифметических выражений).

Л А Б О Р А Т О Р Н А Я Р А Б О Т А # 2

" Ввод, преобразование и анализ КС-грамматик "

Студент : БЕЗРУКОВ , группа : 0352 .

Сеанс : 9.12.02 , 20:23 .

Файл : "G3.TXT" .

ГРАММАТИКА G3.

Терминалы :

+ = ; * = ; ( = ;

) = ; Id = идент-р ; CVe = комп.в-ра ;

Cns = конст. ; VOp = в.опер. ;

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

ArE = 2 ; E = 1 ;

T = 2 ; T1 = 1 ;

P = 5 ;

Правила :

1) ArE -> E T

2) ArE -> T

3) E -> ArE +

4) T -> T1 P

5) T -> P

6) T1 -> T *

7) P -> Cns

8) P -> Id

9) P -> CVe

10) P -> VOp

11) P -> ( ArE )

Обработка грамматики возможна;

Конец.

5. Подграмматика G4 (подграмматика операций над векторами).

Л А Б О Р А Т О Р Н А Я Р А Б О Т А # 2

" Ввод, преобразование и анализ КС-грамматик "

Студент : БЕЗРУКОВ , группа : 0352 .

Сеанс : 7.12.02 , 19:56 .

Файл : "G4.TXT" .

ГРАММАТИКА G4.

Терминалы :

len = length ; sum = ; ms = multscal ;

mc = multconst ; , = ; ( = ;

) = ; Id = идент-р ; Cns = конст. ;

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

VOp = 14 ;

Правила :

1) VOp -> len ( Id )

2) VOp -> len ( VOp )

3) VOp -> sum ( Id , Id )

4) VOp -> sum ( Id , VOp )

5) VOp -> sum ( VOp , Id )

6) VOp -> sum ( VOp , VOp )

7) VOp -> ms ( Id , Id )

8) VOp -> ms ( Id , VOp )

9) VOp -> ms ( VOp , Id )

10) VOp -> ms ( VOp , VOp )

11) VOp -> mc ( Id , Cns )

12) VOp -> mc ( VOp , Cns )

13) VOp -> mc ( Id , Id )

14) VOp -> mc ( VOp , Id )

Обработка грамматики возможна;

Конец.

6. Подграмматика G5 (подграмматика констант).

Л А Б О Р А Т О Р Н А Я Р А Б О Т А # 2

" Ввод, преобразование и анализ КС-грамматик "

Студент : БЕЗРУКОВ , группа : 0352 .

Сеанс : 7.12.02 , 19:56 .

Файл : "G5.TXT" .

ГРАММАТИКА G5.

Терминалы :

Nat = целое ; Num = веществ. ; + = ;

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

Cns = 4 ;

Правила :

1) Cns -> Nat

2) Cns -> + Nat

3) Cns -> Num

4) Cns -> + Num

Обработка грамматики возможна;

Конец.

7. Подграмматика G6 (подграмматика компонент вектора).

Л А Б О Р А Т О Р Н А Я Р А Б О Т А # 2

" Ввод, преобразование и анализ КС-грамматик "

Студент : БЕЗРУКОВ , группа : 0352 .

Сеанс : 7.12.02 , 19:56 .

Файл : "G6.TXT" .

ГРАММАТИКА G6.

Терминалы :

Id = идент-р ; Nat = целое ; ArE = ар.выр-е ;

[ = ; ] = ;

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

CVe = 3 ;

Правила :

1) CVe -> Id [ Id ]

2) CVe -> Id [ Nat ]

3) CVe -> Id [ ArE ]

Обработка грамматики возможна;

Конец.

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

Тетрада				Семантика тетрады
Код операции	Операнд1	Операнд2	Результат
+	A	B	T	T=A+B
-	A	B	T	T=A-B
*	A	B	T	T=A*B
/	A	B	T	T=A/B
-	A		T	T=-A
<	A	B	T	T=A<B
>	A	B	T	T=A>B
<=	A	B	T	T=A<=B
>=	A	B	T	T=A>=B
=	A	B	T	T=A=B
<>	A	B	T	T=A<>B
BLBEG				Начало блока
BLEND				Конец блока
:=	B		A	Присвоить A значение B
DEFL	L			Определение метки L
BRL	L			Безусловный переход на метку L
BF	L	R		Переход на метку L, если R=false
ITOA	I		T	Преобразование типа целыйвещественный
SUBS	A	i	T	Выборка элемента A[i] вектора A
READ	I			Запрос на ввод значения переменной I
WRITE	S	F1	F2	Вывести значение S. Ширина поля вывода F1 (если 0, то число символов S), число дробных цифр F2 (если –1, то выводится число в форме с плавающей точкой).
CR				Возврат каретки
LF				Перевод строки
length	A		T	Определение длины вектора A
sum	A	B	T	Сумма векторов A и B
multscal	A	B	T	Скалярное произведение векторов A и B
multconst	A	B	T	Умножение вектора A на константу B

3. 3. Неформальное описание перевода операторов if и while.

3. 3. 1. Оператор if.

1. Полная форма.

Входная конструкция:		Последовательность тетрад:
IF
<Выражение>		1	Перевод выражения (R – результат)
THEN		2	BF	L1	R
<Операторы>		3	Перевод операторов
ELSE		4	BRL	L2
		5	DEFL	L1
<Операторы>		6	Перевод операторов
		7	DEFL	L2