close

Вход

Забыли?

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

?

Otchet lab4

код для вставкиСкачать
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
"Государственный университет -
учебно-научно-производственный комплекс"
Кафедра "Информационные системы"
ОТЧЕТ
по лабораторной работе № 4
на тему:
"Таблично управляемый синтаксический разбор сверху вниз"
по дисциплине "Теория языков программирования"
Выполнили: Писарев А.В.Шифр 110128
Синяков В.Д.Шифр 110130
Новиков М.С.Шифр 110126
Факультет: УНИИ ИТ
Специальность: 230400 "Информационные системы и технологии"
Группа: 31-ИТ
Проверил: Кравцова Э.А.
Отметка о зачете: ________ Дата: "31" октября 2013 г.
Орел, 2013 г.
Грамматика языка
1. GOAL --> createx_table_x id bkt1 PARAMS PRIMS FORS bkt2
2. PARAMS --> id typex NULLS zpx PARAMS1
3. PARAMS1 --> id typex NULLS zpx PARAMS1
4. PARAMS1 --> e
5. NULLS --> nullx
6. NULLS --> not_nullx
7. PRIMS --> pkx bkt1 id PRIMS1 bkt2 zpx
8. PRIMS1 -->zpx id PRIMS1
9. PRIMS1 --> e
10. FORS --> forx bkt1 id bkt2 refx id bkt1 id bkt2 FORS1
11. FORS1 --> zpx forx bkt1 id bkt2 refx id bkt1 id bkt2 FORS1
12. FORS1 --> e
Множество first
СимволfirstGOAL{createx_tablex}PARAMS{id}PARAMS1{id,e}NULLS{nullx, not_nullx}PRIMS{pkx}PRIMS1{zpx,e}FORS{forx}FORS1{zpx, e}createx_tablex{createx_tablex}id{id}e{e}bkt1{bkt1}bkt2{bkt2}typex{typex}zpx{zpx}nullx{nullx}not_nullx{not_nullx}pkx{pkx}forx{forx}refx{refx}Множество follow
Нетерминал1234followGOAL{eof}{eof}PARAMS{pkx}{pkx}PARAMS1{pkx}{pkx}NULLS{zpx}{zpx}PRIMS{forx}{forx}PRIMS1{bkt2}{bkt2}FORS{bkt2}{bkt2}FORS1{bkt2}{bkt2}
Таблица разбора
createx_tablexidbkt1bkt2typexzpxnullxnot_nullxpkxforxrefxGOALGOAL --> createx_tablex id bkt1 PARAMS PROMS FORS bkt2 GOAL --> createx_tablex id bkt1 PARAMS PROMS FORS bkt2 GOAL --> createx_tablex id bkt1 PARAMS PROMS FORS bkt2 GOAL --> createx_tablex id bkt1 PARAMS PROMS FORS bkt2 erererererererPARAMSerPARAMS --> id typex NULLS zpx PARAMS1ererPARAMS --> id typex NULLS zpx PARAMS1PARAMS --> id typex NULLS zpx PARAMS1erererererPARAMS1erPARAMS --> id typex NULLS zpx PARAMS1ererPARAMS --> id typex NULLS zpx PARAMS1PARAMS --> id typex NULLS zpx PARAMS1erererererNULLSererererererNULLS --> nullxNULLS --> not_nullxerererPRIMSerPRIMS --> pkx bkt1 id PRIMS1 bkt2 zpxPRIMS --> pkx bkt1 id PRIMS1 bkt2 zpxPRIMS --> pkx bkt1 id PRIMS1 bkt2 zpxerPRIMS --> pkx bkt1 id PRIMS1 bkt2 zpxererPRIMS --> pkx bkt1 id PRIMS1 bkt2 zpxererPRIMS1erPRIMS1 --> zpx id PRIMS1erererPRIMS1 --> zpx id PRIMS1erererererFORSerFORS--> forx bkt1 id bkt2 refx id bkt1 id bkt2 FORS1FORS--> forx bkt1 id bkt2 refx id bkt1 id bkt2 FORS1FORS--> forx bkt1 id bkt2 refx id bkt1 id bkt2 FORS1erererererFORS--> forx bkt1 id bkt2 refx id bkt1 id bkt2 FORS1FORS--> forx bkt1 id bkt2 refx id bkt1 id bkt2 FORS1FORS1erFORS--> zpx forx bkt1 id bkt2 refx id bkt1 id bkt2 FORS1FORS--> zpx forx bkt1 id bkt2 refx id bkt1 id bkt2 FORS1FORS--> zpx forx bkt1 id bkt2 refx id bkt1 id bkt2 FORS1erFORS--> zpx forx bkt1 id bkt2 refx id bkt1 id bkt2 FORS1erererFORS--> zpx forx bkt1 id bkt2 refx id bkt1 id bkt2 FORS1FORS--> zpx forx bkt1 id bkt2 refx id bkt1 id bkt2 FORS1
Контрольные вопросы
1 Что представляет собой таблица разбора?
Таблица разбора состоит из продукций грамматики. Столбцы таблицы именованы терминалами грамматики, а строки - нетерминалами. Эта таблица определяет, какую продукцию нужно рассматривать для некоторой пары: терминал на входе и нетерминал в вершине стека.
2 Что такое множество first грамматических символов, и каковы правила его построения?
Для последовательности a определим множество first как множество терминалов, с которых может начинаться последовательность, выводимая из a. Если из a можно вывести пустую строку, то в множество first последовательности a должно присутствовать e.
Правила построения:
1. Если х - терминал, то first(x)={x}. Так как первым символом последовательности из одного терминала может являться только сам терминал.
2. Если в грамматике присутствует правило Х--> e, то множество first(х) включает e. Это означает, что Х может начинаться с пустой последовательности, то есть отсутствовать вообще.
3. Для всех продукций вида X-->Y1 Y2 ... Yk выполняем следующее. Добавляем в множество first(Х) множество first(Yi) до тех пор, пока first(Yi-1) содержит e, а first(Yi) не содержит e. При этом i изменяется от 0 до k. Это необходимо, так как если Yi-1 может отсутствовать, то необходимо выяснить, с чего будет начинаться вся последовательность в этом случае.
3 Что такое множество follow грамматических символов, для каких символов оно строиться, и каковы правила его построения? Для каждого нетерминала грамматики можно построить множество follow, то есть множество терминалов, которые можно встретить непосредственно после нетерминала в какой-либо последовательности, соответствующей грамматике.
Алгоритм построения множества follow заключается в следующем. Вначале символ конца входной последовательности помещается в множество follow стартового нетерминала (шаг 1). Затем выполнятся шаги 2-4 до тех пор, пока можно еще что-либо добавить в множество follow(X).
2. Если есть правило А-->aBb, то в множество follow(В) добавляем множество first(b) без e. То есть, если есть правило, утверждающее, что за В следует b, то за нетеримналом будут следовать терминалы, с которых начинается последовательность b.
3. Если есть правило А-->aB, то в множество follow(B) добавляется множество follow(A). То есть, если есть правило, утверждающее, что нетерминалом В заканчивается последовательность А, то за нетрминалом В будут следовать те же терминалы, что и за всей последовательностью А.
4. Если есть продукция А-->aBb и пустая последовательность принадлежит first(b), то в множество follow(B) добавляется множество follow(A). Если последовательность b не пуста, то терминалы, которые могут следовать за В уже найдены на шаге 1. Если же последовательность b пуста, то шаг 3 фактически сводится к шагу 2.
4 Как строится таблица разбора?
Для всех продукций А-->a грамматики выполняем:
1 Для всех терминалов а, принадлежащих first(a) в клетку [А, а] таблицы разбора записываем продукцию А-->a.
2 Если e принадлежит first(a), то для всех b, принадлежащих follow(А), в клетку [A, b] записываем продукцию А-->a.
Во все остальные клетки таблицы записываем признак ошибки.
5 В чем состоит алгоритм таблично управляемого синтаксического разбора? Занести символ окончания входной последовательности в стек
Занести в стек стартовый нетерминал
Распознать символ входной последовательности
Повторять Если в вершине стека находится терминал
то Если распознанный символа равен вершине стека
то Извлечь из стека верхний элемент и распознать символ входной последовательности
иначе вывести сообщение об ошибке;
иначе {если в вершине стека нетерминал}
Если в клетке[вершина стека, распознанный символ] таблицы разбора существует правило
то извлечь из стека элемент и занести в стек все терминалы и нетерминалы найденного в таблице правила в стек в порядке обратном порядку их следования в правиле
иначе вывести сообщение об ошибке
пока вершина стека не равна концу входной последовательности
Если распознанный символ не равен концу входной последовательности
то вывести сообщение об ошибке
Документ
Категория
Рефераты
Просмотров
14
Размер файла
28 Кб
Теги
lab4, otchet
1/--страниц
Пожаловаться на содержимое документа