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

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

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

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

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

 

 

 

 

 

 

 

 

 

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

 

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

 

 

 

 

 

 

 

 

 

 

 

Выполнил:

 

 

 

 

 

 

 

Глава № 1

 

1. Вопрос:

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

1. Ответ: 

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

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

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

 

2. Вопрос:

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

2.  Ответ: 

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

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

 

3. Вопрос:

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

3. Ответ:

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

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

1) Входные

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

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

4) Выходные

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

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

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

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

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

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

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

2) Пассивные

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

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

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

3) Голосовые

4) Смешанные

 

4. Вопрос:

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

4. Ответ:

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

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

 

Глава № 2

 

1. Вопрос: 

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

1. Ответ: 

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

 

2. Вопрос:

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

2. Ответ:

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

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

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

 

3. Вопрос:

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

3. Ответ: 

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

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

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

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

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

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

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

 

4. Вопрос:

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

4. Ответ: 

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

 

5. Вопрос:

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

5. Ответ:

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

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

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

 

6. Вопрос:

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

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. Ответ: 

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

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

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

 

2. Вопрос:

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

2. Ответ:

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

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

 

3. Вопрос:

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

3. Ответ:

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

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

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

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

 

4. Вопрос:

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

4. Ответ:

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

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

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

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

 

5. Вопрос:

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

5. Ответ:

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

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

 

6. Вопрос:

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

6. Ответ:

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

 

7. Вопрос:

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

7. Ответ:

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

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

 

 

 

 

Глава №4

 

1. Вопрос:

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

1. Ответ:

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

 

2. Вопрос:

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

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

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

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

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

2. Ответ:

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

Правила:

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

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

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

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

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

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

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

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

 

3. Вопрос:

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

3. Ответ:

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

 

4. Вопрос:

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

4. Ответ:

G₀=(T₀  , N₀ ,  S , R₀)

T₀={a,b}

N₀={A,B,S}

R₀:

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)ⁿb; n>=1}

S®aS®aaS®abA®aab

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

 

6. Вопрос:

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

6. Ответ:

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