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