БРЯНСКИЙ ОТКРЫТЫЙ ИНСТИТУТ УПРАВЛЕНИЯ И БИЗНЕСА

Образовательный консорциум Среднерусский университет

Негосударственное образовательное учреждение

высшего профессионального образования

Брянский открытый институт управления и бизнеса

УТВЕРЖДАЮ

Проректор по учебной и

инновационной работе Хвостенко Т.М.

«_» 20 г

ТЕОРИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ И МЕТОДЫ

ТРАНСЛЯЦИИ

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ

Укрупненная группа направлений и Информатика и вычислительная техника специальностей Специальность: 230105.65 «Программное обеспечение вычислительной техники и автоматизированных систем»

Специализация: «Программное обеспечение вычислительной техники и автоматизированных систем»

Разработал: Горбунов А.Н.

№ На учебный ОДОБРЕНО УТВЕРЖДАЮ пп год на заседании кафедры заведующий кафедрой Протокол Дата Подпись Дата 1 20 - 20 № «»20г. «»20г.

2 20 - 20 № «»20г. «»20г.

3 20 - 20 № «»20г. «»20г.

… 20 - 20 № «»20г. «»20г.

Брянск 1. Основные дидактические единицы СД.04 Теория языков программирования и методы трансляции Основы теории формальных языков и грамматик; распознаватели и преобразователи:

конечные автоматы и преобразователи, автоматы и преобразователи с магазинной памятью; связь между грамматиками и автоматами; формальные методы описания перевода: СУ-схемы, транслирующие грамматики, атрибутные транслирующие грамматики;

алгоритмы синтаксического анализа для LL(K)грамматик, LR(K)-грамматик, грамматик предшествования; включение семантики в алгоритмы синтаксического анализа.

.

2. Цель и задачи изучения дисциплин Дисциплина «Теория языков программирования и методы трансляции»

включает 17 тем. Темы объединены в пять дидактических единиц: «Основы теории формальных языков и грамматик», «Конечные распознающие автоматы», «Распознаватели и преобразователи», «Формальные методы описания перевода», «Методы трансляции».

Цель изучения дисциплины: формирование знаний о принципах построения грамматик языков программирования, методах грамматического разбора, анализа и синтеза конечных распознающих автоматов, методах трансляции и построения трансляторов.

Основными задачами изучения дисциплины являются:

1) изучение теоретических основ и принципов построения формальных грамматик и языков;

2) изучение принципов построения конечных распознающих автоматов;

3) приобретение навыков использования синтаксически управляемых схем и транслирующих грамматик для построения трансляторов.

3. ТРЕБОВАНИЯ К УРОВНЮ ОСВОЕНИЯ ДИСЦИПЛИНЫ

В результате изучения дисциплины студенты должны:

знать:

- основы теории формальных языков и грамматик, - основные принципы анализа и синтеза конечных автоматов;

- алгоритмы синтаксического анализа для LL(k) –грамматик и LR(k)грамматик, - нисходящие и восходящие методы грамматического разбора, - методы трансляции и способы построения трансляторов, уметь:

- производить синтез конечных автоматов по заданной формальной грамматике;

- составлять правила для транслирующей грамматики и производить ее проверку на соответствие заданным входному и выходному языкам;

- составлять функции переходов и производить анализ процесса реализации входной цепочки магазинным автоматом;

владеть:

- основными методами построения формальных грамматик и - основными методами грамматического разбора и способами

class='zagtext'> 4. ТЕМАТИЧЕСКАЯ СТРУКТУРА ДИСЦИПЛИНЫ

дидактической единицы Основы теории формальных 3 Распознаватели Нисходящие распознаватели. LL(k)- грамматики.

Формальные методы описания перевода

5. МЕСТО ДИСЦИПЛИНЫ В СТРУКТУРНО-ЛОГИЧЕСКОЙ

Для изучения дисциплины, необходимы знания и умения из дисциплин, изучаемых ранее по учебному плану. Согласно учебному плану дисциплина «Теория языков программирования и методы трансляции» изучается в пятом семестре третьего курса при очной форме обучения и в шестом семестре третьего курса при заочной форме обучения.

Знания и умения, приобретаемые студентами после изучения дисциплины будут использоваться ими в ходе осуществления профессиональной деятельности.

