Разработка формальных грамматик
Разработка формальных грамматик
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-го типа:
Л ВЫР
Л ВЫР
“EQU”
Л ОПЕР1
Л ОПЕР1
Л ОПЕР1
“OR”
Л ОПЕР2
Для избежания конфликтов 1-го типа введем новые правила:
Л_ВЫР = Л_ВЫР «EQU» Л_ОПЕР11!
Л_ОПЕР1.
Л ВЫР
Л_ОПЕР11 = Л_ОПЕР1.
К
Л ВЫР
“EQU”
Л ОПЕР11
онфликт ликвидирован и рекурсия сохранена.
Л ОПЕР1
Л ОПЕР1
Л ОПЕР1
“OR”
Л ОПЕР2
При ликвидации конфликтов 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 = нD>1>! дD>1>.
D>1> = нD>1>! дD>1>!». «D>2>! е.
D>2> = нD>3>! дD>3>.
D>3> = нD>3>! дD>3>! е.
е = «"! «*»!» –"! «+»! «*»! «/"! «^»!»)"! «=»! «<»! «>».
н,д
н,д
D>1>
F
н,д
"."
н,д
е
D>2>
D>3>
S
е
конст_2
S = «&«B>0>.
B>0> = «B» B>1>.
B>1> = дB>2>.
B>2> = дB>2>!». «B>3>! е.
B>3> = дB>4>.
B>4> = дB>4>! е.
е = «"! «*»!» –"! «+»! «*»! «/"! «^»!»)"! «=»! «<»! «>».
д
д
S
"&"
B>0>
B>2>
B>3>
B>4>
F
"B"
д
"."
е
S
B>1>
д
е
конст_16
S = «&«B>0>.
B>0> = «H» H>1>.
H>1> = дH>1>! нH>1>! «A" H>1>! «B» H>1>! «C» H>1>! «D» H>1>! «E» H>1>! «F» H>1>! е.
е = «"! «*»!» –"! «+»! «*»! «/"! «^»!»)"! «=»! «<»! «>».
д,н,"A".."F"
S
"&"
B>0>
F
"H"
е
S
H>1>
ид_р
S = бА! «B» A! «H» A.
А = бА! нА! дА! «A» A! «B» A! «C» A! «D» A! «E» A! «F» A! «H» A! «%«A>2>! «&«A>2>! «$«A>2.>
A>2> = е.
е = «"! «*»!» –"! «+»! «*»! «/"! «^»!»)"! «=»! «<»! «>».
б,н,д,"A".."F","H"
S
б,"B","H"
A
A>2>
F
"%","&","$"
е
е>4>
"s"
"i"
"n"
sin
S = «s» A>4>.
A>4> = «i» A>5>.
A>5> = «n» A>6>.
A>6> = е>4>.
е>4> = р! «(».
S
A>4>
A>5>
A>6>
F
left
S = «l» A>7>.
A>7> = «e» A>8>.
A>8> = «f» A>9>.
A>9> = «t» A10.
A10 = е>4>.
е>4> = р! «(».
S
A>7>
A>8>
A>9>
A10
"l"
"e"
"f"
"t"
F
е>4>
not
S = «n» A>11>.
A>11> = «o» A>12>.
A>12> = «t» A>13>.
A>13> = е>4>.
е>4> = р! «(».
S
A>1>>1>
A>1>>2>
A>1>>3>
F
"n"
"o"
"t"
е>4>
and
S = «a» A>14>.
A>14> = «n» A>15>.
A>15> = «d» A>16>.
A>16> = е>4>.
е>4> = р! «(».
S
A>1>>4>
A>1>>5>
A>1>>6>
F
"a"
"n"
"d"
е>4>
or
S = «o» A>17>.
A>17> = «r» A>18>.
A>18> = е>4>.
е>4> = р! «(».
S
A>1>>7>
A>1>>8>
F
"o"
"r"
е>4>
xor
S = «x» A>19>.
A>19> = «o» A>20>.
A>20> = «r» A>21.>
A>21 >= е>4>.
е>4> = р! «(».
S
A19
A20
A21
F
"x"
"o"
"r"
е>4>
equ
S = «e» A>22>.
A>22> = «q» A>23>.
A>23> = «u» A>24.>
A>24 >= е>4>.
е>4> = р! «(».
S
A22
A23
A24
F
"e"
"q"
"u"
е>4>
разделитель
S = рR>1>.
R>1> = рR>1>! e>0>
e>0> – любой символ из ТТС1
р
e>0>
S
р
F
R>1>
+
S = «+«U>1>.
U>1> = e>3>.
e>3> = б! «B»! «H»! д! н! р! «&»! «(».
"+"
e>3>
S
F
U>1>
-
S = «– «U>1>.
U>1> = e>3>.
e>3> = б! «B»! «H»! д! н! р! «&»! «(».
"-"
e>3>
S
F
U>1>
*
S = «*«U>1>.
U>1> = e>3>.
e>3> = б! «B»! «H»! д! н! р! «&»! «(».
"*"
e>3>
S
F
U>1>
mod
S = «mod» U>1>.
U>1> = e>3>.
e>3> = б! «B»! «H»! д! н! р! «&»! «(».
"mod"
e>3>
S
F
U>1>
S = «^«U>1>.
U>1> = e>3>.
e>3> = б! «B»! «H»! д! н! р! «&»! «(».
"^"
e>3>
S
F
U>1>
оо
S = «<«O>1>! «>«O>2>! «=«O>3>.
O>1> = «>«O>4>! «=«O>4>! e>3>.
O>2> = «=«O>5>! e>3>.
O>4 >= e>3>.
O>5 >= e>3>.
O>3 >= e>3>.
e>3> = б! «B»! «H»! д! н! р! «&»! «(».
(
S = «(«K>1>.
K>1> = e>2>.
e>2> = б! «B»! «H»! д! н! р! «+»!» –"! «&»! «(».
S
"("
K>1>
e>2>
F
)
S =»)«K>2>.
K>2> = e.
е = «"! «*»!» –"! «+»! «*»! «^»!»)"! «=»! «<»! «>».
S
")"
K>2>
e
F
4) Описываем использованные в сканере подпрограммы:
end – Процедура окончания работы сканера
podgot – Процедура производит общую подготовку сканера к работе
tip – Процедура устанавливает тип литеры
vkl – Процедура добавляет текущую литеру в текущую лексему
cll – Процедура считывает из файла очередную литеру
zaptab – Процедура проверяет наличие текущей лексемы в таблице ключевых слов
out – Процедура заполняет основные таблицы
6) Пример работы сканера
Исходное выражение:
(sin (2*aa%-&B01)<bb#) and (2+3+4<10) xor &H0
Заполненные в результате работы сканера таблицы:
|
Табл.10. Таблица идентификаторов |
|||||
|
ТИ |
|||||
|
ид |
описатели |
адр |
|||
|
тип |
точка |
точность |
осн |
||
|
Aa% |
Integer |
0 |
2 |
10 |
0 |
|
Bb# |
Double |
1 |
16 |
10 |
2 |
|
Табл.11. Таблица констант |
|||||
|
ТК |
|||||
|
конст |
Описатели |
||||
|
тип |
точка |
точность |
осн |
||
|
2 |
Integer |
0 |
0 |
10 |
|
|
&B01 |
Bin |
0 |
0 |
2 |
|
|
2 |
Integer |
0 |
0 |
10 |
|
|
3 |
Integer |
0 |
0 |
10 |
|
|
4 |
Integer |
0 |
0 |
10 |
|
|
10 |
Integer |
0 |
0 |
10 |
|
|
&H0 |
Hex |
0 |
0 |
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_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