Прямой лексический анализ - требуется найти одну из многих лексем. Моделируется множеством работающих параллельно конечных автоматов или одним конечным преобразователем, моделирующим много конечных автоматов и выдающий сигнал о том, какой из них распознал цепочку.
Таким образом, входом лексического блока является цепочка символов, выходом - цепочка лексем и таблица имен.
7.5.2. Модель синтаксического анализатора
Синтаксический блок моделируется МП-преобразователем. Выходом синтаксического блока является синтаксическое дерево. Фактический выход - последовательность команд, необходимых для того, чтобы строить промежуточную программу. Представление промежуточной программы, вырабатываемой синтаксическим блоком может быть:
- постфиксная польская запись;
- префиксная польская запись;
- связанные списочные структуры, представляющие деревья;
- многоадресный код с явно именуемым результатом;
- многоадресный код с неявно именуемым результатом.
7.5.3. Модель генератора команд
Генератор кода выполняет отображение промежуточной программы в цепочку машинных команд. Это функция, определенная на синтаксическом дереве и на информации, содержащейся в таблице имен. Кроме того, генератор кода должен решить задачи распределения памяти и оптимизации (улучшения) кода. Генератор кода моделируется МП-преобразователем.
1. Барздшь Г.Я., Булюнкое М.А. Смешанные вычисления и трансляция: линеаризация и декомпозиция транслятора / Препринт 791, Новосибирск, 1988.
2. Пастор Франтишек, Абстрактная модель компилятора / Автореф. ... канц.физ.-мат.наук. Киев,!981 (спец.01.01.09).
3. В.Н.Редько II Программирование, Ne 3, 1979, с.3-13.
4. В.Н.Редъко //' Программирование, Ne 5, 1978. с.3-24.
5. Льюис ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов -М.:Мир, 1979.
6. Ахо А; Ульман Дж. Теория синтаксического анализа, перевода и компиляции / в 2-х томах. -М.:Мир, 1978.
7. Хопгуд ф. Методы компиляции. - М.:Мир, 1972.
8. Хантер Р. Проектирование и конструирование компиляторов. - М.: Фин. и стат., 1984.
9. Серебряков В.А. Лекции по конструированию компиляторов / Рос. АН ВЦ.- М.:ВЦ РАН, 1994.
В данном разделе рассматриваются методы выявления программных закладок в текстах программ, при условии, что в исходном алгоритме, по которому написана данная программа, ошибок нет. Во всех рассмотренных методах общим является построение транслятора для языка высокого уровня, на котором написана программа. Исходный алгоритм и соответствующая ему программа переводятся в некоторую одинаковую форму представления, после чего сравниваются. Так как считается, что в алгоритме нет ошибок, то все найденные несоответствия являются ошибками либо в программе, либо в трансляторе. Для упрощения задачи считается, что транслятор не вносит искажений.
Пусть имеется исходный алгоритм A некоторого вычислительного процесса, несодержащий ошибок и представленный в форме ФA , и программа Р, реализующая алгоритм А , представленная в форме ФP и возможно содержащая ошибки вследствие программных закладок. Требуется проверить корректность программы Р, т.е. определить, соответствует ли программа Р алгоритму А.
Поставленная задача будет решаться следующим образом. Исходный алгоритм А и программа Р будут преобразовываться к одной и той же форме представления ФE. Далее после их сравнения будет сделан вывод о соответствии программы Р исходному алгоритму А. Таким образом, решение задачи можно представить в виде схемы, изображенной на рис.8.1.
Будем считать, что алгоритм будет преобразовываться к форме ФE программистом, а программа - транслятором.
Основная идея метода состоит в использовании синтаксического дерева, получаемого на выходе синтаксического блока транслятора не только для проверки соответствия программы правилам некоторого языка программирования, но и для проверки соответствия программы исходному алгоритму.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.