6. ВИДЫ УЧЕБНОЙ РАБОТЫ И ИХ ТРУДОЕМКОСТЬ

дисциплины

7. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

Раздел 1. Основы теории формальных языков и грамматик Основы теории формальных языков и грамматик. Основные понятия и определения. Операции над языками. Вывод контекстно-свободных (кс) – грамматик и правила построения дерева вывода. Синтаксический разбор.

Способы задания схем грамматик. Форма Бэкуса-Наура. Построение грамматик и грамматики, описывающие основные конструкции языков программирования. Приведенные грамматики. Определение непроизводящих, недостижимых и бесполезных символов. Исключение леворекурсивных и цепных правил.

Раздел 2. Конечные распознающие автоматы Недетерминированные конечные автоматы. Преобразование некоторых грамматик к автоматному виду. Детерминированные конечные автоматы.

Эквивалентные состояния и автоматы. Автоматы с магазинной памятью.

Построение автомата с магазинной памятью. Способы задания функций перехода автомата с магазинной памятью. Связь между грамматиками и автоматами Нисходящие распознаватели. LL(k)- грамматики. Разделенные грамматики.

Построение детерминированного нисходящего распознавателя. Восходящие распознаватели. LR(k) – грамматики. Построение и работа распознавателя..

Построение SLR(1)-распознавателя. Восходящие распознаватели для грамматик с аннулирующими правилами.

Раздел 4. Формальные методы описания перевода Описание перевода или трансляции. Синтаксически – управляемые (СУ) – схемы. Построение простой СУ – схемы. Транслирующие грамматики. Построение транслирующей грамматики по СУ- схеме.

Магазинные преобразователи. Перевод, определяемый преобразователем.

Порядок построения детерминированного магазинного преобразователя.

Построение восходящих преобразователей. Атрибутные транслирующие (АТ) грамматики. Синтаксический анализ с использованием АТ – грамматики. L – атрибутные транслирующие (LAT) грамматики. Атрибутные преобразователи (АП). Представление правил LAT – грамматики в магазине.

Порядок построения АП Трансляторы: интерпретаторы и компиляторы. Стадии работы компилятора.

Лексический анализ. Синтаксический анализ. Восходящие и нисходящие методы синтаксического анализа. Метод операторного предшествования.

Метод рекурсивного спуска. Генерация объектного кода. Особенности компиляторов. Интерпретаторы.

7.2. Распределение разделов дисциплины по видам занятий 1 Основы теории формальных языков и грамматик.

Основные понятия и определения. Операции над языками.

2 Вывод контекстно-свободных (кс) – грамматик и правила Способы задания схем грамматик. Форма Бэкуса-Наура.

3 Построение грамматик и грамматики, описывающие основные конструкции языков программирования.

4 Приведенные грамматики. Определение непроизводящих, леворекурсивных и цепных правил.

6 Детерминированные конечные автоматы. Эквивалентные состояния и автоматы.

7 Автоматы с магазинной памятью. Построение автомата с автомата с магазинной памятью 8 Нисходящие распознаватели. LL(k)- грамматики.

детерминированного нисходящего распознавателя.

9 Восходящие распознаватели. LR(k) – грамматики.

Построение и работа распознавателя.

10 Построение SLR(1)-распознавателя. Восходящие 11 Описание перевода или трансляции. Синтаксически – управляемые (СУ) – схемы. Построение простой СУ – транслирующей грамматики по СУ- схеме.

12 Магазинные преобразователи. Перевод, определяемый детерминированного магазинного преобразователя.

Построение восходящих преобразователей.

Синтаксический анализ с использованием АТ – грамматики. L – атрибутные транслирующие (LAT) 14 Атрибутные преобразователи (АП). Представление правил LAT – грамматики в магазине. Порядок построения АП 15 Трансляторы: интерпретаторы и компиляторы. Стадии работы компилятора. Лексический анализ.

16 Синтаксический анализ. Восходящие и нисходящие предшествования. Метод рекурсивного спуска.

17 Генерация объектного кода. Особенности компиляторов.

Интерпретаторы.

Всего 1 Основы теории формальных языков и грамматик.

Основные понятия и определения. Операции над языками.

2 Вывод контекстно-свободных (кс) – грамматик и правила Способы задания схем грамматик. Форма Бэкуса-Наура.

