Разработка формальных грамматик
Разработка формальных грамматик 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 | | | | | | | |
Страницы: 1, 2
| 
