Разработка формальных грамматик

Разработка формальных грамматик

1. Следуя условиям задания, исходя из заданных операций и их приоритетов, была построена следующая грамматика:

Просмотр выражения и свертка слева-направо.

ВЫРАЖЕНИЕ = А_ВЫР!

Л_ВЫР.

Л_ВЫР = Л_ВЫР «EQU» Л_ОПЕР1! // Операция леворекурсивная=>свертка слева-направо

Л_ОПЕР1.

Л_ОПЕР1 = Л_ОПЕР1 «XOR» Л_ОПЕР2!

Л_ОПЕР1 «OR» Л_ОПЕР2!

Л_ОПЕР2.

Л_ОПЕР2 = Л_ОПЕР2 «AND» Л_ОПЕР3!

Л_ОПЕР3.

Л_ОПЕР3 = «NOT» ЗНАК!

ЗНАК.

ЗНАК = А_ВЫР ОПЕР_СР А_ВЫР.

А_ВЫР = А_ВЫР «+» А_ОПЕР1!

А_ВЫР «-» А_ОПЕР1!

А_ОПЕР1.

А_ОПЕР1 = А_ОПЕР1 «*» А_ОПЕР2!

А_ОПЕР2.

А_ОПЕР2 = А_ОПЕР2 «MOD» А_ОПЕР3!

А_ОПЕР3.

А_ОПЕР3 = А_ОПЕР4 «^» А_ОПЕР3! // Операция праворекурсивная=>свертка справа-налево

А_ОПЕР4.

А_ОПЕР4 = FUNK «(«А_ВЫР «)»!

FUNK «(» ИД_К «)»!

«(» А_ВЫР «)»!

ИД_К.

ИД_К = ИД!

КОНСТ.

ИД = «DOUBLE»!

«INTEGER»!

«STRING».

КОНСТ = «КОНСТ_10»!

«КОНСТ_16»!

«КОНСТ_2».

FUNK = «LEFT»!

«SIN».

ОПЕР_СР = «<»!

«>»!

«<=»!

«>=»!

«<>»!

«=».

EOG

2. Построим матрицу предшествования исходной грамматики в соответствии с требованиями метода параллельного предшествования:

Матрица содержит конфликты:

* строка 1, столбец 31: 1 - конфликт типа =,<

* строка 2, столбец 32: 1 - конфликт типа =,<

* строка 3, столбец 32: 1 - конфликт типа =,<

* строка 6, столбец 36: 1 - конфликт типа =,<

* строка 7, столбец 36: 1 - конфликт типа =,<

* строка 8, столбец 37: 1 - конфликт типа =,<

* строка 11, столбец 29: 1 - конфликт типа =,<

* строка 11, столбец 41: 1 - конфликт типа =,<

* строка 21, столбец 29: 4 - конфликт типа >, X

* строка 22, столбец 29: 4 - конфликт типа >, X

* строка 23, столбец 29: 4 - конфликт типа >, X

* строка 24, столбец 29: 4 - конфликт типа >, X

* строка 25, столбец 29: 4 - конфликт типа >, X

* строка 26, столбец 29: 4 - конфликт типа >, X

* строка 35, столбец 29: 1 - конфликт типа =,<

Отладка

Для наглядности построим дерево:

Конфликт 1-го типа:

Для избежания конфликтов 1-го типа введем новые правила:

Л_ВЫР = Л_ВЫР «EQU» Л_ОПЕР11!

Л_ОПЕР1.

Л_ОПЕР11 = Л_ОПЕР1.

Конфликт ликвидирован и рекурсия сохранена.

При ликвидации конфликтов 1-го типа исчезают конфликты 4-го типа.

Получим новую бесконфликтную грамматику:

ВЫРАЖЕНИЕ = А_ВЫР!

Л_ВЫР.

Л_ВЫР = Л_ВЫР «EQU» Л_ОПЕР11!

Л_ОПЕР1.

Л_ОПЕР11 = Л_ОПЕР1.