3 Построение грамматик и грамматики, описывающие основные конструкции языков программирования.

4 Приведенные грамматики. Определение непроизводящих, леворекурсивных и цепных правил.

6 Детерминированные конечные автоматы. Эквивалентные состояния и автоматы.

7 Автоматы с магазинной памятью. Построение автомата с автомата с магазинной памятью детерминированного нисходящего распознавателя.

9 Восходящие распознаватели. LR(k) – грамматики.

Построение и работа распознавателя.

10 Построение SLR(1)-распознавателя. Восходящие 11 Описание перевода или трансляции. Синтаксически – управляемые (СУ) – схемы. Построение простой СУ – транслирующей грамматики по СУ- схеме.

12 Магазинные преобразователи. Перевод, определяемый детерминированного магазинного преобразователя.

Построение восходящих преобразователей.

Синтаксический анализ с использованием АТ – грамматики. L – атрибутные транслирующие (LAT) 14 Атрибутные преобразователи (АП). Представление правил LAT – грамматики в магазине. Порядок построения АП 15 Трансляторы: интерпретаторы и компиляторы. Стадии работы компилятора. Лексический анализ.

16 Синтаксический анализ. Восходящие и нисходящие предшествования. Метод рекурсивного спуска.

17 Генерация объектного кода. Особенности компиляторов.

Всего

8. ЛАБОРАТОРНЫЕ РАБОТЫ

Учебным планом не предусмотрены

9. ПРАКТИЧЕСКИЕ ЗАНЯТИЯ

Рекомендуемые темы для проведения практических занятий:

1. Основные понятия формальных грамматик. Алфавит, цепочка, нетерминальные и терминальные символы. Синтаксис и семантика.

Операции над цепочками символов.

2. Классификация грамматик (по Н. Хомскому). Правила вывода.

3. Схемы грамматик. Левосторонние и правосторонние грамматики.

4. Построение грамматики.

5. Контекстно-свободные (КС) грамматики. Преобразование КСграмматики в автоматную. Конечные распознающие автоматы.

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

6. Детерминированные конечные автоматы. Устранение недетерминированности при преобразовании недетерминированного автомата в детерминированный.

7. Эквивалентные состояния в автоматах. Минимизация автоматов.

8. Построение автомата с магазинной памятью. Функции переходов.

9. LL(1) – грамматики. Нисходящие распознаватели.

10. LR(1) – грамматики. Восходящие распознаватели.

11. Построение простой синтаксически-управляемой (СУ) схемы.

12. Построение транслирующей грамматики по СУ- схеме.

13. Перевод или трансляция. Магазинные преобразователи.

14. Составление правил атрибутной транслирующей грамматики и проверка их правильности путем моделирования.

15. Принципы построения компиляторов. Лексемы. Лексический анализ.

16. Нисходящие и восходящие методы синтаксического разбора.

17. Генераторы объектного кода.

1. Алфавит, цепочка, нетерминальные и терминальные символы.

Синтаксис и семантика. Классификация грамматик (по Н. Хомскому).

2. Схемы грамматик. Построение грамматики.

3. Построение недетерминированного автомата по автоматной 4. Устранение недетерминированности при преобразовании недетерминированного автомата в детерминированный.

5. Построение автомата с магазинной памятью. Функции переходов.

6. Нисходящие и восходящие распознаватели.

7. Атрибутные транслирующие грамматики.

8. Трансляторы: интерпретаторы и компиляторы. Синтаксический анализ.

Нисходящие и восходящие методы синтаксического анализа.

9. СЕМИНАРСКИЕ ЗАНЯТИЯ

Семинарские занятия не предусмотрены.

11. САМОСТОЯТЕЛЬНАЯ РАБОТА

11.1 ОБЩИЙ ПЕРЕЧЕНЬ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

Рекомендуются следующие виды самостоятельной работы:

- изучение теоретического материала с использованием курса лекций и рекомендованной литературы;

- подготовка к практическим занятием;

- подготовка к экзамену по дисциплине.

Тема курсовой работы: «Синтез конечного распознающего автомата».

Работа выполняется в соответствии с индивидуальным заданием.

1) Формальные грамматики. Основные понятия: (Алфавит. Цепочка.

Грамматика. Продукционное правило).

