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

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

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

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

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

 

 

   

 

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

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

 

 

  

 

 

   

Выполнил: 

 

 

  

 

 

  

 

 

  

 

 

 

 

 

 

Глава № 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.  Ответ: L={авс, аавс, васс} Это пример конечного языка, состоящего из трех цепочек.

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.  Ответ: Выучи лекции, если хочешь сдать экзамен, ответь на билет и получи отличную оценку.

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

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

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

7.  Вопрос: а) Дана грамматика G= (Т, N, S, R), Т= {a, b, c, d}, N= {A, B, S},

R₀: S→aSc

bAB→ab

bAd→abc

aS→bAdc 

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

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

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

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

7.  Ответ: а) Язык: L={(a)ⁿb(c)ⁿ⁺²; n>=0}

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

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