Разработка формальных грамматик (стр. 1 из 3)
Разработка формальных грамматик
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-го типа:
 |
 | |||
 | |||
| Обозначение лексемы | Смысл лексемы |
| конст_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 = нD1! дD1.
D1 = нD1! дD1!». «D2! е.
D2 = нD3! дD3.
D3 = нD3! дD3! е.
е = «"! «*»!» –"! «+»! «*»! «/"! «^»!»)"! «=»! «<»! «>».
| н,д |
