3) Каждый тип лексических единиц описываем с помощью автоматной грамматики и для каждой грамматики составляем эквивалентный ей конечный автомат.

конст_10

S = нD1! дD1.

D1 = нD1! дD1!». «D2! е.

D2 = нD3! дD3.

D3 = нD3! дD3! е.

е = «"! «*»!» -"! «+»! «*»! «/"! «^»!»)"! «=»! «<»! «>».

конст_2

S = «&«B0.

B0 = «B» B1.

B1 = дB2.

B2 = дB2!». «B3! е.

B3 = дB4.

B4 = дB4! е.

е = «"! «*»!» -"! «+»! «*»! «/"! «^»!»)"! «=»! «<»! «>».

конст_16

S = «&«B0.

B0 = «H» H1.

H1 = дH1! нH1! «A" H1! «B» H1! «C» H1! «D» H1! «E» H1! «F» H1! е.

е = «"! «*»!» -"! «+»! «*»! «/"! «^»!»)"! «=»! «<»! «>».

ид_р

S = бА! «B» A! «H» A.

А = бА! нА! дА! «A» A! «B» A! «C» A! «D» A! «E» A! «F» A! «H» A! «%«A2! «&«A2! «$«A2.

A2 = е.

е = «"! «*»!» -"! «+»! «*»! «/"! «^»!»)"! «=»! «<»! «>».

sin

S = «s» A4.

A4 = «i» A5.

A5 = «n» A6.

A6 = е4.

е4 = р! «(».

left

S = «l» A7.

A7 = «e» A8.

A8 = «f» A9.

A9 = «t» A10.

A10 = е4.

е4 = р! «(».

not

S = «n» A11.

A11 = «o» A12.

A12 = «t» A13.

A13 = е4.

е4 = р! «(».

and

S = «a» A14.

A14 = «n» A15.

A15 = «d» A16.

A16 = е4.

е4 = р! «(».

or

S = «o» A17.

A17 = «r» A18.

A18 = е4.

е4 = р! «(».

xor

S = «x» A19.

A19 = «o» A20.

A20 = «r» A21.

A21 = е4.

е4 = р! «(».

equ

S = «e» A22.

A22 = «q» A23.

A23 = «u» A24.

A24 = е4.

е4 = р! «(».

разделитель

S = рR1.

R1 = рR1! e0

e0 - любой символ из ТТС1

+

S = «+«U1.

U1 = e3.

e3 = б! «B»! «H»! д! н! р! «&»! «(».

-

S = «- «U1.

U1 = e3.

e3 = б! «B»! «H»! д! н! р! «&»! «(».

*

S = «*«U1.

U1 = e3.

e3 = б! «B»! «H»! д! н! р! «&»! «(».

mod

S = «mod» U1.

U1 = e3.

e3 = б! «B»! «H»! д! н! р! «&»! «(».

S = «^«U1.

U1 = e3.

e3 = б! «B»! «H»! д! н! р! «&»! «(».

оо

S = «<«O1! «>«O2! «=«O3.

O1 = «>«O4! «=«O4! e3.

O2 = «=«O5! e3.

O4 = e3.

O5 = e3.

O3 = e3.

e3 = б! «B»! «H»! д! н! р! «&»! «(».

(

S = «(«K1.

K1 = e2.

e2 = б! «B»! «H»! д! н! р! «+»!» -"! «&»! «(».

)

S =»)«K2.

K2 = e.

е = «"! «*»!» -"! «+»! «*»! «^»!»)"! «=»! «<»! «>».

4) Описываем использованные в сканере подпрограммы:

end - Процедура окончания работы сканера

podgot - Процедура производит общую подготовку сканера к работе

tip - Процедура устанавливает тип литеры

vkl - Процедура добавляет текущую литеру в текущую лексему

cll - Процедура считывает из файла очередную литеру

zaptab - Процедура проверяет наличие текущей лексемы в таблице ключевых слов

out - Процедура заполняет основные таблицы

6) Пример работы сканера

Исходное выражение:

(sin (2*aa%-&B01)<bb#) and (2+3+4<10) xor &H0

Заполненные в результате работы сканера таблицы:

5. Синтаксический анализ выражения, которое использовалось в п. 2

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

1) выделение синтаксической конструкции

2) классификация синтаксической конструкции

3) определение синтаксической ошибки и, возможно, ее нейтрализация

4) в процессе синтаксического анализа формируется некоторая внутренняя форма представления программы.

Метод параллельного предшествования:

Отношение предшествования, используемые в методе параллельного предшествования:

< аналог отношения простого предшествования

= два символа входят в простую фразу

X>1Y, X - последний символ фразы, Y - следует за Х и находится правее соответствующей простой фразы и Y не является первым символом простой фразы.

X><Y, X - последний символ простой фразы, Y - первый символ следующей простой фразы (Y следует за X)

(>1)=(LAST) (=)

(><)=(LAST) (=) FIRST

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

В алгоритме используются следующие обозначения:

TL - текущая литера

NTL - номер текущей литеры

PL - предыдущая литера

ST - следующая литера

SL - стек результата

ST2 - стек преобразований

ST.SIZE - размер стека

ST.PUSH - добавить в «голову» стека

ST.POP - взять (удалить) из «головы» стека

ST.RESET - очистить стек.

Блоки 2-4 производят инициализацию очереди (установка в начальное положение)

Блоки 5-6 производится проверка на наличие отношений между символами, если таковых не существует, то ошибка, иначе продолжается анализ

Блоки 7-10 осуществляется поиск простой фразы

Блоки 10-14 осуществляется редукция простой фразы на левую часть G[i]. 1 правило i из грамматики G

Блоки 15-17 осуществляется сохранение результата редукции и переход на следующий элемент

Блок 18 осуществляется проверка на окончание строки

Блоки 19-23 осуществляется проверка на окончание анализа, если анализ окончен, УСПЕХ, иначе сохранение результата и перевод в начало.

Сентенциальная форма:

1)# NOT A% MOD 5 < C# AND M% ^ 6 ^ I% - SIN (&HA09B + B# - C% * D#) + &B1 > 0 #

2)# NOT ИД MOD конст_10 о_ср ИД AND ИД^ конст_10^ ИД - FUNK (конст_16+ ИД- ИД* ИД)+ конст_2 о_ср ИД #

3)# NOT ИД_К MOD ИД_К о_ср ИД_К AND ИД_К^ИДК^ИДК-FUNK (ИД_К+ ИД_К-ИД_К*ИД_К)+ ИД_К о_ср ИД_К #

4)# NOT A_4 MOD A_4 o_cp A_4 AND A_4^ A_4^ A_4 - FUNK (A_4+ A_4 - A_4* A_4)+ A_4 o_cp A_4 #

5)# NOT A_3 MOD A_3 o_cp A_3 AND A_4^ A_^ A_3 - FUNK (A_3 + A_3 - A_3 * A_3)+ A_3 o_cp A_3 #

6)# NOT A_2 MOD A_3 o_cp A_2 AND A_4^ A_3 - FUNK (A_2 + A_2 - A_2 * A_2)+ A_2 o_cp A_2 #

7)# NOT A_2 o_cp A_1 AND A_3 - FUNK (A_1 + A_1 - A_2 * A_1)+ A_1 o_cp A_1 #