Л_ОПЕР1 = Л_ОПЕР1 «XOR» Л_ОПЕР22!

Л_ОПЕР1 «OR» Л_ОПЕР22!

Л_ОПЕР2.

Л_ОПЕР22 = Л_ОПЕР2.

Л_ОПЕР2 = Л_ОПЕР2 «AND» Л_ОПЕР3!

Л_ОПЕР3.

Л_ОПЕР3 = «NOT» ЗНАК!

ЗНАК.

ЗНАК = А_ВЫР ОПЕР_СР А_ВЫР2.

А_ВЫР2 = А_ВЫР.

А_ВЫР = А_ВЫР «+» А_ОПЕР11!

А_ВЫР «-» А_ОПЕР11!

А_ОПЕР1.

А_ОПЕР11 = А_ОПЕР1.

А_ОПЕР1 = А_ОПЕР1 «*» А_ОПЕР22!

А_ОПЕР2.

А_ОПЕР22 = А_ОПЕР2.

А_ОПЕР2 = А_ОПЕР2 «MOD» А_ОПЕР3!

А_ОПЕР3.

А_ОПЕР3 = А_ОПЕР4 «^«А_ОПЕР3!

А_ОПЕР4.

А_ОПЕР4 = FUNK «(» А_ВЫР2»)"!

FUNK «(» ИД_К1»)"!

«(» А_ВЫР2»)»!

ИД_К.

ИД_К1 = ИД_К.

ИД_К = ИД!

КОНСТ.

ИД = «DOUBLE»!

«INTEGER»!

«STRING».

КОНСТ = «КОНСТ_10»!

«КОНСТ_16»!

«КОНСТ_2».

FUNK = «LEFT»!

«SIN».

ОПЕР_СР = «<»!

«>»!

«<=»!

«>=»!

«<>»!

«=».

EOG

Построим матрицу предшествования бесконфликтной грамматики:

4. Разработка сканера

1) Определяем лексемы языка

Табл.1. Лексемы языка

Обозначение лексемы	Смысл лексемы
конст_10	Десятичная константа
конст_16	Шестнадцатеричная константа (префикс &H)
конст_2	Двоичная константа (префикс &B)
ид_р	Идентификатор (integer, double или string)
sin	Синус вещественного числа
left	Функция работы со строками
not	Логическое «НЕ»
and	Логическое «И»
or	Логическое «ИЛИ»
xor	Исключающее «ИЛИ»
разделитель	Пробел
+	Арифметическая операция сложения
-	Арифметическая операция вычитания
*	Арифметическая операция умножения
mod	Арифметическая операция целочисленное деление
^	Арифметическая операция возведения в степень
оо	Операция отношения (результат - логический)
(	Открывающая скобка
)	Закрывающая скобка

2) Разрабатываем базу данных сканера

Табл.2. Таблица одно-литерных		Табл.3. Таблица классов литер
терминальных символов
ТТС1		KTL
«а» … «z» «A» «C» … «K» «M» … «Z»	Буквы	б		б	0
				«B»	1
				д	2
				н	3
				р	4
				«+»	5
				«-»	6
				«*»	7
				«^»	8
«H»	Шестнадцатеричный префикс	«H»		«=»	9
«B»	Двоичный префикс	«B»		«<»	10
«0» «1»	Двоичные цифры	д		«>»	11
				«#»	12
«2» … «9»	Недвоичные цифры	н		«%»	13
				«$»	14
				«(»	15
«»	Разделитель (пробел)	р		«)»	16
«+»	Сложение	«+»		«.»	17
«-»	Вычитание	«-»		«ы»	18
«*»	Умножение	«*»		«H»	19
«^»	Степень	«^»		Табл.4. Таблица типов лексем
«<»	Меньше	«<»
«>»	Больше	«>»		TLE
«=»	Равно	«=»		конст_10	0
«#»	Суффикс double	«#»		конст_16	1
«%»	Суффикс integer	«%		конст_2	2
«$»	Суффикс string	«$»		ид_р	3
«(»	Открывающая скобка	«(»		sin	4
«)»	Закрывающая скобка	«)»		left	5
«.»	Точка	«.»		not	6
	Недопустимый символ	х		and	7
	Конец файла	ы		or	8
				xor	9
