Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Теория языков программирования и методы трансляции
###THEMES###
Формальные языки и грамматики
1 В классификации грамматик по Хомскому выделяется … типа (ов) грамматик
2 Продолжить определение. Теория формальных языков - это раздел математической лингвистики, изучающий
3 Выбрать правильное определение формальной грамматики.
A формальная грамматика - это математическая система, определяющая язык посредством порождающих правил.
B формальная грамматика – это система правил, определяющих принадлежность фраз языку.
C формальная грамматика – это система правил, определяющих правильность расстановки знаков препинания в фразах языка.
D формальная грамматика – это математическая система, позволяющая определить правильность построения фраз языка.
4 Выбрать правильное определение семантики языка.
-семантика языка определяет смысл фраз.
-семантика языка определяет принадлежность фраз языку.
- семантика языка это правила, определяющие множество текстов.
- семантика языка это наука о естественных языках и их классификации.
5 Выбрать правильное определение синтаксиса языка.
-Синтаксис языка определяет принадлежность фраз языку
-Синтаксис языка определяет правила, которые определяют предложения языка.
-Синтаксис языка определяет смысл фраз языка.
-Синтаксис языка это система правил, определяющих правильность расстановки знаков препинания в фразах языка.
6 Какое понятие является более общим?
-Сентенциальная форма.
-Строка языка
-Терминальная сентенциальная форма
-Предложение языка.
7 Какую роль в грамматике играет аксиома ?
-Начальный символ грамматики, с которого начинается вывод, генерирующий любую строку языка.
-Аксиома- это префикс строки.
-Аксиома - это правило грамматики.
-Аксиома- это пустая цепочка.
8 Какую задачу решает распознаватель?
-Задачу проверки правильности имеющихся строк
-Задачу генерации правильных строк языка.
-Задачу порождения лексических единиц.
- Задачу построения графа распознавателя.
9 Какой тип грамматики из классификации Хомского является наиболее общим?
+Тип 0.
-Тип 3
-Тип 1
-Тип 2
10 Распознаватель допускает (принимает) входную цепочку ,если
-от начальной конфигурации, в которой цепочка записана на входной ленте, он может проделать последовательность шагов, заканчивающуюся заключительной конфигурацией.
-он может переместить считывающую головку на шаг влево.
-он обрабатывает последовательность входных символов, принадлежащих некоторому конечному множеству
-он может переместить считывающую головку на шаг вправо.
11 Укажите правильный вариант соответствия классов формальных грамматик и распознавателей.
-Кл.0- машины Тьюринга, кл.1- линейные ограниченные автоматы, кл. 2- автоматы с магазинной памятью, кл.3- конечные автоматы.
-Кл.0- машины Тьюринга, кл.1- линейные ограниченные автоматы, кл. 2-конечные автоматы, кл.3- конечные автоматы с магазинной памятью.
- Кл.0- линейные ограниченные автоматы, кл.1- машины Тьюринга, кл. 2-конечные автоматы, кл.3- конечные автоматы с магазинной памятью.
- Кл.0- линейные ограниченные автоматы, кл.1- машины Тьюринга, кл. 2-конечные автоматы, кл.3- конечные автоматы с магазинной памятью.
12 Каким методом описания синтаксиса языков программирования дано определение понятия «идентификатор» ?
<идентификатор> ::= <буква> | <идентификатор> <буква>
| <идентификатор> <цифра>
<буква> :: = a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z
<цифра> :: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
-С использованием формы Бэкуса-Наура
- С использованием диаграмм Вирта.
- С использованием грамматики
- С использованием диаграммы переходов.
13 Практического применения не имеют грамматики, относящиеся только к типу
-с фразовой структурой
- контекстно- зависимых
- контекстно-свободных
- регулярных
14 К какому типу по классификации Хомского относится грамматика , если на ее правила вывода не наложено никаких ограничений, кроме тех, которые указаны в определении формальной грамматики.
-типа 0
-типа 3
-типа 1
-типа 2
15 Грамматика называется … грамматикой, если на ее правила вывода не наложено никаких ограничений, кроме тех, которые указаны в определении грамматики.
-С фразовой структурой
-Контекстно-зависимой
-Контекстно-свободной
-Регулярной
16. При построении дерева вывода сверху вниз в корень дерева помещается
-аксиома грамматики
-терминальный символ
-нетерминальный символ
-знак операции
17 Грамматика называется … грамматикой, если каждое правило вывода из множества Р имеет вид A , где A VN , , (VT VN)* и (VT VN)+.
-Контекстно-зависимой
-Тип 0
-Контекстно-свободной
-Регулярной
18 Грамматика называется … , если ее правила вывода имеют вид , где , или , где .
-Тип 0
-Регулярной
-Контекстно-зависимой
-Контекстно-свободной
19 Грамматика называется … грамматикой, если ее правила вывода имеют вид: , где и
-Тип 0
-Контекстно-свободной
-Контекстно-зависимой
-Регулярной
20 Алфавитом V называется …
-конечное множество символов
-любая конечная последовательность символов
-упорядоченное множество символов
-количество нетерминальных символов
21 Цепочкой в алфавите V называется …
-любая конечная последовательность символов этого алфавита
-упорядоченное множество символов этого алфавита
-конечное множество символов
-нет правильного ответа
22 Задать язык L в алфавите V можно … способами
-3
-2
-4
-5
23 Формальным языком L в алфавите V называют …
- -множество, содержащее все цепочки в алфавите V, исключая пустую цепочку .
-произвольное подмножество множества V*
-множество, содержащее все цепочки в алфавите V, включая пустую цепочку
-произвольное подмножество множества V+
24 Язык L(G)={(ac)n(cb)n | n>0 }, определяемый грамматикой с правилами вывода: 1) S aQb | accb; 2) Q cSc, является …
-Контекстно-свободным
-Тип 0
-Контекстно-зависимым
-Регулярным
25 Язык L(G)={anbncn | n1}, определяемый грамматикой с правилами вывода: 1) S aSBC | abc; 2) bC bc; 3) CB BC; 4) cC cc; 5) BB bb, является …
-Тип 0
-Контекстно-зависимым
-Контекстно-свободным
-Регулярным
26 Язык L(G)={ | {a, b}+, где нет двух рядом стоящих а, определяемый грамматикой с правилами вывода: 1) S A | B; 2) A a | Ba; 3) B b | Bb | Ab, является …
-Контекстно-зависимым
-Тип 0
-Регулярным
-Контекстно-свободным
27 В классификации распознавателей выделяется … типа (ов) распознавателей
-3
-4
-5
-2
28 Регулярные грамматики делятся на … типа (ов)
-3
-4
-2
-5
29 Грамматика G, определяемая правилами: SAB; ABCBb; CBABB; Aa; aBa, является…
-Контекстно-зависимой
-Тип 0
-Контекстно-свободной
-Регулярной
30 Грамматика G, определяемая правилами: SaAbB; AbBaAbB; bBbbb; Aе, является…
-Контекстно-зависимой
-Тип 0
-Контекстно-свободной
-Регулярной
31 Грамматика G, определяемая правилами: SAaB; AaBaAaBb; aBbabb; Aе, является…
-Контекстно-зависимой
-Контекстно-свободной
-Тип 0
-Регулярной
32 Грамматика G, определяемая правилами: SAB; ABaDB; DBABB; Bb; Abb, является…
-Контекстно-зависимой
-Тип 0
-Контекстно-свободной
-Регулярной
33 Грамматика G, определяемая правилами: SAS|е; Aa|b, является…
-Тип 0
-Контекстно-свободной
-Контекстно-зависимой
-Регулярной
34 Грамматика G, определяемая правилами: SAB; ABaABB; Bb; Aa, является…
-Тип 0
-Контекстно-свободной
-Контекстно-зависимой
-Регулярной
35 Грамматика G, определяемая правилами: SASB|BSA; Aa; Bb|е; Sbе, является…
-Тип 0
-Контекстно-зависимой
-Контекстно-свободной
-Регулярной
36 Грамматика G, определяемая правилами: SAcBs; AAcA|B; Ba|b, является…
-Тип 0
-Контекстно-свободной
-Контекстно-зависимой
-Регулярной
37 Из перечисленного регулярные языки могут быть заданы с помощью: 1) регулярных грамматик; 2) нерегулярных грамматик; 3) конечных автоматов; 4) нерегулярных множеств; 5) регулярных множеств.
- 2,4
- 1,4
-1, 3, 5
-1,2,3
38 Из перечисленного: 1) круглые скобки; 2) угловые скобки; 3) квадратные скобки; 4) запятая; 5) точка - в качестве метасимволов для задания грамматик используются
-2,4,5
-1,4,5
-1,2, 3
-3,4,5
39 Из перечисленного: 1) ленты; 2) устройства управления; 3) внешняя память; 4) внутренняя память; 5) решающее устройство - распознаватель состоит из компонентов
-3,4,5
-1,4,5
-1, 2, 3
-2,3,4
40 Когда символ определяется сам через себя в одном правиле, рекурсия называется
-косвенной
-явной
-левосторонней
-правосторонней
41 Конфигурация распознавателя определяется параметрами: 1) содержимое выходной цепочки символов; 2) содержимое входной цепочки символов; 3) состояние УУ; 4) содержимое внешней памяти; 5) содержимое внутренней памяти -из перечисленного
-1, 5
-1,2,3
-2, 3, 4
-3,4,5
42 По видам устройства управления распознаватели подразделяются на: 1) стохастические; 2) алгоритмизированные; 3) детерминированные; 4) недетерминированные; 5) аналитические - из перечисленного
-1,2,5
-1,3,5
-3, 4
-4,5
43 Существует … способ(а) представления функции переходов в конечном автомате.
-1
-3
-2
-4
44 Язык L(G)={ambn | m,n0} определяется грамматикой с правилами вывода:
-1) S AB ; 2) A aA| ; 3) B bB|;
-1) S A|B ; 2) A aA| ; 3) B bB|;
-1)S A|B|АВ ; 2) A aA ; 3) B bB;
-1) S AB ; 2) A aA|а ; 3) B bB|b;
Регулярные языки и грамматики
45 Конечный автомат –это простейший распознаватель
- с магазинной памятью.
- без вспомогательной памяти.
- без вспомогательной памяти и устройства управления
- без устройства управления
46 Конечный автомат создается
- для конкретного контекстно-свободного языка.
- для конкретного регулярного языка.
- для конкретного контекстно-зависимого языка.
- для конкретного языка с фразовой структурой.
47 Недетерминированным конечным автоматом (НКА) называется конечный автомат, в котором
- функция переходов задана графом переходов.
- функция переходов однозначна
- функция переходов неоднозначна.
- не задана функция переходов
48 Функция переходов конечного автомата по заданному текущему состоянию и текущему входному символу…
- следующий символ входной строки.
-указывает все возможные следующие состояния.
-указывает символ, на который перемещать считывающую головку
-указывает номер символа, на который перемещать считывающую головку
49 При табличном способе задания функции переходов конечного автомата, если в позиции таблицы указано более одного состояния, то..
- конечный автомат- детерминированный.
-считывающая головка не перемещается
- конечный автомат- недетерминированный.
-такой автомат существовать не может
50 Возможно ли преобразование недетерминированного конечного автомата в детерминированный, принимающий тот же регулярный язык?
- да
- нет
-да, при введении вспомогательной памяти
-да, если оставить в грамматике только заключительные правила
51 Конечный автомат может содержать лишние состояния двух типов:
- недостижимые и эквивалентные состояния.
- эквивалентные и заключительные состояния.
- эквивалентные и начальные состояния
- недостижимые и заключительные состояния
52 Минимальный конечный автомат, не содержит
- недостижимых и эквивалентных состояний.
- эквивалентных и начальных состояний.
- эквивалентных и заключительных состояний.
- недостижимых и заключительных состояний.
53 Построить конечный автомат по заданной регулярной грамматике с правилами
-M=({S,A,B,N},{a,b},F,{S},{N}), 1) SaB|aA 2) BbB|a|aN 3)AaA|b|bN; Функция F переходов автомата : F(a,S)=A; F(a,S)=B; F(b,S)= F(a,A)=A; F(b,A)=N; F(a,B)=N; F(b,B)=B; F(a,N)=; F(b,N)=;
-M=({S,A,B },{a,b},F,{S},{N}), 1) SaB|aA 2) BbB|a|aN 3)AaA|b|bN; Функция F переходов автомата : F(a,S)=A; F(b,S)= F(a,A)=A; F(b,A)=N; F(a,B)=N; F(b,B)=B; F(a,N)=; F(b,N)=;
- M=({S,A,B},{a,b},F,{S},{N}), 1) SaB|aA 2) BbB|a|aВ 3)AaA|b|bВ; Функция F переходов автомата : F(a,S)=A; F(a,S)=B; F(b,S)= F(a,A)=A; F(b,A)=В; F(a,B)=В; F(b,B)=B; F(a,N)=; F(b,N)=;
- M=({S,A,B },{a,b},F,{S},{N}), 1) SaB|aA 2) BbB|a|aN 3)AaA|b|bN; Функция F переходов автомата : F(a,S)=В; F(b,S)= F(a,A)=A; F(b,A)=N; F(a,B)=N; F(b,B)=B; F(a,N)=; F(b,N)=;
Контекстно-свободные языки и грамматики
54 КС-грамматика называется приведенной, если она
-не имеет циклов и -правил.
- не имеет циклов, -правил и бесполезных символов.
- не имеет -правил и бесполезных символов.
-не имеет циклов и бесполезных символов.
55 Грамматику с правилами преобразовать в эквивалентную грамматику удалением недостижимых символов.
- с правилом
-=({a,b,с},{S},Р,S) с правилом
- с правилами
- с правилами
56 Грамматику с правилами преобразовать в эквивалентную грамматику без -правил для всех нетерминальных символов, кроме начального, который не должен встречаться в правых частях правил грамматики. Результирующая грамматика будет иметь вид:
- с правилами .
-=({0,1},{S,А,B,C},Р, S) с правилами .
- с правилами .
-=({0,1},{S,А,B,C},Р, S) с правилами .
57 Грамматику с правилами преобразовать в эквивалентную грамматику ,устранив цепные правила. Результирующая грамматика будет иметь вид:
- с правилами .
- с правилами
- с правилами .
- с правилами .
58 Грамматику с правилами . преобразовать в эквивалентную грамматику , устранив прямую левую рекурсию. Результирующая грамматика будет иметь вид:
- с правилами
-=({a, b, с, d, z},{S,А,B,C}, P’, S) с правилами
- с правилами
- с правилами
59 Контекстно-свободные языки можно распознавать с помощью
- автомата с магазинной памятью (МП-автомата).
- конечного автомата.
- машины Тьюринга с конечным объемом ленты.
-машины Тьюринга.
60 Шаг работы МП-автомата называется -шагом, который может выполняться даже после завершения чтения входной строки, если
- он переходит в очередное состояние , сдвигает входную головку на ячейку вправо и заменяет верхний символ S строкой магазинных символов.
- входной символ t не принимается во внимание, и входная головка не сдвигается.
- входной символ t копируется в стек, и входная головка не сдвигается.
- входной символ t копируется в стек, и входная головка сдвигается на одну позицию вправо.
61 МП-автомат принимает строку языка опустошением магазина, если
-имеет в вершине стека символ S (аксиому грамматики).
-cчитывающая головка устройства управления сошла с входной ленты.
- после завершения ее чтения стек автомата будет пуст.
- cчитывающая головка устройства управления стоит на первом символе входной ленты.
62МП-автомат называют детерминированным (ДМП-автоматом), если, находясь в любой конфигурации
- он может выбрать более одной следующей конфигурации.
- он может считать не более одного символа входной ленты.
- он может выбрать не более одной следующей конфигурации.
- он может выбрать две следующие конфигурации.
63 Дана грамматика с правилами . Требуется выполнить анализ строки cabca.
Левосторонний вывод цепочки имеет вид:
-.
-
-
-
64 МП-автомат называется расширенным автоматом c магазинной памятью, т.е. автоматом, который может заменять
- каждый раз только один символ в вершине стека.
- цепочку символов конечной длины в верхушке стека на другую цепочку символов конечной длины.
- символ в вершине стека на пустую строку.
-несколько символов в вершине стека на пустую строку.
65. КС-грамматика обладает свойством LL(k) для некоторого k>0, если на каждом шаге вывода для однозначного выбора очередной альтернативы МП-автомату достаточно знать символ на верхушке стека и
- рассмотреть первые k символов от текущего положения считывающей головки во входной строке.
- рассмотреть первый символ от текущего положения считывающей головки во входной строке.
- рассмотреть первые k-1 символов от текущего положения считывающей головки во входной строке.
- рассмотреть первые k+1 символов от текущего положения считывающей головки во входной строке.
66 КС-грамматику называют LL(1) грамматикой, если
- не пересекаются множества направляющих символов для правил, определяющих один и тот же нетерминал грамматики.
- в правилах присутствует левая рекурсия.
-не пересекаются множества символов предшественников для правил, определяющих один и тот же нетерминал грамматики.
-в правилах присутствует правая рекурсия.
67 КС-грамматика не является LL(1) грамматикой, если
- в альтернативных правых частях правил для нетерминала присутствуют одинаковые головные символы или левая рекурсия.
- не пересекаются множества направляющих символов для правил, определяющих один и тот же нетерминал грамматики.
- в альтернативных правых частях правил для нетерминала присутствует правая рекурсия.
- в альтернативных правых частях правил для нетерминала присутствует правая рекурсия.
- в альтернативных правых частях правил для нетерминала присутствует правая рекурсия и цепные правила.
68 Что является главной проблемой восходящего анализа ?
-Процесс выполнения операций «перенос» и «свертка».
-Получение очередной правовыводимой сентенциальной формы.
-Обеспечение однозначности определения строки в вершине стека для свертки к нетерминалу.
-Определение исходной сентициальной формы
69 В основе распознавателя для грамматик простого предшествования лежит
- правосторонний разбор строки языка.
- левосторонний разбор строки языка.
-нисходящая стратегия разбора строки языка
-разбор строки языка без использования стека
70 Отношения простого предшествования Вирта-Вебера позволяют
- выделить основу правовыводимой сентенциальной формы.
- выполнить эквивалентные преобразования по устранению бесполезных символов и циклов.
-выделить основу левовыводимой сентенциальной формы.
- выполнить эквивалентные преобразования по устранению -правил и циклов.
71 В строке b1< b2= b3< b4= b5> b6 c указанными отношениями предшествования между символами основой является подстрока
- b4b5
- b3b4
- b1b2
- b5b6
72 Пустые клетки матрицы предшествования указывают на то, что
- данные символы не связаны отношением предшествования.
- данные символы связаны отношением предшествования.
- допущена ошибка в построении матрицы
- данные символы не могут попасть в основу сентенциальной формы
73 Приведенное отношение предшествования между двумя соседними символами распознаваемой строки Bi < Bi+1, существует
- если Bi+1 –крайний левый символ некоторой основы;
- если Bi –крайний правый символ некоторой основы.
- если Bi –центральный символ некоторой основы.
- если Bi+1 –центральный символ некоторой основы.
74 МП-автомат называется недетерминированным, если из одной и той же его конфигурации …
-возможен более чем 1 переход
-возможен не более чем 1 переход
-возможен только 1переход
-возможно менее 2 переходов
75 Два МП-автомата называются … , если они определяют один и тот же язык.
-конечными
-эквивалентными
-детерминированными
-недетерминированными
76 МП-автомат называется детерминированным, если, находясь в любой конфигурации, он может выбрать .
- не более 2-х следующих конфигураций
- не более 1 следующей конфигурации
- не менее 2-х следующих конфигураций
- не более 3-х следующих конфигураций
77 Можно выделить две основные цели преобразований КС-грамматик: …
-упрощение правил грамматики и облегчение создания распознавателя языка
-удаление недостижимых и бесплодных символов
-удаление бесплодных символов и устранение цепных правил
-удаление недостижимых и e-правил
78 Дерево разбора можно построить двумя способами: ....
-сверху вниз и снизу вверх.
-слева направо и справа налево
-слева направо и сверху вниз
-справа налево и снизу вверх
79 Для того чтобы преобразовать произвольную КС-грамматику к приведенному виду, необходимо выполнить следующие действия:
-удалить все недостижимые символы и цепные правила
-удалить все бесплодные символы, все недостижимые символы, e-правила и цепные правила
-удалить все бесплодные символы и все недостижимые символы
-удалить все недостижимые символы и e-правила
80 Бесполезными символами грамматики называют:
-нетерминалы, не порождающие терминальных строк; недостижимые нетерминалы, порождающие терминальные строки; недостижимые терминалы
-недостижимые терминалы
-нетерминалы, не порождающие терминальных строк; недостижимые нетерминалы, порождающие терминальные строки
-нетерминалы, не порождающие терминальных строк
81 МП-автомат с магазинной функцией называется … МП-автоматом
-конечным
-расширенным
-детерминированным
-недетерминированным
82 Чтобы исключить появление циклов в цепочках вывода КС-грамматик, достаточно устранить …
-e-правила
-цепные правила
-недостижимые правила
-левую факторизацию правил
83 КС-грамматика G(VT, VN, P, S) называется грамматикой в нормальной форме …. , если в её множестве правил Р присутствуют только правила следующего вида:
1.A->BC,где A,B,CОVN
. A->a, где AОVN и aОVT
3. S->e, если eОL(G)
-Хомского
-Бэкуса - Наура
-Вирта
-Грейбаха
84 Грамматика называется однозначной, если для каждой цепочки символов языка, заданного этой грамматикой, можно построить …
-единственный левосторонний (и единственный правосторонний) вывод
-множество левосторонних и правосторонних выводов
-единственный правосторонний вывод
-единственный левосторонний вывод
85 Алгоритм «сдвиг-свёртка» предусматривает циклическое выполнение следующих шагов:
-Попытка свёртки, перенос-сдвиг, возврат
-Попытка свёртки, перенос-сдвиг, завершение
-Попытка свёртки, перенос-сдвиг, завершение, переход к возврату, возврат
-Попытка свёртки, перенос-сдвиг
86 … называются языки, определяемые грамматиками типа G(VT,VN,P,S), в которых правила Р имеют вид A->, где A VN и V*, V=VT VN
-Регулярными
-Контекстно-свободными
-Формальными
-Контекстно-зависимыми
87 МП-автомат в отличии от обычного КА имеет … , куда можно помещать специальные «магазинные» символы
-стек
-алфавит
-правила
-входную ленту
88 МП-автомат имеет специальные «магазинные символы, которые состоят из …
-только нетерминальных символов
-только терминальных символов
-терминальных и нетерминальных символов
-специальных символов, которые не входят ни в терминальные, ни в нетерминальные символы
89 Конфигурация автомата определяется следующими параметрами:
-текущим символом входной цепочки и содержимым стека
-состоянием автомата и текущим символом входной цепочки
-состоянием автомата, текущим символом входной цепочки и содержимым стека
-состоянием автомата и содержимым стека
90 Язык, определяемый МП-автоматом, - это …
-нетерминальные символы
-множество всех цепочек символов, которые допускает данный автомат -терминальные символы
-специальные символы
91 Грамматика называется неоднозначной, если для каждой цепочки символов языка, заданного этой грамматикой, можно построить …
-множество деревьев вывода
-единственный левосторонний вывод дерева
-единственное дерево вывода
-единственный правосторонний вывод дерева
92 В результате эквивалентных преобразований над КС-грамматикой (устранение бесполезных символов, -правил, цепных правил, левой факторизации и левой рекурсии), мы получаем грамматику, определяющую …
-тот же самый язык
-новый язык
-почти эквивалентный язык
-регулярный язык
93 Символ x (VTVN) называется …, если он не встречается ни в одной сентенциальной форме грамматики G(VT,VN,P,S)
-бесплодным
-недостижимым
-символом с цепным правилом
-рекурсивным
94 Нетерминальный символ называется … тогда, когда из него нельзя вывести ни одной цепочки терминальных символов.
-недостижимым
-бесплодным
-символом с цепным правилом
-рекурсивным
95 В грамматике G(VT,VN,P,S) символ X VN называется …, если для него выполняется:
-недостижимым
-бесплодным (не порождающим терминальных строк)
-символом с цепным правилом
-рекурсивным
96 … называются все правила грамматики вида A®e, где AVN
-Цепными правилами
-e-правилами
-Правилами с левой факторизацией
-Правилами с левой рекурсией
97 … в грамматике G(VT,VN,P,S) называется вывод вида A®*А, AVN
-Прямой левой рекурсией
-Циклом
-Левой факторизацией правил
-Правой рекурсией
98 Чтобы исключить возможность появления циклов в цепочках вывода, достаточно устранить … из набора правил грамматики.
-e-правила
-прямую левую рекурсию
-цепные правила
-левую факторизацию правил
99 Символ AVN в КС-грамматике G(VT,VN,P,S) называется … , если для него существует цепочка вывода вида A® -А, где , (VTVN)*
-рекурсивным
-цепным
-недостижимым
-бесплодным
100 Приведенные грамматики –это КС-грамматики, которые не содержат …
-недостижимых и бесплодных символов
-недостижимых и бесплодных символов, циклов и e-правил
-циклов и e-правил
-недостижимых символов и циклов
Основные принципы построения трансляторов
101 Транслятор, который осуществляет перевод исходной программы в эквивалентную ей объектную программу на языке машинных команд или на языке ассемблера, называется...
-ассемблером
-интерпретатором
-компилятором
-анализатором.
102 Программа, которая переводит входную программу на исходном (входном) языке в эквивалентную ей выходную программу на результирующем (выходном) языке, называется...
-компилятор
-ассемблер
-транслятор
-интерпретатор
103 Процесс последовательного чтения компилятором данных из внешней памяти, их обработки и помещения результатов во внешнюю память, называется проходом ...
-компилятора
-транслятора
-ассемблера
-интерпретатора
104 В основе метода рекурсивного спуска лежит ... разбор строки языка
-правосторонний
-левосторонний
-двусторонний
-односторонний
Первый этап процесса компиляции, на котором символы, составляющие исходную программу, группируются в отдельные минимальные единицы текста, несущие смысловую нагрузку , называется …. анализатором
-Семантическим
-Лексическим
-Синтаксическим
-Орфографическим
106 Часть компилятора, которая читает литеры программы на исходном языке и строит из них слова (лексемы) исходного языка, называется …
-синтаксический разбор
-лексический анализ
-семантический анализ
-генерация кода
107 Фаза компиляции, непосредственно связанная с порождением команд, составляющих предложения выходного языка и в целом текст результирующей программы, называется … кода
-генерация
-оптимизация
-синтез
-анализ
108 Программа, которая воспринимает входную программу на исходном языке и выполняет ее, называется …
-транслятор
-интерпретатор
-компилятор
-ассемблер
109 Метод рекурсивного спуска является методом … анализа.
-семантического
-лексического
-синтаксического
-сравнительного
110 Метод рекурсивного спуска реализует разбор цепочки …
-снизу вверх
-сверху вниз
-справа налево
-слева направо
111 Компилятор, который переводит каждую команду исходной программы в одну машинную команду, называется…
-транслятор
-ассемблер
-анализатор
-интерпретатор
112 К основным функциям компилятора относится … и
-генерация выходной цепочки символов на языке машинных команд или ассемблере;
-проверка исходной цепочки символов на принадлежность к входному языку;
-проверка исходной цепочки символов на принадлежность к выходному языку;
-генерация входной цепочки символов на языке машинных команд или ассемблере;
113 К двум основным этапам процесса компиляции относятся этапы …
- анализа и трансляции
синтеза и анализа
-трансляции и синтеза
-генерации и трансляции
114 При компиляции программы результатом работы этапа … является объектный код
-синтеза;
-анализа;
-трансляции;
-интерпретации
115 На этапе … на основании внутреннего представления программы и информации, содержащейся в таблице идентификаторов, порождается текст результирующей программы.
-анализа
-синтеза
-трансляции
-интерпретации
116 Компилятор отличается от транслятора лишь тем, что его результирующая программа всегда должна быть написана на языке …..
-Паскаля
-с-++
-Ассемблера
-Пролог
117 В отличие от …… интерпретаторы не порождают результирующую программу.
-анализаторов;
-трансляторов;
-ассемблера;
-генераторов.
118 Проверка исходной цепочки символов на принадлежность к входному языку и генерация выходной цепочки символов на языке машинных команд или ассемблере являются основными функциями …..
-интерпретатора
-компилятора
-генератора
-трансляторов
119 Этапы синтеза и анализа состоят из более мелких стадий, называемых...
-фазами
-периодами
-уровнями
-формами
120 В каждом компиляторе выделяются следующие две фазы:
-лексический анализ и генерация кода;
- лексический анализ и оптимизация кода;
-синтаксический анализ и семантический анализ;
- семантический анализ и генерация кода;
121 Распознавание текста исходной программы , создание и заполнение таблиц идентификаторов выполняется на этапе …
-синтеза;
-анализа;
-генерации;
-компиляции.
122 Лексический анализатор (ЛА) –это ….. этап процесса компиляции
-первый
-второй
-третий
-заключительный
123 Выделить лексемы и преобразовать их к виду, удобному для последующей обработки является задачей ….. анализа
-синтаксического
-семантического
-лексического
-сравнительного
124 ... анализ уменьшает длину программы, устраняя из ее исходного представления несущественные пробелы и комментарии.
-синтаксический
-семантический
-лексический
-сравнительный
125 После лексического анализа каждая лексема представляет собой пару чисел вида (n, k), где n –номер таблицы лексем, k -…..
-размер лексемы в таблице
-номер лексемы в таблице
-вид лексемы в таблице
-тип лексемы в таблице
126 Таблицы идентификаторов и чисел формируются в ходе ….. анализа.
-лексического
-синтаксического
-семантического
-сравнительного
127 Сканер проводит анализ текста программы путем разбора по регулярным грамматикам и опирается на способ разбора по …..состояний
-диаграмме
-графику
-таблице
-формуле
128 Построение диаграммы состояний (ДС) с действиями для распознавания и формирования внутреннего представления лексем; и написание программы сканирования текста исходной программы по ДС с действиями, являются этапами построения …. анализа
-синтаксического
-лексического
-семантического
-сравнительного
129 При организации таблиц идентификаторов на этапе лексического анализа не используется метод...
-оптимизации кода;
-бинарного дерева;
-хеш-функций;
-цепочек;
130 К двум методам организации взаимосвязи лексического анализа и синтаксического разбора относятся ...
-параллельный и линейный;
-последовательный и параллельный;
-линейный и последовательный;
- параллельный и нелинейный.
131При ... варианте лексический анализатор просматривает весь текст исходной программы от начала до конца и преобразует его в структурированный набор данных.
-последовательном;
-параллельном;
-линейном;
-нелинейном.
132 Ситуация, когда двум или более идентификаторам соответствует одно и то же значение функции, называется ...
-коллизией;
-тетрадой;
-триадой;
-диффузией.
133 Процесс выполнения макрокоманды называется ...
-макрогенерацией;
-макрорасширением;
-трансляцией;
-генерацией.
134 Цепочка символов, получаемая в результате выполнения макрокоманды, называется ...
-макрорасширением
-макрогенерацией;
-трансляцией;
-генерацией.
135 Основное отличие интерпретатора от трансляторов и компиляторов заключается в том, что интерпретатор не порождает ... .
-исходный код;
-результирующую программу;
-объектный код;
-машинную программу.
136 Преимуществом интерпретатора перед компилятором является ... .
-независимость выполнения программы от архитектуры целевой вычислительной системы;
-отсутствие фазы оптимизации в общей структуре;
-отсутствие шага оптимизации;
-исполнение команд по мере их поступления.
137 Структурная единица языка, которая состоит из элементарных символов языка и не содержит в своем составе других структурных единиц языка, называется ...
-лексема;
-сканер;
-лексический анализатор;
-синтаксический анализатор.
138 При прямой работе лексического анализатора возможно его ... взаимодействие с синтаксическим распознавателем.
-последовательное;
-параллельное;
-линейное;
-нелинейное.
139 При непрямой работе лексического анализатора возможно его ... взаимодействие с синтаксическим распознавателем.
-параллельное;
-последовательное;
-линейное;
-нелинейное.
140 Программой для генерации сканеров (лексических анализаторов) является ....
-LEX;
-Mathcad;
-Statistica;
-ISAPI.
141 Набор данных, служащий для хранения информации об элементах исходной программы называется таблицей ... .
-трансляторов;
-идентификаторов;
-компиляторов;
-анализаторов.
142 Результирующая программа компилятора называется ...кодом .
-объектным;
-внутренним;
-исходным;
-внешним.
143 К способам организации таблиц идентификаторов относятся методы ...
-цепочек;
-бинарного дерева;
-хеш-функций;
-оптимизации кода;
144 В синтаксическом дереве внутренние узлы (вершины) соответствуют … .
-операциям
-операндам
-идентификаторам
-записям
Генерация и оптимизация кода
145 Польская инверсная запись —это … запись операций.
-префиксная
-постфиксная
-инфиксная
-обычная
146 При … записи операция записывается между своими операндами.
-инфиксной
-префиксной
-постфиксной
-обратной польской записи
147 Перевод компилятором внутреннего представления программы в цепочку символов выходного языка - это….
-оптимизация программы
-генерация объектного кода
-синтаксические деревья
-ассемблерный код
148 Тетрады имеют вид:
-<операция>(<операнд1>,<операнд2>,<результат>)
-<операция>(<операнд1>, <операнд2>)
-<операнд1>,<операция>,<операнд2>(<результат>)
-<операнд1>,<операнд2>(<результат>)
149 Выражение (a-b)*(c+e) представляется в форме триад следующим образом
- 1) - а b; 2) + c e; 3) * (1)(2)
- 1) а b-; 2) c e+; 3) (1)*(2)
- 1) - а b; 2) c e+;3) (1)*(2)
- 1) а b-; 2) + c e; 3) * (1)(2)
150 … представляют собой запись операций в форме из трех составляющих: операция и два операнда.
-машинные команды
-тетрады
-триады
-монады
151 Обработка, связанная с переупорядочиванием и изменением операций в компилируемой программе с целью получения более эффективной результирующей объектной программы называется…
-оптимизацией программы
-генерацией кода
-СУ-переводом
-СУ-компиляцией
152 Выполняемая по порядку последовательность операций, имеющая один вход и один выход- это… .
-линейный участок программы
-свертка объектного кода
-оптимизация программы
-исключение лишних операций
153 Выполнение во время компиляции тех операций исходной программы, для которых значения операндов уже известны называется ….
-линейным участком программы
-оптимизацией программы
-свёрткой объектного кода
-исключением лишних операций
154 Тетрады представляют собой … последовательность команд.
-линейную
-иерархическую
-логическую
-нелинейную
155 Оператор x:=x+9 в ПОЛИЗе имеет вид:
-x x 9 + :=
-x:= x 9 +
-x 9 + := x
-x x:= 9 +
156 Для выражения в обычной (инфиксной записи) a*(b+c)-(d-e)/f ПОЛИЗ имеет вид:
-a b c * + d e - / f -
-a b c + * d e - / f
-a b c + * d e - / f -
-a * b c + - d e / f
157 Для оптимизации циклов не используется следующий метод:
-обратная польская запись операций
-вынесение инвариантных вычислений из циклов
-замена операций с индуктивными переменными
-слияние и развертывание циклов
158 В процессе оптимизации кода при компиляции замена цикла на линейную последовательность операций - это….
-развёртывание
-слияние
-обратная польская запись
-ассемблерный код
159 Оператор присваивания I:=E в ПОЛИЗе записывается:
-:= IE
- I:=E
- IE:=
-:=IE
160 Область памяти, размер которой известен на этапе компиляции, называется … .
-статической
-динамической
-глобальной
-локальной
161 Область памяти, которая выделяется один раз при инициализации результирующей программы и действует всё время выполнения программы, называется ….
-локальной
-динамической
-глобальной
-статической
162 Область памяти, размер которой на этапе компиляции не известен, называется ….
-глобальной
-статической
-динамической
-локальной
163 Область памяти, которая выделяется в начале выполнения некоторого фрагмента результирующей программы и может быть освобождена по завершении выполнения данного фрагмента, называется…
-локальной
-динамической
-глобальной
-статической
164 Результат выражения 6 7 + 10 4 * + , записанного в форме обратной польской записи, равен… .
-53
-104
-74
-83
165 Две основные схемы компиляции, которые чаще всего используются при создании компиляторов это:
-интегрированная и последовательная
-последовательная и динамическая
-параллельная и динамическая
-динамическая и интегрированная
166 Подстановка кода функции в вызывающий объектный код называется … .
-inline подстановкой
-оптимизацией циклов
-передачей параметров через регистры
-свёрткой объектного кода
167 Изменение порядка следования операций, которое может повысить эффективность программы, называется ….
-перестановкой
-удаление бесполезных присваиваний
-линейный участок программы
-арифметические преобразования
168 Схема, в которой компоненты выполняются под управлением синтаксического анализатора, называется ….
-интегрированной
-последовательной
-статической
-динамической
169 К машинно-зависимым методам оптимизации кода относятся … и ….
-распределение регистров процессора, распараллеливание вычислений
-распараллеливание вычислений, тетрады
-триады, тетрады
-тетрады, распределение регистров процессора
170 МП - преобразователь будет …, если он имеет не более одной возможной очередной конфигурации.
-детерминированным
-недетерминированным
-входным
-выходным
180 Индуктивной переменной в цикле S:= 10; for i:=l to N do A[i] :=i*S; является ….
-i
-S
-i,S
-A
181 Методы оптимизации, ориентированные на конкретную архитектуру целевой вычислительной системы, на которой будет выполняться результирующая программа,
называются ….
-машинно-зависимыми
-машинно-независимыми
-машинными
-независимыми
182 Переменная называется индуктивной в цикле, если ее значения в процессе выполнения цикла образуют … прогрессию.
-математическую
-арифметическую
-геометрическую
-инвариантную
183 Два метода построения объектной программы путем преобразования исходной программы:
-СУ-перевод и Т-грамматика
-Т-грамматика и АТ-грамматика
-СУ-компиляция и СУ-перевод
-АТ-грамматика и СУ-перевод