МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
ОДЕСЬКИЙ НАЦІОНАЛЬНИЙ ПОЛІТЕХНІЧНИЙ УНІВЕРСИТЕТ
ІНСТИТУТ КОМП’ЮТЕРНИХ СИСТЕМ
КАФЕДРА СИСТЕМНОГО ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ
Лабораторна робота № 5
з дисципліни: “Теорія формальних граматик і трансляції”
на тему:
«Синтаксический анализ методом простого предшествования»
Виконав:
Студент групи АС-191:
Сокольський А. К.
Перевірили:
Комлева Н.О.
Жиро Л. С.
Одеса
2020
Задание
1. Разработать формальную грамматику (ЛР №1) для выражений, которые могут содержать:
1.1. логические операции: !, ||
1.2. Арифметические и сдвиговые операции: * + -
1.3. Константы: десятичные, шестнадцатеричные (префикс - &H) и двоичные (префикс - &B).
1.4. Идентификаторы: int (суффикс %), float (суффикс #), string (суффикс @)
1.5. Функции: exp, strrev.
1.6. Знаки отношений.
1.7. Приоритет выполнения операций - традиционный, использовать круглые скобки для возможности изменения приоритета.
1.8. Просмотр выражения слева-направо. Свертка выражения слева-направо.
1.9. Если в перечне типов идентификаторов отсутствуют типы, требуемые для реализации функции, необходимо доопределить перечень типов.
Задачи:
1. Приведение грамматики к виду грамматики простого предшествования.
2. Выбор цепочки для свертки.
3. Выполнение синтаксического анализа выбранной цепочки с использованием правил бесконфликтной грамматики и соответствующей матрицы предшествования.
Протокол лабораторной работы должен включать:
• отлаженную грамматику и бесконфликтную матрицу простого предшествования;
• выбранную цепочку;
• синтаксическое дерево для выбранной цепочки (по желанию);
• таблицу с шагами синтаксического анализа;
• выводы.
Ход работы:
Отлаженная грамматика:
ВЫРАЖЕНИЕ = АР_ВЫР ! ЛОГ_ВЫР
ЛОГ_ВЫР = ЛОГ_ВЫР "||" ЛОГ_ОПЕР1 ! ЛОГ_ОПЕР1
ЛОГ_ОПЕР1 = "!" ЛОГ_ОПЕР2 ! ЛОГ_ОПЕР2
ЛОГ_ОПЕР2 = "STRREV" "(" STRING ")" ! ЛОГ_ОПЕР3
ЛОГ_ОПЕР3 = АР_ВЫР ОПЕР_СР АР_ВЫР
АР_ВЫР = АР_ВЫР1
АР_ВЫР1 = АР_ВЫР1 "+" АР_ОПЕР11 ! АР_ВЫР1 "-" АР_ОПЕР11 ! АР_ОПЕР11
АР_ОПЕР11 = АР_ОПЕР1
АР_ОПЕР1 = АР_ОПЕР1 "*" АР_ОПЕР2 ! АР_ОПЕР2
АР_ОПЕР2 = ИД ! КОНСТ ! "(" АР_ВЫР ")" ! "EXP" "(" FLOAT ")"
ИД = INTEGER ! FLOAT
INTEGER = "ИД%"
FLOAT = "ИД#"
STRING = "ИД@"
КОНСТ = "КОНСТ" ! "&BКОНСТ" ! "&HКОНСТ"
ОПЕР_СР = "==" ! "!=" ! ">" ! ">=" ! "<" ! "<=" ! "<>"
Бесконфликтная матрица простого предшествования:
Нумерация правил грамматики:
ВЫРАЖЕНИЕ = АР_ВЫР ! ЛОГ_ВЫР (1, 2)
ЛОГ_ВЫР = ЛОГ_ВЫР "||" ЛОГ_ОПЕР1 ! ЛОГ_ОПЕР1 (3, 4)
ЛОГ_ОПЕР1 = "!" ЛОГ_ОПЕР2 ! ЛОГ_ОПЕР2 (5, 6)
ЛОГ_ОПЕР2 = "STRREV" "(" STRING ")" ! ЛОГ_ОПЕР3 (7, 8)
ЛОГ_ОПЕР3 = АР_ВЫР ОПЕР_СР АР_ВЫР (9)
АР_ВЫР = АР_ВЫР1 (10)
АР_ВЫР1 = АР_ВЫР1 "+" АР_ОПЕР11 ! АР_ВЫР1 "-" АР_ОПЕР11 ! АР_ОПЕР11 (11,12,13)
АР_ОПЕР11 = АР_ОПЕР1 (14)
АР_ОПЕР1 = АР_ОПЕР1 "*" АР_ОПЕР2 ! АР_ОПЕР2 (15, 16)
АР_ОПЕР2 = ИД ! КОНСТ ! "(" АР_ВЫР ")" ! "EXP" "(" FLOAT ")" (17, 18, 19, 20)
ИД = INTEGER ! FLOAT (21, 22)
INTEGER = "ИД%" (23)
FLOAT = "ИД#" (24)
STRING = "ИД@" (25)
КОНСТ = "КОНСТ" ! "&BКОНСТ" ! "&HКОНСТ" (26, 27, 28)
ОПЕР_СР = "==" ! "!=" ! ">" ! ">=" ! "<" ! "<=" ! "<>" (29, 30, 31, 32, 33, 34, 35)
Входная цепочка + синтаксическое дерево:
A# != B% – EXP(C#)
Таблица с шагами синтаксического анализа:
| № | Сентенциальная форма | Основа | Левая часть | Номер правила |
| 1 | #<A#>!=<B%>-<EXP(<C#>)># | A# | FLOAT | 24 |
| 2 | #<FLOAT>!=< B%>-<EXP(<C#>)># | FLOAT | ИД | 22 |
| 3 | #<ИД>!=< B%>-<EXP(<C#>)># | ИД | АР_ОПЕР2 | 17 |
| 4 | #<АР_ОПЕР2>!=< B%>-<EXP(<C#>)># | АР_ОПЕР2 | АР_ОПЕР1 | 16 |
| 5 | #<АР_ОПЕР1>!=< B%>-<EXP(<C#>)># | АР_ОПЕР1 | АР_ОПЕР11 | 14 |
| 6 | #<АР_ОПЕР11>!=< B%>-<EXP(<C#>)># | АР_ОПЕР11 | АР_ВЫР1 | 13 |
| 7 | #<АР_ВЫР1>!=< B%>-<EXP(<C#>)># | АР_ВЫР1 | АР_ВЫР | 10 |
| 8 | #<АР_ВЫР=!=< B%>-<EXP(<C#>)># | != | ОПЕР_СР | 30 |
| 9 | #<АР_ВЫР=ОПЕР_СР=B%>-<EXP(<C#>)># | B% | INTEGER | 23 |
| 10 | #<АР_ВЫР=ОПЕР_СР=INTEGER>-<EXP(<C#>)># | INTEGER | ИД | 21 |
| 11 | #<АР_ВЫР=ОПЕР_СР=ИД>-<EXP(<C#>)># | ИД | АР_ОПЕР2 | 17 |
| 12 | #<АР_ВЫР=ОПЕР_СР=АР_ОПЕР2>-<EXP(<C#>)># | АР_ОПЕР2 | АР_ОПЕР1 | 16 |
| 13 | #<АР_ВЫР=ОПЕР_СР=АР_ОПЕР1>-<EXP(<C#>)># | АР_ОПЕР1 | АР_ОПЕР11 | 14 |
| 14 | #<АР_ВЫР=ОПЕР_СР=АР_ОПЕР11>-<EXP(<C#>)># | АР_ОПЕР11 | АР_ВЫР1 | 13 |
| 15 | #<АР_ВЫР=ОПЕР_СР=АР_ВЫР1=-<EXP(<C#>)># | C# | FLOAT | 24 |
| 16 | #<АР_ВЫР=ОПЕР_СР=АР_ВЫР1=-<EXP(=FLOAT=)># | EXP(FLOAT) | АР_ОПЕР2 | 20 |
| 17 | #<АР_ВЫР=ОПЕР_СР=АР_ВЫР1=-< АР_ОПЕР2># | АР_ОПЕР2 | АР_ОПЕР1 | 16 |
| 18 | #<АР_ВЫР=ОПЕР_СР=АР_ВЫР1=-< АР_ОПЕР1># | АР_ОПЕР1 | АР_ОПЕР11 | 14 |
| 19 | #<АР_ВЫР=ОПЕР_СР=АР_ВЫР1=-= АР_ОПЕР11># | АР_ВЫР1-АР_ОПЕР11 | АР_ВЫР1 | 12 |
| 20 | #<АР_ВЫР=ОПЕР_СР=АР_ВЫР1># | АР_ВЫР1 | АР_ВЫР | 10 |
| 21 | #<АР_ВЫР=ОПЕР_СР=АР_ВЫР># | АР_ВЫР ОПЕР_СР АР_ВЫР | ЛОГ_ОПЕР3 | 9 |
| 22 | #<ЛОГ_ОПЕР3># | ЛОГ_ОПЕР3 | ЛОГ_ОПЕР2 | 8 |
| 23 | #<ЛОГ_ОПЕР2># | ЛОГ_ОПЕР2 | ЛОГ_ОПЕР1 | 6 |
| 24 | #<ЛОГ_ОПЕР1># | ЛОГ_ОПЕР1 | ЛОГ_ВЫР | 4 |
| 25 | #<ЛОГ_ВЫР># | ЛОГ_ВЫР | ВЫРАЖЕНИЕ | 2 |
| 26 | #<ВЫРАЖЕНИЕ># | | | |
Вывод
В ходе данной лабораторной работы я изучил метод синтаксического анализа простого предшествующего и научиться методике и технике проектирования синтаксического анализатора.