Рефераты Главная Начертательная геометрия Оккультизм и уфология Педагогика Полиграфия Политология Программированиекомпьютеры и кибернетика Производство и технологии Социальная работа Начертательная геометрия Не сортированные Таможенная система Теория государства и права Арбитражный процесс Реклама Нотариат Менеджмент Металлургия Минералогия Москвоведение |
Разработка формальных грамматикРазработка формальных грамматикРазработка формальных грамматик 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. Лексемы языка
2) Разрабатываем базу данных сканера
Временные таблицы:
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)<bb#) and (2+3+4<10) xor &H0 Заполненные в результате работы сканера таблицы:
5. Синтаксический анализ выражения, которое использовалось в п. 2 Синтаксический анализ выполняет определенные функции: 1) выделение синтаксической конструкции 2) классификация синтаксической конструкции 3) определение синтаксической ошибки и, возможно, ее нейтрализация 4) в процессе синтаксического анализа формируется некоторая внутренняя форма представления программы. Метод параллельного предшествования: Отношение предшествования, используемые в методе параллельного предшествования: < аналог отношения простого предшествования = два символа входят в простую фразу X>1Y, X - последний символ фразы, Y - следует за Х и находится правее соответствующей простой фразы и Y не является первым символом простой фразы. X><Y, 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 A_4 MOD A_4 o_cp A_4 AND A_4^ A_4^ A_4 - FUNK (A_4+ A_4 - A_4* A_4)+ A_4 o_cp A_4 # 5)# NOT A_3 MOD A_3 o_cp A_3 AND A_4^ A_^ A_3 - FUNK (A_3 + A_3 - A_3 * A_3)+ A_3 o_cp A_3 # 6)# NOT A_2 MOD A_3 o_cp A_2 AND A_4^ A_3 - FUNK (A_2 + A_2 - A_2 * A_2)+ A_2 o_cp A_2 # 7)# NOT A_2 o_cp A_1 AND A_3 - FUNK (A_1 + A_1 - A_2 * A_1)+ A_1 o_cp A_1 # 8)# NOT A_1 o_cp A_B AND A_2 - FUNK (A_B + A_1 - A_1)+ A_1 o_cp A_B # 9)# NOT A_B o_cp A_B AND A_1 - FUNK (A_B - A_1)+ A_1 o_cp A_B # 10)# NOT ЗНАК AND A_B - FUNK (A_B)+ A_1 o_cp A_B # 11)# Л_3 AND A_B - FUNK (A_B)+ A_1 o_cp A_B # 12)# Л_2 AND A_B - A_4 + A_1 o_cp A_B # 13)# Л_2 AND A_B - A_3 + A_1 o_cp A_B # 14)# Л_2 AND A_B - A_2 + A_1 o_cp A_B # 15)# Л_2 AND A_B - A_1 + A_1 o_cp A_B # 16)# Л_2 AND A_B + A_1 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) A_4, A_4, A_4, A_4, A_4 5) A_3, A_3, A_4^ A_3, A_3, A_3, A_3, A_3, A_3, A_3 6) A_2 MOD A_3, A_2, A_4^ A_3, A_2, A_2, A_2, A_2, A_2 |
|
