close

Вход

Забыли?

вход по аккаунту

?

лаба3+ (2)

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
МАРИЙСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра ИВС
Построение простейшего дерева вывода
Лабораторная работа № 3
по дисциплине "Системное программное обеспечение"
Вариант 5
Выполнил: студент гр. ВМ-32
Иванов П.В.
Проверил: Морохин Д.В.
г.Йошкар-Ола,
2007г.
Цель работы
Изучение основных понятий теории грамматик простого и операторного предшествования, ознакомление с алгоритмами синтаксического анализа (разбора) для некоторых классов КС-грамматик, получение практических навыков создания простейшего синтаксического анализатора для заданной грамматики операторного предшествования.
Задание
Написать программу, которая выполняет лексический анализ входного текста в соответствии с заданием, порождает таблицу лексем и выполняет синтаксический разбор текста по заданной грамматике с построением дерева разбора. Текст на входном языке задается в виде символьного (текстового) файла. Допускается исходить из условия, что текст содержат не более одного предложения входного языка. Программа должна выдавать сообщения о наличие во входном тексте ошибок.
Вариант грамматики в форме Бэкуса-Наура
SS+T | S-T | T
TT*E | T/E | E
E(S) | a
Символ S является начальным символом грамматики; S, T и E обозначают нетерминальные символы. Терминальные символы выделены жирным шрифтом. Вместо символа a должны подставляться лексемы. Допустимые лексемы входного языка: идентификаторы, шестнадцатеричные числа.
МНОЖЕСТВА КРАЙНИХ ЛЕВЫХ И КРАЙНИХ ПРАВЫХ СИМВОЛОВ
СимволШаг 1Шаг 2(U)L(U)R(U)L(U)R(U)SS TTS T ET ETT EET E ( aE ) aE( a) a( a) aШаг 3
L(U)R(U)S T E ( aT E ) aT E ( aE ) a( a) a
МНОЖЕСТВА КРАЙНИХ ЛЕВЫХ И КРАЙНИХ ПРАВЫХ ТЕРМИНАЛЬНЫХ СИМВОЛОВ
СимволШаг 1 Шаг 2(U)Lt(U)Rt(U)Lt(U)Rt(U)S+ -+ -+ - * / ( a+ - * / ) aT* /* /* / ( a* / ) aE( a) a( a) a
МАТРИЦА ПРЕДШЕСТВОВАНИЯ ДЛЯ ГРАММАТИКИ
Символ+-*/(a)+>><<<<>->><<<<>*>><<>/>><<>(<<<<<<=a>>>>>)>>>>>>
Пример разбора простейшего предложения
Исходное предложение: q+($F+wrt)*$A2
Результат работы программы:
№ лексема тип лексемы 1 q Идентификатор
2 + Знак сложения
3 ( Открывающая скобка
4 $F Шестнадцатеричное число
5 + Знак сложения
6 wrt Идентификатор
7 ) Закрывающая скобка
8 * Знак умножения
9 $A2 Шестнадцатеричное число
Дерево вывода:
№ нач кон ссылка тип уровень тип лексемы значение лексемы
0 1 9 0 S 0 # 1 1 1 0 S 1 Идентификатор q
2 2 2 0 + 1 Знак сложения +
3 3 9 0 T 1 # 4 1 1 1 T 2 Идентификатор q
5 3 7 3 T 2 # 6 8 8 3 + 2 Знак умножения *
7 9 9 3 E 2 Шестнадцатеричное число $A2
8 1 1 4 E 3 Идентификатор q
9 3 7 5 E 3 # 10 9 9 7 + 3 Шестнадцатеричное число $A2
11 1 1 8 + 4 Идентификатор q
12 3 3 9 + 4 Открывающая скобка (
13 4 6 9 S 4 # 14 7 7 9 + 4 Закрывающая скобка )
15 4 4 13 S 5 Шестнадцатеричное число $F
16 5 5 13 + 5 Знак сложения +
17 6 6 13 T 5 Идентификатор wrt
18 4 4 15 T 6 Шестнадцатеричное число $F
19 6 6 17 E 6 Идентификатор wrt
20 4 4 18 E 7 Шестнадцатеричное число $F
21 6 6 19 + 7 Идентификатор wrt
22 4 4 20 + 8 Шестнадцатеричное число $F
S0
S1(<=0) "+"(<=0) T3(<=0) T4(<=1) T5(<=3) "*"(<=3) E7(<=3) E8(<=4) E9(<=5) "$A2"(<=7) "q"(<=8) "("(<=9) S13(<=9) ")"(<=9) S15(<=13) "+"(<=13) T17(<=13) T18(<=15) E19(<=17) E20(<=18) "wrt"(<=19) "$F"(<=20)
Дерево вывода
Выводы
В данной работе мы написали программу, выполняющую разбор произвольного предложения заданной грамматики и выдающую исходные данные для построения дерева вывода. Программа выводит сообщение об ошибке, если что-либо во входном предложении не соответствуют заданной грамматике.
ПРИМЕР ВЫПОЛНЕНИЯ РАЗБОРА
Входная цепочка a+(a-a).
{a+(a-a)к; н; } п {+(a-a)к; нa; } c {+(a-a)к; нE; 8} п {(a-a)к; нE+; 8} п {a-a)к; нE+(; 8} п {-a)к; нE+(a; 8} с {-a)к; нE+(E; 8,8} п {a)к; нE+(E-; 8,8} п {)к; нE+(E-a; 8,8} c {)к; нE+(E-E; 8,8,8} с {)к; нE+(E; 8,8,8,2} п {к; нE+(E); 8,8,8,2} c {к; нE+E; 8,8,8,2,7} с {к; нE; 8,8,8,2,7,1}
Дерево вывода:
2
Документ
Категория
Рефераты
Просмотров
9
Размер файла
130 Кб
Теги
лаба
1/--страниц
Пожаловаться на содержимое документа