В.С. Фомичев

1. Формальные языки и грамматики.
2. Контекстно-свободные грамматики и магазинные автоматы.
3. Нисходящие  и восходящие распознаватели.
4. Способы описания перевода и преобразователи.
5. Атрибутные грамматики и преобразователи.
6. Автоматные грамматики и конечные автоматы.(в работе)
7. Абстрактный синтез автоматов.(в работе)
8. Переключательные функции и синтез комбинационных схем.(в работе)
9. Структурный синтез автоматов.

1. Формальные языки и грамматики

• 1.1. Введение
• 1.1.1. Трансляторы , интерпретаторы и компиляторы
• 1.1.2. Стадии работы компилятора
• 1.1.3. Построение компилятора
• 1.1.4. Термины
• 1.2. Определение формальной грамматики и языка
• 1.2.1. Первичные понятия
• 1.2.2. Примеры, иллюстрирующие первичные понятия
• 1.2.3. Пустой язык
• 1.2.4. Резюме
• 1.2.5. Термины
• 1.3. Типы формальных языков и грамматик
• 1.3.1. Грамматики типа 0
• 1.3.2. Грамматики типа 1
• 1.3.3. Грамматики типа 2
• 1.3.4. Грамматики типа 3
• 1.3.5. Вывод в КС-грамматиках и правила построения дерева вывода
• 1.3.6. Синтаксический разбор
• 1.3.7. Левый и правый выводы
• 1.3.8. Неоднозначные и эквивалентные грамматики
• 1.3.9. Резюме
• 1.3.10. Упражнения
• 1.3.11. Термины
• 1.4. Способы задания схем грамматик
• 1.4.1. Форма Наура-Бэкуса
• 1.4.2. Итерационная форма
• 1.4.3. Синтаксическая диаграмма
• 1.4.4. Резюме
• 1.4.5. Упражнение
• 1.4.6. Термины
• 1.5. Построение грамматик и грамматики, описывающие основные конструкции языков программирования
• 1.5.1. Рекомендации по построению грамматик
• 1.5.2. Описание списков
• 1.5.3. Пример построения грамматик
• 1.5.4. Грамматики, описывающие целые числа без знака и идентификаторы
• 1.5.5. Грамматики для арифметических выражений
• 1.5.6. Грамматика для описаний
• 1.5.7. Грамматика, задающая последовательность операторов присваивания
• 1.5.8. Грамматики, описывающие условные операторы и операторы цикла
• 1.5.9. Резюме
• 1.5.10. Упражнения
2. Контекстно-свободные грамматики и магазинные  автоматы.
• 2.1 Приведенные грамматики.
• 2.2  Определение непроизводящих символов.
• 2.3 Определения недостижимых символов.
• 2.4  Определения бесполезных символов.
• 2.5 Исключение леворекурсивных правил.
• 2.6 Исключение цепных правил.
• 2.7 Преобразование неукорачивающих грамматик.
• 2.8  Магазинные автоматы.
• 2.9 Работа магазинного автомата.
• 2.10.Язык, допускаемый магазинным автоматом.
• 2.11 Построение магазинного автомата.
• 2.12 Пример построения автомата.
•  2.13 Резюме.
•  2.14 Упражнения.
• 2.15 Термины.

