Какие типы ошибок должна распознавать анализирующая часть транслятора

1. Первый кусок

1. Назначение трансляторов. Их роль при
   создании ПО

1. Классификация

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

Интерпретатор – на входе: язык
высокого уровня, на выходе: машинный
код ( по операторно).

Перекодировщик – перевод с 1го
языка высокого уровня на другой.

Ретранслятор — с
низкого на язык высокого уровня.

1. Аналитическая и генерирующая части
   

Аналитическая часть – поиск
ошибок.(лексические и синтаксические
, семантические)

Генерирующая часть — выдача результата.

1. Многопроцессорные трансляторы

Параллельное выполнение нескольких
процессов

1. Второй кусок

1. Лексический
   анализатор

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

1. Вход и выход
   лексического анализатора. Анализирующая
   и генерирующая части

На входе – тексты
на входном языке.

На выходе – лексем
(последовательность допустимых символов).

Анализирующая
часть – поиск ошибок.

Генерирующая часть
– создание лексем.

1. Лексические
   ошибки

Три вила ошибок:

Лексические
– ошибки набивания текста.

Синтаксические
– ошибки данного языка программирования.

Семантические –
смысловые, ошибки в алгоритме.

Анализирующая
часть:

Лексические ошибки
– ошибки в словах.

Неверная буква.

Пропущена буква.

Лишняя буква.

Неправильно
поставлены местами буквы.

Генерирующая
часть:

В
лексемах отсутствуют комментарии.

Лексемы одинаковой
длины.

Лексемы несут
числовую информацию.

1. Третий кусок

1. Синтаксический анализатор

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

1. Вход и выход синтаксического
   анализатора. Анализирующая и генерирующая
   части

На входе – лексемы.

На выходе – промежуточные таблицы.

Анализирующая часть – поиск ошибок.

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

1. Синтаксический управляемый перевод.
   Свободная грамматика. Синтаксические
   ошибки

Синтаксический управляемый перевод –
соответствие между записью в БНФ и ее
графическим отображением.

Язык – “Begin” Множество
Оператор “end”

Множество – множ…множ

Оператор – опер…опер

Язык – “Begin”
Множ…множ Опер…опер “end”

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

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

Синтаксические – ошибки данного языка
программирования.

Третий кусок
часть 2

1. Восходящие и
   нисходящие распознаватели. Распознавание
   с возвратом и без возврата. Метод
   рекурсивного спуска.

Распознаватели
– распознает поток информации.

Нисходящие
распознаватели – сверху вниз по дереву
разбора.

Восходящие
распознаватели – снизу вверх по дереву
разбора.

Нисходящие
распознаватели более логичны.

Распознавание
происходит слева направо.

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

Распознавание без
возврата – к заголовку программы
создается таблица переменных. В процессе
прохода по программе , когда встречается
переменная, мы обращаемся к таблице.

Метод рекурсивного
спуска — это
один из методов определения принадлежности
входной строки к некоторому формальному
языку, описанному контекстно-свободной
грамматикой. Это класс алгоритмов
грамматического анализа, где правила
формальной грамматики раскрываются,
начиная со стартового символа, до
получения требуемой последовательности
лексем.

1. Многопрограммность-
   количество проходов по входному тексту.
   1) Иду
   по входной
   строке, на выходе сразу же формирую
   выходную строку.2) Иду по входной строке
   – формирую лексемы, выбрасывая
   комментарии, или для начала выброшу
   комментарии, затем сформирую лексемы.

1. Четвертый кусок

1. Генератор кода.
   Назначение. Способы реализации. Вход
   и выход. Анализирующая и генерирующая
   части.

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

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

На входе –
промежуточные таблицы (подаётся дерево
разбора или абстрактное синтаксическое
дерево)

На выходе – текст
на выходном языке.

Анализирующая
часть отсутствует.

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

Пятый кусок

1. Четыре этапа создания ПО.

1. Методы структурного программирования

Принципы:

1. Писать больше комментариев.

2. Не использовать goto.

3. Использовать три различных блока:

а) Функция

б) Блок ветвления
(if, then, else)

с) Цикл (for,
while, return-until)

1. Три этапа программирования. Отлаженный
   оператор. Графическое описание цикла.

Этапы программирования:

1. Написание программы.

2. Откладка.

3. Тестирование

Отлаженный
оператор – полностью рабочий оператор.
Программист способен написать 5 отлаженных
операторов в день.

Цикл с предусловием (0…∞)

Цикл с постусловием (1…∞).

1. Перевод конструкции в блок-схемы и в
   операторы языков программирования.

Блок-схема	Pascal	Си
	begin	{
	End	}
	Var	В любом месте
	If условие then инструкция1 else инструкция2	If условие then инструкция1 else инструкция2
	Procedure имя(), function имя()	Void имя() {}
	For i=1 to n do	For {i=1;i=<n;i++}
	While (условие) begin инструкция1 end	While(условие) {инструкция}
	Return инструкция until (условие)	Do {инструкция} while (условие)
	Writeln(“Hello”)	Cin>>”Hello”

1. БНФ. Терминалы. Нетерминалы. Специальные
   символы. Приближение БНФ к
   программированию. Перевод БНФ в блок
   схемы. Однозначность в БНФ – два правила.

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

БНФ-конструкция определяет конечное
число символов (нетерминалов). Кроме
того, она определяет правила замены
символа на какую-то последовательность
букв (терминалов) и символов.

Перевод в блок-схемы (см. 3.3).

Однозначность БНФ:

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

2. Все нетерминалы встречаются как слева,
   так и справа, кроме корней терминала.

1. Шестой кусок

1. Разбор арифметических выражений.
   Алгоритмы реализации функции.

