Конвертер программы с подмножества языка Си в Паскаль с использованием LL(1) метода синтаксического анализа (выражения)
Новокузнецкий филиал-институт
Кемеровский Государственный Университет
Факультет Информационных Технологий
Кафедра Автоматизированных Систем
КУРСОВАЯ РАБОТА
Дисциплина:
"Языки программирования и методы трансляции"
Тема:
"Конвертер программы с подмножества языка Си в Паскаль с использованием LL(1) метода синтаксического анализа
(выражения)"
Выполнили:
Студенты группы ИАС-00
Мардасова У. А.
Шалудько В. А.
Проверил:
Бочаров М. И.
Новокузнецк, 2002г.
ВВЕДЕНИЕ
При знакомстве с языком СИ, особенно после изучения Паскаля и Бейсика,
погружение в детали его изобразительных средств может затушевать важную
мысль: хотя на СИ можно написать практически любую прикладную программу, он
изначально для этого не предназначен. СИ является результатом эволюционного
развития языков создания системных программных средств. Если в прикладном
программировании эволюция шла от Фортрана к Алголу, Коболу, Паскалю и т.д.,
то в системном - от Ассемблеров, привязанных к архитектуре ЭВМ, к СИ, для
которого созданы трансляторы, делающие его хоть и независимым от
архитектуры, но не меняющим основного предназначения.
С помощью СИ можно сделать то, что на Паскале сделать невозможно (или
почти невозможно) - например, написать фрагмент операционной системы (или
новую операционную систему), утилиты и т.п. Так, ряд трансляторов с Паскаля
написаны на СИ; обратное невозможно представить. В то же время, не раз
отмечалось, что прикладные программы, написанные на Паскале, отличаются
большей надежностью, чем написанные на СИ; их легче читать, передавать от
одного программиста другому для совершенствования и сопровождения. Это
связано с тем, что Паскаль содержит существенно больше ограничений и
является языком более высокого уровня с сильной типизацией данных. Для
языка же, который предназначен для разработки системного программного
обеспечения, чем меньше ограничений, тем лучше; так, в СИ возможны неявные
преобразования всех базовых типов данных и указателей друг в друга, что
крайне желательно при создании системных средств, но при невнимательности
программиста приводит к ошибкам, не улавливаемым транслятором с СИ (Паскаль
же подобные недопустимые операции пресекает немедленно).
Разумеется, сказанное выше не следует абсолютизировать. Программисты,
привыкшие к СИ, успешно пишут на нем программы различных классов. Это
касается не только СИ - вспомните об экспертных системах, написанных на
Бейсике. В то же время, при массовом программировании придерживаться
"разделение труда" между языками представляется более естественным.
Широкой популярности Паскаля среди программистов способствуют
следующие причины:
. Благодаря своей компактности, удачному первоначальному описанию
Паскаль оказался достаточно лёгким для изучения.
. Язык программирования Паскаль отражает фундаментальные и наиболее важные концепции (идеи) алгоритмов в очевидной и легко воспринимаемой форме, что предоставляет программисту средства, помогающие проектировать программы.
. Язык Паскаль позволяет чётко реализовать идеи структурного программирования и структурной организации данных.
. Язык Паскаль сыграл большую роль в развитии методов аналитического доказательства правильности программ и позволил реально перейти от методов отладки программ к системам автоматической проверки правильности программ.
. Применение языка Паскаль значительно подняло "планку" надёжности разрабатываемых программ за счёт требований Паскаля к описанию используемых в программе переменных, проверки согласованности программы при компиляции без её выполнения.
. Использование в Паскале простых и гибких структур управления: ветвлений, циклов.
С другой стороны язык программирования СИ - это универсальный язык с
богатым набором операторов и компактным способом записи выражений.
Благодаря гибкости, выразительности и компактности своей конструкции СИ
завоевал наибольшую популярность в среде профессиональных программистов и
широко используется при разработке системных и прикладных программ.
Язык СИ представляет собой удачный компромисс между желанием
располагать теми возможностями, которые обычно предоставляют программисту
столь понятные и удобные языки высокого уровня, и стремлением эффективно
использовать особенности компьютера. Кроме набора средств, присущих
современным языкам программирования высокого уровня (структурность,
модульность, определяемые типы данных) в него включены средства для
программирования "почти" на уровне ассемблера (использование указателей,
побитовые операции, операции сдвига). Большой набор операторов позволяет
писать компактные и эффективные программы. Однако, такие мощные средства
требуют от программиста осторожности, аккуратности и хорошего знания языка
со всеми его преимуществами и недостатками. В отличие от языков
программирования типа Паскаль, требующих жесткой дисциплины
программирования ограничивающих свободу программиста, содействующих
устранению многих ошибок еще на стадии их трансляции, язык СИ предоставляет
программисту наибольшую свободу. Однако, ответственность за корректность
программ при этом полностью ложится на программиста.
В настоящее время имеется большое количество систем программирования
на СИ для разных типов компьютеров. Разработано много библиотек модулей,
инструментальных средств разработки и отладки, облегчающих создание новых
программ. Программы на СИ обладают высокой мобильностью, без каких либо
изменений они переносятся, транслируются и выполняются на машинах
различного типа.
В рамках учебного проекта реализована программная система, называемая
в дальнейшем конвертором, позволяющая автоматизировать процесс
преобразования программ на Паскале в программы на языке СИ. На вход
конвертора подается синтаксически правильная программа на Паскале, на
выходе его формируется эквивалентная ей программа на языке СИ.
Задача разработки конвертора относится к классу задач автоматизации
реинженеринга программ с устаревших языков на современные языки
программирования и новые платформы. Разработка конвертора для языка Паскаль
является достаточно трудоёмкой в силу особенностей синтаксиса и семантики
языка Паскаль.
Язык Паскаль не допускает использования принципов умолчаний и
сокращений, требует строгого соблюдения соответствия типов данных, в нём
жёстко регламентированы структура и место описания программных объектов.
В силу выше сказанного, даже ручной перевод программы на Паскале на
язык СИ требует от программиста приложения значительных интеллектуальных
усилий, а реализация конвертора для языка Паскаль возможна лишь при наличии
существенных временных и материальных ресурсов. Помимо синтаксических
ограничений входная программа конвертора имеет ряд чисто семантических
ограничений, связанных с реализацией собственно конвертора. Перечислим
основные из них:
. Ограниченное использование типов данных, в полном объёме поддерживаются только арифметические типы данных.
. Вложенность блоков, в которых используются одноименные объекты, не должна превышать двух уровней.
. Процедурные блоки не должны быть внутри BEGIN-блоков, вложенность процедурных блоков не ограничивается.
. Допускается использовать только одномерные массивы с открытой правой границей (динамические массивы) в качестве параметров процедурных блоков; при этом адресуются элементы массива в Паскаль программе, начиная с нулевого элемента.
. Ограниченное использование смешения различных типов данных.
Выражения в Паскале
Конструкция языка, задающая порядок выполнения действия над элементами
данных, называется выражением. Выражение состоит из операндов (operand -
элемент данных, участвующий в операции), - величин и выражений, над
которыми производится операция (константы и переменные всех типов,
обращения к функциям); круглых скобок и знаков операций. Операции
определяют действия, которые надо выполнить над операндами. Например, в
выражении (X+Y-10) X, Y и 10 - операнды; а "+" и "-" - знаки операций
сложения и вычитания.
В простейшем случае выражение может состоять из одной переменной или
константы. Круглые скобки ставятся так же, как и в обычных арифметических
выражениях для управления ассоциативностью и порядком выполнения операций.
Операции в языке Паскаль делятся на арифметические, отношения,
логические (булевские), операцию @, строковые и др. Выражения
соответственно называются арифметическими, отношения, булевскими,
строковыми и т.д. в зависимости от того, какого типа операнды и операции в
них используются.
Тип значения, вычисляемого с помощью выражения, определяется типом
его операндов и знаками выполняемых над ними операций.
Операции могут быть унарными и бинарными. В первом случае операция
относится к одному операнду и всегда записывается перед ним, во втором -
операция выражает отношение между двумя операндами и записывается между
ними.
Например, -А - унарная операция, Х+У - бинарная.
Арифметические выражения и операции.
Арифметическим называется выражение, составленное из операндов
арифметического типа и использующее только знаки арифметических операций и
круглые скобки. Порядок вычисления определяется скобками и старшинством
операций.
Арифметическое выражение порождает целое или действительное
(вещественное) значение. Наиболее простыми формами арифметических выражений
являются:
. Целая или действительная константа без знака;
. Целая или действительная переменная;
. Элемент массива целого или действительного типа;
. Функция, принимающая целое или действительное значение.
Значение переменной или элемента массива должно быть определено до их
появления в арифметическом выражении. Другие арифметические выражения
составляются из вышеперечисленных простых форм путем применения круглых
скобок и арифметических операций.
Арифметические операции выполняют арифметические действия в выражениях
над значениями операндов целочисленных и вещественных типов. Арифметические
операции языка Паскаль представлены в таблице1.
Арифметические операции
|Операция |Действие |Типы операндов |Тип результата |
|Бинарные |
|+ |Сложение |Целый |Целый |
| | |Вещественный |Вещественный |
|- |Вычитание |Целый |Целый |
| | |Вещественный |Вещественный |
|* |Умножение |Целый |Целый |
| | |Вещественный |Вещественный |
|/ |Деление |Целый |Вещественный |
| | |Вещественный |Вещественный |
|DIV |Целочисленное деление |Целый |Целый |
|MOD |Остаток от деления |Целый |Целый |
|AND |Арифметическое И |Целый |Целый |
|SHL |Сдвиг влево |Целый |Целый |
|SHR |Сдвиг вправо |Целый |Целый |
|OR |Арифметическое ИЛИ |Целый |Целый |
|XOR |Исключающая дизъюнкция |Целый |Целый |
| | | | |
|Унарные |
|+ |Сохранение знака |Целый |Целый |
| | |Вещественный |Вещественный |
|- |Отрицание знака |Целый |Целый |
| | |Вещественный |Вещественный |
|NOT |Арифметическое отрицание |Целый |Целый |
Выражения и операции отношения.
Выражением отношения называется словосочетание языка, в котором два
выражения связаны знаком операции отношения. Выражение отношения определяет
истинность или ложность результата. Операции отношения выполняют сравнение
двух операндов и определяют, истинно значение выражения или ложно.
В языке Паскаль операции отношения и рассмотренные ниже булевские
операции более важны при написании программ, чем в других языках, так как
они интенсивно используются для реализации разветвляющихся и циклических
алгоритмов. В таблице 2 приведены операции отношения, допустимые в версии
языка Паскаль для ПЭВМ.
Сравниваемые величины могут принадлежать к любому скалярному или
перечисляемому типу данных. Результат всегда имеет булевский тип и
принимает одно из двух значений: True (истина) или False (ложь).
Операции отношения.
|Операция|Название |Выражение |Результат |
|= |Равно |A=B |True, если А равно В |
| |Не равно |AB |True, если А не равно В |
|> |Больше |A>B |True, если А больше В |
|< |Меньше |A= |Больше или равно |A>=B |True, если А больше или равно В |
|=B
| B= П | П=B П(+C
B(BBB’
28. B1(BB’
44. B’(=BB’
46. B’(=П
10. B’( | | |27 | | |43 | | | | | | |
|< | | |28 | | |44 | | | | | | |
|- | | |26 | | |42 | | | | | | |
|+ | | |25 | | |41 | | | | | | |
|/ | | |24 | | |40 | | | | | | |
|* | | |23 | | |39 | | | | | | |
|% | | |22 | | |38 | | | | | | |
|-- |56 |20 |7 |15 | | | | | | | | |
|++ |57 |21 |8 |17 | | | | | | | | |
|K | | | |18 | | | | | | | | |
|I |54 |1 | |12 | | | |16 | | | | |
|) | | |37 | | |53 |13 | |19 |59 |10 | |
|( |55 |11 |9 |14 | | | | | | | | |
| |S |B |B1 |B2 |B3 |B’ |C |C1 |C2 |S’ |S1 |# |
Управляющая таблица для выражения на языке Turbo Pascal 7.0
||- | | |11 | |32 | |23 | | |19 |38 |39 |
|Or | | | | |32 | |23 | | |18 | | |
|= | | |9 | |32 | |23 | | |19 | | |
|> | | |7 | |32 | |23 | | |19 | | |
|< | | |6 | |32 | |23 | | |19 | | |
| | | |8 | |32 | |23 | | |19 | | |
|= | | |5 | |32 | |23 | | |19 | | |
|And | | | | |31 | |23 | | | | | |
|Mod | | | | |30 | |23 | | | | | |
|Div | | | | |29 | |23 | | | | | |
|/ | | | | |28 | |23 | | | | | |
|* | | | | |27 | |23 | | | | | |
|- |34 |2 | | |32 | |23 | |13 |17 | | |
|+ |33 |1 | | |32 | |23 | |12 |16 | | |
|, | | |11 | |32 | |23 | | |19 |37 | |
|I |35 |3 | |25 | |20 | | |14 | | | |
|) | | |11 | |32 | |23 |24 | |19 |38 | |
|( |36 |4 | |26 | |21 |22 | |15 | | | |
| |S |B |B’ |C |C’ |M |M’ |M1 |П |П’ |S’ |# |
Пример работы программы
Ввели выражение на языке СИ:
КУРСОВАЯ РАБОТА ПО ЯПМТ
Выберете язык: 1 - СИСИ++ 2 - Turbo Pascal 7.0
1
Напишите выражение на языке С:
(e+e==7)
Дескрипторный текст:
0 2 9 2 16 2 1
Заменить(S',В2) Сдвиг
Заменить(C,В1) Сдвиг
Заменить(В',В) Сдвиг
Заменить(В1) Сдвиг
Заменить(В',В) Сдвиг
Заменить(В1) Сдвиг
Вытолкнуть Держать
Вытолкнуть Держать
Заменить(В') Сдвиг
Вытолкнуть Держать
Вытолкнуть Держать
ДОПУСТИТЬ
Выходная лента:
55 12 25 1 31 1 37 53 53 13 53 59 60
Ввели не выражение:
КУРСОВАЯ РАБОТА ПО ЯПМТ
Выберете язык: 1 - СИСИ++ 2 - Turbo Pascal 7.0
1
Напишите выражение на языке С:
t+
Дескрипторный текст:
2 9
Заменить(S',В1) Сдвиг
Заменить(В',В) Сдвиг
Отвергнуть
Выходная лента:
54 25 0
Ввели выражение на Паскале:
КУРСОВАЯ РАБОТА ПО ЯПМТ
Выберете язык: 1 - СИСИ++ 2 - Turbo Pascal 7.0
2
Напишите выражение на языке TP:
ww=s+1
Дескрипторный текст:
2 11 2 4 2
Заменить(В'П'C'M') Сдвиг
Вытолкнуть Держать
Вытолкнуть Держать
Вытолкнуть Держать
Заменить(П) Сдвиг
Заменить(П'C'M') Сдвиг
Вытолкнуть Держать
Вытолкнуть Держать
Заменить(П'C) Сдвиг
Заменить(C'M') Сдвиг
Вытолкнуть Держать
Вытолкнуть Держать
Вытолкнуть Держать
ДОПУСТИТЬ
Выходная лента:
3 23 32 19 5 14 23 32 16 25 23 32 19 39
Ввели не выражение
КУРСОВАЯ РАБОТА ПО ЯПМТ
Выберете язык: 1 - СИСИ++ 2 - Turbo Pascal 7.0
2
Напишите выражение на языке TP:
f=s+
Дескрипторный текст:
2 11 2 4
Заменить(В'П'C'M') Сдвиг
Вытолкнуть Держать
Вытолкнуть Держать
Вытолкнуть Держать
Заменить(П) Сдвиг
Заменить(П'C'M') Сдвиг
Вытолкнуть Держать
Вытолкнуть Держать
Заменить(П'C) Сдвиг
Отвергнуть
Выходная лента:
3 23 32 19 5 14 23 32 16 0
Листинг программы:
#include
#include
#define n 100
#define t 17
#define m 53
#define g 11
char s1[n],s[n],a[n];
int j=0,h,vl[n],y=0;
/*---------------------------ВВОД ВЫРАЖЕНИЯ------------------------------*/
int vvod()
{
int i;
printf("tttКУРСОВАЯ РАБОТА ПО ЯПМТn");
printf("Выберете язык: 1 - СИСИ++ 2 - Turbo Pascal 7.0n");
scanf("%d",&y);
if(y==1)
printf("Напишите выражение на языке С:n");
{for(i=0;i