3. Нисходящие и вщсходящие распознаватели.
• 3.1 Нисходящие распознаватели и LL(K) - грамматики
• 3.2 Разделенные грамматики
• 3.3 Построение детерминированного нисходящего распознавателя.
• 3.4  Множества выбора.
• 3.4.1 Функции  ПЕРВ, СЛЕД  и  ВЫБОР.
• 3.4.2 Построение функции ПЕРВ(µ) .
• 3.4.3 Построение функции СЛЕД(<B>).
• 3.4.4 Построение функции ВЫБОР.
• 3.5. Слаборазделенные грамматики
• 3.6. LL(1) - грамматики.
• 3.7. Построение магазинного автомата.
• 3.8.  Преобразование грамматик к виду LL(1).
• 3.8.1.  Исключение леворекурсивных правил.
• 3.8.2.  Выделение общих частей.
• 3.9. Резюме.
• 3.10.Упражнения.
• 3.11.Восходящие распознаватели.
• 3.11.1. Расширенный магазинный автомат.
• 3.11.2. Пример работы расширенного автомата.
• 3.12. LR(k)-грамматики .
• 3.12.1. Построение и работа распознавателя.
• 3.12.2. Пример построения LR(0)-распознавателя .
• 3.13. SLR(1)-распознаватели и их построение .
• 3.14. Восходящие распознаватели для грамматик с аннулирующими правилами.
• 3.15. Резюме.
• 3.16. Упражнения.
• 3.17. Термины .

4. Способы  описания  перевода.  Бесскобочные  выражения. Преобразователи.
• 4.1. Описание перевода или трансляции .
• 4.1.1.  Синтаксически - управляемые  схемы
• 4.1.2. Перевод, определяемый СУ-схемой.
• 4.1.3.  Простая СУ - схема.
• 4.1.4.  Построение  простой СУ - схемы.
• 4.1.5.  Транслирующие грамматики
• 4.1.6.  Входная  и  выходная  грамматики  заданной  транслирующей грамматики.
• 4.1.7.  Построение   транслирующей  грамматики по  СУ - схеме
• 4.2. Бесскобочные выражения
• 4.2.1. Префиксная  польская  запись.
• 4.2.2.  Вычисление  префиксных  польских  записей.
• 4.2.3.  Постфиксная  польская  запись.
• 4.2.4.   Вычисление постфиксных польских записей.
• 4.2.5.  Примеры  постфиксных польских записей.
• 4.2.6.  Примеры  СУ - схем.
• 4.3. Магазинные Преобразователи.
• 4.3.1. Определение магазинного преобразователя.
• 4.3.2. Описание работы магазинного преобразователя.
• 4.3.3. Перевод, определяемый преобразователем.
• 4.3.4. Построение преобразователя.
• 4.3.5. Пример построения детерминированного преобразователя.
• 4.3.6. Порядок построения детерминированного магазинного преобразователя.
• 4.4. Резюме.
• 4.5. Упражнения.
• 4.6. Термины.

•   5.1. Атрибутные транслирующие грамматики.
•   5.1.1. Атрибутные транслирующие грамматики.
•   5.1.2. Определение АТ-грамматик
•   5.1.3. Пример АТ-грамматики
•   5.1.4. Демонстрация вычисления значений атрибутов с левым выводом
•   5.1.5. Пример использования АТ-грамматики
•    5.2. Cинтаксический анализ, с использованием АТ-грамматики
•   5.2.1. Процесс синтаксического анализа
•   5.2.2. Пример использования АТ-грамматики.
•     5.3. L - атрибутные транслирующие грамматики
•   5.3.1. L - атрибутные транслирующие грамматики
•   5.3.2. Форма простого присваивания АТ-грамматик
•   5.3.3. Преобразование LАТ-грамматики в LАТ-грамматику в форме простого присваивания.
•   5.3.4. Расширенный вывод для АТ-грамматики
• 5.4. Атрибутные преобразователи ( АП )
• 5.4.1. Представление правил LAT-грамматики в магазине
• 5.4.2. Построение инструкций АП
• 5.4.3. Описание работы АП
• 5.4.4. Порядок построения АП
• 5.4.5. Пример построения АП
• 5.4.6 Демонстрация работы АП
• 5.4.7. Построение восходящих атрибутных преобразователей
• 5.5. Резюме.
• 5.6. Упражнения.

5.7.Термины.
6. Автоматные грамматики и конечные автоматы.
                                                    ( в работе )

