Конец

Выход

Выход

Выход

Язык = “Начало” Множ “;” . . . Множ Оператор . . . оператор “Конец”.

Язык

Вход

А

Начало

Опе-

ратор

Множ.

Выход

А

3) Синтаксические ошибки (их суть, пути избавления от них). Нисходящий и восходящий распознаватели. (Примеры). Слева-направо. С возвратом, без возвратов. (Примеры: обработка переменных с возвратом и без возвратов; обработка функции с возвратом и без возвратов). Метод рекурсивного спуска (вариант появления новых ветвей в дереве разбора). Рекурсия: прямая и косвенная. Примеры. Многопроходность.

Прямая рекурсия:

S = S + X

Косвенная рекурсия:

A = B + C

C = E + 1

E = 15 + A

Лекция 3. Генератор кода.

Общий вид транслятора и место генератора кода в нем. Отсутствие анализирующей части. Генерирующая часть – формирование текстов на выходном языке. Основные принципы построения. Обоснование отсутствия блока оптимизации. Представление объектного кода и последующая работа с ним. Реализация генерирующей части транслятора. Общие положения и с учетом синтаксически управляемого перевода. Размещение соответствующих программных блоков на дереве разбора.

Лекция 4. Методы программирования (I).

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

2) Три этапа программирования: написание программы, отладка и тестирование. Отлаженный оператор. Проблемы этапов отладки и тестирования. Значение формализации для уменьшения времени отладки и тестирования.

Постановка

задачи

Программа

Алгоритм

Блок схема

1. Методический пример

а) Постановка задачи: Написать программу вычисляющую сумму чисел.

Вход: последовательность чисел (X). Выход: сумма чисел входной последовательности.

б) Описание поставленной задачи в виде алгоритма:

S = 0

S = S + X _i

в) Построение блок-схемы по приведенному выше алгоритму:

Вход

S = 0

I = 1, N

S = S + X_i

Печать S

Выход

г) Написание текста программы на алгоритмическом языке (С#) по приведенной выше блок-схеме:

using System;

class MainClass

{

public static void Main(string[] args)

{

double S = 0;

foreach (string inputToken in args)

{

double Xi = 0;

if (double.TryParse(inputToken, out Xi))

{

S = S + Xi;

}

else

{

Console.WriteLine(

"Значение '{0}' – не число!", inputToken);

return;

}

}

Console.WriteLine("S = {0}", S);

}

}

Три этапа программирования:

5%

• Написание программы –

5 % общего времени

- Отладка и тестирование –

95 % общего времени

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

Число операторов в программе

Число отлаженных операторов = -------------------------------------------------

Время создания программы (в днях).

Например, если программа в 300 операторов сделана (написана, отлажена и оттестирована) за 60 дней, это означает, что программист пишет 5 отлаженных операторов в день.

Нет никакого смысла пытаться сократить время собственно написания программы (ввиду того, что этот этап – только 5 % общего времени создания программы).

Реально можно (и нужно) сократить этап отладки и тестирования. Для этого требуется очень серьезно относиться к формализации описания процесса программирования (ввод еще двух этапов: описание алгоритма; создание блок-схемы алгоритма).

3) Графическое описание цикла (различные варианты). Графическое описание цикла, близкое к программированию. Перевод конструкций б/с в операторы инструментального языка программирования.

Гост:

Вариант приближенный к программированию:

Лекция 5. Методы программирования (II).

1) БНФ (терминалы, нетерминалы, специальные символы). Терминалы – основа создаваемого проблемно-ориентированного языка программирования, их выбор (о необходимости отличия терминалов друг от друга, примеры). Нетерминалы – вспомогательный инструмент формального описания языка (о необходимости также создавать данные элементы максимально отличными друг от друга). Специальные символы – их соответствие основным инструментам программирования. Методический пример описания проблемно-ориентированного языка программирования с помощью БНФ.

Терминалы – слова входного языка. Терминалы являются основой создаваемого проблемно-ориентированного языка программирования.

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

Специальные символы - соответствуют основным инструментам программирования:

«...» - повторение данной конструкции.

«;» - разделитель

«!» - разделитель вариантов

«[», «]» - группировка (ветвление)

«</ />» - может быть, может не быть.

