Московский государственный текстильный унивеситет им. А. Н. Косыгина

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕКСТИЛЬНЫЙ УНИВЕСИТЕТ им. А.Н. КОСЫГИНА

 

 

Учебно-методический комплекс по специальности 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. Множество терминальных символов V_t={a,b,c,d}.

Множество нетерминальных символов V_n={A,B.S}

Начальное состояние S=S

Правила подстановки:

S®AB|bS                

A®aA|dB                     

B®AB|c                   

 

2. Множество терминальных символов V_t={a,b,c,d}.

Множество нетерминальных символов V_n={A,B.S}

Начальное состояние S=S

Правила подстановки:

S®aAaB|bAbB                

A®dS| λ                               

B®cB|a                                

 

3. Множество терминальных символов V_t={a,b,c,d,m}.

Множество нетерминальных символов V_n={A,B,D}

Начальное состояние S=A

Правила подстановки:

A®aB|bA

B®cD| λ

D®dBd|m

 

4. Множество терминальных символов V_t={a,b,d,m,q}.

Множество нетерминальных символов V_n={X,Y,Z,S}

Начальное состояние S=S

Правила подстановки:

S®aXY| bYZ             

X®mXq| λ           

Y®bY|d                                 

Z®S|qZ                                                                  

 

5. Множество терминальных символов V_t={a,b,c,d,q,p}.

Множество нетерминальных символов V_n={X,Y,N,S}

Начальное состояние S=S

Правила подстановки:

S®aXY|XY                      

X®bY|cN| λ                           

N®qY|p                                 

Y®dN                                    

6. Множество терминальных символов V_t={x,y,c,m}.

Множество нетерминальных символов V_n={A,B,C,S}

Начальное состояние S=S

Правила подстановки:

S®AB|xCB

A®yA|m

B®aC|c

C®bC|λ

 

 

7. Множество терминальных символов V_t={ x,y,c,m }.

Множество нетерминальных символов V_n={A,B,C,S}

Начальное состояние S=S

Правила подстановки:

S®AB|xCB

A®yA| λ

B®aC|c

C®bC|m

 

8. Множество терминальных символов V_t={a,b,c,d}.

Множество нетерминальных символов V_n={A,B.S}

Начальное состояние S=S

Правила подстановки:

S®aAaB|bAbB                

A®mS| λ                               

B®dmB|a                                

 

9. Множество терминальных символов V_t={a,b,c,d,m}.

Множество нетерминальных символов V_n={S,A,B,D}

Начальное состояние S=S

Правила подстановки:

S®aAa|bAb

A®aBa|bA

B®cD| λ

D®dBd|m

 

10. Множество терминальных символов V_t={a,b,d,m,q}.

Множество нетерминальных символов V_n={X,Y,Z,S}

Начальное состояние S=S

Правила подстановки:

S®aX| bYZ             

X®mXq| λ           

Y®bY|d                                     

Z®S|qZ        

 

11. Множество терминальных символов V_t={a,b,c,d,q,p}.

Множество нетерминальных символов V_n={X,Y,N,S}

Начальное состояние S=S

Правила подстановки:

S®aXY|XY                      

X®cN| λ                           

N®qY|p                                 

Y®dN                                    

12. Множество терминальных символов V_t={x,y,c,m}.

Множество нетерминальных символов V_n={A,B,C,S}

Начальное состояние S=S

Правила подстановки:

S®AB|xCa

A®yA|m

B®aC|c

C®bC|λ

 

 

13. Множество терминальных символов V_t={ x,y,c,m,n }.

Множество нетерминальных символов V_n={A,B,C,S}

Начальное состояние S=S

Правила подстановки:

S®An|CB

A®yA| λ

B®aB|c

C®bC|m

 

14. Множество терминальных символов V_t={a,b,c,d}.

Множество нетерминальных символов V_n={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