• 6.2. Ндетерминированные конечные автоматы.
• 6.3. Конечные преобразователи и переводы.
•  6.4.Преобразование некоторвх типов языков и грамматик к автоматному виду.
• 6.5. Построение лексического анализатора.
• 6.6. Резюме.
• 6.7. Упражнения.
• 6.8. Термины

 
7. Абстрактный синтез автоматов.
                     ( в работе )
• 7.1. Преобразование входов.
• 7.2. Построение распознавателя для заданного конечног языка.
• 7.3. Построение конечных преобразователей.
• 7.4. Эквивалентные автоматы и состояния.
• 7.5. Частичные автоматы и совместимые состояния.
• 7.6. Построение управляющих автоматов.
• 7.7. Резюме.
• 7.8. Упражнения.
• 7.9. Термины.

 

 
 




8. Переключательные функции и синтез комбинационных схем.
( в работе )

• 8.1. Переключательные функции и их свойства
• 8.1.1. Алгебра   переключательных функций
• 8.1.2. Аналитическая запись переключательных функций
• 8.1.3. Совершенные дизъюнктивные и конъюктивные нормальные формы
• 8.1.4. Графическое и геометрическое представление переключательных функций
• 8.2. Минимальные формы переключательных функций
• 8.2.1.Геометрическое представление конъюнкций
• 8.2.2. Различные  дизъюнктивные формы переключательных функций
• 8.2.3. Табличный метод построения множества минималей Квайна - Мак-Класки
• 8.2.4. Неизбыточные покрытия и экстремали
• 8.2.5. Построение минимальных покрытий для функций, без экстремалей
• 8.2.6. Визуальные методы минимизации переключательных функций
• 8.3. Функциональная полнота систем переключательных функций
• 8.3.1. Теорема о функциональной полноте
• 8.3.2. Реализация функций в различных базисах
• 8.4. Резюме
• 8.5. Упражнения
• 8.6. Термины

 

 
 
 
 
 

9. Структурный синтез автоматов

•  9.1. Синхронные автоматы
• 9.1.1 Задача структурного синтеза.
•   9.1.1.1 Обобщенная структурная схема автомата. .
•   9.1.1.2 Структурная схема с преобразователями входных и выходных сигналов.
•   9.1.1.3 Структурная схема на элементах импульсного типа.
•  9.1.2 Основные этапы структурного синтеза.
•  9.1.3 Типы элементов памяти.
•  9.1.4 Построение функций возбуждения.
•  9.1.5 Примеры структурного синтеза.
•   9.1.5.1 Пример 1.
•   9.1.5.2 Пример 2.
• 9.1.6 Кодрование состояний с использованием соседей первого и второго рода.
• 9.1.7 Кодирование с числом элементов памяти, равным числу состояний .
• 9.1.8 Структурные схемы с дешифратором.
• 9.1.9 Структурная схема с удвоенным числом элементов памяти.
• 9.1.10 Структурные схемы, использующие типовые блоки цифровых устройств.
•   9.1.10.1 Структурная схема с запоминанием входного слова.
•   9.1.10.2 Структурная схема на основе счетчика.
•   9.1.10.3 Структурная схема на основе регистра со сдвигом.
• 9.1.11 Термины.
• 9.2. Асинхронные автоматы
• 9.2.1. Описание работы асинхронного автомата
• 9.2.2. Состязание элементов памяти
• 9.2.3. Кодирование состояний
• 9.2.3.1 Универсальный способ кодирования
• 9.2.3.2 Эвристический способ кодирования
• 9.2.4. Связь асинхронного автомата с внешней средой
• 9.2.5. Построение элементов памяти
• 9.2.5.1. Асинхронный триггер
• 9.2.5.2. Асинхронный S-триггер
• 9.2.5.3. Триггеры с синхронизацией
• 9.2.6. Триггеры с задержкой
• 9.2.6.1.T-триггер с задержкой
• 9.2.6.2. Асинхронный триггер J-K с задержкой
• 9.2.6.3. Триггер J-K с задержкой и синхронизацией
• 9.2.6.4. Триггер D-V с задержкой и синхронизацией
• 9.2.7. Термины