Разработка формальных грамматик
Определение синтаксической ошибки и, возможно, ее нейтрализация. При ликвидации конфликтов 1-го типа исчезают конфликты 4-го типа. Podgot — Процедура производит общую подготовку сканера к работе. Синтаксический анализ выражения, которое использовалось в п. 2. Построим матрицу предшествования бесконфликтной грамматики: ИД, конст10, ИД, ИД, конст10, ИД, конст16, ИД, ИД, ИД, конст2, конст10. А = бА… Читать ещё >
Разработка формальных грамматик (реферат, курсовая, диплом, контрольная)
Разработка формальных грамматик
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» | Буквы | б | б | ||||
«B» | |||||||
д | |||||||
н | |||||||
р | |||||||
«+» | |||||||
«-» | |||||||
«*» | |||||||
«^» | |||||||
«H» | Шестнадцатеричный префикс | «H» | «=» | ||||
«B» | Двоичный префикс | «B» | «<�» | ||||
«0» «1» | Двоичные цифры | д | «>» | ||||
«#» | |||||||
«2» … «9» | Недвоичные цифры | н | «%» | ||||
«$» | |||||||
«(» | |||||||
«« | Разделитель (пробел) | р | ")" | ||||
«+» | Сложение | «+» | «.» | ||||
«-» | Вычитание | «-» | «ы» | ||||
«*» | Умножение | «*» | «H» | ||||
«^» | Степень | «^» | Табл.4. Таблица типов лексем | ||||
«<�» | Меньше | «<�» | |||||
«>» | Больше | «>» | TLE | ||||
«=» | Равно | «=» | конст10 | ||||
«#» | Суффикс double | «#» | конст16 | ||||
«%» | Суффикс integer | «% | конст2 | ||||
«$» | Суффикс string | «$» | ид_р | ||||
«(» | Открывающая скобка | «(» | sin | ||||
")" | Закрывающая скобка | ")" | left | ||||
«.» | Точка | «.» | not | ||||
Недопустимый символ | х | and | |||||
Конец файла | ы | or | |||||
xor | |||||||
Табл.5. Таблица ключевых слов | equ | ||||||
разделитель | |||||||
ТКС | |||||||
sin | ; | ||||||
left | * | ||||||
not | mod | ||||||
and | ^ | ||||||
or | оо | ||||||
xor | ( | ||||||
equ | ) | ||||||
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 = р! «(».
and
S = «a» A14.
A14 = «n» A15.
A15 = «d» A16.
A16 = е4.
е4 = р! «(».
or
S = «o» A17.
A17 = «r» A18.
A18 = е4.
е4 = р! «(».
xor
S = «x» A19.
A19 = «o» A20.
A20 = «r» A21.
A21 = е4.
е4 = р! «(».
equ
S = «e» A22.
A22 = «q» A23.
A23 = «u» A24.
A24 = е4.
е4 = р! «(».
разделитель
S = рR1.
R1 = рR1! e0
e0 — любой символ из ТТС1
S = «+"U1.
U1 = e3.
e3 = б! «B»! «H»! д! н! р! «&»! «(».
;
S = «- «U1.
U1 = e3.
e3 = б! «B»! «H»! д! н! р! «&»! «(».
*
S = «*"U1.
U1 = e3.
e3 = б! «B»! «H»! д! н! р! «&»! «(».
mod
S = «mod» U1.
U1 = e3.
e3 = б! «B»! «H»! д! н! р! «&»! «(».
S = «^"U1.
U1 = e3.
e3 = б! «B»! «H»! д! н! р! «&»! «(».
оо
S = «<�"O1! «>"O2! «="O3.
O1 = «>"O4! «="O4! e3.
O2 = «="O5! e3.
O4 = e3.
O5 = e3.
O3 = e3.
e3 = б! «B»! «H»! д! н! р! «&»! «(».
(
S = «("K1.
K1 = e2.
e2 = б! «B»! «H»! д! н! р! «+»!" -" ! «&»! «(».
)
S =")"K2.
K2 = e.
е = «» ! «*»!" -" ! «+»! «*»! «^»!")" ! «=»! «<�»! «>».
4) Описываем использованные в сканере подпрограммы:
end — Процедура окончания работы сканера
podgot — Процедура производит общую подготовку сканера к работе
tip — Процедура устанавливает тип литеры
vkl — Процедура добавляет текущую литеру в текущую лексему
cll — Процедура считывает из файла очередную литеру
zaptab — Процедура проверяет наличие текущей лексемы в таблице ключевых слов
out — Процедура заполняет основные таблицы
6) Пример работы сканера
Исходное выражение:
(sin (2*aa%-&B01)<10) xor &H0
Заполненные в результате работы сканера таблицы:
Табл.10. Таблица идентификаторов | ||||||
ТИ | ||||||
ид | описатели | адр | ||||
тип | точка | точность | осн | |||
Aa% | Integer | |||||
Bb# | Double | |||||
Табл.11. Таблица констант | ||||||
ТК | ||||||
конст | Описатели | |||||
тип | точка | точность | осн | |||
Integer | ||||||
&B01 | Bin | |||||
Integer | ||||||
Integer | ||||||
Integer | ||||||
Integer | ||||||
&H0 | Hex | |||||
Табл.12. Таблица операций и специальных символов | ||||||
ТОС | ||||||
Символ | ||||||
( | ||||||
Sin | ||||||
( | ||||||
* | ||||||
; | ||||||
) | ||||||
< | ||||||
) | ||||||
And | ||||||
( | ||||||
< | ||||||
) | ||||||
Xor | ||||||
5. Синтаксический анализ выражения, которое использовалось в п. 2
Синтаксический анализ выполняет определенные функции:
1) выделение синтаксической конструкции
2) классификация синтаксической конструкции
3) определение синтаксической ошибки и, возможно, ее нейтрализация
4) в процессе синтаксического анализа формируется некоторая внутренняя форма представления программы.
Метод параллельного предшествования:
Отношение предшествования, используемые в методе параллельного предшествования:
< аналог отношения простого предшествования
= два символа входят в простую фразу
X>1Y, X — последний символ фразы, Y — следует за Х и находится правее соответствующей простой фразы и Y не является первым символом простой фразы.
X>
(>1)=(LAST) (=)
(><)=(LAST) (=) FIRST
Входная цепочка представляется в виде очереди, каждый элемент которой имеет два поля: S — символ цепочки и nx — указатель на следующий символ.
В алгоритме используются следующие обозначения:
TL — текущая литера
NTL — номер текущей литеры
PL — предыдущая литера
ST — следующая литера
SL — стек результата
ST2 — стек преобразований
ST.SIZE — размер стека
ST.PUSH — добавить в «голову» стека
ST.POP — взять (удалить) из «головы» стека
ST.RESET — очистить стек.
Блоки 2−4 производят инициализацию очереди (установка в начальное положение) Блоки 5−6 производится проверка на наличие отношений между символами, если таковых не существует, то ошибка, иначе продолжается анализ Блоки 7−10 осуществляется поиск простой фразы Блоки 10−14 осуществляется редукция простой фразы на левую часть G[i]. 1 правило i из грамматики G
Блоки 15−17 осуществляется сохранение результата редукции и переход на следующий элемент Блок 18 осуществляется проверка на окончание строки Блоки 19−23 осуществляется проверка на окончание анализа, если анализ окончен, УСПЕХ, иначе сохранение результата и перевод в начало.
Сентенциальная форма:
1)# NOT A% MOD 5 < C# AND M% ^ 6 ^ I% - SIN (&HA09B + B# - C% * D#) + &B1 > 0 #
2)# NOT ИД MOD конст10 о_ср ИД AND ИД^ конст10^ ИД — FUNK (конст16+ ИДИД* ИД)+ конст2 о_ср ИД #
3)# NOT ИД_К MOD ИД_К о_ср ИД_К AND ИД_К^ИДК^ИДК-FUNK (ИД_К+ ИД_К-ИД_К*ИД_К)+ ИД_К о_ср ИД_К #
4)# NOT A4 MOD A4 o_cp A4 AND A4^ A4^ A4 — FUNK (A4+ A4 — A4* A4)+ A4 o_cp A4 #
5)# NOT A3 MOD A3 o_cp A3 AND A4^ A_^ A3 — FUNK (A3 + A3 — A3 * A3)+ A3 o_cp A3 #
6)# NOT A2 MOD A3 o_cp A2 AND A4^ A3 — FUNK (A2 + A2 — A2 * A2)+ A2 o_cp A2 #
7)# NOT A2 o_cp A1 AND A3 — FUNK (A1 + A1 — A2 * A1)+ A1 o_cp A1 #
8)# NOT A1 o_cp A_B AND A2 — FUNK (A_B + A1 — A1)+ A1 o_cp A_B #
9)# NOT A_B o_cp A_B AND A1 — FUNK (A_B — A1)+ A1 o_cp A_B #
10)# NOT ЗНАК AND A_B — FUNK (A_B)+ A1 o_cp A_B #
11)# Л3 AND A_B — FUNK (A_B)+ A1 o_cp A_B #
12)# Л2 AND A_B — A4 + A1 o_cp A_B #
13)# Л2 AND A_B — A3 + A1 o_cp A_B #
14)# Л2 AND A_B — A2 + A1 o_cp A_B #
15)# Л2 AND A_B — A1 + A1 o_cp A_B #
16)# Л2 AND A_B + A1 o_cp A_B #
17)# Л2 AND A_B o_cp A_B #
18)# Л2 AND ЗНАК #
19) # Л2 AND Л3
20) # Л2 #
21) # Л1 #
22) # Л_B #
23) #ВЫРАЖЕНИЕ#
Простые фразы:
1) A%, 5, C#, M%, 6, I%, SIN, &HA09B, B#, C%, D#, &B1, >, 0
2) ИД, конст10, ИД, ИД, конст10, ИД, конст16, ИД, ИД, ИД, конст2, конст10
3) ИД_К, ИД_К, ИД_К, ИД_К, ИД_К, ИД_К, ИД_К, ИД_К, ИД_К, ИД_К, ИД_К, ИД_К
4) A4, A4, A4, A4, A4
5) A3, A3, A4^ A3, A3, A3, A3, A3, A3, A3
6) A2 MOD A3, A2, A4^ A3, A2, A2, A2, A2, A2