2) Сентенциальная форма. Предложение. Язык. Фраза.

3) Понятия разбора. Синтаксические деревья.

4) Грамматика БНФ, правила вывода.

5) Нотация Бекуса-Наура. Вывод цепочек.

6) Синтаксический разбор. Левый и правый выводы.

7) Дерево грамматического разбора.

8) Неоднозначные и эквивалентные грамматики.

9) Вывод в КС-грамматиках и правила построения дерева вывода.

10) Автоматные грамматики.

11) Классификация языков.

12) Конечные автоматы. Недетерминированные автоматы.

13) Автоматы Мили и Мура.

14) Детерминированный конечный автомат.

15) Минимизация автоматов. Эквивалентность состояний.

16) Автоматы с магазинной памятью.

17) Принципы работы МП - автомата.

18) Регулярные выражения.

19) Система переходов.

20) Преобразование системы переходов в конечный автомат.

21) Преобразование модифицированной БНФ к БНФ.

22) Основные функции транслятора.

23) Лексема, лексический анализ.

24) Синтаксис и семантика языка программирования, их учет при построении транслятора.

25) Синтаксический анализ. Метод операторного предшествования.

26) Восходящие и нисходящие методы синтаксического анализа.

27) Генерация объектного кода.

28) Нисходящие распознаватели. Распознаватели и LL(k) - грамматики 29) Разделенные грамматики 30) LL(1) – грамматики.

31) Синтаксически управляемые схемы. Перевод, определяемый СУсхемой.

32) Транслирующие грамматики.

33) Построение транслирующей грамматики по СУ - схеме.

34) Атрибутные транслирующие грамматики. Определение АТ-грамматик 11.4. ДЕМОНСТРАЦИОННЫЙ ВАРИАНТ ТЕСТА 1. Задание Алфавит – это:

последовательность символов;

последовательность букв;

совокупность неделимых символов.

2. Задание Формальная грамматика – это четверка:

3. Задание Язык, порождаемый грамматикой G - это:

множество терминальных цепочек;

совокупность цепочек;

множество слов, составленных из терминальных символов 4. Задание Продукционное правило - это правило, порождающее цепочки символов;

правило, определяющее значение символа;

правило, задающее схему грамматики;

правило, задающее последовательность слов.

5. Задание Синтаксический разбор – это:

анализ цепочки на соответствие правилам грамматики;

анализ правил грамматики анализ символов, составляющих цепочку.

6. Задание Контекстно-зависимая грамматика допускает:

замену в левой части правила только одного символа;

замену в левой части правила двух символов;

замену в левой части правила любого количества символов;

замену символов в правой части правила.

7. Задание Контекстно-свободная грамматика – это грамматика имеющая правила вывода вида:

8. Задание Недетерминированный конечный автомат:

допускает возможность нескольких переходов по одному допускает возможность анализа количества входных символов;

допускает возможность посимвольного разбора цепочки;

используется для синтаксического анализа.

9. Задание Автомат Мура отличается от автомата Мили независимостью функции выходов от входных символов;

независимостью функции переходов от состояний;

независимостью функций переходов и выходов от входных 10. Задание Минимальный автомат имеет:

минимально возможное число состояний;

минимально возможное число входных символов;

минимально возможное число выходных сигналов;

минимально возможное число распознаваемых цепочек.

11. Задание Магазинный автомат позволяет:

решить задачу распознавания принадлежности цепочки осуществлять формирование входных сигналов;

осуществлять управление процессом работы ЭВМ;

решить задачу накопления символов входной цепочки.

12. Задание Синтаксическая диаграмма – это:

графическое представление правил грамматики;

графическое представление распознающего автомата;

графическое представление магазинного автомата;

графическое представление символов грамматики.

13. Задание Конечный автомат и система переходов связаны...

правилами грамматики;

диаграммой состояний.

14. Задание Синтаксически-управляемая схема – это:

схема синтаксически управляемого перевода;

схема управления переходами конечного автомата;

схема структуры магазинного автомата;

схема управления формированием объектного кода.

15. Задание Разделенные грамматики это:

грамматики магазинных автоматов;

грамматики, содержащие атрибуты;

контекстно зависимые грамматики.

16. Задание Нисходящими распознавателями являются:

