Разработка компиляторов - тест 4

Одна из первых задач, возникающих в процессе компиляции - это:

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

Грамматики представляют собой:

Получение любого предложения языка в грамматике начинается с этого:

В формальном определении грамматики нетерминалы обозначаются:

Различные грамматики могут порождать:

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

Определение грамматик не накладывает никаких ограничений на количество:

Иерархия Хомского - это классификация грамматик согласно:

Согласно иерархии Хомского, если любое правило из P имеет вид A->xB или A->x, где A, B - нетерминалы, а x - терминал, то грамматика G называется:

Согласно иерархии Хомского, если любое правило из P имеет вид A->a, где A - нетерминал, a - нетерминал или терминал то грамматика G называется:

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

В качестве примеров распознавателей можно назвать:

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

Основная часть конечного автомата - это:

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

Язык распознается конечным автоматом, если:

Удобная форма записи конечных автоматов – это:

Следующий набросок программы:q = q0;
c = GetChar();
while (c != eof) {
  q = move (q, c);
  c = GetChar();
}
if (q is in F) return "yes";
else return "no";
 
демонстрирует (предполагается, что входная лента заканчивается символом end_of_file):

Два детерминированных автомата называются эквивалентными, если они:

Если мы предположим, что начальные состояния конечных автоматов эквивалентны, то мы можем получить:

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

Классы языков, определяемых праволинейной грамматикой являются:

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

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

Любая КС-грамматика может быть приведена к нормальному виду Хомского, в котором все правила имеют один из следующих видов:

В нормальной форме Грейбах все правые части правил начинаются:

Магазинные автоматы, известны также как:

На каждом шаге работы МП-автомат может либо:

МП-автоматы обладают одним существенным недостатком:

Детерминированные МП-автоматы описывают только подмножество всего класса КС-языков - это подмножество называется:

Форма Бэкуса-Наура был разработана для описания:

При определении синтаксиса языков Pascal и Modula-2 Вирт использовал расширенную форму Бэкуса-Наура (EBNF):

Следующее правило:REF to MODE NEST assignation: 
REF to MODE NEST destination, becomes token, 
MODE NEST source.
определяет:

Синтаксические диаграммы или синтаксические схемы имеют форму: