Теория формальных языков и компиляторов (для студентов дневного отделения) — Контрольно-измерительные материалы

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

 Отношения между символами. Понятие символа-предшественника. Алгоритм определения множества предшественников символа и цепочки символов

29

 Понятие символа-последователя. Алгоритм определения множества непосредственных последователей для символов грамматики

30

 Алгоритм определения множеств символов, которые могут быть последними в цепочках, выводимых из нетерминалов. Вычисление множеств последователей

31

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

32

 Понятие множеств выбора правил грамматики с одним нетерминалом в правой части. Определение LL(1)-грамматик

33

 Процедурная реализация рекурсивного спуска для LL(1)-грамматик

34

 Автоматная реализация рекурсивного спуска. Состав клетки управляющей таблицы автомата с несколькими состояниями

35

 Преобразование LL(1)-грамматики в управляющую таблицу автомата с несколькими состояниями

36

 Преобразование LL(1)-грамматики в автомат с одним состоянием, управляемый входным символом и содержимым стека

37

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

38

 Конфликты свертка/свертка и перенос/свертка. Развитие основной идеи восходящего анализа, восходящий автомат с несколькими состояниями

39

 Операции сдвига и свертки восходящего синтаксического автомата с несколькими состояниями

40

 Понятие конфигурации и его связь с понятием состояния восходящего акцептора и его операциями

41

 Построение таблицы конфигураций по грамматике

42

 Преобразование таблицы конфигураций в управляющую таблицу восходящего акцептора. Выявление конфликтов. Понятие LR(0)-грамматик

43

 Разрешение конфликтов методом использования полных множеств последователей. Понятие SLR(1)-грамматик

44

 Понятие ожидаемого правого контекста и расширенной конфигурации. Правила определения правого контекста для расширенных конфигураций

45

 Метод использования правого контекста для предотвращения конфликтов при построении управляющей таблицы. LR(1)-грамматики и автоматы

46

 LALR(1)-грамматики и автоматы

47

 Эквивалентные преобразования грамматик

48

 Нейтрализация ошибок при синтаксическом анализе.

49

 Понятие постфиксной записи, преобразование выражений в ПФЗ.

50

 Преобразование управляющих операторов в постфиксную запись.

51

Семантический анализ, основные задачи и понятия. Операции и данные, адреса и значения, l-value и r-value

52

Тетрады и триады, алгоритм преобразования ПФЗ в последовательность тетрад

53

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

54

Оптимизация псевдокода. Методы глубокой оптимизации

55

Генерация кода, основные понятия

56

Генерация кода. Распределение памяти

57

Генерация кода. Формирование исполнительных адресов

58

Интерпретация псевдокода

59

Зависимость времени работы программы от метода ее трансляции (генерация кода или интерпретация)

60

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

1

Что такое транслятор?

2

Какова типичная последовательность этапов трансляции?

3

Компилятор отличается от интерпретатора тем, что

4

Расположите в порядке вложенности конструкции формального языка (наиболее общая вверху):

5

Формальный язык - это

6

Какие данные обрабатываются компонентами компилятора?

7

Что такое токен в лексическом анализе?

8

Могут ли в системе лексических правил присутствовать разные регулярные выражения с одним и тем же именем группы слов?]

9

Какие знаки операций можно использовать в регулярных выражениях пакета Вебтранслаб для определения цепочек символов длины, большей 1?

10

Какие два конечных автомата без памяти являются эквивалентными?

11

Какие состояния конечного автомата должны быть удалены из него?

12

Какие регулярные выражения действительно определяют знак операции "присваивание со сложением" в языке Си?

13

В каком случае конечный автомат без памяти является недетерминированным?

14

Что такое конечный автомат без памяти, применяемый в лексическом анализе?

15

Что такое первичное регулярное выражение?

16

Перечислите постфиксные знаки операций, которые могут быть использованы в регулярных выражениях.

17

Дано регулярное выражение [01][10]. Сколько разных цепочек символов оно порождает?

18

Что такое история работы конечного автомата без памяти?

19

Что такое полностью определенный конечный автомат?

20

Какие существуют способы задания (определения) конечных автоматов без памяти?

21

Выберите правильные регулярные выражения

22

Что такое эпсилон-замыкание подмножества вершин графа состояний и переходов недетерминированого конечного автомата без памяти?

23

Что такое предопределенная группа слов языка программирования?

24

Что такое определяемые слова языка программирования?

25

Что входит в функции лексического анализатора транслятора?

26

Какие существуют модели лексических анализаторов?

27

В какой последовательности выполняется преобразование системы регулярных выражений в автоматный лексический акцептор/анализатор?

28

Отметьте действия, которые выполняются на самом первом этапе преобразования системы именованных регулярных выражений в конечный автомат.

29

Установите соответствие между видом регулярного выражения и фрагментом графа состояний и переходов конечного автомата.