распознаватели, обрабатывающие верхние правила раньше распознаватели, использующие LR(k)-грамматики;

распознаватели, обрабатывающие нисходящие цепочки;

распознаватели, обрабатывающие нетерминальные символы.

17. Задание Транслирующая грамматика – это:

КС-грамматика, множество терминальных символов которой называются символами действия;

LL(k)-грамматика;

LR(k)-грамматика;

КС-грамматика, использующая только входные терминальные 18. Задание Атрибуты в транслирующей грамматике … отражают семантическую информацию;

служат для описания перевода;

выполняют функции ввода цепочек символов;

выполняют функции дополнительных служебных символов.

19. Задание Лексический анализ – это:

определение правильности записи лексем;

определение порядка записи лексем;

анализ нетерминальных символов;

анализ входных цепочек.

20. Задание Метод рекурсивного спуска служит для.., синтаксического разбора входных цепочек;

определения порядка следования входных символов;

анализа структуры входных цепочек;

анализа терминальных символов.

21. Задание Метод операторного прешествования относится к … восходящим методам синтаксического разбора;

методам анализа правил грамматики;

методам построения цепочек символов;

нисходящим методам синтаксического разбора.

22. Задание Семантика языка программирования учитывается при … генерации объектного кода;

выполнении синтаксического анализа;

формировании входных цепочек;

записи терминальных символов.

23. Задание Интерпретатор представляет собой … формирователь машинного кода;

анализатор объектного кода;

анализатор правил грамматики.

24. Задание Компилятор – это:

транслятор, формирующий машинный код на основе анализа преобразователь правил грамматики языка программирования;

формирователь входных цепочек;

анализатор последовательности терминальных символов.

25. Задание Детерминированный конечный автомат предназначен для … распознавания входных цепочек терминальных символов;

управления программными комплексами;

анализа объектного кода;

формирования цепочек нетерминальных и терминальных

12. РЕКОМЕНДУЕМОЕ ИНФОРМАЦИОННО-МЕТОДИЧЕСКОЕ

ОБЕСПЕЧЕНИЕ

Основой нормативного сопровождения дисциплины являются: ГОС ВПО по специальности 230105.65 «Программное обеспечение ВТ и АС».

12.2. МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

В состав учебно-методического комплекса дисциплины входят следующие материалы:

- аннотация дисциплины;

- рабочая программа дисциплины;

- методические указания по освоению дисциплины;

- методические указания для аудиторных занятий;

- курс лекций;

- глоссарий;

- банк тестовых заданий.

1. Иванова Г.С. Технология программирования. - М.:КНОРУС, 2011. – 356 с.

2. Кауфман В. Ш. Языки программирования. Концепции и принципы.

- М.: ДМК Пресс, 2011. - 464 с. - http://www.biblioclub.ru 3. Сальников Ю.Н. Программирование. Базовый курс. – М.: Маркет ДС, 2010. – 336 с.

1. Алгазин С. Д., Кондратьев В. В. Программирование на Visual Fortran. - М.: Диалог-МИФИ, 2008. - 472 с. - http://www.biblioclub.ru 2. Батоврин В. К. Системная и программная инженерия. Словарьсправочник. Учебное пособие для вузов. - М.: ДМК Пресс, 2010. - 280 с. http://www.biblioclub.ru информатики:программирование,вычислительная техника,Интернет(словарь). - М.:Эксмо, 2007. – 640 с.

4. Фаронов В.В. Delphi: программирование на языке высокого уровня. СПб.:Питер, 2008. – 640 с.

12.5. ТЕХНИЧЕСКИЕ И ПРОГРАММНЫЕ СРЕДСТВА

Для проведения практических занятий по дисциплине требуется компьютерный класс c общим программным обеспечением (Microsoft Office), а также специализированные программные системы для изучения программирования – Visual С.

Для проведения лекционных занятий используется ноутбук, экран и мультимедийный проектор.

Программу составил:

Горбунов А.Н., доцент Брянского института управления и бизнеса кафедры «Информатика и программное обеспечение «»_ 20 г.

Программа одобрена и утверждена на заседании кафедры «Информатика и программное обеспечение»:

Протокол № 1 от «29» августа 2012 г.

Зав. кафедрой «Информатика и программное обеспечение»

Гришанова Т.В.