Задание на лабораторную работу
Разработать синтаксический анализатор подмножества заданного языка программирования на основе метода LL(1). Варианты заданий приведены в таблице 3.6. Код задания на лабораторную работу состоит из трех компонент.
Первая цифра варианта определяет язык программирования (1- PL0, 2- ASPLE). Описание синтаксиса языков программирования PL0 и ASPLE приведены соответственно в приложениях 1 и 2.
Вторая цифра варианта определяет подмножество языка программирования. Описание подмножеств языков программирования PL0 и ASPLE приведены соответственно в приложениях 3 и 4.
Таблица 3.6
| Номер варианта | 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П |
Третья цифра-язык программирования: П- Паскаль, С -Си.
Содержание отчета
3.4.1.Постановка задачи.
3.4.2.Управляющая таблица разбора.
3.4.3.Текст программы.
3.4.4.Описание тестовых примеров.
3.4.5.Распечатка результатов.
Библиографический список
1. А.Ахо, Дж.Ульман. Теория синтаксического анализа, перевода и компиляции. Т.1. Синтаксический анализ. - М.: Мир, 1978. - 612с.
2. Р.Хантер. Проектирование и конструирование компиляторов. - М.: Финансы и статистика, 1984. - 232с.
3. Д.Грис. Конструирование компиляторов для ЦВМ. - М.: Мир, 1975.- 544 с.
ЛАБОРАТОРНАЯ РАБОТА № 4. Восходящий синтаксический анализ методом предшествования
|
|
|
Цель работы: Изучение восходящего синтаксического анализа методом предшествования, получение навыков в программировании алгоритмов синтаксического разбора
Синтаксический анализ для грамматики простого предшествования
Алгоритм синтаксического анализа на основе грамматики предшествования относится к классу алгоритмов восходящего разбора.
Строкам и столбцам управляющей таблицы М (матрицы отношений предшествования) ставятся в соответствие элементы множества T U V U $ (в строке - символ в вершине рабочего стека, в столбце - входной символ).
Каждую запись рабочего стека представим парой: (символ, знак отношения предшествования символа предыдущей записи стека с данным символом). Перед началом работы алгоритма в стек записывается пара ($,0).
Возможные значения элементов таблицы и их интерпретация алгоритмом разбора приведены в таблице 4.1.
Таблица 4.1
| Nп/п | Значение элемента таблицы | Интерпретация значения алгоритмом разбора | |||
| 1 | <. | Запись текущего входного символа в выходной стек и в паре со знаком "<." - в рабочий стек; если этот символ - нетерминал, установка указателей на него в ближайших к нему n записях выходного стека с пустыми указателями, где n - количество символов в правой части правила для этого нетерминала. | |||
| 2 | =.
| Запись текущего входного символа в выходной стек и в паре со знаком "=." - в рабочий стек; если этот символ - нетерминал, установка указателей на него в ближайших к нему n записях выходного стека с пустыми указателями, где n - количество символов в правой части правила для этого нетерминала. | |||
| 3 | >. | Удаление из рабочего стека записей (символы которых образуют цепочку w) со знаками отношения =. до первого знака <. включительно; если <A>::=w - правило заданной грамматики, имитация считывания <A> в качестве следующего входного символа. | |||
| 4 | "допуск” |
| Конец работы | ||
| 5 | "ошибка” | Вывод сообщения об ошибке, конец работы. | |||
Отношения предшествования Вирта-Вебера <., =., >. для КС- грамматики G(V,T,P,S) определяются на множестве V U T следующим образом /1/:
1) X<.Y, если в Р есть такое правило <A>::=rX<B>q, что Y является головным символом хотя бы одной из цепочек, выводимых из <B>;
2) X=.Y, если в Р есть правило <A>::=rXYq;
3) X>.a, если a - терминал, и в Р есть правило <A>::=r<B>Yq такое, что X является хвостовым символом хотя бы одной из цепочек, выводимых из <B>, а Y=at, или a является головным символом хотя бы одной из цепочек, выводимых из Y.
|
|
|
Для анализа входной цепочки методом предшествования удобно добавлять к ней левый и правый концевые маркеры ($). Будем считать, что $<.X для всех X, являющихся головными символами цепочек, выводимых из <S>, и Y>.$ для всех Y, являющихся хвостовыми символами таких цепочек.
КС-грамматика G(V,T,P,S) называется грамматикой предшествования, если она приведенная, не содержит "lambda"-правил, и для любой пары символов из T U V выполняется не более одного отношения предшествования Вирта-Вебера. Обратимая грамматика предшествования называется грамматикой простого предшествования.
Пример.
Анализируя грамматику G(V,T,P,S) из п.1.1, заметим, что она не удовлетворяет определению грамматики предшествования, поскольку <T> =. + в соответствии с правилом 2) и <T> >. + в соответствии с правилами 2) и 4). Чтобы избавиться от этого конфликта, преобразуем эту грамматику к грамматике G2(V2,T,P2,S) с правилами:
1) <S>::=<E>
2) <E>::=<X>+<E>
3) <E>::=<X>
4) <T>::=<F>*<T>
5) <T>::=<F>
6) <F>::=i
7) <X>::=<T>
Матрица отношений предшествования для грамматики G2 представлена таблицей 4.2.
Таблица 4.2
| <S> | <E> | <T> | <F> | <X> | i | + | * | $ | |
| <S> | >. | ||||||||
| <E> | >. | ||||||||
| <T> | >. | >. | |||||||
| <F> | >. | =. | >. | ||||||
| <X> | =. | ||||||||
| i | >. | >. | >. | ||||||
| + | =. | <. | <. | <. | <. | ||||
| * | =. | <. | <. | ||||||
| $ | <. | <. | <. | <. | <. | <. |
Незаполненные элементы матрицы соответствуют парам символов грамматики, для которых не определены отношения предшествования. При использовании этой матрицы в качестве управляющей таблицы в алгоритме синтаксического анализа можно считать, что эти элементы содержат значение "ошибка", а M(<S>,$)="допуск".
|
|
|
Проанализируем входную цепочку i*i с использованием метода предшествования. Результат анализа представлен в таблице 4.3.
Таблица 4.3
| Рабочий стек | Вх.символ | M(A,a) |
| $,0 | i | M($,i)=<. |
| i,<. $,0 | * | M(i,*)=>. |
| $,0 | <F> | M(<F>,$)=<. |
| <F>,<. $,0 | * | M(<F>,*)==. |
| *,=. <F>,<. $,0 | i | M(7,i)=<. |
| i,<. *,=. <F>,<. $,0 | $ | M(i,$)=>. |
| *,=. <F>,<. $,0 | <F> | M(*,<F>)=<. |
| <F>,<. *,=. <F>,<. $,0 | $ | M(<F>,$)=>. |
| *,=. <F>,<. $,0 | <T> | M(*,<T>)==. |
| <T>,=. *,=. <F>,<. $,0 | $ | M(<T>,$)=>. |
| $,0 | <T> | M($,<T>)=<. |
| <T>,<. $,0 | $ | M(<T>,$)=>. |
| $,0 | <X> | M($,<X>)=<. |
| <X>,<. $,0 | $ | M(<X>,$)=>. |
| $,0 | <E> | M($,<E>)=<. |
| <E>,<. $,0 | $ | M(<E>,$)=>. |
| $,0 | <S> | M($,<S>)=<. |
| <S>,<. $,0 | $ | M(<S>,$)="допуск" |
В результате анализа получено синтаксическое дерево разбора (рис.4.1).
Рис.4.1. Синтаксическое дерево разбора
В выходном стеке это дерево представляется таблицей 4.4.
Таблица 4.4
| 10 | <S>,0 |
| 9 | <E>,10 |
| 8 | <X>,9 |
| 7 | <T>,8 |
| 6 | <T>,7 |
| 5 | <F>,6 |
| 4 | i,5 |
| 3 | *,7 |
| 2 | <F>,7 |
| 1 | i,2 |
Порядок выполнения работы
2.1.Проверить является ли заданная грамматика грамматикой предшествования, при необходимости выполнить соответствующие преобразования.
2.2.Построить управляющую таблицу разбора.
2.3.Разработать и отладить синтаксический анализатор, который должен быть оформлен в виде отдельной процедуры (подпрограммы).
Дата добавления: 2019-02-12; просмотров: 306; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!