История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
Топ:
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Интересное:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Дисциплины:
2020-10-20 | 129 |
5.00
из
|
Заказать работу |
|
|
Скажем, что цепочка a называется аннулирующей, если из нее может быть получена пустая цепочка (a® *l).
Множество Перв(a) определяется как множество первых символов цепочек, которые можно получить из a.
Множество След (А), где А –нетерминальный символ, как множество символов, которые могут стоять за А в сентенциальных формах.
Пусть правило подстановки имеет вид А ®a, тогда через Напр(А ®a) обозначим направляющее множество для правила А ®a.
Если a не аннулирующая цепочка, то Напр(А ®a) = Перв(a).
Если a аннулирующая цепочка, то Напр(А ®a) = Перв(a) È След (А).
Необходимым условием обладания грамматикой признаком LL(I)-грамматики является не пересекаемость множеств направляющих символов, соответствующих правым частям альтернативных порождающих правил для каждого нетерминального символа.
Для языков, описываемых LL(I)-грамматикой, можно построить простые, надежные и достаточно небольшие синтаксические анализаторы. Основная трудность заключается в описании конкретного входного языка грамматикой, обладающей признаком LL(I)-грамматики. Однако обычно очень большое число конкретно свободных языков в САПР можно представить в требуемой форме.
Преимущества применения LL(I)-анализаторов:
1. Время синтаксического анализа входного текста пропорционально его длине, что позволяет отнести LL(I)-анализаторы к наиболее быстрым программам такого типа.
2. Анализатор имеет хорошие диагностические характеристики и обладает возможностью коррекции синтаксических ошибок.
3. Таблицы синтаксического разбора меньше, чем соответствующие таблицы в других методах синтаксического анализа.
4. LL(I)-разбор применим к достаточно широкому классу языков.
|
СВЯЗЬ LL (I)-ГРАММАТИКИ С МП-АВТОМАТАМИ.
Для любой LL(I)-грамматики можно построить МП-автомат с одним состоянием, который будет принимать язык, порождаемой этой грамматикой.
Алгоритм построения МП-автомата для LL(I)-грамматики.
Итак, пусть дана LL(1) грамматика, Т- множество ее терминальных символов, N – множество нетерминальных символов, S – начальный символ, Р – множество правил подстановки.
Пусть А,Х – нетерминальные символы, t,r, tn – терминальные символы, l - пустая цепочка, a, b - цепочки состоящие из любого числа терминальных и нетерминальных символов. Если некоторая цепочка a помещается в стек, то ее символы помещаются в порядке справа налево, что бы левый символ цепочки был на вершине стека.
Соответствующий этой грамматики МП-автомат будет иметь:
1. Внешний алфавит А=Т È{*};
2. Алфавит магазинной памяти М=NÈ{r|rÎT и содержится в цепочке a, которая либо имеет вид Хb и является правой частью правила подстановки, либо правой частью правила подстановки будет цепочка ta}:
3. Q – множество состояний автомата состоит из единственного состояния q, которое мы не будем указывать в командах автомата;
4. Начальное состояние автомата равно q;
5. Начальная запись в магазинной памяти S#, где S – начальный символ грамматики, # - маркер дна магазина;
6. Команды МП-автомата определяются следующим образом:
a. Если правило имеет вид A®ta, то этому правилу ставится в соответствие команда At®a сдвиг;
b. Если правило имеет вид A®a, где a = Хb, тогда для всех терминальных символов tn из множества Напр(A®a) ставятся в соответствие команды А tn ®a Стоп;
c. Если правило имеет вид A®l, тогда для всех терминальных символов tn из множества Напр(A®l) ставятся в соответствие команды А tn ®l Стоп;
d. Если правило имеет вид A®t, то этому правилу ставится в соответствие команда At®l Сдвиг;
e. Если по одной из команд МП-автомата, в магазин попадает терминальный символ t, то в этом случае формируется команда tt®lСдвиг;
f. Если *- знак конца строки, #-маркер конца стека, то формируется команда *#®Допустить.
|
Если автомат во время работы столкнется с ситуацией, для которой нет команды, то эта ситуация будет означать, что слово отвергается.
РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ ЛАБОРАТОРНОЙ РАБОТЫ
Для разработки LL(I)-синтаксического анализатора рекомендуется использовать МП-автомат, созданный во второй лабораторной работе.
При этом надо изменить команды МП-автомата
Этапы выполнения лабораторной работы
Подготовительный этап:
1. Изучить основные сведения, приведенные в описании данной работы.
3. Ответить на все контрольные вопросы.
Этап проектирования
· Найти 20 слов языка, порождаемого грамматикой, определенной вариантом задания или выяснить закономерность, определяющую слова, входящие в этот язык.
· Построить направляющие множества для грамматики, определенной вариантом;
· Проверить является ли заданная грамматика LL(1) грамматикой;
· Построить МП-автомат, принимающий язык, порождаемый заданной грамматикой. На данном этапе команды автомата записать в виде таблицы.
· Записать команды автомата в стандартном виде.
· Проанализировать МП-автомат, разработанный во второй лабораторной работе. Внести необходимые изменения так, что бы он решал новую задачу.
План отчета
1. Название и цель работы.
2. 20 слов языка, порождаемого грамматикой, определенной вариантом задания или закономерность, определяющую слова, входящие в этот язык.
3. Направляющие множества для грамматики, определенной вариантом;
4. Проверка того, является ли заданная грамматика LL(1) грамматикой;
5. Таблица команд МП- автомата, принимающего язык порождаемый заданной грамматикой..
6. Текст программы.
7. Результаты работы LL(I)-анализатора как для правильных, так и ошибочных цепочек символов.
Варианты индивидуальных заданий
1. Множество терминальных символов Vt={a,b,c,d}.
Множество нетерминальных символов Vn={A,B.S}
Начальное состояние S=S
Правила подстановки:
S®AB|bS
A®aA|dB
B®AB|c
2. Множество терминальных символов Vt={a,b,c,d}.
Множество нетерминальных символов Vn={A,B.S}
Начальное состояние S=S
Правила подстановки:
S®aAaB|bAbB
A®dS| λ
B®cB|a
|
3. Множество терминальных символов Vt={a,b,c,d,m}.
Множество нетерминальных символов Vn={A,B,D}
Начальное состояние S=A
Правила подстановки:
A®aB|bA
B®cD| λ
D®dBd|m
4. Множество терминальных символов Vt={a,b,d,m,q}.
Множество нетерминальных символов Vn={X,Y,Z,S}
Начальное состояние S=S
Правила подстановки:
S®aXY| bYZ
X®mXq| λ
Y®bY|d
Z®S|qZ
5. Множество терминальных символов Vt={a,b,c,d,q,p}.
Множество нетерминальных символов Vn={X,Y,N,S}
Начальное состояние S=S
Правила подстановки:
S®aXY|XY
X®bY|cN| λ
N®qY|p
Y®dN
6. Множество терминальных символов Vt={x,y,c,m}.
Множество нетерминальных символов Vn={A,B,C,S}
Начальное состояние S=S
Правила подстановки:
S®AB|xCB
A®yA|m
B®aC|c
C®bC|λ
7. Множество терминальных символов Vt={ x,y,c,m }.
Множество нетерминальных символов Vn={A,B,C,S}
Начальное состояние S=S
Правила подстановки:
S®AB|xCB
A®yA| λ
B®aC|c
C®bC|m
8. Множество терминальных символов Vt={a,b,c,d}.
Множество нетерминальных символов Vn={A,B.S}
Начальное состояние S=S
Правила подстановки:
S®aAaB|bAbB
A®mS| λ
B®dmB|a
9. Множество терминальных символов Vt={a,b,c,d,m}.
Множество нетерминальных символов Vn={S,A,B,D}
Начальное состояние S=S
Правила подстановки:
S®aAa|bAb
A®aBa|bA
B®cD| λ
D®dBd|m
10. Множество терминальных символов Vt={a,b,d,m,q}.
Множество нетерминальных символов Vn={X,Y,Z,S}
Начальное состояние S=S
Правила подстановки:
S®aX| bYZ
X®mXq| λ
Y®bY|d
Z®S|qZ
11. Множество терминальных символов Vt={a,b,c,d,q,p}.
Множество нетерминальных символов Vn={X,Y,N,S}
Начальное состояние S=S
Правила подстановки:
S®aXY|XY
X®cN| λ
N®qY|p
Y®dN
12. Множество терминальных символов Vt={x,y,c,m}.
|
Множество нетерминальных символов Vn={A,B,C,S}
Начальное состояние S=S
Правила подстановки:
S®AB|xCa
A®yA|m
B®aC|c
C®bC|λ
13. Множество терминальных символов Vt={ x,y,c,m,n }.
Множество нетерминальных символов Vn={A,B,C,S}
Начальное состояние S=S
Правила подстановки:
S®An|CB
A®yA| λ
B®aB|c
C®bC|m
14. Множество терминальных символов Vt={a,b,c,d}.
Множество нетерминальных символов Vn={A,B.S}
Начальное состояние S=S
Правила подстановки:
S®AB|bS
A®aA| | λ
B®dB|c
Контрольные вопросы
1.Что такое сентенциальная форма, предложение?
2.Что такое синтаксическое дерево?
3.Что такое неоднозначная грамматика?
4.Понятие восходящего и нисходящего разбора предложений?
5.Проблемы,возникающие при нисходящем и восходящем разборе предложений, с чем они связаны?
6.Каким образом решается проблема возвратов при восходящем разборе предложений?
7. Каким образом решается проблема возвратов при нисходящем разборе предложений?
8.Дать определение S-грамматики.
9.Привести пример S-грамматики.
10.Привести пример LL(I)- грамматики.
11.Как LL(I)-грамматика связаны с S-грамматикой.
12.Как LL(I)-грамматика связана с МП-автоматом.
13.Можно ли язык, порождаемый LL(I)-грамматикой или S-грамматикой анализировать с помощью детерминированного конечного автомата? Ответ пояснить.
14.Дать определение фразы, основы. Когда эти понятия используются?
15.Что такое множество направляющих символов?
16.Каковы достоинства и недостатки LL(I)-анализаторов.
Литература:
1. Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий, 2-е изд., М.: Вильямс, 2008.
2. Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Введение в теорию автоматов, языков и вычислений, М.: Вильямс, 2002.
3.Р.И.Компаниец, Е.В.Маньков, Н.Е.Филатов, Системное программирование. Основы построения трансляторов. Санк-Петербург, 2000.
Оглавления
Лабораторная работа №1. 2
Лексический анализ. Детерминированный конечный автомат. Демонстрация работы детерминированного конечного автомата. 2
Теоретический материал, необходимый для выполнения лабораторной работы.. 2
Этапы выполнения лабораторной работы.. 4
План отчета. 5
Варианты индивидуальных заданий. 6
Контрольные вопросы.. 6
Лабораторная работа №2. 7
Детерминированного автомата с магазинной памятью.. 7
Теоретический материал, необходимый для выполнения лабораторной работы.. 7
Этапы выполнения лабораторной работы.. 9
План отчета. 10
Варианты индивидуальных заданий. 10
Контрольные вопросы.. 14
Лабораторная работа №3. 14
Разработка синтаксического анализатора предложений, порожденных LL(1)- грамматикой 14
|
Теоретический материал, необходимый для выполнения лабораторной работы.. 15
Этапы выполнения лабораторной работы.. 18
План отчета. 19
Варианты индивидуальных заданий. 20
Контрольные вопросы.. 22
Литература: 23
Оглавления. 23
|
|
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!