История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Топ:
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Интересное:
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Дисциплины:
2020-10-20 | 114 |
5.00
из
|
Заказать работу |
|
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕКСТИЛЬНЫЙ УНИВЕСИТЕТ им. А.Н. КОСЫГИНА
Учебно-методический комплекс по специальности 230104.65 Системы автоматизированного проектирования,
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к лабораторным работам по курсу «Лингвистическое обеспечение систем логистики» (6 семестр)
Составила: доц. Т.М. Кузьмина
Допущено к изданию редакционно-издательским советом университета
Москва 2010
Лабораторная работа №1
Лексический анализ. Детерминированный конечный автомат. Демонстрация работы детерминированного конечного автомата.
Цель работы: освоение метода распознания терминальных символов с использованием детерминированного конечного автомата с демонстрацией работы самого детерминированного конечного автомата.
Детерминированного автомата с магазинной памятью
Цель работы: изучение алгоритма работы детерминированного автомата с магазинной памятью (МП- автомата), используемого для осуществления синтаксического анализа исходных текстов.
Этапы выполнения лабораторной работы
Подготовительный этап
1. Изучить основные сведения, приведенные в описании данной работы.
2. Ответить на все контрольные вопросы.
Этап визуального программирования
2. На форму поместить следующие компоненты:
a. компонент textВox, для ввода анализируемой строки,
b. компонент listBox1, который будет моделировать входную ленту автомата, текст из textbox в listBox1 должен переносится, при нажатии на кнопку «Ввод», причем в каждой строке listBox1, должен располагаться один символ;
|
c. кнопка «Ввод».
d. компонент listBox2, в котором будут записаны команды автомата;
e. компонент listBox3, в котором будут записано содержимое магазинной памяти, поскольку этот компонент нам нужен для моделирования работы со стеком, то в нем всегда будет выделена верхняя строка;
f. компонент label, в котором будет выводиться название текущего состояния автомата;
g. кнопка «Шаг», при нажатии на которую будет моделироваться один шаг работы автомата, при запуске программы она должна быть не активна.
Описание того, как должна функционировать программа
Анализируемое слово пользователь вводит в textВox.
При нажатии на кнопку «Ввод» должны выполняться следующие действия:
1. текст из textbox дополняется заключительным символом и переносится в listBox1,
2. в listBox1 должна быть выделена первая строка, что соответствует тому, что автомат обозревает первый символ;
3. в label выведено название начального состояния автомата;
4. в listBox2 выделена команда, соответствующая начальному состоянию автомата, первому обозреваемому символу и символу магазинной памяти, находящемуся на вершине стека;
5. в listBox3 начальный символ и маркер дна (если такой используется);
6. кнопка «Шаг» должна стать активной.
При нажатии на кнопку «Шаг» должны выполняться следующие действия:
1. если в listBox1 была выделена не последняя строка, то
a. в listBox1 выделить следующую строку,
b. в label вывести название нового состояния автомата;
c. в listBox2 выделить команду, которая соответствует новому обозреваемому символу, новому состоянию автомата, и символу, находящемуся на вершине стека;
d. в listBox3 удалить первый символ (символ, находящийся на вершине стека) и поместить новые символы, определенные выполненной командой.
2. если в listBox1 была выделена последняя строка, то в зависимости от того, в каком состоянии находится автомат или в зависимости от состояния магазинной памяти, вывести сообщение о том принимается слово или нет, и завершить работу программы.
|
План отчета
1. Название и цель работы.
2.Описание МП- автомата, соответствующего индивидуальному заданию.
3. Пример цепочек символов, допускаемых данным МП- автоматом.
4. Распечатка текста программы.
5. Результат работы программы, представленные как для нескольких примеров цепочек, допускаемых автоматом, так и для ошибочных цепочек.
6. Записать результат проведенного эксперимента, т.е. ответить на вопрос: принимает ли построенный автомат предложенный язык.
Варианты индивидуальных заданий
1. Язык L состоит из цепочек следующего вида:
aabb, ab, ba, bbaa, aaabbb,…
МП-автомат:
M:
2. Язык L состоит из цепочек следующего вида:
ab*, abab*, ababab*,…, ba*, baba*,…
МП-автомат:
M:
3. Язык L состоит из цепочек следующего вида::
abba, abbaabba
МП-автомат:
M:
4. Язык L состоит из согласованных скобок:
МП-автомат:
M:
5 Язык L состоит из цепочек следующего вида::
cdd, cddcdd, …, dcc, dccdcc,…
МП-автомат:
M:
6. Язык L состоит из цепочек следующего вида::
cddd, cdddcddd, …, dccc, dcccdccc,…
МП-автомат:
M:
.7 Язык L состоит из цепочек следующего вида::
cаdас, cаdаcсаdас, …
МП-автомат:
.8 Язык L состоит из цепочек следующего вида::
cаddас, cаddаcсаddас, …
МП-автомат:
9. Язык L состоит из цепочек следующего вида::
abbba, abbbaabbba
МП-автомат:
M:
.10 Язык L состоит из цепочек следующего вида::
abcc, aabbcc, aaabbbcc, aaaabbbbcc ….
МП-автомат:
M:
.11 Язык L состоит из цепочек следующего вида::
abbc, abbcabbc, abbcabbcabbc,….
МП-автомат:
M:
Контрольные вопросы
1. дать определение конечного детерминированного МП - автомата.
2. Чем отличается недетерминированный МП - автомат от детерминированного МП - автомата?
3. Совпадает или нет класс языков, допускаемый детерминированным и недетерминированным МП - автоматами?
4. Какой класс языков допускает недетерминированный МП - автомат?
5. Что такое МП - преобразователь?
6. Что такое конфигурация МП - автомата?
7. Что такое рекурсивные грамматики (право - рекурсивные и лево - рекурсивные)?
Лабораторная работа №3
S -грамматика
Продукции S-грамматики удовлетворяют следующим требованиям:
А) правая часть каждой продукции начинается с терминала;
Б) в тех случаях, когда в левой части более чем одного порождающего правила появляется один и тот же нетерминал, соответствующие правые части начинаются с разных терминалов.
|
ПРИМЕР S-грамматики:
(1) <S> -> p<X>
(2) <S> -> q<Y>
(3) <X> -> a<X>b
(4) <X> ->x
(5) <Y> -> a<Y>d
(6) <Y>-> y
При разборе предложения языка, определенного S-грамматикой,всегда можно точно определить,какую продукцию нужно применить на каждом этапе разбора. Например, на первом этапе разбора, мы должны определить, какое из правил мы должны применить – первое или второе: если анализируемая цепочка начинается с символа p, то – первое правило, если с q – второе и т.д.
LL(I)-грамматика является обобщением S-грамматики, но принцип обобщения позволяет строить аналогичные нисходящие анализаторы.
Правые части в LL(I)-грамматике не обязательно должны начинаться с терминальных символов, но заданный вариант какого-либо правила может дать начало только строкам, начинающимся с одного терминального символа из конкретного множества терминалов.
Например:
(1) <S> -> <R><Y>
(2) <S>-> <T><Z>
(3) <R> -> p<X>b
(4) <T> -> q<Y>d
(5) <X> -> …
(6) <Y> -> …
Из рассмотрения представленных правил можно заключить, что правило <S> -> <R><Y> нужно применить при нисходящем разборе, когда просматриваемым символом входной строки является символ p. Аналогично порождающее правило <S>-> <T><Z> должно применяться в том случае, если таким символом является терминальный символ q.
ОПРЕДЕЛЕНИЕ: множества символов, по которым при синтаксическом разборе входной строки производится выбор того или иного порождающего правила, называются множествами направляющих символов или направляющими множествами.
План отчета
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
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕКСТИЛЬНЫЙ УНИВЕСИТЕТ им. А.Н. КОСЫГИНА
Учебно-методический комплекс по специальности 230104.65 Системы автоматизированного проектирования,
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к лабораторным работам по курсу «Лингвистическое обеспечение систем логистики» (6 семестр)
Составила: доц. Т.М. Кузьмина
Допущено к изданию редакционно-издательским советом университета
Москва 2010
Лабораторная работа №1
|
|
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!