30

Отметьте критерии, которым должен удовлетворять оптимальный детерминированный конечный автомат без памяти.

31

Расположите в правильной последовательности шаги алгоритма устранения недетерминированностей конечного автомата без памяти.

32

Тупиковое состояние конечного автомата без памяти, это такое состояние

33

Недостижимое - это такое состояние конечного автомата без памяти,

34

Эквивалентные - это такие два состояния конечного автомата без памяти,

35

Каков фактический смысл понятия пустой цепочки символов в лексическом анализе?

36

Как не полностью определенный конечный автомат без памяти преобразуется в полностью определенный?

37

Для чего в регулярные выражения системы лексических правил может быть включено действие (фрагмент программы)?

38

Лексика формального языка - это:

39

Что такое формальная грамматика?

40

Что входит в функции синтаксического анализатора?

41

Чем нетерминальный символ грамматики отличается от терминального?

42

Что такое терминальный символ грамматики?

43

Что такое аннулируемый нетерминал грамматики?

44

Что такое рекурсивный нетерминал грамматики?

45

Отметьте все возможные виды рекурсии в формальных грамматиках.

46

Что такое контекстно-свободная грамматика?

47

Непосредственным выводом называется

48

Что называется деревом грамматического разбора?

49

Символ Y называется предшественником символа X, если

50

Для вычисления матрицы отношения предшествования нужно:

51

Множество предшественников цепочки символов вычисляется так:

52

Символ Y называется последователем символа X, если

53

Для вычисления множеств последователей нетерминалов грамматики необходимо

54

Для вычисления матрицы отношения «Y есть непосредственный последователь X» нужно:

55

Для вычисления матрицы отношения «X есть последний (замыкающий) символ в цепочке, выводимой из Z» нужно:

56

В чем состоит основная задача синтаксического анализа?

57

Как формулируется основная идея нисходящего детерминированного (безоткатного) синтаксического анализа?

58

Как вычисляется множество выбора правила грамматики?

59

Как соотносятся между собой языки и грамматики?

60

В каком случае грамматика относится к классу LL(1)?

61

Как рекурсивность символов грамматики влияет на возможность преобразования ее в нисходящий синтаксический анализатор?

62

Что такое процедурная реализация рекурсивного спуска?

63

Пусть в LL(1)-грамматике есть два правила для нетерминала N: N : t M N : и множество последователей нетерминала N включает в себя символы {q, w}. Выберите правильный вариант реализации функции, поставленной в соответствие нетерминалу N при преобразовании грамматики в процедурную реализацию рекурсивного спуска.

64

Процесс проверки правильности входной цепочки терминалов нисходящим синтаксическим анализатором можно интерпретировать как:

65

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

66

Преобразование LL(1)-грамматики в нисходящий стековый автомат с несколькими состояниями выполняется путем такой последовательности действий:

67

Какие операции могут находиться в клетках нисходящего стекового автомата с одним состоянием?

68

Как грамматика преобразуется в управляющую таблицу нисходящего стекового автомата с одним состоянием?

69

Что такое конфигурация?

70

Какие операции выполняет восходящий синтаксический анализатор?

71

В какое время обнаруживаются и разрешаются конфликты типа "сдвиг/свертка" и "свертка/свертка" при восходящем синтаксическом анализе по LR(0)-грамматике?

72

В какое время обнаруживаются и разрешаются конфликты типа "сдвиг/свертка" и "свертка/свертка" при восходящем синтаксическом анализе по SLR(1)-грамматике?

73

В какое время обнаруживаются и каким способом предупреждаются конфликты типа "сдвиг/свертка" и "свертка/свертка" при восходящем синтаксическом анализе по LALR(1)-грамматике?

74

В какой последовательности выполняется формирование таблицы простых конфигураций?

75

В какой последовательности выполняется преобразование таблицы простых конфигураций в управляющую таблицу восходящего синтаксического анализатора?

76

Для чего используется ожидаемый правый контекст?

77

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

78

Чем просто расширенная конфигурация отличается от канонической расширенной?

79

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

80

Какие отличия постфиксной формы записи определяют возможность и целесообразность ее использования в качестве промежуточной формы представления программ между синтаксическим и семантическим анализом?

81

Что относится к функциям семантического анализа?

82

Что такое виртуальная машина в семантическом анализе?

83

Перечислите типы виртуальных машин, модели которых могут применяться в семантическом анализе.

84

Какова максимальная арность операций постфиксной записи, которую можно реализовать средствами псевдокода?

85

Какие характеристики/атрибуты связаны с понятием типа данных при семантическом анализе?

86

Какие дополнительные по отношению к постфиксной форме записи слова могут появиться в псевдокоде в процессе семантического анализа?

87

Чем производные типы данных отличаются от базовых?

88

Расположите шаги алгоритма преобразования ПФЗ в псевдокод в правильной последовательности.