Табл.5. Таблица ключевых слов			equ	10
			разделитель	11
ТКС			+	12
sin			-	13
left			*	14
not			mod	15
and			^	16
or			оо	17
xor			(	18
equ			)	19
mod

Временные таблицы:

Табл.6. Таблица идентификаторов
ТИ
Ид	описатели	адр
	тип	точка	точность	осн
Табл.7. Таблица констант
ТК
конст	описатели
	тип	точка	точность	осн
Табл.8. Таблица операций и специальных символов
ТОС
символ
Табл.9. Таблица стандартных символов
ТСС
TLE	ALE

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

конст_10

S = нD₁! дD₁.

D₁ = нD₁! дD₁!». «D₂! е.

D₂ = нD₃! дD₃.

D₃ = нD₃! дD₃! е.

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



конст_2

S = «&«B₀.

B₀ = «B» B₁.

B₁ = дB₂.

B₂ = дB₂!». «B₃! е.

B₃ = дB₄.

B₄ = дB₄! е.

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

конст_16

S = «&«B₀.

B₀ = «H» H₁.

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

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

ид_р

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

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

A₂ = е.

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

sin

S = «s» A₄.

A₄ = «i» A₅.

A₅ = «n» A₆.

A₆ = е₄.

е₄ = р! «(».



left

S = «l» A₇.

A₇ = «e» A₈.

A₈ = «f» A₉.

A₉ = «t» A10.

A10 = е₄.

е₄ = р! «(».

not

S = «n» A₁₁.

A₁₁ = «o» A₁₂.

A₁₂ = «t» A₁₃.

A₁₃ = е₄.

е₄ = р! «(».

and

S = «a» A₁₄.

A₁₄ = «n» A₁₅.

A₁₅ = «d» A₁₆.

A₁₆ = е₄.

е₄ = р! «(».

or

S = «o» A₁₇.

A₁₇ = «r» A₁₈.

A₁₈ = е₄.

е₄ = р! «(».

xor

S = «x» A₁₉.

A₁₉ = «o» A₂₀.

A₂₀ = «r» A_21.

A₂₁ = е₄.

е₄ = р! «(».



equ

S = «e» A₂₂.

A₂₂ = «q» A₂₃.

A₂₃ = «u» A_24.

A₂₄ = е₄.

е₄ = р! «(».

разделитель

S = рR₁.

R₁ = рR₁! e₀

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

+

S = «+«U₁.

U₁ = e₃.

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



-

S = «- «U₁.

U₁ = e₃.

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

*

S = «*«U₁.

U₁ = e₃.

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

mod

S = «mod» U₁.

U₁ = e₃.

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

S = «^«U₁.

U₁ = e₃.

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

оо

S = «<«O₁! «>«O₂! «=«O₃.

O₁ = «>«O₄! «=«O₄! e₃.

O₂ = «=«O₅! e₃.

O₄ = e₃.

O₅ = e₃.

O₃ = e₃.

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

(

S = «(«K₁.

K₁ = e₂.

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



)

S =»)«K₂.

K₂ = e.

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

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

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

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

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

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

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

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

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

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

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

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

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

Табл.10. Таблица идентификаторов
ТИ
ид	описатели	адр
	тип	точка	точность	осн
Aa%	Integer	0	2	10	0
Bb#	Double	1	16	10	2
Табл.11. Таблица констант
ТК
конст	Описатели
	тип	точка	точность	осн
2	Integer	0	0	10
&B01	Bin	0	0	2
2	Integer	0	0	10
3	Integer	0	0	10
4	Integer	0	0	10
10	Integer	0	0	10
&H0	Hex	0	0	16
Табл.12. Таблица операций и специальных символов
ТОС
Символ
(
Sin
(
*
-
)
<
)
And
(
+
+
<
)
Xor

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