1. Алгоритм работы транслятора до первой
   ошибки.

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

2. Выход из программы и из объемлющих.

1. Алгоритм, реализующий скобки в
   арифметических выражениях.

Cypma4

В
формате печати выбрать 4 страницы на
одном листе печатать с двух сторон

Шпоры
лучше класть под листок

Сдавайте
все вовремя и будет вам счастье

8

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

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

•специфики управления используемыми техническими средствами,

•операционной системы,

•среды и языка программирования,

•реализуемых процессов,

•природы и специфики различных ошибок,

•методик отладки и соответствующих программных средств. 

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

Вцелом сложность отладки обусловлена следующими причинами:

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

•психологически дискомфортна, так как необходимо искать собственные ошибки и, как правило, в условиях ограниченного времени;

•возможно взаимовлияние ошибок в разных частях программы, например, за счет затирания области памяти одного модуля другим из-за ошибок адресации;

•отсутствуют четко сформулированные методики отладки.

Всоответствии с этапом обработки, на котором проявляются ошибки, различают (рис. 10.1):

    синтаксические ошибки — ошибки, фиксируемые компилятором (транслятором, интерпретатором) при выполнении синтаксического и частично семантического анализа программы; ошибки компоновки — ошибки, обнаруженные компоновщиком (редактором связей) при объединении модулей программы;

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

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

Следует иметь в виду, что чем лучше формализованы правила синтаксиса языка, тем больше ошибок из общего количества может обнаружить компилятор и, соответственно, меньше ошибок будет обнаруживаться на следующих этапах. В связи с этим говорят о языках программирования с защищенным синтаксисом и с незащищенным синтаксисом. К первым, безусловно, можно отнести Pascal, имеющий очень простой и четко определенный синтаксис, хорошо проверяемый при компиляции программы, ко вторым — Си со всеми его модификациями. Чего стоит хотя бы возможность выполнения присваивания в условном операторе в Си, например:

if (c = n) x = 0; /* в данном случае не проверятся равенство с и n, а выполняется присваивание с значения n, после чего результат операции сравнивается с нулем, если программист хотел выполнить не присваивание, а сравнение, то эта ошибка будет обнаружена только на этапе выполнения при получении результатов, отличающихся от ожидаемых */ 

Ошибки компоновки. Ошибки компоновки, как следует из названия, связаны с проблемами,

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

    Ошибки выполнения. К самой непредсказуемой группе относятся ошибки выполнения. Прежде всего они могут иметь разную природу, и соответственно по-разному проявляться. Часть ошибок обнаруживается и документируется операционной системой. Выделяют четыре способа проявления таких ошибок:

• появление сообщения об ошибке, зафиксированной схемами контроля выполнения машинных команд, например, переполнении разрядной сетки, ситуации «деление на ноль», нарушении адресации и т. п.;

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

•«зависание» компьютера, как простое, когда удается завершить программу без перезагрузки операционной системы, так и «тяжелое», когда для продолжения работы необходима перезагрузка;

•несовпадение полученных результатов с ожидаемыми.

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

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

•неверное определение исходных данных,

•логические ошибки,

•накопление погрешностей результатов вычислений (рис. 10.2).

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

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

Кпоследней группе относят:

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

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

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

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

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

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

опосредованного проявления ошибок;

возможности взаимовлияния ошибок;

возможности получения внешне одинаковых проявлений разных ошибок;

отсутствия повторяемости проявлений некоторых ошибок от запуска к запуску – так называемые стохастические ошибки;

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

написания отдельных частей программы разными программистами.

Методы отладки программного обеспечения

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

ручного тестирования;

индукции;

дедукции;

обратного прослеживания.

Метод ручного тестирования. Это — самый простой и естественный способ данной группы. При обнаружении ошибки необходимо выполнить тестируемую программу вручную, используя тестовый набор, при работе с которым была обнаружена ошибка.

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

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

Метод индукции. Метод основан на тщательном анализе симптомов ошибки, которые могут проявляться как неверные результаты вычислений или как сообщение об ошибке. Если компьютер просто «зависает», то фрагмент проявления ошибки вычисляют, исходя из последних полученных результатов и действий пользователя. Полученную таким образом информацию организуют и тщательно изучают, просматривая соответствующий фрагмент программы. В результате этих действий выдвигают гипотезы об ошибках, каждую из которых проверяют. Если гипотеза верна, то детализируют информацию об ошибке, иначе — выдвигают другую гипотезу. Последовательность выполнения отладки методом индукции показана на рис. 10.3 в виде схемы алгоритма.

Самый ответственный этап — выявление симптомов ошибки. Организуя данные об ошибке, целесообразно записать все, что известно о ее проявлениях, причем фиксируют, как ситуации, в которых фрагмент с ошибкой выполняется нормально, так и ситуации, в которых ошибка проявляется. Если в результате изучения данных никаких гипотез не появляется, то необходима дополнительная информация об ошибке. Дополнительную информацию можно получить, например, в результате выполнения схожих тестов.

В процессе доказательства пытаются выяснить, все ли проявления ошибки объясняет данная гипотеза, если не все, то либо гипотеза не верна, либо ошибок несколько.

Метод дедукции. По методу дедукции вначале формируют множество причин, которые могли бы вызвать данное проявление ошибки. Затем анализируя причины, исключают те, которые противоречат имеющимся данным. Если все причины исключены, то следует выполнить дополнительное тестирование исследуемого фрагмента. В противном случае наиболее вероятную гипотезу пытаются доказать. Если гипотеза объясняет полученные признаки ошибки, то ошибка найдена, иначе — проверяют следующую причину (рис. 10.4).

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