Е.В.Мясников
ОСНОВЫ ТРАНСЛЯЦИИ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ
Сборник задач для практических занятий
Электронное учебное пособие
Самара
2011
Автор: МЯСНИКОВ Евгений Валерьевич
Пособие представляет собой сборник задач для практических занятий. <...> Алфавит, цепочка, язык
1.1 Краткие теоретические сведения
Алфавит – конечное непустое множество символов, используемых в языке. <...> Цепочка – любая конечная последовательность, составленная из символов некоторого
множества. <...> Так, 45098, 34.676, abc][#$99 –примеры цепочек, составленных из символов
приведенных выше алфавитов. <...> Конкатенацией цепочек α и β называется цепочка αβ,
получаемая путем дописывания символов цепочки β вслед за символами цепочки α. <...> Обращением цепочки α называется цепочка αR, полученная
путем записи символов цепочки α в обратном порядке. <...> Для нее справедливо: |ε|=0, αε=εα=ε, εi=ε, α0=ε, εR=ε
В том случае, если U – некоторое множество символов, мы будем обозначать через U+
множество всех возможных цепочек, составленных из символов множества U, за
исключением пустой цепочки, а через U* - множество всех возможных цепочек,
составленных из символов множества U, включая пустую цепочку: U*= U+∪{ε}. <...> В том случае, если некоторая непустая цепочка γ составлена из символов множеств U
и V, то γ∈(U∪V)+. <...> Языком в алфавите A называют некоторое множество цепочек, составленных из
символов алфавита A. <...> D) Язык, составленный из цепочек α,β,γ, всех возможных конкатенаций этих
цепочек и пустой цепочки. <...> A) Множество всех непустых цепочек в алфавите {a,b} <...> B) Множество всех цепочек, составленных из символов множеств U,V,W,
включая пустую цепочку <...> Грамматики
2.1 Краткие теоретические сведения
Грамматикой называется четверка
G=(S,VN,VT,R)
где S – начальный символ грамматики,
VN - множество нетерминальных символов грамматики,
VT – множество терминальных символов грамматики, определяемое алфавитом языка,
R – непустое множество правил грамматики. <...> Каждое правило грамматики в общем случае записывается в виде α→β, где <...>
Основы_трансляции_языков_программирования._Сборник_задач_для_практических_занятий_[Электронный_ресурс]_.pdf
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ
УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ
УНИВЕРСИТЕТ имени академика С.П.КОРОЛЕВА
(НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)»
Е.В.Мясников
ОСНОВЫ ТРАНСЛЯЦИИ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ
Сборник задач для практических занятий
Электронное учебное пособие
Самара
2011
Стр.1
Автор: МЯСНИКОВ Евгений Валерьевич
Пособие представляет собой сборник задач для практических занятий. В сборник
включены краткие теоретические сведения, необходимые для решения задач, задания для
практических и самостоятельных занятий, подробно разобраны примеры решения типовых
задач. Задачи способствуют закреплению теоретического материала и выработке
практических навыков по дисциплине. В сборнике представлены задачи по всем темам
курса, освещаемым на практических занятиях по дисциплине.
Пособие предназначено для студентов факультета информатики, направление 010400
– Прикладная математика и информатика, бакалавриат (010400.62)/магистратура (010400.68,
магистерская программа – Технологии параллельного программирования и
суперкомпьютинг).
Стр.2
Оглавление
ОГЛАВЛЕНИЕ ................................................................................................................................................ 3
1. АЛФАВИТ, ЦЕПОЧКА, ЯЗЫК ...................................................................................................................... 4
1.1 КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ ................................................................................................................. 4
1.2 ЗАДАНИЯ ...................................................................................................................................................... 5
2. ГРАММАТИКИ ........................................................................................................................................... 7
2.1 КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ ................................................................................................................. 7
2.2 ПРИМЕРЫ ................................................................................................................................................... 12
2.3 ЗАДАНИЯ .................................................................................................................................................... 15
3. СИНТАКСИЧЕСКИЙ АНАЛИЗ АВТОМАТНЫХ ЯЗЫКОВ ............................................................................ 18
3.1 КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ ............................................................................................................... 18
3.2 ПРИМЕР ...................................................................................................................................................... 20
3.3 ЗАДАНИЯ .................................................................................................................................................... 22
4. СИНТАКСИЧЕСКИЙ АНАЛИЗ КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ ....................................................... 25
4.1 КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ ............................................................................................................... 25
4.2 ЗАДАНИЯ .................................................................................................................................................... 30
5. НИСХОДЯЩИЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ КС-ЯЗЫКОВ. LL(1) ГРАММАТИКИ .................................... 31
5.1 КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ ............................................................................................................... 31
5.2 ПРИМЕР ...................................................................................................................................................... 34
5.3 ЗАДАНИЯ .................................................................................................................................................... 38
6. ВОСХОДЯЩИЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ КС-ЯЗЫКОВ. ГРАММАТИКИ ПРЕДШЕСТВОВАНИЯ ......... 41
6.1 КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ ............................................................................................................... 41
6.2 ПРИМЕР ...................................................................................................................................................... 44
6.3 ЗАДАЧИ ...................................................................................................................................................... 49
7. ВОСХОДЯЩИЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ КС-ЯЗЫКОВ. LR(K) ГРАММАТИКИ .................................. 51
7.1 КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ ............................................................................................................... 51
7.2 ПРИМЕР ...................................................................................................................................................... 53
7.3 ЗАДАЧИ ...................................................................................................................................................... 56
8. ПОЛЬСКАЯ ИНВЕРСНАЯ ЗАПИСЬ ............................................................................................................ 58
8.1 КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ ............................................................................................................... 58
8.3 ЗАДАНИЯ .................................................................................................................................................... 61
9. ТРЕХАДРЕСНЫЙ КОД. ТЕТРАДЫ И ТРИАДЫ. ......................................................................................... 62
9.1 ЗАДАНИЯ .................................................................................................................................................... 63
ЛИТЕРАТУРА ............................................................................................................................................... 64
Стр.3