Правительство Российской Федерации
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
"Национальный исследовательский университет
"Высшая школа экономики"
Факультет бизнес-информатики
Программа дисциплины
«Фо рмаль ные языки и грамм а тики »
для направления 231000.62 – Программная инженерия
подготовки бакалавров (2 курс)
Авторы программы: А.О. Сухов, [email protected]
Одобрена на заседании кафедры информационных технологий в бизнесе
«___»____________ 2013 г.
Зав. кафедрой
/ О.Л. Викентьева /
Утверждена Учебно-методическим Советом ПФ ГУ-ВШЭ
«___»_____________2013 г.
Председатель
/ Г.Е. Володина /
Пермь, 2013
Настоящая программа не может быть использована другими подразделениями
университета и другими вузами без разрешения кафедры-разработчика программы
Государственный университет – Высшая школа экономики
Программа учебной дисциплины «Формальные языки и грамматики»
231000.62 – Программная инженерия подготовки бакалавра
1.
Область применения и нормативные ссылки
Настоящая программа учебной дисциплины устанавливает минимальные требования к
знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности
для дисциплины «Формальные языки и грамматики», изучаемой на втором курсе
бакалавриата по направлению «Программная инженерия» в НИУ ВШЭ – Пермь.
Программа предназначена для преподавателей, ведущих данную дисциплину,
учебных ассистентов и студентов направления подготовки 231000.62 – Программная
инженерия, изучающих дисциплину «Формальные языки и грамматики» на втором курсе.
Программа разработана в соответствии с:
Образовательным стандартом государственного образовательного бюджетного
учреждения высшего профессионального образования
«Государственный
университет – Высшая школа экономики», в отношении которого установлена
категория «Национальный исследовательский университет» по направлению
подготовки 231000.62 «Программная инженерия» (Уровень подготовки: Бакалавр).
Образовательной программой для направления подготовки 231000.62 –
Программная инженерия, реализуемой в НИУ ВШЭ – Пермь.
Рабочим учебным планом по направлению подготовки 231000.62 – Программная
инженерия, утвержденным в 2013 г.
2.
Цели освоения дисциплины
Цель освоения дисциплины «Формальные языки и грамматики» состоит в изучении
теории формальных языков и грамматик, их практического применения для описания языков
программирования и реализации трансляторов.
Для достижения поставленной цели при изучении дисциплины решаются следующие
задачи:
Рассмотреть основные понятия теории формальных языков и грамматик.
Освоить приемы формального описания языков программирования.
Познакомиться с методами лексического, синтаксического разбора.
Освоить инструментальные средства, автоматизирующие построение трансляторов.
Изучение теоретического материала поддерживается практическими занятиями. Часть
вопросов, хорошо обеспеченных литературой и не представляющих сложности для изучения
ввиду того, что их содержание основано на теоретическом материале и практическом опыте,
полученном при изучении других дисциплин, вынесена на самостоятельное изучение.
Содержание программы дисциплины должно обеспечить базовую подготовку
студентов в процессе формирования устойчивых знаний и навыков использования
теоретических основ программной инженерии при разработке приложений.
Навыки работы закрепляются при выполнении контрольной работы и домашних
заданий.
3.
Компетенции обучающегося, формируемые в результате освоения
дисциплины
В результате освоения дисциплины студент должен:
Иметь представление:
о существующих формальных основах теории трансляции;
об использовании методов разбора грамматик при разработке трансляторов.
Знать:
основные термины, понятия, изучаемые в рамках данной дисциплины;
2
Государственный университет – Высшая школа экономики
Программа учебной дисциплины «Формальные языки и грамматики»
231000.62 – Программная инженерия подготовки бакалавра
основные способы задания формальных языков;
методы разбора грамматик различных классов.
Уметь:
описывать формальные языки;
выполнять классификацию языков по виду грамматики;
строить конечные автоматы для разбора грамматики;
строить деревья разбора грамматики;
применять теоретические знания, полученные в рамках курса, при создании
трансляторов.
Обладать навыками использования инструментальных средств для построения
трансляторов.
В результате освоения дисциплины студент осваивает следующие компетенции:
Код по
стандарту
Дескрипторы – основные признаки освоения
(показатели достижения результата)
Способность
логически верно,
аргументировано и
ясно строить устную
и письменную речь.
ОК-2
Демонстрирует умение обосновывать
предлагаемые решения, доказывать
правильность используемых методов,
анализировать и оценивать эффективность
решений.
Стремление к
саморазвитию,
повышению своей
квалификации и
мастерства.
ОК-6
Демонстрировать
навыки
моделирования,
анализа и
использования
формальных методов
конструирования
программного
обеспечения.
ПК-12
Компетенция
Формы и методы
обучения,
способствующие
формированию и
развитию
компетенции
Аудиторные
занятия проводятся
в форме,
предполагающей
активное участие
студентов в работе,
обсуждение
проблем и анализ
решений,
предлагаемых
студентами и
преподавателем на
лекциях и
практических
занятиях.
Демонстрирует способность самостоятельно Самостоятельное
определять формирующиеся дефициты
изучение
знаний, умений и навыков в ходе обучения. отдельных тем.
Выполнение
индивидуальных
Показывает умение сформулировать
проблемы, связанные с недостатком знаний заданий (с
получением
и навыков, и выбрать подходы к их
консультаций
решению.
преподавателя).
Владеет знаниями, достаточными для
самостоятельного изучения и понимания
формальных моделей.
Способен описывать формальные языки, Практические
занятия.
определять подходящие методы
Выполнение
синтаксического разбора языков.
индивидуальных
заданий,
требующих знаний
в области
формальных языков
и грамматик.
3
Государственный университет – Высшая школа экономики
Программа учебной дисциплины «Формальные языки и грамматики»
231000.62 – Программная инженерия подготовки бакалавра
Код по
стандарту
Компетенция
Демонстрировать
навыки
использования
операционных
систем, сетевых
технологий, средств
разработки
программного
интерфейса,
применения языков и
методов формальных
спецификаций,
систем управления
базами данных.
ПК-15
Дескрипторы – основные признаки освоения
(показатели достижения результата)
Способен применять полученные при
изучении дисциплины теоретические
знания при разработке трансляторов.
Формы и методы
обучения,
способствующие
формированию и
развитию
компетенции
Выполнение
индивидуальных
заданий, связанных
с разработкой
трансляторов
языков
программирования.
В ходе изучения курса студенты должны научиться свободно оперировать основными
понятиями изучаемой дисциплины, получить знания и навыки, необходимые для
самостоятельного освоения формальных основ теории трансляции.
4.
Место дисциплины в структуре образовательной программы
Настоящая дисциплина относится к циклу математических и естественнонаучных
дисциплин (вариативная часть).
Изучение данной дисциплины базируется на следующих дисциплинах:
Информатика, математическая логика и теория алгоритмов.
Дискретная математика.
Программирование.
Для освоения учебной дисциплины студенты должны владеть следующими знаниями:
Знание основ дискретной математики.
Знание теории конечных автоматов.
Знание основ процедурного и объектно-ориентированного программирования.
Знание рекурсивных типов данных и алгоритмов реализации основных операций над
динамическими структурами данных.
Основные положения дисциплины будут использованы в дальнейшем при изучении
следующих дисциплин: «Введение в методы трансляции», «Введение в формальные методы
программной
инженерии»,
«Предметно-ориентированные
языки
и
языковые
инструментарии», «Функциональное и логическое программирование», а также при
выполнении курсовых и выпускных квалификационных работ.
5.
Тематический план учебной дисциплины
№
Название раздела
1
Основные понятия теории формальных
языков и грамматик.
Виды грамматик и языков.
Проблема разбора.
2
3
Всего
часов
26
34
28
4
Аудиторные часы
СамостояПрактические тельная
Лекции
работа
занятия
6
8
10
10
4
8
4
16
18
Государственный университет – Высшая школа экономики
Программа учебной дисциплины «Формальные языки и грамматики»
231000.62 – Программная инженерия подготовки бакалавра
4
5
6
6.
Нисходящий разбор.
Восходящий разбор.
Инструментальные средства построения
трансляторов.
Всего:
20
38
44
4
6
4
4
6
8
12
20
32
180
34
38
108
Контроль знаний студентов
6.1. Формы контроля знаний студентов
Тип
контроля
Текущий
(неделя)
Итоговый
1 год
Форма контроля
1
2
Контрольная работа
7
Домашнее задание
4
Зачет
Параметры
3
9
*
4
Письменная работа (45 минут).
Отчет о выполнении домашнего
задания.
Письменный зачет (90 минут).
6.2.Критерии оценки знаний, навыков
Текущий контроль предусматривает выполнение контрольной работы и двух
домашних заданий. Оценки по всем формам текущего контроля выставляются по 10-ти
балльной шкале.
Предусматривается возможность «защиты» выполненных домашних заданий. В ходе
защиты студент должен продемонстрировать знание профессиональной терминологии в
рамках соответствующей темы, продемонстрировать знание теоретического материала по
теме, а также умение оценивать эффективность решений. Кроме того, он должен показать,
что владеет культурой мышления, способен к обобщению, анализу, восприятию
информации, постановке цели и выбору путей ее достижения, способен логически верно,
аргументировано и ясно строить речь.
Итоговый контроль осуществляется в форме письменной работы.
Итоговая оценка определяется в соответствии с «Положением об организации
контроля знаний», утверждённым протоколом ученого совета НИУ ВШЭ от 24.06.2011 № 26.
Формы и сроки проведения определяются учебным планом и графиком учебного
процесса.
Итоговый зачет включает теоретические вопросы по темам всего курса. Примерный
перечень вопросов для подготовки к зачету по дисциплине представлен в разделе 9.2.
Критерии оценивания письменного ответа представлены в следующей таблице:
8-10 баллов
Оценка
Параметр
Критерии оценки
оценки
Содержание Содержание ответа в целом соответствует теме задания. В ответе
отражен
весь
материал,
предусмотренный
заданием.
Продемонстрировано знание фактического материала, отсутствуют
фактические ошибки.
Понимание
Продемонстрировано
уверенное
владение
понятийнотерминологическим
аппаратом
дисциплины
(уместность
употребления, аббревиатуры, толкование и т.д.), отсутствуют
ошибки в употреблении терминов.
Показано умелое использование категорий и терминов дисциплины
в их ассоциативной взаимосвязи.
5
Государственный университет – Высшая школа экономики
Программа учебной дисциплины «Формальные языки и грамматики»
231000.62 – Программная инженерия подготовки бакалавра
Структура и
логика
Содержание
6-7 баллов
Понимание
Структура и
логика
1-3
балла
4-5 баллов
Содержание
Продемонстрировано
умение
аргументировано
излагать
собственную точку зрения.
Студент продемонстрировал уверенное владение освоенным
материалом, изложение сопровождено адекватными примерами из
практики.
Ответ четко структурирован и выстроен в заданной логике. Части
ответа логически взаимосвязаны.
Отражена логическая структура вопроса: постановка проблемы –
аргументация – выводы.
Содержание ответа в целом соответствует теме задания. В ответе
отражено 75-80% материала, предусмотренного заданием.
Продемонстрировано знание фактического материала, встречаются
несущественные фактические ошибки.
Продемонстрировано владение понятийно-терминологическим
аппаратом дисциплины (уместность употребления, аббревиатуры,
толкование и т.д.), отсутствуют ошибки в употреблении терминов.
Показано умелое использование категорий и терминов дисциплины
в их ассоциативной взаимосвязи.
Продемонстрировано
умение
аргументировано
излагать
собственную точку зрения.
Изложение отчасти сопровождено адекватными примерами из
практики.
Ответ в достаточной степени структурирован и выстроен в заданной
логике без нарушений общего смысла.
Части ответа логически взаимосвязаны.
Отражена логическая структура вопроса: постановка проблемы –
аргументация – выводы.
Содержание ответа в целом соответствует теме задания. В ответе
отражено 60-70% материала, предусмотренного заданием.
Продемонстрировано удовлетворительное знание фактического
материала, есть фактические ошибки (25-30%).
Понимание
Продемонстрировано
достаточное
владение
понятийнотерминологическим аппаратом дисциплины, есть ошибки в
употреблении и трактовке терминов, расшифровке аббревиатур.
Ошибки в использовании категорий и терминов дисциплины в их
ассоциативной взаимосвязи.
Нет собственной точки зрения, либо она слабо аргументирована.
Примеры, приведенные в ответе в качестве практических
иллюстраций, в малой степени соответствуют изложенным
теоретическим аспектам.
Структура и Ответ плохо структурирован, нарушена заданная логика.
логика
Части ответа разорваны логически, нет связок между ними.
Ошибки в представлении логической структуры вопроса:
постановка проблемы – аргументация – выводы.
Содержание Содержание ответа не соответствует теме задания или
соответствует ему в очень малой степени.
В ответе отражено менее 50% материала, предусмотренного
заданием.
Продемонстрировано крайне низкое (отрывочное) знание
фактического материала, много фактических ошибок – практически
6
Государственный университет – Высшая школа экономики
Программа учебной дисциплины «Формальные языки и грамматики»
231000.62 – Программная инженерия подготовки бакалавра
все факты (данные) либо искажены, либо неверны.
Понимание Продемонстрировано крайне слабое владение понятийнотерминологическим
аппаратом
дисциплины
(неуместность
употребления, неверные аббревиатуры, искаженное толкование и
т.д.), присутствуют многочисленные ошибки в употреблении
терминов.
Показаны неверные ассоциативные взаимосвязи категорий и
терминов дисциплины.
Отсутствует аргументация изложенной точки зрения, нет
собственной позиции. Отсутствуют примеры из практики либо они
неадекватны.
Структура и Ответ представляет собой сплошной текст без структурирования,
логика
нарушена заданная логика.
Части ответа не взаимосвязаны логически.
Нарушена логическая структура вопроса: постановка проблемы –
аргументация – выводы.
Преподаватель оценивает работу студентов на практических занятиях: активность
студентов при ответах на вопросы преподавателя, правильность решение задач. Оценки за
работу на семинарских и практических занятиях преподаватель выставляет в рабочую
ведомость. Оценка по 10-ти балльной шкале за работу на семинарских и практических
занятиях определяется перед промежуточным или итоговым контролем и называется –
Оаудиторная.
Накопленная оценка за текущий контроль учитывает результаты студента по
текущему контролю следующим образом:
Онакопленная = 2/3* Отекущий + 1/3* Оаудиторная
где Отекущий рассчитывается как взвешенная сумма всех форм текущего контроля,
предусмотренных в РУП:
Отекущий = n1·Ок/р + n2·Одз + n3·Одз ,
при этом n1 = 0.25, n2 = 0.375, n3 = 0.375.
Способ округления накопленной оценки текущего контроля: арифметический.
Результирующая оценка за дисциплину рассчитывается следующим образом:
Орезультирующая = 0,6* Онакопленная + 0,4*·Озач
Способ округления накопленной оценки промежуточного (итогового) контроля в форме
зачета: арифметический.
На пересдаче студенту не предоставляется возможность получить дополнительный
балл для компенсации оценки за текущий контроль.
На зачете студент может получить дополнительный вопрос (дополнительную
практическую задачу, решить к пересдаче домашнее задание), ответ на который оценивается
в 1 балл.
7.
Содержание дисциплины
Раздел 1. Основные понятия теории формальных языков и грамматик (26 часов).
Понятие языка. Лексиса, синтаксис, семантика, прагматика. Понятие формальной
грамматики. Описание формального языка с помощью грамматики. Классификация
грамматик по Хомскому. Примеры. Метаязыки. Описание грамматик с помощью
металингвистических формул (БНФ) и диаграмм Вирта. Примеры.
7
Государственный университет – Высшая школа экономики
Программа учебной дисциплины «Формальные языки и грамматики»
231000.62 – Программная инженерия подготовки бакалавра
Лекции: 6 часов.
Практические занятия: 8 часов.
Самостоятельная работа: 10 часов.
На практических занятиях рассматриваются примеры описания синтаксиса языков
программирования с использованием диаграмм Вирта и БНФ, приводятся примеры
формальных грамматик и дается их классификация.
Отведенное на самостоятельную работу время используется для закрепления
лекционного и практического материала.
Литература по разделу:
1. Волкова И.А., Вылиток А.А., Руденко Т.В. Формальные грамматики и языки.
Элементы теории трансляции: уч. пособие для студентов II курса. – М.:
Издательский отдел факультета ВМиК МГУ, 2009. – 115 с.
2. Мартыненко Б.К. Языки и трансляция: учебное пособие. – СПб: Из-во С.Петербургского университета, 2004. – 236 с.
3. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и
вычислений: Пер. с англ. – М.: Издательский дом «Вильямс», 2008. – 528 с.
Раздел 2. Виды грамматик и языков (34 часа).
Регулярные языки и выражения. Алгебры регулярных выражений. Свойства
регулярных языков. Конечные автоматы для разбора регулярных языков. Теорема Клини о
регулярных языках.
Контекстно-свободные языки и грамматики. Свойства контекстно-свободных языков.
Автоматы с магазинной памятью. Теорема об эквивалентности автоматов с магазинной
памятью и контекстно-свободных грамматик.
Контекстно-зависимые грамматики. Грамматики без ограничений (класс 0).
Лекции: 10 часов.
Практические занятия: 8 часов.
Самостоятельная работа: 16 часов.
На практических занятиях студенты строят конечные автоматы, позволяющие
произвести разбор языка, определяют порождаемый автоматом язык.
Отведенное на самостоятельную работу время используется для закрепления
лекционного и практического материала.
Литература по разделу:
1. Волкова И.А., Вылиток А.А., Руденко Т.В. Формальные грамматики и языки.
Элементы теории трансляции: уч. пособие для студентов II курса. – М.:
Издательский отдел факультета ВМиК МГУ, 2009. – 115 с.
2. Мартыненко Б.К. Языки и трансляция: учебное пособие. – СПб: Из-во С.Петербургского университета, 2004. – 236 с.
3. Пентус А.Е., Пентус М.Р. Математическая теория формальных языков. – М:
Бином. Лаборатория знаний, 2006. – 248 с.
4. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и
вычислений: Пер. с англ. – М.: Издательский дом «Вильямс», 2008. – 528 с.
Раздел 3. Проблема разбора (28 часов).
Левосторонний и правосторонний разбор. Деревья разбора. Примеры построения
деревьев разбора. Атрибутные грамматики. Неоднозначные грамматики. LL(k) и LR(k)грамматики. Грамматики вида LL(1). Алгоритмы преобразования КС-грамматик к форме
LL(1). Нисходящий и восходящий разбор.
Лекции: 4 часа.
Практические занятия: 4 часа.
Самостоятельная работа: 18 часов.
8
Государственный университет – Высшая школа экономики
Программа учебной дисциплины «Формальные языки и грамматики»
231000.62 – Программная инженерия подготовки бакалавра
На практических занятиях студенты строят деревья разбора для различных видов
грамматик, проводят преобразования грамматик к форме LL(1).
Отведенное на самостоятельную работу время используется для закрепления
лекционного и практического материала, выполнения домашнего задания.
Литература по разделу:
1. Ахо А., Лам М., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и
инструментарий. – М.: Издательский дом «Вильямс», 2008. – 1185 с.
2. Волкова И.А., Вылиток А.А., Руденко Т.В. Формальные грамматики и языки.
Элементы теории трансляции: уч. пособие для студентов II курса. – М.:
Издательский отдел факультета ВМиК МГУ, 2009. – 115 с.
3. Мартыненко Б.К. Языки и трансляция: учебное пособие. – СПб: Из-во С.Петербургского университета, 2004. – 236 с.
Раздел 4. Нисходящий разбор (20 часов).
Метод рекурсивного спуска. Достаточное условие применимости метода рекурсивного
спуска. Таблично-управляемый и программно-управляемый разбор.
Лекции: 4 часа.
Практические занятия: 4 часа.
Самостоятельная работа: 12 часов.
На практических занятиях студенты знакомятся с методом рекурсивного спуска,
строят управляющие таблицы для LL(1)- разбора.
Отведенное на самостоятельную работу время используется для закрепления
лекционного и практического материала, выполнения домашнего задания.
Литература по разделу:
1. Ахо А., Лам М., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и
инструментарий. – М.: Издательский дом «Вильямс», 2008. – 1185 с.
2. Волкова И.А., Вылиток А.А., Руденко Т.В. Формальные грамматики и языки.
Элементы теории трансляции: уч. пособие для студентов II курса. – М.:
Издательский отдел факультета ВМиК МГУ, 2009. – 115 с.
3. Залогова Л.А. Разработка Паскаль-компилятора. – М: Бином. Лаборатория знаний,
2007. – 183 с.
Раздел 5. Восходящий разбор (38 часов).
Метод «перенос-свертка». Построение управляющей таблицы для LR(1)-разбора.
Конфликты «перенос-свертка». Разрешения конфликта «перенос-свертка».
Лекции: 6 часов.
Практические занятия: 6 часов.
Самостоятельная работа: 20 часов.
На практических занятиях студенты знакомятся с методом «перенос-свертка», строят
управляющие таблицы для LR(1)- разбора.
Отведенное на самостоятельную работу время используется для закрепления
лекционного и практического материала, выполнения домашнего задания.
Литература по разделу:
1. Ахо А., Лам М., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и
инструментарий. – М.: Издательский дом «Вильямс», 2008. – 1185 с.
2. Мартыненко Б.К. Языки и трансляция: учебное пособие. – СПб: Из-во С.Петербургского университета, 2004. – 236 с.
3. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и
вычислений: Пер. с англ. – М.: Издательский дом «Вильямс», 2008. – 528 с.
9
Государственный университет – Высшая школа экономики
Программа учебной дисциплины «Формальные языки и грамматики»
231000.62 – Программная инженерия подготовки бакалавра
Раздел 6. Инструментальные средства построения трансляторов (44 часа).
Система Lex. Структура Lex-программы. Способы записи регулярных выражений в
Lex-программе. Пример Lex-программы.
Генератор анализаторов YACC. Структура программы в YACC. Обработка ошибок в
YACC. Пример программы на YACC.
Лекции: 4 часа.
Практические занятия: 8 часов.
Самостоятельная работа: 32 часа.
На практических занятиях студенты знакомятся с инструментариями Lex и YACC,
выполняют построение анализаторов с использованием данных систем.
Отведенное на самостоятельную работу время используется для закрепления
лекционного и практического материала, выполнение домашнего задания.
Литература по разделу:
1. Ахо А., Лам М., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и
инструментарий. – М.: Издательский дом «Вильямс», 2008. – 1185 с.
2. Волкова И.А., Вылиток А.А., Руденко Т.В. Формальные грамматики и языки.
Элементы теории трансляции: уч. пособие для студентов II курса. – М.:
Издательский отдел факультета ВМиК МГУ, 2009. – 115 с.
8.
Образовательные технологии
Используется «проблемное» чтение лекций по дисциплине с использованием
компьютерного мультимедийного оборудования, предусматривающее разбор практических
задач теории формальных языков и грамматик.
На практике используются инструментальные средства, автоматизирующие разработку
трансляторов.
Методические рекомендации преподавателю
На лекциях используется «проблемный» подход к изложению материала: материал
каждой лекции иллюстрируется примерами, рассматриваются нестандартные ситуации,
требующие решения с использованием рассматриваемого материала. При этом студенты
должны активно участвовать в обсуждении вопросов, выработке решений, предлагаемые
студентами решения, обсуждаются, анализируются и оцениваются в ходе лекции.
Предлагается рассматривать не только «верные», оптимальные решения, но и решения,
приводящие к ошибкам. По каждому рассматриваемому на лекции вопросу следует
предложить задачи для самостоятельного решения и вопросы для самостоятельного
изучения.
На практических занятиях используются следующие методы обучения и контроля
усвоения материала:
1) выполнение практических работ по теме занятия сопровождается контрольным
опросом;
2) обсуждение различных вариантов решения, предложенных студентами, сравнение
решений, анализ возможных ситуаций.
Рекомендуется использовать «защиту» выполненных домашних заданий.
Методические указания студентам
Студенту рекомендуется следующая схема подготовки к практическому занятию:
2) проработать конспект лекций;
3) проанализировать основную и дополнительную литературу, рекомендованную
по изучаемому разделу;
4) при необходимости найти дополнительную информацию в сети Интернет, на
сайтах электронных библиотек;
10
Государственный университет – Высшая школа экономики
Программа учебной дисциплины «Формальные языки и грамматики»
231000.62 – Программная инженерия подготовки бакалавра
5) проанализировать варианты решений, предложенные преподавателем,
найденные в дополнительных источниках;
6) при затруднениях сформулировать вопросы к преподавателю.
Студенту рекомендуется следующая схема подготовки к лекции:
1) проработать конспект лекций;
2) изучить материал, предложенный для самостоятельного изучения;
3) выполнить предложенные преподавателем задания;
4) при затруднениях задать вопросы к преподавателю при проведении
индивидуальных консультаций.
Рекомендуется при выполнении домашних заданий рассмотреть возможность защиты
предложенных решений, подготовить документацию и «презентацию» работы.
Для самостоятельного изучения и подготовки к лекциям предлагается использовать
электронные ресурсы, размещаемые на сервере НИУ ВШЭ – Пермь.
9.
Оценочные средства для текущего контроля и аттестации студента
9.1. Тематика заданий текущего контроля
Примерные задания для контрольной работы:
1. Построить вывод заданной цепочки символов в грамматике.
2. Определить класс заданной грамматики.
3. Определить язык, порождаемый грамматикой.
4. Построить грамматику, порождающую заданный язык.
5. Построить конечный автомат по заданному языку.
6. Построить грамматику эквивалентную заданной.
7. Устранить неоднозначность грамматики.
Примерный перечень домашних заданий:
1. Построить восходящим и нисходящим методом дерево вывода для заданной
цепочки символов.
2. Построить нисходящий/восходящий анализатор по заданной грамматике.
3. Сгенерировать лексический анализатор с использованием системы Lex для
заданной грамматики.
4. С помощью системы YACC сгенерировать синтаксический анализатор для
заданной LL-грамматики.
5. С помощью системы YACC сгенерировать синтаксический анализатор для
заданной LR-грамматики.
9.2.Вопросы для оценки качества освоения дисциплины
Примерный перечень вопросов к зачету по всему курсу для самоконтроля студентов:
1. Понятие формального языка. Лексиса, синтаксис, семантика, прагматика языка.
2. Формальное определение грамматики. Описание формального языка с помощью
грамматики. Классификация грамматик по Хомскому. Примеры.
3. Метаязыки. Описание грамматик с помощью металингвистических формул (БНФ) и
диаграмм Вирта. Примеры.
4. Регулярные языки и выражения. Алгебры регулярных выражений. Свойства
регулярных языков.
5. Конечные автоматы для разбора регулярных языков. Теорема Клини о регулярных
языках.
6. Контекстно-свободные языки и грамматики. Свойства контекстно-свободных языков.
7. Автоматы с магазинной памятью. Теорема об эквивалентности автоматов с
магазинной памятью и контекстно-свободных грамматик.
11
Государственный университет – Высшая школа экономики
Программа учебной дисциплины «Формальные языки и грамматики»
231000.62 – Программная инженерия подготовки бакалавра
8. Контекстно-зависимые грамматики. Атрибутные грамматики. Грамматики без
ограничений (класс 0).
9. Левосторонний и правосторонний разбор. Деревья разбора. Примеры построения
деревьев разбора. Неоднозначные грамматики.
10. . LL(k) и LR(k)-грамматики. Грамматики вида LL(1). Алгоритмы преобразования КСграмматик к форме LL(1).
11. Нисходящий и восходящий разбор. Метод рекурсивного спуска. Достаточное условие
применимости метода рекурсивного спуска.
12. Метод рекурсивного спуска. Таблично-управляемый и программно-управляемый
разбор.
13. Нисходящий и восходящий разбор. Метод «перенос-свертка». Построение
управляющей таблицы для LR(1)-анализа. Конфликты «перенос-свертка». Разрешения
конфликта «перенос-свертка».
14. Система Lex. Структура Lex-программы. Способы записи регулярных выражений в
Lex-программе. Пример Lex-программы.
15. Генератор анализаторов YACC. Структура программы в YACC. Обработка ошибок в
YACC. Пример программы на YACC.
10. Учебно-методическое и информационное обеспечение дисциплины
11.1. Базовый учебник
1. Волкова И.А., Вылиток А.А., Руденко Т.В. Формальные грамматики и языки.
Элементы теории трансляции: уч. пособие для студентов II курса. – М.:
Издательский отдел факультета ВМиК МГУ, 2009. – 115 с.
11.2. Основная литература
2. Ахо А., Лам М., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и
инструментарий. – М.: Издательский дом «Вильямс», 2008. – 1185 с.
3. Пентус А.Е., Пентус М.Р. Математическая теория формальных языков. – М:
Бином. Лаборатория знаний, 2006. – 248 с.
4. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и
вычислений: Пер. с англ. – М.: Издательский дом «Вильямс», 2008. – 528 с.
11.3. Дополнительная литература
5. Залогова Л.А. Разработка Паскаль-компилятора. – М: Бином. Лаборатория знаний,
2007. – 183 с.
6. Мартыненко Б.К. Языки и трансляция: учебное пособие. – СПб: Из-во С.Петербургского университета, 2004. – 236 с.
11.4. Справочники, словари, энциклопедии
Не предусмотрены.
11.5. Программные средства
Для успешного освоения дисциплины, студент использует следующие программные
средства:
1) Программа генерации лексических анализаторов Lex.
2) Программа генерации синтаксических анализаторов YACC.
3) Средства, обеспечивающие возможность доступа к материалам для подготовки к
занятиям в различных форматах (документы MS Word, документы в формате
HTML, презентации MS Power Point), размещенные на сервере, доступные в сети
Интернет.
12
Государственный университет – Высшая школа экономики
Программа учебной дисциплины «Формальные языки и грамматики»
231000.62 – Программная инженерия подготовки бакалавра
11.6. Дистанционная поддержка дисциплины
Дистанционная поддержка курса предусмотрена
образовательной среды LMS.
в
рамках
информационной
11. Материально-техническое обеспечение дисциплины
Для проведения лекционных занятий используется компьютер с установленным
программным обеспечением для демонстрации презентаций и проектор.
Практические занятия проводятся в компьютерных классах с установленным
программным обеспечением, перечисленным выше.
13
