Разработка формальных грамматик
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 = н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 = р! «(».
