Реферат: Разработка формальных грамматик
Разработкаформальных грамматик
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-го типа:
/> /> /> /> /> /> /> /> /> />Л ВЫР
/> /> /> /> /> /> <td/> /> /> /> />Для избежания конфликтов 1-го типа введем новыеправила:
Л_ВЫР = Л_ВЫР «EQU» Л_ОПЕР11!
Л_ОПЕР1.
Л ВЫР
Л_ОПЕР11 = Л_ОПЕР1./>/>
Л ВЫР
Л ОПЕР11
“EQU”
Конфликт ликвидирован и рекурсия сохранена./> /> /> /> /> /> /> /> /> /> /> /> /> /> <td/> /> /> />Л ОПЕР1
/> /> <td/> /> /> /> /> /> />При ликвидации конфликтов 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» 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 «#» Суффикс 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! е.
е = «"! «*»!» –"! «+»!«*»! «/"! «^»!»)"! «=»! «<»! «>».
/> /> /> /> /> /> /> /> /> <td/>
н, д
<td/>н, д
/> /> /> /> /> /> />· конст_2
S = «&«B0.
B0= «B» B1.
B1= дB2.
B2= дB2!». «B3! е.
B3= дB4.
B4= дB4! е.
е = «"! «*»!» –"!«+»! «*»! «/"! «^»!»)"! «=»! «<»! «>».
/> /> /> /> /> /> /> /> /> /> /> /> /> />е
<td/> /> /> <td/> /> /> /> /> <td/> />· конст_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 = е.
е = «"! «*»!»–"! «+»! «*»! «/"! «^»!»)"! «=»! «<»! «>».
/> <td/>б, н, д,«A»..«F»,«H»
/> /> /> /> /> /> /> /> /> /> /> /> /> /> <td/>«s»
<td/>«i»
<td/>«n»
<td/>е4
· 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= р!«(».
/> /> /> /> /> /> /> /> /> /> /> /> /> /> /> <td/> /> <td/> /> /> <td/> <td/> <td/> <td/> /> />/>/>/>/>
· 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
/> /> /> /> /> <td/>р
/> /> />· +
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
Заполненные в результате работысканера таблицы:
Табл.10. Таблица идентификаторов
ТИ
ид описатели адр тип точка точность осн Aa% Integer 2 10 Bb# Double 1 16 10 2 Табл.11. Таблица константТК
конст Описатели тип точка точность осн 2 Integer 10 &B01 Bin 2 2 Integer 10 3 Integer 10 4 Integer 10 10 Integer 10 &H0 Hex 16 Табл.12. Таблица операций и специальных символов
ТОС
Символ ( Sin ( * - ) < ) And ( + + < ) Xor /> /> /> /> /> /> /> /> />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_4o_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_3o_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_3o_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_cpA_1 AND A_3 – FUNK (A_1 + A_1 – A_2 * A_1)+ A_1 o_cp A_1 #
8)# NOT A_1 o_cpA_B AND A_2 – FUNK (A_B + A_1 – A_1)+ A_1 o_cp A_B #
9)# NOT A_B o_cpA_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