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