При выборе имен терминалов / нетерминалов важным фактором является необходимость задавать как можно более уникальные имена, а так же следить за соответствием данного имени - сути его носителя. Соблюденные данных мер поможет сделать БНФ вашего проблемно-ориентированного языка удобной для восприятия, а так же поможет избежать ошибок.

2) Приближение БНФ к программированию. Необходимость этих действий. Описание циклической операции в “классической” БНФ – в виде рекурсии. Неудобство использования данного средства при переходе собственного к программированию. Введение описания циклической операции и замена рекурсии в БНФ на традиционный вариант описания итерации, соответствующий общим принципам программирования.

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

В «классической» БНФ циклическая операция задаётся в виде рекурсии:

Операторы = Опер </Операторы/>

Такой подход очень не удобен при переходе собственно к программирова-нию. Для приближения БНФ к программированию заменяем рекурсию на традиционный вариант описания итерации, соответствующий общим принципам программирования:

Оператор = Опер ... Опер.

Приближением является введение в БНФ спецсимвола «...».

Пример:

Язык = “Вegin” Звено...Звено Опр “;” ... Опр “End”

Звено = [“First” ! “Second”] Вещ “,” ... Вещ

Опр = </ Метка”:” /> Переменная “=” Цел

Вещ = Цел “.” Цел

Метка = Цел

Цел = Цифра...Цифра

Переменная = Б</Символ...Символ/>

Символ = Б!Ц

Буква = “A” ! “B” ! ... ! “Z”

Цифра = “0” ! “1” ! ... ! “9”

3) Однозначность описания БНФ (два правила): один корневой нетерминал; все нетерминалы, в конечном счете – путем подстановки, выражаются через терминалы. Представление описания БНФ в виде дерева разбора, обеспечивающий однозначность восприятия предлагаемого проблемно-ориентированного языка программирования. И, соответственно, невозможность однозначного трактования описаний на предлагаемом языке, если эти два условия не выполняются.

Язык задан с помощью БНФ однозначно если при составлении БНФ соблюдается два правила:

Правило 1: Все не терминалы в конечном счете, путем подстановки, выражаются через терминалы.

Правило 2: Все не терминалы стоят как справа так и слева. За исключением одного корневого не терминала.

Лекция 6. Арифметическое выражение.

1) Последовательность выполнения арифметических операций. Разбиение текста аддитивными операциями, мультипликативными операциями, стенными операциями, логическими операциями. Несоответствие математической записи арифметических операций и последовательности их реализации в программном обеспечении. Примеры. Проблемы. связанные с реализацией логических операций. Реализация в обратном порядке. Примеры.

Пример :

Оператор это переменная '=' правая часть. Правая часть это целое и вещественные числа соединены аддитивными, мультипликативными и степенными операциями. Вещественное – два целых через точку. Переменная – две буквы. Затем три цифры. Латинско-русский алфавит, шестнадцатеричная арифметика.

Оператор = переменная «=» правая часть.

Правая часть = </ « - » /> Блок Зн1... Блок

Зн1 = «+» ! «-»

Блок = Часть Зн2 ... Часть

Зн2 = «*» ! «/»

Часть = Частица «^» ... Частица

Частица = Цел ! Вещ

Вещественное = цел «.» цел

Цел = Цифра...Цифра

Переменная = Буква Буква Цифра Цифра Цифра

Буква = “A” ! “B” ! ... ! “Я”...'A'...'B' ... 'C' ... 'W'

Цифра = “0” ! “1” ! ... ! “9”!...! «A» ! ... ! «F»

2) Реализация функций. Место данной конструкции среди арифметических операций. Примеры. Обработка функции при проходе по тексту с возвратом и без возвратов. Положительные и отрицательные стороны. Стандартный набор функций в проблемно-ориентированном языке программирования. Реализация функций при наличии и отсутствии скобок.

3) Реализация скобок. Место данной конструкции среди арифметических операций. Примеры. Скобки с любой глубиной вложенности и с фиксированным числом скобок. Значение данного элемента при реализации метода рекурсивного спуска.

Лекция 7. Другие алгоритмы. Диагностика транслятора.

