Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка та реалізація компонент системного програмного забезпечення
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра електронні обчислювальні машини
Інформація про роботу
Рік:
2005
Тип роботи:
Курсовий проект
Предмет:
Інші
Група:
КІ34
Частина тексту файла (без зображень, графіків і формул):
Національний університет “Львівська Політехніка”
Кафедра “Електронні обчислювальні машини”
КУРСОВИЙ ПРОЕКТ
на тему: „Розробка та реалізація компонент системного
програмного забезпечення”
Львів 2005
Анотація
В курсовому проекті розроблено компілятор з простої мови програмування .
Компілятор розроблений в середовищі програмування Borland C/C++ на мові С, та поданий у пояснювальній записці, а також в електронному варіанті. В пояснювальній записці подано огляд існуючих методів розробки компіляторів, детальний опис мови, а також описано процес розробки програми компілятора на рівні блок-схем ексту програми. В додатку міститься текст компілятора, а також результати тестування програми.
Завдання на курсовий проект
Розробити транслятор заданої вхідної мови програмування, до якої висуваються наступні базові вимоги :
Кожна програма починається зі слова start і закінчується словом stop. Все що до start і після stop не аналізується. Наприклад як у мові Паскаль begin end.
Програма має надавати можливість працювати зі змінними. Змінні перед використанням мають бути попередньо оголошені за наступним форматом: “тип даних” “змінна1”, “змінна2”; Наприклад int x,y;
Присвоєння до змінних виконується оператором присвоєння :=. Наприклад x:=y+5;
Програма має надавати можливість працювати з константами. Константи ініціюються наступним чином: “константа” = “число;”. Наприклад а=3;
Ввід даних зі стандартного вводу відбувається оператором input(), а вивід оператором output(). Наприклад input(x); output (y).
Програма має працювати з типом даних char, int.
Програма має виконувати операції ,&,~,>
Програма має надавати можливість використовувати оператор case (Pascal)
Програма має надавати можливість працювати з масивами.
Вихідною мовою трансляції є мова С.
Математичний вираз має бути розібраний в залежності від пріоритету виконання та розписаний викликом власних С функцій.
Цільова мова компілятора: ANSI C. Для отримання виконавчого файлу на виході розробленого компілятора скористатися програмою bcc.exe. Мова розробки компілятора: ANSI C. Реалізувати інтерфейс командного рядка. На вхід розробленого компілятора має подаватися текстовий файл, написаний на заданій мові програмування. На виході розробленого компілятора мають з’являтися чотири файли: файл з повідомленнями про помилки (або про їх відсутність), файл на мові СІ, об’єктний та виконавчий файли.
Назва вхідної мови програмування утворюється від першої букви у прізвищі студента та номеру його варіанту. Саме таке розширення повинні мати текстові файли, написані на цій мові програмування.
Зміст
Анотація……………………………………………………………………….……………..2
Завдання на курсовий проект....................................................................................3
Формальний опис вхідної мови програмування.......................................................5
Розробка компілятора вхідної мови програмування...............................................7
Формальний опис вхідної мови програмування.................................................7
2.1.1Повне дерево граматичного розбору………………………….………………….9
Розробка лексичного аналізатора....................................................................11
Розробка синтаксичного аналізатора...............................................................13
Розробка генератора коду.................................................................................15
Відладка та тестування компілятора......................................................................16
Висновки...................................................................................................................17
Література.................................................................................................................18
Додаток А. Текст програми………………………………………………..……..................19
Додаток Б. Тестові програми ........................................................................................31
Аналітичний розділ
Компілятор – програма, яка зчитує текст програми, що написана на одній мові –вхідній, і транслює (переводить) його в еквівалентний текст на іншій мові –
цільовій. Процес компіляціі складається з двох частин: аналізу та синтезу.
Аналіз – це розбиття вхідної програми на складові частини та створення її проміжного представлення. Синтез – це процес конструювання потрібної цільової програми із проміжного представлення. Стосовно компіляції аналіз поділяють на три фази – лінійного, ієрархічного та семантичного аналізу.
Під час лінійного аналізу потік символів вхідної програми зчитується зліва направо і групується у токени (token) – послідовності символів із певним спільним значенням. Тобто токеном є сукупність символів із певним логічним значенням. Сукупність символів, що формує токен – це лексема.
Фаза ієрархічного аналізу передбачає процес, коли символи чи токени ієрархічно групуються у вкладені конструкції із спільним значенням.
Семантичний аналіз – перевіряє коректність спільного розташування компонентів програми. Лінійний аналіз – це, власне, і є лексичний аналіз або сканування. Лексичний аналізатор – це, відповідно, програма, котра втілює принципи такого лінійного аналізу. Для прикладу розглянемо таку конструкцію:
point = init + var * 23
Отримавши таку інструкцію лексичний аналізатор згрупує наступні послідовності символів, токени:
1. ідентифікатор point.
2. символ присвоєння =.
3. ідентифікатор init.
4. знак додавання.
5. ідентифікатор var.
6. знак множення.
7. число 23.
Пробіли, що розділяють токени, зазвичай ігноруються.
Коротко роботу лексичного аналізатора можна описати так: аналізатор зчитує символи із вхідного потоку, групує їх в лексеми та передає токени, які створені цими лексемами, разом з їх атрибутами синтаксичному аналізатору.
Стосовно методів лексичний анлізатор можна поділити на прямий а непрямий лексичний аналізатор. Непрямий лексичний аналіз полягає у послідовній перевірці лексем на відповідність токенам. Якщо аналізатор не „впізнає” в поточній лексемі один з токенів, то відбувається повернення у потоці вхідних символів і здійснюється перевірка на відповідність наступному токену. А прямий лексичний аналіз дозволяє визначити відповідний токен без повернення в потоці вхідних символів.
Непрямий лексичний аналізатор як програма на мові високого рівня складається із окремих функцій, кожна з яких розпізнає лише одну лексему.
Такі функції мають схожу структуру та відрізняються, в основному, тільки лексемою, що потрібна для порівняння із вхідною. Функції викликаються в певному порядку, що визначається перевагою в аналізі одних лексем перед іншими. Наявність приорітету пояснються тим, що деякі лексеми мають подібні початкові символи і деякі лексеми можуть складатися із простіших лексем.
Прямий лексичний аналізатор як програма складається із функцій, що розпізнають окремі лексеми. Така програма зчитує один вхідний символ на кожному кроці і передає його функції, яка може розпізнати лексему чи сформувати помилку. Для лексем, що мають подібні послідовності символів, існують функції, які розпізнають саме ці послідовності. В цих функціях реалізовані інші функції, що розпізнають решту символів у лексемах. Повідомлення про помилку може бути згенеровано тоді, коли не знайдено відповідної послідовності символів.
2. Розробка компілятора вхідної мови програмування
2.1. Формальний опис вхідної мови програмування
Одною з перших задач, що виникають при побудові компілятора, є визначення вхідної мови програмування. Для цього я використовую розширену нотацію Бекуса-Наура (Backus/Naur Form - BNF).
Перелік термінальних символів та ключових слів
{ } ;
: = + & ~ > ( ) [
]
“
start
stop
.
char
int
input
output
case
of
0..9
a..z,A..Z, ’ ‘
23+10+52+1=86 термінальних символів.
Приорітет операторів: 1. &
~
>
В проекті потрібно реалізувати оператор case(), а саме, його форму із мови Pascal :
case <expr> of
const_list1: <stmt>
const_list2: begin
<stmt>
<stmt>
end;
end;
Формальний опис вхідної мови в термінах BNF.
Правила написання правил у розширеній нотації Бекуса-Наура:
нетермінальні вирази записуються у кутових дужках: “<”, “>” ;
термінальні вирази записуються жирним шрифтом або у подвійних лапках;
усі нетермінальні вирази мають бути “розкриті” за допомогою термінальних;
сивол “::=” відділяє праву частину правила від лівої;
символ “|” розділяє альтернативи;
сиволи “[”, “]” означають необов’язковість (вираз в дужках може бути відсутнім);
сиволи “{”, “}” означають повторення.
<program> ::= “start” [{<block>}] “stop” ”.”
<block> ::= <stmt> | “start” [{<block>}] [{<stmt>}] “stop”
<stmt> ::= <declaration> | <const> | <operator>
<declaration> ::= <iddecl> | <ardecl>
<iddecl> ::= <type> <id> [ {“,” <id>} ] ”;”
<ardecl> ::= <type> <id> ”[“ <num> ”]” ”;”
<const> ::= <id> “=” <num> “;”
<operator> ::= <bind> | <inop> | <outop> | <caseop>
<bind> ::= <id> “:” “=” <expr> “;” | <id>”[”<expr>”]” “:” “=” <expr> “;”
<inop> ::= “input” “(“ <expr> “)” “;”
<outop> ::= “output” “(“ [“ “ ”]<expr>[“ “ ”] “)” “;”
<caseop> ::= “case” “(“ <expr> “)” “of” <num> “:” <block> [{<num> ”:” <block>}]
<type> ::= “char” | “int”
<id> ::= <letter>[{<letter>|<number>}]
<num> ::= <number>[{<number>}]
<letter> ::= a|b|c|d|e|f|g|h|i|j|k|l|n|m|o|p|q|r|s|t|u|v|w|x|y|z| A|B|C|D|E|F|G|H|I|J|K|L|N|M|O|P|Q|R|S|T|U|V|W|X|Y|Z
<number> ::= 0|1|2|3|4|5|6|7|8|9
<expr> ::= <operand> [{<op> <operand>}]
<operand> ::=”(”<expr>“)” | <num> | <id> [”[”<expr>”]”]
<op> ::= <grt>
<grt> ::= <inv> | ”>”
<inv> ::= <log> | “~”
<log> ::= “&” | “+” | [<op>]
Формальний опис складено за допомогою 23-ох нетермінальних виразів.
Повне дерево граматичного розбору
Повне дерево граматичного розбору
2.2. Розробка лексичного аналізатора
Основна задача лексичного аналізу – розбити вихідний текст, що складається з послідовності одиночних символів, на послідовність слів, або лексем, тобто виділити ці слова з безперервної послідовності символів. Всі символи вхідної послідовності з цієї точки зору розділяються на символи, що належать яким-небудь лексемам, і символи, що розділяють лексеми. В цьому випадку використовуються звичайнi засоби обробки рядків. Вхiдна програма проглядається послiдовно з початку до кінця. Базовi елементи, або лексичнi одиницi, роздiляються пробiлами, знаками операцiй i спецiальними символами (новий рядок, знак табуляції), i таким чином видiляються та розпізнаються iдентифiкатори, лiтерали i термiнальнi символи (операцiї, ключові слова).
При виділенні лексеми вона розпізнається та записується у таблицю лексем за допомогою відповідного номера лексеми, що є унікальним для кожної лексеми із усього можливого їх набору. Це дає можливість наступним фазам компiляції звертатись лексеми не як до послідовності символів, а як до унікального номера лексеми, що значно спрощує роботу синтаксичного аналізатора: легко перевіряти належність лексеми до відповідної синтаксичної конструкції та є можливість легкого перегляду програми, як вгору, так і вниз, від текучої позиції аналізу. Також в таблиці лексем ведуться записи, щодо рядка відповідної лексеми – для місця помилки – та додаткова інформація.
При лексичному аналiзі виявляються i вiдзначаються лексичнi помилки (наприклад, недопустимi символи i неправильнi iдентифiкатори). Лексична фаза вiдкидає також i коментарi, оскiльки вони не мають нiякого впливу на виконання програми, отже ж й на синтаксичний розбір та генерацію коду.
Лексичний аналізатор (сканер) не обов’язково обробляє всю програму до початку всіх інших фаз. Якщо лексичний аналіз не виділяється як окрема фаза компіляції, а є частиною синтаксичного аналізу, то лексична обробка тексту програми виконується по мірі необхідності по запиту синтаксичного аналізатора.
Блок-схема лексичного аналізатора
2.3. Розробка синтаксичного аналізатора
Синтаксичний аналіз – це процес, в якому досліджується послідовність лексем, яку повернув лексичний аналізатор, і визначається, чи відповідає вона структурним умовам, що сформульовані у визначені синтаксису мови.
Синтаксичний аналізатор – це частина компілятора, яка відповідає за виявлення основних синтаксичних конструкцій вхідної мови. В задачу синтаксичного аналізатора входить: знайти та виділити основні синтаксичні конструкції мови в послідовності лексем програми, встановити тип та правильність побудови кожної синтаксичної конструкції і представити синтаксичні конструкції у вигляді, зручному для подальшої генерації тексту результуючої програми. Як правило, синтаксичні конструкції мови програмування можуть бути описані за допомогою контекстно-вільних граматик. Розпізнавач дає відповідь на питання, належить чи ні, ланцюжок вхідних лексем заданій мові. Але, задача синтаксичного аналізу, не обмежується тільки такою перевіркою. Синтаксичний аналізатор повинен мати, деяку результуючу мову, за допомогою якої він передає наступним фазам компіляції, інформацію про знайдені і розібрані синтаксичні конструкції, якщо відокремлюється фаза генерації об’єктного коду.
2.3.1 Блок-схема синтаксичного аналізатора
2.4. Розробка генератора коду
Вихідною мовою компілятора є мова високого рівня С. Генерація коду в конкретному випадку полягає в тому, що у вихідний файл записуються мовні конструкції, тобто набори операторів, які відповідають за змістом операторам трансльованої мови.
Наприклад, у вхідному файлі маємо конструкцію:
start
int a;
a:=10;
output(a);
stop.
В такому випадку генератор сформує наступну послідовність операторів:
#include <iostream.h>
void main()
{
int a;
a=10;
cout<<(a);
}
Цей приклад показує найпростіший варіант генерації вихідного коду.
Оскільки, це ще не машинний код, потрібно викликати компілятор мови С для запуску написаної програми.
3. Реалізація, відладка та тестування компілятора
При відладці та при тестуванні виникли деякі труднощі, пов’язані з типами змінних.
start
int a;
input(a);
case(a)of
10: output(1234);
20: start
a:=23;
output(a);
stop
stop.
------------------------
succesful..
4. Висновок
При виконанні курсового проекту, я ознайомився з принципами роботи компіляторів, їх структурою а також різними методами їх реалізації. Розроблений компілятор для мови програмування S7 задовільняє вимогам, згаданим у завданні. Компілятор реалізовано із генерацію коду у вигляді програми на мові СІ.
5.Список літератури
1. Страуструп Б. Введение в язык C++, 1985.
2. Джордейн Р. Справочник программиста ПК IBM PC, XT/AT. - – М.: ФиС, 1992. 3. Абель П. Ассемблер для IBM PC, 1991.
4. Прата С. Язык программирования Си, 2003
Додаток А. Текст програми
//---------------------------------------[ pack.h ]----------------------------------------------------
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef struct {
char *lexptr;
int token;
int line;
int type;
} rec;
extern rec symtab[];
extern rec idtab[];
extern FILE *source, *symfile, *idfile, *error, *tree, *prod;
extern int pos;
extern char str[];
extern int strnum;
extern char *resword[];
extern int index;
extern int index2;
extern int numval;
extern char *lex;
extern void err(int ekod);
//---------------------------------------[ scan.c ]----------------------------------------------------
#include "s7pack.h"
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
//int scan(void);
rec symtab[350];
rec idtab[60];
FILE *symfile, *idfile;
int pos;
char str[256];
int strnum=0;
char *resword[23]={"start","stop","char","int",
"input","output","case",
"of","const","[","]",".",",",":",";",
"(",")","&","~",">","+",
"\"","=" };
int index=1;
int index2=1;
int numval;
char *lex="\0";
int isreserv(char *lex)
{
int i;
for(i=0;i<23;i++)
if(strcmp(lex,resword[i])==0) return i+260;
return 0;
}
void getstr(void)
{
do
{
if(feof(source))return;
fgets(str,256,source);
strnum++;
} while(str[0]=='\n');
pos=0;
}
void setpos(void)
{
while((isspace(str[pos])) || (!str[pos]))
if((str[pos]=='\n') || (!str[pos])) getstr();
else pos++;
}
int insert(char *lex, int tok, int snum, int mode)
{
if(mode==1)
{
symtab[index].lexptr=(char*)malloc(strlen(lex)+1);
strcpy(symtab[index].lexptr,lex);
symtab[index].token=tok;
symtab[index].line=snum;
index++;
return index;
}
if(mode==2)
{
idtab[index2].lexptr=(char*)malloc(strlen(lex)+1);
strcpy(idtab[index2].lexptr,lex);
idtab[index2].token=tok;
idtab[index2].line=snum;
symtab[index]=idtab[index2];
index++;
index2++;
return index2;
}
return 0;
}
int lookup(char *lex, int mode)
{
int i;
if(mode==0)
{
for(i=index;i>0;i--)
if(strcmp(lex,symtab[i].lexptr)==0) return i;
}
if(mode==1)
{
for(i=index2;i>0;i--)
if(strcmp(lex,idtab[i].lexptr)==0) return i;
}
return 0;
}
int istoken(void)
{
int ch=str[pos];
if(((ch>='A')&&(ch<='Z')) || ((ch>='a')&&(ch<='z'))) return 1;
if((ch>='0')&&(ch<='9')) return 2;
if((ch=='(')||(ch==')')) return 3;
if((ch=='=')||(ch==':')||(ch==';')||(ch==',')||(ch=='.')||(ch=='[')||(ch==']')||(ch=='\"')) return 4;
if((ch=='+')||(ch=='&')) return 5;
if(ch=='~') return 6;
if(ch=='>') return 7;
if(ch!=' '&& ch!='\n'&& ch!='\t') err(17);
return -1;
}
int id(void)
{
int p=0,cond;
if(istoken()==1)
{
lex[p]=str[pos];
p++;
pos++;
while( (cond=istoken())==1 || cond==2)
{
lex[p]=str[pos];
pos++;p++;
}
lex[p]='\0';
return 1;
}
return 0;
}
int num(void)
{
int p=0;
numval=0;
while(istoken()==2)
{
lex[p]=str[pos];
numval=numval*10+str[pos]-'0';
pos++;
p++;
}
lex[p]='\0';
if(p==0) return 0;
return 1;
}
int sign(void)
{
int p=0;
if(istoken()>2)
{
lex[p]=str[pos]; //бЄ®Їiоў вЁ ©®Ј®
pos++;
p++;
lex[p]='\0';
return 1;
}
return 0;
}
int scan(void)
{
int i,v,idmarker=300,numarker=700;
clrscr();
if((symfile=fopen("symf.dat","w+"))==NULL)
{
printf("error: create file symfile.txt\n");
fclose(source);
return 1;
}
if((idfile=fopen("idf.dat","w+"))==NULL)
{
printf("error: create file idfile.txt\n");
fclose(source);
fclose(symfile);
return 1;
}
if((error=fopen("error.txt","w+"))==NULL)
{
printf("error: open file error.txt\n");
fclose(source);
fclose(symfile);
fclose(idfile);
return 1;
}
while((strcmp("start",lex)!=0) && !feof(source))
{
setpos();
id();
}
insert(lex,260,strnum,1);
setpos();
while(!feof(source))
{
if(id())
{
if(v=isreserv(lex)) insert(lex,v,strnum,1);
else if((v=lookup(lex,1))==0) insert(lex,idmarker++,strnum,2);
else
{
symtab[index]=idtab[v];
symtab[index].line=strnum;
index++;
}
setpos();
}
if(num())
{
if((v=lookup(lex,1))==0) insert(lex,numarker++,strnum,2);
else
{
symtab[index]=idtab[v];
symtab[index].line=strnum;
index++;
}
setpos();
}
if(sign())
{
if((isreserv(lex)) && (!lookup(lex,1))) insert(lex,lex[0],strnum,1);
setpos();
}
if(strcmp(".",lex)==0) break;
}
printf("\n\t----------symtab---------"); for(i=1;i<index;i++)
{
printf("\n %d) \tlex: \t%s\ttoken: %d\tline: %d",i,symtab[i].lexptr,symtab[i].token,symtab[i].line);
fprintf(symfile,"\n %d) \tlex: \t%s\ttoken: %d\tline: %d",i,symtab[i].lexptr,symtab[i].token,symtab[i].line);
}
printf("\n\n\t----------idtab---------"); for(i=1;i<index2;i++)
{
printf("\n %d) \tlex: \t%s\tatrib: %d\tline: %d",i,idtab[i].lexptr,idtab[i].token,idtab[i].line);
fprintf(idfile,"\n %d) \tlex: \t%s\tatrib: %d\tline: %d",i,idtab[i].lexptr,idtab[i].token,idtab[i].line);
}
index--;
getch();
return 0;
}
//---------------------------------------[ parc.c ]----------------------------------------------------
#include "s7pack.h"
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
FILE *error, *tree, *prod;
int gen(int ,char*);
void err(int ekod);
int expr();
int block();
int oper();
int operand();
int grt();
int op();
int at=0;
int idtype=0;
struct {
char *lex;
int type;
} dec[20];
//---------------------[semantic interpretation]------------------------------
//----------------------------------------------------------------------------
int link(char *lex, int type)
{
dec[at].lex=lex;
dec[at].type=type;
at++;
return at<20;
}
int check(char *lex)
{
int i;
for(i=0;i<at;i++)
if(strcmp(lex,dec[i].lex)==0) return dec[i].type;
return 10;
}
//------------------------------------------------------------------------
int log()//[ & + ]--------------------------------------------------------
{
if(symtab[++index].token==38) gen(21,"");
else if(symtab[index].token==43) gen(20,"");
else{--index; return 0;}
return 1;
}
int inv()//[ ~ ]---------------------------------------------------------
{
if(log())
if(!operand()) err(192);
if(symtab[++index].token!=126) {--index; return 0;}
gen(19,"");
if(log())
if(!operand()) err(14);
return 1;
}
int grt()//[ > ]--------------------------------------------------------
{
if(inv())
if(!operand()) err(14);
if(symtab[++index].token!=62) {--index; return 0;}
gen(18,"");
if(inv())
if(!operand()) err(14);
return 1;
}
int op()//mathematical expression------------------------------------------
{
if(grt()) return 1;
return 0;
}
int operand()//------------------------------------------------------------
{
if(symtab
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора