Контрольная работа по "Основам трансляции"

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ПОДГОТОВКИ ИНЖЕНЕРНЫХ КАДРОВ

КАФЕДРА САПР и ПК

 

 

 

 

 

 

 

 

 

Контрольная работа

 

по курсу:    «Основы  трансляции»

 

 

 

 

 

 

 

 

 

 

 

Выполнил:

 

 

 

 

 

 

 

Глава № 1

 

  1. Вопрос:

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

  1. Ответ: 

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

а) Универсальный язык не всегда удобен в конкретной узкой  области – или громоздок, или не подходит модель, взятая за его основу, или…

б) САПР создается для  конечных пользователей – конструкторов  и технологов, следовательно, взаимодействие с САПР должно вестись на удобном  для пользователя языке. Конструкторы и технологи не обязаны знать программирование. Элементы вновь созданного языка должны быть близки к области, в которой работают конструкторы. Пользователь должен легко оперировать знакомыми и понятными ему терминами.

 

  1. Вопрос:

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

2.  Ответ: 

Языки проектирования – языки, предназначенные для описания информации об объекте и процессе проектирования.

Языки программирования – формальные языки для описания данных (информации) и алгоритма (программы) их обработки на ЭВМ. Основу языков программирования составляют алгоритмические языки.

 

  1. Вопрос:

По каким признакам  классифицируют языки проектирования?

3. Ответ:

Языки проектирования классифицируются по следующим признакам:

а) По месту в процессе проектирования, которые в свою очередь делятся:

1) Входные

2) Внутренние

3) Промежуточные

4) Выходные

5) Сопровождения

6) Управления

б) По связи с универсальными ЯП

1) Автономные

2) Расширяющие

в) По оперативности

1) Диалоговые

2) Пассивные

г) По способу представления информации

1) Алф-цифровые

2) Графические

3) Голосовые

4) Смешанные

 

  1. Вопрос:

Перечислите требования к языкам проектирования.

4. Ответ:

Требования к языкам проектирования:

  1. Эффективность – точность передачи задания пользователя и лаконичность записи.
  2. Полнота – возможность описания всех объектов проектирования, а также всех действий, имеющих отношение к цели проектирования конкретной САПР.
  3. Непротиворечивость – каждое предложение, сформулированное в терминах данного языка с использованием правил (синтаксиса) данного языка должно иметь естественную семантическую интерпретацию (смысл).
  4. Расширяемость – обеспечение возможности дополнения языка в соответствии с развитием предметной области.
  5. Выразительность и проблемная ориентация – обеспечение простоты изучения и использования языков проектировщиками – не программистами. Языки должны быть близки к естественному.

 

Глава № 2

 

  1. Вопрос: 

В чем состоит задача трансляции?

1. Ответ: 

Задача трансляции – построить алгоритм, осуществляющий перевод программы, написанной на языке L1 в требуемый выход (в частности, на другой язык).

 

  1. Вопрос:

Какой тип языкового  процессора называют компилятором? Препроцессором? Интерпретатором?

2. Ответ:

Компилятором – называют транслятор, у которого язык L2 (объектный язык) – язык машинных команд.

Препроцессором – называют транслятор, у которого язык L2 (объектный язык) – язык высокого уровня.

Интерпретатором – называют транслятор, который не выдает результата на языке L2, а сразу выполняет действие.

 

  1. Вопрос:

Из каких основных блоков обычно состоит компилятор?

3. Ответ: 

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

1) Лексического

2) Синтаксического

3) Генератора кода

Иногда дополнительно  используются:

1) Семантический блок 

2) Блок оптимизации

 

  1. Вопрос:

Что понимается под лексемой при разработке компилятора?

4. Ответ: 

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

 

  1. Вопрос:

 Какова главная  функция лексического блока? Синтаксического?  Генератора кода?

5. Ответ:

Лексический блок – устанавливает из каких частей состоит данная цепочка и преобразует части в лексемы.

Синтаксический блок (парсер) – переводит последовательность лексем, построенную сканером, в последовательность лексем, которая непосредственно отражает порядок, в котором должны выполняться операции в программе.

Генератор кода) – «развертывает» атомы, построенные синтаксическим блоком в последовательность команд ЭВМ.

 

  1. Вопрос:

Опишите входную и  выходную информацию при обработке  каждым блоком компилятора следующей программы:

Begin a:=5; b:=a+7*(2*a/b-abc)/40b; end

6. Ответ:

Лексический блок:

Входная инф.:     

Begin a:=5; b:=a+7*(2*a/b-abc)/40b; end

Выходная инф.:

Begin | a | := | 5| ; | b | := | a | + | 7 | * | ( | 2 | * | a | / | b | - | abc | ) | / | 40b | ; | end

Begin (1,0)

a (30,1)

:= (24,0)

5(40,1)

; (20,0)

b (30,2)

:= (24,0)

a (30,1)

+ (22,0)

7 (40,2)

* (23,0)

( (25,0)

2 (40,3)

* (23,0)

a (30,1)

/ (23,1)

b (30,2)

- (22,1)

abc (30,3)

) (26,0)

/ (23,1)

40b (30,4)

; (20,0)

end (2,0)

 

Синтаксический блок:

Входная инф.:

Выходная инф. с лексического блока.

Выходная инф.:

begin

сум(5,0,a)

умнож(2,а,R1)

дел(R1,b,R2)

выч(R2,abc,R3)

умнож(7,R3,R4)

дел(R4,40b,R5)

сум(a,R5,b)

end

 

Генератора кода

Входная инф.:

Выходная инф. с синтаксического  блока.

Выходная инф.:

Выполнение программы

 

Глава №3

 

  1. Вопрос:

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

1. Ответ: 

Словарь языка содержит множество лексем.

Синтаксис языка представляет собой совокупность правил построения языковых конструкций (предложений) из лексем.

Семантика языка это совокупность правил интерпретации лексем и языковых конструкций.

 

  1. Вопрос:

В чем суть метода синтаксически-ориентированной  трансляции?

2. Ответ:

Метод синтаксически-ориентированной  трансляции, основанный на работах  американского ученого Ноэля Хомского. Из гипотезы Хомского следует, что семантический анализ сводится к синтаксическому и состоит из двух процедур:

  1. распознавание структуры входного предложения;
  2. построение выходного текста (действий) на основе этой структуры.

 

  1. Вопрос:

Назовите основные понятия  теории формальных языков.

3. Ответ:

Основные понятия теории формальных языков:

Словарь – это конечное множество элементов, называемых символами.

Цепочка над  словарем V – это произвольная упорядоченная последовательность символов словаря.

Пустая цепочка – это цепочка, не содержащая символов (обозначается e).

 

  1. Вопрос:

Перечислите основные операции над цепочками.

4. Ответ:

Операции над цепочками:

  1. Конкатенация (склеивание) – бинарная операция на множестве V*.

Если a, bÎV*, то результат конкатенации – цепочка ab.

  1. Подстановка – замена некоторой цепочки заданной цепочки a цепочкой b:                        a= aabcc, b= bca, g= abcac.

 

  1. Вопрос:

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

5. Ответ:

Языком над  словарем V называется некоторое множество цепочек над словарем V.

Обозначение:           L(V)Î V*.

 

  1. Вопрос:

Дан словарь V={a, в, с}. Приведите примеры конечного и бесконечного языков над данным словарем.

6. Ответ:

  1. L={авс, аавс, васс} Это пример конечного языка, состоящего из трех цепочек.
  2. L={an , вn , сn} (n³0). aaaвввсссÎ L, aaaвсÏL. Это пример языка содержащего бесконечное количество цепочек.

 

  1. Вопрос:

Дан язык L={синий лес, синий темный лес, темный лес}. Приведите примеры словарей, над которыми можно определить этот язык.

7. Ответ:

V1={синий, лес, темный}

V2={с,и,н,й,л,е,т,м,ы}

 

 

 

 

Глава №4

 

1. Вопрос:

К какому описанию языка  применим термин формальная грамматика?

1. Ответ:

Термин «формальная  грамматика» применим к любому определению  формального языка, основанному  на грамматических правилах, с помощью которых можно порождать и анализировать цепочки аналогично тому, как грамматики используются при изучении естественных языков.

 

2. Вопрос:

 Опишите при помощи грамматики язык, состоящий из следующих предложений:

Зеленый крокодил видит зеленый лес.

Большой зеленый крокодил видит лес.

Крокодил видит большой  зеленый лес.

Крокодил видит зеленый  лес.

2. Ответ:

V={крокодил, лес, зеленый, большой, видит}

Правила:

1) <предложение>®<подлежащее><сказуемое><дополнение>

2)<подлежащее>®<прилагательное><существительное>|

<существительное>

3) <дополнение >®<прилагательное><существительное>|

<существительное>

4) <прилагательное>®зеленый | большой | большой зеленый

5) <существительное>®лес | крокодил

6) <сказуемое>®видит 

 

3. Вопрос:

Дайте определение порождающей грамматики Хомского

3. Ответ:

Порождающей грамматикой  Хомского – называется грамматика, которая «порождает» (выводит)  множество  называемое языком.

 

4. Вопрос:

 Задайте с помощью  грамматики Хомского следующий  язык: L={aab, abab, abc, aabc}. Постройте дерево вывода для одной из цепочек языка.

4. Ответ:

G0=(T0  , N0 ,  S , R0)

T0={a,b}

N0={A,B,S}

R0:

S®aAb|aBc

A®a|ba

B®b|ab

S®aAb® abab


    aab

 

5. Вопрос:

Пусть грамматика G содержит следующие правила: bA®acBc, aBc®c. Выводимы ли в данной из цепочки  a=acbAacaBc цепочки b= acacBcacc,  g= acacBcaca ? Докажите.

Дана грамматика G: G= (Т, N, S, R), Т= {a, b}, N= {A, B, S}, R: S®aS

bA®ab

aS®bA

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

5.Ответ:

1) a=acbAacaBc

b= acacBcacc

a=acbAacaBc® acacBcacaBc ® acacBcacc=b

g= acacBcaca

так как грамматика G содержит следующие правила: bA®acBc, aBc®c.

из a можно вывести b и нельзя вывести g

2) Дана грамматика G: G= (Т, N, S, R), Т= {a, b}, N= {A, B, S}, R: S®aS

bA®ab

aS®bA

Язык L={(a)nb; n>=1}

S®aS®aaS®abA®aab

Cентенциальные формы: aS,aaS,abA

 

6. Вопрос:

Приведите пример продукции, задающей процесс усвоения знаний студентом  на лекции.

6. Ответ:

Выучи лекции, если хочешь сдать экзамен, ответь на билет и получи отличную оценку.

Выучи лекции – условие  применимости ядра

если хочешь сдать  экзамен - ядро продукции

ответь на билет и  получи отличную оценку - постусловия продукции

 

7. Вопрос:

а) Дана грамматика G= (Т, N, S, R), Т= {a, b, c, d}, N= {A, B, S},

R0: S®aSc

bAB®ab

      bAd®abc

aS®bAdc 

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

Построить эквивалентную ей грамматику.

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

L={abcda, abcaba, daabc, aabdaa, cada}. Докажите, что построенная Вами грамматика действительно порождает этот язык.

7. Ответ: 

а) Язык: L={(a)nb(c)n+2; n>=0}

Эквивалентная грамматика:

    G= (Т, N, S, R), Т= {a, b, c}, N= {S},

R0: S®aSc

aS®abcc

б) L={abcda, abcaba, daabc, aabdaa, cada}.

R1: S® abcda | abcaba | daabc | aabdaa | cada; G1={{a,b,c,d},{S},S,R1}

R2: S® AB | Aaba | BA | aabBa | caB, A®abc, B®da; G2={{a,b,c,d},{S,A,B},S,R2}

Проверка:

 

 

 

8. Вопрос:

Можно ли построить дерево вывода для грамматики G из упражнения 7а ? Поясните.

8. Ответ:

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

 

9. Вопрос:

Построить вывод в  данной грамматике следующих констант: 0.253, 0.5E35, 2E-3

9.Ответ:

<константа>®<десятичное число>®<целое без знака>.<целое без знака>®<0>.<253>®0.253

<константа>®<десятичное число>E<целое>®<целое без знака>.<целое без знака>E<целое без знака>®<0>.<5>E<35>®0.5E35

<константа>®<целое>E<целое>®<целое без знака>E-<целое без знака>®<2>E-<3>®2E-3

 

 

10. Вопрос:

Постройте  вывод в данной грамматики следующей конструкции: ((АТОМ.(АТОМ.АТОМ))(АТОМ.АТОМ)

10. Ответ: 

<S>®(<S>.<S>)®((<S>.<S>).<S>)® ((<S>.<S>)(<S>.<S>))® ((<S>.(<S>.<S>))(<S>.<S>))® ((АТОМ.(АТОМ.АТОМ))(АТОМ.АТОМ))

 

 

11. Вопрос:

Постойте в данной грамматике вывод  цепочки  (2+7)*(5-(3+1)). Покажите, каким образом для данной цепочки определяются операнды в  каждой операции.

11. Ответ:

 

 

12. Вопрос:

   а) Приведите примеры правил для каждого типа грамматик.

б) Определите типы следующих  грамматик:

1) G1= {{a, b, c}, {A, B, S}, S, R}

R: S®AaB; A®Bbc; B®ab.