1) Диагностика транслятора. Основная ценность транслирующего средства – нахождение любой ошибки в тексте на входном языке. Для этого (в качестве “ловушки”) используется дерево разбора, благодаря которому исходный текст расчленяется на отдельные составляющие. Ветку ИНАЧЕ блоков, реализующих ветвление, желательно использовать для указания ошибок. Это делается и для того, чтобы ошибка не раскрывала на достаточно большом расстоянии от места ошибки.

Адекватное указание ошибки. Диагностические сообщения должны нести в небе конкретный характер. Не приветствуются расплывчатые сообщения типа CINTAXIS, часто используемые в промышленных трансляторах. В тех случаях, когда существует некоторая неоднозначность (можно указать два или три варианта ошибки), необходимо перечислять все варианты.

Алгоритм работы транслятора до первой ошибки. Традиционный вариант диагностики (все ошибки) имеет существенные недостатки – так называемые наведенные ошибки. Например: при неправильном описании переменной в заголовке программы, все вхождения этой переменной в основной части программы будут диагностироваться ошибочными.

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

Алгоритм работы до первой ошибки вполне приемлем при реализации проблемно-ориентированного языка программирования. Упор делается на точное диагностирование ошибки.

Вторым обязательным условием является - указание места ошибки. Надо выделять место – где произошла ошибка.

Можно на это место устанавливать курсор. Можно делать и по-другому: разрывать текст на две части и выдавать 1) первую часть текста (до ошибки), 2) сообщение об ошибке, 3) вторую часть текста (после ошибки).

Установление признака N в первой программе.

Язык

Вход

N = 0

“Начало”

. . .

Множество

Вход

“Перв.”

“Втор.”

Ветвь “Иначе”

“Второе”

“Первое”

1) Сообщение об ошибке

2) Выход из программы

Вещ.

Выход

Вход

Правая часть

Правая-часть = 0

“-“

Вставить “+”

“+,-“

Блок

Блок

N=1

N=1

да

вых вых

Правая-часть = Правая-часть - Блок

Правая-часть = Правая-часть + Блок

Выход

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

Лекция 8. Сочетание анализирующей и генерирующей частей трансляторов.

1) Дерево разбора – основа построения транслирующего средства.

Язык начинается словом “начало”, потом идут множества через «;» потом идут операторы россыпью, потом слово “конец”. Множество, это – слово “анализ” и набор комплексных чисел россыпью, либо слово “синтез”, и потом набор целых чисел через запятую. Оператор – сначала метки (их может быть несколько) потом «:», потом переменная, знак «=», и одно вещественное число. Метка целочисленная. Переменная первая буква потом цифры (цифр может быть сколько угодно; а может их и совсем не быть). Комплексное число это два вещественных числа через запятую. Вещественное – два целых через точку. Русский алфавит, шестнадцатеричная арифметика.

Язык = «Начало» Множ “;” ... Множ Опер ... Опер «Конец»

Множество = «Анализ» Комплексное...Комплексное ! «Синтез» Цел «,» ... Цел

Оператор = Метка...Метка «:» Переменная «=» Вещ

Метка = Цел

Переменная = Б </Цифра....Цифра/>

Комплексное = Вещ «,» Вещ

Вещественное = Цел «.» Цел

Цел = Цифра...Цифра

Буква = “A” ! “B” ! ... ! “Я”

Цифра = “0” ! “1

” ! ... ! “9”!...! «A» ! ... ! «F»

2) Общие требования при построении транслятора.

Назначение транслирующего средства. Его место в программном обеспечении. Требования к нему, разработка проблемно-ориентированного языка программирования, позволяющего работать с данным средством непрограммисту. Требования, предъявляемые к разрабатываемому языку. Транслятор должен принять на входе задание. Если есть ошибка, то сделать сообщение об этом, если нет – выполнить генерирующую часть и выдать результаты. Потом вновь быть готовым к принятию очередного задания.

Значение транслирующей части для любого проблемно-ориентированного программного обеспечения.

Качество транслирующей части – одна из основных составляющих привлекательности программного продукта.

Тщательность составления входного проблемно-ориентированного языка (в целом) и грамотный выбор терминальных символов (в частности).

Анализирующая часть транслятора. Исключение комментария из исходного текста. Обеспечение поиска всех ошибок (диагностика). Указание типа (вида) ошибки и места ошибки в тексте.

Реализация диагностического аппарата с работой до первой ошибки. Необходимость как можно более точно указывать место ошибки и тип ошибки.

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

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