8)# NOT A_1 o_cp A_B AND A_2 - FUNK (A_B + A_1 - A_1)+ A_1 o_cp A_B #

9)# NOT A_B o_cp A_B AND A_1 - FUNK (A_B - A_1)+ A_1 o_cp A_B #

10)# NOT ЗНАК AND A_B - FUNK (A_B)+ A_1 o_cp A_B #

11)# Л_3 AND A_B - FUNK (A_B)+ A_1 o_cp A_B #

12)# Л_2 AND A_B - A_4 + A_1 o_cp A_B #

13)# Л_2 AND A_B - A_3 + A_1 o_cp A_B #

14)# Л_2 AND A_B - A_2 + A_1 o_cp A_B #

15)# Л_2 AND A_B - A_1 + A_1 o_cp A_B #

16)# Л_2 AND A_B + A_1 o_cp A_B #

17)# Л_2 AND A_B o_cp A_B #

18)# Л_2 AND ЗНАК #

19) # Л_2 AND Л_3

20) # Л_2 #

21) # Л_1 #

22) # Л_B #

23) #ВЫРАЖЕНИЕ#

Простые фразы:

1) A%, 5, C#, M%, 6, I%, SIN, &HA09B, B#, C%, D#, &B1, >, 0

2) ИД, конст_10, ИД, ИД, конст_10, ИД, конст_16, ИД, ИД, ИД, конст_2, конст_10

3) ИД_К, ИД_К, ИД_К, ИД_К, ИД_К, ИД_К, ИД_К, ИД_К, ИД_К, ИД_К, ИД_К, ИД_К

4) A_4, A_4, A_4, A_4, A_4

5) A_3, A_3, A_4^ A_3, A_3, A_3, A_3, A_3, A_3, A_3

6) A_2 MOD A_3, A_2, A_4^ A_3, A_2, A_2, A_2, A_2, A_2

Страницы: 1, 2