2) G= {{a, b, c}, {A, B, S}, S, R}

R: S®AaB; aAb®aBbcb; aB®ab.

3) G= {{a, b, c}, {A, B, S}, S, R}

R: S®aA; A®cB; B®e

в) Для каких из данных грамматик существует самый эффективный алгоритм распознавания цепочек?

12. Ответ: 

а)

0-типа:

G= (Т, N, S, R), Т= {a, b, c}, N= {S}, R: S®aFD; F®AFB; FB®bA; AF®D; D® ε

 1-типа:

G= {{a, b, c}, {A, B, S}, S, R}, R: S®AaB; aAb®aBbcb; aB®ab.

2-типа:

G1= {{a, b, c}, {A, B, S}, S, R},  R: S®AaB; A®Bbc; B®ab.

 3-типа:

G= {{a, b, c}, {A, B, S}, S, R}, R: S®aA; A®cB; B®e

б)

1) G1= {{a, b, c}, {A, B, S}, S, R}; R: S®AaB; A®Bbc; B®ab.

Грамматика 2типа: контекстно-свободная

2) G= {{a, b, c}, {A, B, S}, S, R}; R: S®AaB; aAb®aBbcb; aB®ab.

Грамматика 1типа: контекстно-зависимая

3) G= {{a, b, c}, {A, B, S}, S, R}; R: S®aA; A®cB; B®e

Грамматика 3типа: автоматная

в) Для 2-типа – существует алгоритм, и он более эффективен, а также для 3-типа – существует простой и эффективный алгоритм.

 

Глава№7

1.Вопрос:

С какой целью множество  входных символов обрабатывают двумя  автоматами?

 

1.Ответ: 

Множество входных символов обрабатываются двумя автоматами с целью уменьшения размера таблицы переходов.

 

2.Вопрос:

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

2.Ответ: 

Явный - это способ представления состояния, который заключается в запоминании номера, соответствующего текущему состоянию автомата, в некотором регистре или переменной.

Неявный - это способ, который заключается в том, что  для каждого состояния имеется  отдельная часть программы. Тот факт, что моделирующий автомат находится в заданном состоянии, «запоминается» тем, что моделирующая программа исполняет часть кода, которая принадлежит этому состоянию.

 

3.Вопрос:

Составьте таблицу переходов  данного автомата для цепочки 001101. Опишите переходы методом вектора переходов и методом списка переходов. Каким из методов это удобнее сделать?

 

 

 

 

 

 

 

3.Ответ:

Таблица переходов для цепочки 001101:

 

0

1

А

B

-

B

D

B

D

-

B




 

 

 

 

 

Вектор переходов для  состояния B:

 

0

1

B

-

B


Список переходов для  состояния B:

0

D

1

B


 

Переходы по неудаче - обработчик ошибок

0

B

  

1

  

B


 

4.Вопрос:

Построить конечный процессор, имеющий входной алфавит {О, М, С, Ы, И, А, ε} для идентификации множества {САМ, СОМ, САМИ, СОМЫ, МЫС}.

 

 

 

 

 

 

 

 

4.Ответ:

 

О

М

С

Ы

И

А

ε

ε

  

М

С

        

М

      

МЫ

      

С

СО

        

СА

  

МЫ

    

МЫС

        

СО

  

СОМ

          

СА

  

САМ

          

МЫС

            

«МЫС»

СОМ

      

СОМЫ

    

«СОМ»

САМ

        

САМИ

  

«САМ»

СОМЫ

            

«СОМЫ»

САМИ

            

«САМИ»


 Элементы таблицы в кавычках означают, что автомат идентифицировал соответствующее слово. Пустые ячейки соответствуют выходам «слово Ï множеству». Сообщение об ошибке откладывается, пока слово не просмотрено полностью. Переходы не сопровождаются никакими действиями, кроме изменения состояния.

 

5.Вопрос:

В чем главная сложность  применения метода индексов?

5.Ответ:

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

  1. Количество слов не должно быть слишком большим. Это условие, например, исключает множество переменных Си, так как содержит более миллиарда элементов.
  2. Индекс должен легко вычисляться. Это условие может исключить даже небольшие множества зарезервированных слов, для которых нет хорошего способа построения индекса.
  3. Объем множества слов фиксируется при построении, так как метод вычисления индекса неудобно изменять во время компиляции.

 

6.Вопрос:

Укажите достоинства  и недостатки метода линейного списка.

6.Ответ: 

Достоинства: Метод легко  приспособить к случаю расширяющихся множеств. Можно применять алгоритмы бинарного, логарифмического поиска, хеширования и т.п.

