Задание на лабораторную работу
Разработать синтаксический анализатор подмножества заданного языка программирования на основе метода предшествования. Варианты заданий приведены в таблице 4.5. Код задания на лабораторную работу состоит из трех компонент.
Первая цифра варианта определяет язык программирования (1- PL0, 2- ASPLE). Описание синтаксиса языков программирования PL0 и ASPLE приведены соответственно в приложениях 1 и 2.
Вторая цифра варианта определяет подмножество языка программирования. Описание подмножеств языков программирования PL0 и ASPLE приведены соответственно в приложениях 3 и 4.
Таблица 4.5
| Номер варианта | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Код задания | 11П | 12С | 13П | 14С | 21П | 22С | 23П | 24С |
| Номер варианта | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| Код задания | 11С | 12П | 13С | 14П | 21С | 22П | 23С | 24П |
Третья цифра-язык программирования: П- Паскаль, С -Си.
Содержание отчета
4.3.1.Постановка задачи.
4.3.2.Исходная и преобразованная грамматики.
4.3.3.Текст программы.
4.3.4.Описание тестовых примеров.
4.3.5.Распечатка результатов.
Библиографический список
1. А.Ахо, Дж.Ульман. Теория синтаксического анализа, перевода и компиляции. Т.1. Синтаксический анализ. - М.: Мир, 1978. - 612с.
2. Р.Хантер. Проектирование и конструирование компиляторов. - М.: Финансы и статистика, 1984. - 232с.
3. Д.Грис. Конструирование компиляторов для ЦВМ. - М.: Мир, 1975.- 544 с.
4. Волкова И.А., Руденко Т.В. Формальные грамматики и языки. Элементы теории трансляции. –МГУ,1998.
|
|
|
ЛАБОРАТОРНАЯ РАБОТА № 5. Восходящий синтаксический анализ методом LR (1)
Цель работы: Изучение восходящего синтаксического анализа методом LR (1) предшествования, получение навыков в программировании алгоритмов синтаксического разбора
Синтаксический анализ для LR(1)-грамматики
Алгоритм синтаксического анализа на основе LR(k)-грамматики относится к классу алгоритмов восходящего разбора.
Строкам управляющей таблицы М (LR-таблицы разбора) /2/ ставятся в соответствие состояния, в которых может находиться анализатор, столбцам - элементы множества VUTU$.
Каждая запись рабочего стека представляет собой пару: (символ, номер состояния). Перед началом работы алгоритма в рабочий стек заносится пара ($,1).
Возможные значения элементов таблицы и их интерпретация алгоритмом разбора приведены в таблице 5.1.
Таблица 5.1
| N п/п | Значение элемента таблицы | Интерпретация алгоритмом разбора |
| 1 | Номер i порождающего правила грамматики | Удаление из рабочего стека n записей (n - количество символов в правой части правила номер i); имитация считывания в качестве следующего входного символа нетерминала левой части правила номер i. |
| 2 | ("Сдвиг", номер j состояния) | Запись текущего входного символа в выходной стек и в паре с номером j - в рабочий стек; если этот символ нетерминал, установка указателей на него в ближайших к нему n записях выходного стека с пустыми указателями. |
| 3 | “допуск” | конец работы |
| 4 | "ошибка" | Вывод сообщения об ошибке; Конец работы. |
Для построения управляющей таблицы М может быть выполнена разметка порождающих правил грамматики номерами состояний анализатора. Номера состояний устанавливаются в правой части каждого правила: перед первым символом, между любыми двумя символами и после последнего символа. При этом номер состояния, непосредственно справа от которого находится нетерминал, следует распространить на позиции перед первыми символами всех правых частей правил для данного нетерминала (и т. д. рекурсивно). А если непосредственно слева от одного и того же символа в каких-либо правилах установлены одинаковые множества меток, то и непосредственно справа от этого символа в этих правилах следует поставить одну и ту же метку. После разметки грамматики выполняется построение таблицы М по следующему алгоритму /2/.
|
|
|
1. Если символ А в правой части правила имеет непосредственно слева от себя метку k, а непосредственно справа от себя - метку j, то
|
|
|
M(k,A) = ("сдвиг",j).
2. Если метка j размещается за последним символом правой части правила номер i (если правая часть правила - "lambda", j совпадает с
меткой состояния, непосредственно справа от которого находится нетерминал левой части правила i), то определяется множество Q символов, которые в какой-либо сентенциальной форме могут следовать за нетерминалом левой части правила номер i, и M(j,q)=i для всех q, принадлежащих Q.
3. M(1,<S>)="допуск".
4. Оставшиеся незаполненными элементы таблицы M получают значение "ошибка".
Пример.
Разметим грамматику G(V,T,P,S):
1) <S>::= <E>
1 2
2) <E>::= <T> + <E>
1,4 3 4 5
3) <E>::= <T>
1,4 3
4) <T>::= <F> * <T>
1,4,7 6 7 8
5) <T>::= <F>
1,4,7 6
6) <F>::= i
1,4,7 9
Управляющая таблица М будет представлена таблицей 5.2.
Таблица 5.2
| <S> | <E> | <F> | <T> | i | + | * | $ | |
| 1 2 3 4 5 6 7 8 9 | “допуск” сдв,5 | сдв,2 сдв,6 сдв,6 | сдв,6 сдв,3 сдв,8 | сдв,9 сдв,9 | сдв,4 5 4 6 | сдв,7 6 | 1 3 2 5 4 6 |
|
|
|
Незаполненные элементы таблицы имеют значение "ошибка". Проанализируем входную цепочку i*i c помощью алгоритма
LR(1) - анализатора. Последовательность изменения состояний стека представлена таблицей 5.3.
Таблица 5.3
| Рабочий стек | Вх.символ | M(A,a) |
| $,1 | i | M(1,i)=сдв,9 |
| i,9 $,1 | * | M(9,*)=6 |
| $,1 | <F> | M(1,<F>)=сдв,6 |
| <F>,6 $,1 | * | M(6,*)=сдв,7 |
| *,7 <F>,6 $,1 | i | M(7,i)=сдв,9 |
| i,9 *,7 <F>,6 $,1 | $ | M(9,$)=6 |
| *,7 <F>,6 $,1 | <F> | M(7,<F>)=сдв,6 |
| <F>,6 *,7 <F>,6 $,1 | $ | M(6,$)=5 |
| *,7 <F>,6 $,1 | <T> | M(7,<T>)=сдв,8 |
| <T>,8 *,7 <F>,6 $,1 | $ | M(8,$)=4 |
| $,1 | <T> | M(1,<T>)=сдв,3 |
| <T>,3 $,1 | $ | M(3,$)=3 |
| $,1 | <E> | M(1,<E>)=сдв,2 |
| <E>,2 $,1 | $ | M(2,$)=1 |
| $,1 | <S> | M(1,<S>)=допуск |
В результате анализа получено синтаксическое дерeво разбора (рис.5.1).
Рис.5.1 Синтаксическое дерево разбора
В выходном стеке это дерево представляется таблицей 5.4.
Таблица 5.4
| 9 | <S>,0 | |
| 8 | <E>,9 | |
| 7 | <T>,8 | |
| 6 | <T>,7 | |
| 5 | <F>,6 | |
| 4 | i,5 | |
| 3 | *,7 | |
| 2 | <F>,7 | |
| 1 | i,2 | |
Дата добавления: 2019-02-12; просмотров: 248; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!