Недостатки: Поиск по длинному списку занимает много времени.

 

Глава№11

 

1.Вопрос:

Что понимают под точностью  программной системы?

1.Ответ: 

Точность - если в программу поступают заданные данные, то на выходе должны быть получены ожидаемые результаты.

2.Вопрос:

Какие группы факторов влияют на комфорт общения?

2.Ответ: 

  1. Социальные - психологический климат в коллективе; его отношение к компьютерам; функции, возлагаемые вычислительной системой на человека.
  2. Физическая эргономичность - читаемость дисплея, расположение клавиш на клавиатуре.
  3. Психологическая эргономичность - несоответствие функций системы психологическим процессам человека, доступность и чувственность системы

3.Вопрос: Перечислите  основные критерии оценки интерфейса

3.Ответ:

  1. Простота освоения и запоминания операций в системе.
  2. Быстрота достижения целей задачи, решаемой с помощью системы.
  3. Субъективная удовлетворенность при эксплуатации.

 

4.Вопрос:

Назовите правила ведения  разговора.

4.Ответ:

Правило 1: Участники разговора должны понимать друг друга.

Правило 2: Нельзя говорить одновременно.

Правило 3: Информация, которую сообщает, новый оратор обычно связана с тем, что говорилось ранее.

 

5.Вопрос:

Каковы задачи диалогового  процесса?

5.Ответ:

Задачи диалогового  процесса:

  1. Определение задания, которое пользователь возлагает на систему.
  2. Прием логически связанных входных данных от пользователя и размещение их в переменных соответствующего процесса в нужном формате.
  3. Вызов процесса выполнения требуемого задания.
  4. Вывод результатов обработки по окончанию процесса в подходящей для пользователя форме.

 

6.Вопрос:

Какие  бывают типы сообщений?

 

6.Ответ:

Подсказка - это выходное сообщение системы, побуждающее пользователя вводить данные.

Входные управляющие  сообщения - это данные, вводимые пользователем, которые могут вызвать процесс выполнения данного задания

Сообщение об ошибке - это сигнал диалогового процесса  о том, что невозможно дальнейшее выполнение обработки.

Сообщение о  состоянии системы - это информация для пользователя о том, что произошло или происходит в системе.

 

7.Вопрос:

 Чем отличается  подсказка от справочной информации?

7.Ответ: 

Подсказка - это выходное сообщение системы, побуждающее пользователя вводить данные.

Справочная  информация - эта информация может выводиться процессом для пояснения пользователю, что дальше делать и почему.

 

8.Вопрос:

Какие бывают типы диалоговых процессов?

8.Ответ:

Диалоговые процессы делятся на два класса:

1 - диалог, управляемый системой;

2 - диалог, управляемый пользователем.

 

9.Вопрос:

 Приведите примеры  всех вариантов подсказок.

9.Ответ:

а) Меню: любое меню программы

б) Вопрос: элемент ввода Combo Box

в) Форма: элемент ввода Edit Box

г) Запрос на ввод команды: командная строка MS-DOS

 

10.Вопрос:

Перечислите основные законы диалога.

10.Ответ:

Законы диалога:

  • диалог не вынуждает существенно подменять свои традиционные способы работы;
  • стиль сообщения должен быть разговорным, а не письменным;
  • избегать фамильярности;
  • добавление имени пользователя в запросе быстро надоедает;
  • фразы не должны требовать дополнительных пояснений;
  • допустимо использовать жаргонизмы при условии использования их в среде пользователя;
  • важен порядок запроса системой информации, необходимо придерживаться порядка, в каком пользователь обычно обрабатывает информацию;
  • не следует заставлять человека вручную обрабатывать информацию перед вводом или после вывода;
  • при размещении данных на экране необходимо соблюдать последовательность и место вывода сообщения на экран;
  • в диалоге пользователь не должен вводить незначащие цифры или символы;
  • не нужно запрашивать информацию, которая была введена ранее или которая может быть сформирована автоматически;
  • объекты следует вводить в уникальной форме;
  • не требовать от пользователя информации, которая не используется в системе;
  • ввод по умолчанию;
  • сокращения не должны быть двусмысленными и неестественными;
  • по возможности использовать идентификаторы из одной буквы или цифры;
  • выходные сообщения должны содержать только ту информацию, которая запрашивалась.

Контрольная работа по Основам трансляции 📙 Контрольная → 🆔 64855

Контрольная работа по Основам трансляции 📙 Контрольная → 🆔 64855

Контрольная работа по "Основам трансляции"