Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Федеральное агентство по образованию
Государственное образовательное учреждение
Высшего профессионального образования
Тульский государственный университет
Кафедра электронных вычислительных машин
Системное программное обеспечение
Лабораторная работа № 2
«Проектирование синтаксического анализатора»
Выполнил:
Проверил: Сычугов А.А.
Тула 2009
1. Цель работы: изучить принцип работы синтаксического анализатора на основе метода нисходящего разбора с возвратами.
2. Тех. задание: Написать синтаксический анализатор для арифметических выражений, содержащих знаки ( , ) + - * / и идентификаторы id.
3. Порядок выполнения работы:
4. Выполнение работы.
Задачей синтаксического анализатора является полный синтаксический разбор исходной программы, т.е. распознавание языковых конструкций и контроль ошибочных. Для этого надо построить грамматику языка.
4.2. Грамматика
Грамматикой G(Z) называют конечное, непустое множество правил; Z – это символ, который должен встретиться в левой части по крайней мере одного правила. Он называется начальным символом.
Правилом называется упорядоченная пара (U,x), которая обычно записывается так:
U::=x,
где U – символ, а x – непустая конечная цепочка символов. U – левая часть правила, х – правая часть.
Все символы, которые встречаются в левой части правил, называются терминальными. При записи грамматики все нетерминальные символы мы будем заключать в угловые скобки < и >.
Цепочка х называется сентенциальной формой, если х выводима из начального символа Z, т.е. если Z=>*x
Пусть W – сентенциальная форма, и W=xuy, тогда u называется простой фазой сентенциальной формы W для нетерминального символа U, если Z=>xUy и U=>u.
Основой сентенциальной формы называется самая левая простая фраза.
ОПГ для языка Cи:
<A>::=<A>+<B>|<A>-<B>|-<B>|<B>
<B>::=<B>*<C>|<B>/<C>|<C>
<C>::=(<A>)|<id>|<number>
Z::=<main><begin_end>.
<main>::=main(void).
<begin_end>::=<begin><peremen><operator’s><end>|<begin><peremen><end>
<Begin>::={
<end>::=}
<operator’s>::=<operator>|<oprerator’s>;<operator>
<operator>::=<for>|<printf>|<scanf>|<if>|<id>:=<A>
<uslovie>::=<|>|<=|>=|<>
<for>::=for<id>:=<A><uslovie><A><Begin_end>;
<if>::=if<id><uslovie><A><Begin_end>;| if<id><uslovie><A><Begin_><else_>
<else_>::=else<begin>;
<prinrf>::=Printf(<string>);
<string>::=<id>|<number>|” “|<string>,<id>|<string>,<number>|<string>,” “|<string>,<id>
<scanf>::=Scanf(<string_>);
4.3. Алгоритм разбора
Метод простого предшествования основан на том что между двумя соседними символами Si и Si+1 приводимой строки могут существовать только три отношения:
Данные отношения называются отношениями предшествования.
Алгоритм разбора заключется в следующем: символы входной строки записываются в стек до тех пор, пока между очередными двумя символами не окажется отношения >, затем стек просматривается в обратном направлении до символа < если такого в стеке не находится то это означает ошибку как и то, если между двумя соседними символами не будет отношения предшествования.
Для определения типа отношения на предварительном этапе строится матрица предшествования. Матрица представляет собой 2х мерный массив, где выписаны все символы граматики по осям, а на стыке находится отношение между двумя соседними символами.
В данной курсовой работе матрица предшествования выглядит так см. рис.4.
После семантического анализа можно приступать к генерации объектного кода, но для облегчения задачи проще сначала сформировать промежуточный код.
После синтаксического анализа сформируется файл:
AS0FI0FI1HR0FI2B W3=I2W2=I2W1=W2*W3R0=W1C;B ES1DI0W1=R0(I0)I1=W1W3=P0W2=I1W1=W2>W3J B ES2EI1C;O B W3=P1W2=I1W1=W2+W3I1=W1ES3EI1C;C.
На рис. 1.1. показано дерево вызова функций.
0
│
┌───────────────┼───────────────────┐
│ │ │
000 001 002
│
┌──────────┴────────────┐
│ │
010 011
│ │
┌──────┼───────┐ ┌─────┴────────────┐
│ │ │ │ │
│ │ │ 040 {040}
│ │ │ │
020 021 022 ┌───┬─┴─┬───┬───┐
│ │ │ │ │ │
┌────┴────┐ 050 051 052 053 022
│ │ │ │
030 031 │ ┌───┴─┬───┬──────┐
│ │ │ │ │
│ 101 102 091 103
┌───┼───┐ │ │
│ │ │ │ │
060 061 022 │ │
│ ┌─┴─┬───┐ ┌┴────┬─────┐
│ │ │ │ │ │ │
┌───┴───────┐ │ │ │ │ │ │
│ │ 070 120 070 050 | 051 | 052
070 071
│ │
┌─────┼─────┐ ┌┴───┐
│ │ │ │ │
080 | 081 | 082 {100 070}
│
┌───┼───┐
│ │ │
090 061 091
Рис. 1.1. Дерево вызова функций
Приложение Листинг программы
// СИНТАКСИЧЕСКИЙ АНАЛИЗАТОР
// простое предшествование
void Sintacsis_Analiz()
{
Tree *p, *beg, *end;
if (Osch>1) return;
Osch=0; // начать просматривать программу с начала
signed char otn;
while(Osch==0)
{
p=Pr;
beg=NULL;
end=NULL;
// поиск конца основы
while (p!=NULL)
{
otn=(signed char)lr[p->kod][(p->r)->kod];
if (otn<0 || otn>4) { Osch=-otn;
Stroka=p->line;
return;
}
if (otn!=R) p=p->r;
else { end=p; break; }
}
// поиск начала основы
while (p!=NULL)
{
otn=(signed char)lr[p->l->kod][p->kod];
if (otn<0 || otn>4) { Osch=-otn;
Stroka=p->line;
return;
}
if (otn!=L) p=p->l;
else { beg=p; break; }
}
switch (beg->kod)
{
case BEGIN: Semantic_Analiz_BeginEnd(beg,end); break;
case PODWHILE: Semantic_Analiz_While(beg,end->r); break;
case Scanf: Semantic_Analiz_I(beg,end); break;
case Printf: Semantic_Analiz_O(beg,end); break;
case ID:
case OTKR:
case INVERS:
case SUB:
case KON:{ Tree *tp=NULL;
tp=beg->l;
Semantic_Analiz_Viragen(beg,end);
if (tp->kod==While)
{ tp->r->kod=PODWHILE;
TreeDel(tp,tp);
}
if ((tp->kod==PODDEREVO || tp->kod==BEGIN || tp->kod==PODWHILE) &&
tp->r->r->kod==TOZ)
TreeDel(tp->r->r,tp->r->r);
}
break;
case Main: Osch=1; return; // успешно разобрана вся программа
default: Osch=24; return;
}
}
}
//Семантический анализатор основы ' { <PODDEREVO> <PODDEREVO>... } '
void Semantic_Analiz_BeginEnd(Tree * beg,Tree * end)
{ Tree *n=NULL,*b=beg->r,*e=end;
if (e->kod!=END) { Osch=9; return;}
while (b!=e)
{ if (b->kod==PODDEREVO) n=new Tree(n,b->kod,b->op,b->v);
else { Osch=2; Stroka=n->line;
return;
}
b=b->r;
}
Tree *tmp=beg->l;
TreeDel(beg,e); // удалить подоснову
TreeIns(tmp,P); // добавить лишь ссылку на неё
}
//Семантический анализатор цикла с предусловием
//While
void Semantic_Analiz_While(Tree * beg,Tree * end)
{ Tree *b=NULL;
b=new Tree(b,LABEL,"Метка",NULL,Labnum);
b=new Tree(b,beg->kod,beg->op,beg->v);
b=new Tree(b,ESLNEONE,"Условие",NULL,Labnum+1);
b=new Tree(b,beg->r->kod,beg->r->op,beg->r->v);
b=new Tree(b,JAMP,"переход на начало",NULL,Labnum);
b=new Tree(b,LABEL,"Метка",NULL,Labnum+1);
Labnum+=2;
Tree *tmp=beg->l;
TreeDel(beg,end);
TreeIns(tmp,P);
}
//Семантический анализатор ввода: scanf(ID)
void Semantic_Analiz_I(Tree * beg,Tree * end)
{
if (beg->r->kod==PODDEREVO && end->kod==TOZ
&& ((Tree*)( beg->r->v )) ->r->kod==ID && ((Tree*)(beg->r->v))->r->r->kod ==NOTH)
{
Tree *n=NULL;
n=new Tree(n,beg->kod,beg->op,((Tree*)(beg->r->v))->r->v);
Tree *tmp=beg->l;
TreeDel(beg,end);
TreeIns(tmp,n);
ioc=1;
}
else {Osch=25; return;}
}
// Семантический анализатор вывода: printf(ID)
void Semantic_Analiz_O(Tree * beg,Tree * end)
{ Tree *n=NULL;
n=new Tree(n,beg->r->kod,beg->r->op,beg->r->v);
n=new Tree(n,beg->kod,beg->op);
Tree *tmp=beg->l;
TreeDel(beg,end);
TreeIns(tmp,P);
ioc=1;
}
// Семантический анализатор вычисляемых выражений
#define P_NOT 6
#define PMULDIV 5
#define PADDSUB 4
#define P_SRAVN 3
#define P_LOGIC 2
#define P_PRIS 1
void Semantic_Analiz_Viragen(Tree * beg,Tree * end)
{
Tree *b=beg,*sp;
StOtren s, p;
int prior=0;
Cnt:
switch(b->kod)
{
case KON: p.push(b); break;
case ID: if (b->r->kod==PRISV)
{b=b->r;
b->v=b->l->v;
if ( b->l->l->kod==PODDEREVO ||
b->l->l->kod==BEGIN)
b->kod=PRIPOP;
while (s.GetTmp()>prior+P_PRIS) p.push(s.pop());
s.push(b,prior+P_PRIS);
break;
}
else
{ p.push(b);
break;
}
case ADD:
case SUB: if ((b->l)->kod!=ID &&
(b->l)->kod!=KON &&
(b->l)->kod!=ZAKR) b->kod=SUBU;
while (s.GetTmp()>=prior+PADDSUB) p.push(s.pop());
s.push(b,prior+PADDSUB);
break;
case MUL:
case DIV: while (s.GetTmp()>=prior+PMULDIV) p.push(s.pop());
s.push(b,prior+PMULDIV);
break;
case OTKR: prior+=10; break;
case ZAKR: prior-=10; if (prior<0)
{ Osch=16; Stroka=b->line;
strcpy(Komment,")");
return;
}
break;
case RAVN:
case BOL:
case MENSH:
case BRAV:
case MRAVN:
case NERAVN: while (s.GetTmp()>=prior+P_SRAVN) p.push(s.pop());
s.push(b,prior+P_SRAVN);
break;
case INVERS: while (s.GetTmp()>=prior+P_NOT) p.push(s.pop());
s.push(b,prior+P_NOT);
break;
case AND:
case OR: while (s.GetTmp()>=prior+P_LOGIC) p.push(s.pop());
s.push(b,prior+P_LOGIC);
break;
default: Osch=15; Stroka=b->line; return;
}
if (b!=end) { b=b->r; goto Cnt;}
if (prior!=0) { Osch=16; Stroka=b->line;
strcpy(Komment,"(");
return;
}
while( (b=s.pop())!=NULL ) p.push(b); // перевод операций в стек p
b=NULL; // создать новую цепочку программы
b=new Tree(b,NOTH,"Exp");
while ((sp=p.popd())!=NULL) // взять элемент
b=new Tree(b,sp->kod,sp->op,sp->v,sp->line); // создать новый элемент программы
b=new Tree(b,NOTH,"Exp");
Tree *predn=beg->l;
TreeDel(beg,end); // удалить цепочку
// Включить вновь созданную цепочку в программу
TreeIns(predn,P);
if ((predn->kod==PODDEREVO || predn->kod==BEGIN)
&& predn->r->r->kod==TOZ)
TreeDel(predn->r->r,predn->r->r);
Tree *t=((Tree*)(predn->r->v))->r;
while(t!=NULL && t->kod!=NOTH)
{
if (t->kod!=ID && t->kod!=KON && t->kod!=OTKR && t->kod!=ZAKR && t->kod!=PODDEREVO)
{
if (t->kod!=SUBU && t->kod!=INVERS && t->kod!=PRIPOP && t->kod!=PRISV)
{
Tree *tmp=NULL,*pn;
tmp=new Tree(tmp,t->l->l->kod,t->l->l->op,t->l->l->v,t->l->l->line);
tmp=new Tree(tmp,t->l->kod,t->l->op,t->l->v,t->l->line);
tmp=new Tree(tmp,t->kod,t->op,t->v,t->line);
pn=t->l->l->l;
TreeDel(t->l->l,t);
TreeIns(pn,P);
t=(Tree*)predn->r->v;
}
else
{
Tree *tmp=NULL,*pn;
tmp=new Tree(tmp,t->l->kod,t->l->op,t->l->v,t->l->line);
tmp=new Tree(tmp,t->kod,t->op,t->v,t->line);
pn=t->l->l;
TreeDel(t->l,t);
TreeIns(pn,P);
t=(Tree*)predn->r->v;
}
}
t=t->r;
}
}
// Вывод Ошибок
void PrintError(void)
{
char strErr[80];
switch(Osch)
{
case 1: strcpy(strErr,"Компиляция завершена"); break;
case 2: strcpy(strErr,"Неправильная конструкция: { ... }"); break;
case 3: strcpy(strErr,"Неправильная конструкция: <идентификатор>=<выражение>;"); break;
case 4: strcpy(strErr,"Неправильная конструкция: while <expression> <тело цикла>"); break;
case 5: strcpy(strErr,"Отсутствует главная программы: void main(void){ ... }"); break;
case 6: strcpy(strErr,"Предполагается идентификатор"); break;
case 7: strcpy(strErr,"Предполагается разделитель ';'"); break;
case 8: strcpy(strErr,"Нет разделителя"); break;
case 9: strcpy(strErr,"Неправильно составлено выражение"); break;
case 10: strcpy(strErr,"Необходим тип Int"); break;
case 11: strcpy(strErr,"Нехватает памяти"); break;
case 12: strcpy(strErr,"Неопределенный идентификатор:"); break;
case 13: strcpy(strErr,"Неправильно использовано слово int,void,main"); break;
case 14: strcpy(strErr,"Неправильно задана числовая константа"); break;
case 15: strcpy(strErr,"Неправильно построено выражение"); break;
case 16: strcpy(strErr,"Нет соответствия скобок ( ), лишняя"); break;
case 17: strcpy(strErr,"Предполагается разделитель ',' или ;"); break;
case 18: strcpy(strErr,"Неправильная конструкция: "); break;
case 19: strcpy(strErr,"Повторное объявление идентификатора"); break;
case 20: strcpy(strErr,"Недопустимый символ"); break;
case 21: strcpy(strErr,"Длинный идентификатор"); break;
case 22: strcpy(strErr,"Длинная константа"); break;
case 23: strcpy(strErr,"Нет СИ-файла:"); break;
case 24: strcpy(strErr,"Ошибка при компиляции"); break;
case 25: strcpy(strErr,"Ошибка В/В: printf(expression); или scanf(<id>);"); break;
}
gotoxy(3,15);
cprintf("%s %s",strErr,Komment);
gotoxy(3,17);
cprintf("просмотрено строк: %d",Stroka);
}
// Найти идентификатор в таблице имен
int FindIDEN(SymbPr *s)
{
if (TV==NULL) return DIEZ;
Peremen *bv=TV;
while(1)
{ if (cmpSlovo(s->str,bv->str)==EQU)
{ s->v=bv;
s->kod=bv->type;
return FIND;
}
if (bv->r!=NULL) { bv=bv->r; continue; }
else return DIEZ;
}
}
// Создание ASM - программы
#define f(st) fprintf(a,st);
void Create_AsmCode()
{ StOtren s;
if (Osch>1) return;
// создать файл для записи
int l= strlen(fc);
for (int i=l;i>0;i--)
if (fc[i]=='.') break;
if (i==0){ i=l; fc[i]='.'; }
fc[i+1]='a'; fc[i+2]='s'; fc[i+3]='m'; fc[i+4]=NULL;
FILE * a=fopen(fc,"w");
if (a==0){ Osch=24; strcpy(Komment,fc); return;}
Tree *p=Pr;
f("\n\nS_STACK segment para stack 'stack'\n\tdw\t100h\tdup(0)\nS_STACK ends")
f("\n\nS_DATE segment para 'date'")
f("\nsosw\tdw\t?")
Peremen *v=TV;
while(v!=NULL)
{
if (v->type==Int)
{
f("\n")
ultoa((unsigned long)v->str,&v->str[strlen(v->str)],36);
f(v->str)
f("\tdw\t0")
}
if (v->type==KON)
{ f("\n_")
f(v->str)
f("\tdw\t")
f(v->str)
}
v=v->r;
}
f("\nS_DATE ends")
f("\n\nASSUME ds:S_DATE,cs:S_CODE,ss:S_STACK")
f("\n\nS_CODE segment para 'code'\nMAIN:")
f("\n\tpush\tds\n\txor\tax,ax\n\tpush\tax\n\tmov\tax,S_DATE\n\tmov\tds,ax\n\tfinit\n")
p=p->r;
while(1)
{
if (p!=0)
switch (p->kod)
{
case NOTH:
case Main: p=(Tree *)p->r; continue;
case PODWHILE:
case PODDEREVO: if (p->v!=NULL) {s.push(p); p=(Tree *)p->v; continue; } else break;
case ID: f("\n\tfild\t") f(p->v->str) break;
case KON: f("\n\tfild\t_")
f(p->v->str)
break;
case LABEL: fprintf(a,"\nLab_%d:",p->line); break;
case JAMP: f("\n\tjmp\t") fprintf(a,"Lab_%d",p->line); break;
case ESLNEONE: f("\n\tftst\n\tfstsw\tsosw\n\tffree\tst(0)\n\tfincstp\n\tand\tsosw,4500h")
f("\n\tcmp\tsosw,4000h")
f("\n\tjne\t") fprintf(a,"Lab_%d",Labnum);
fprintf(a,"\n\tjmp\tLab_%d",p->line);
fprintf(a,"\nLab_%d:",Labnum++);
break;
case ADD: f("\n\tfadd\t") break;
case SUB: f("\n\tfsub\t") break;
case AND:
case MUL: f("\n\tfmul\t") break;
case DIV: f("\n\tfdiv\t") break;
case SUBU: f("\n\tfchs\t") break;
case PRIPOP: f("\n\tfistp\t") f(p->v->str) break;
case PRISV: f("\n\tfist\t") f(p->v->str) break;
case OR: f("\n\tfabs\n\tfabs\n\tfxch\n\tfabs\n\tfadd") break;
case INVERS:f("\n\tftst\n\tfstsw\tsosw\n\tffree\tst(0)\n\tfincstp")
f("\n\tand\tsosw,4500h")
f("\n\tcmp\tsosw,4000h")
f("\n\tje")
lab:fprintf(a,"\tLab_%d\n\tfldz\n\tjmp\tLab_%d",Labnum,Labnum+1);
fprintf(a,"\nLab_%d:\tfld1\nLab_%d:",Labnum,Labnum+1);
Labnum+=2;
break;
case RAVN: f("\n\tfcompp\n\tfstsw\tsosw")
f("\n\tand\tsosw,4500h")
f("\n\tcmp\tsosw,4000h")
f("\n\tje")
goto lab;
case BOL: f("\n\tfcompp\n\tfstsw\tsosw")
f("\n\tand\tsosw,4500h")
f("\n\tcmp\tsosw,0100h\n\tje")
goto lab;
case MRAVN: f("\n\tfcompp\n\tfstsw\tsosw")
f("\n\tand\tsosw,4500h")
f("\n\tcmp\tsosw,0100h\n\tjne")
goto lab;
case MENSH: f("\n\tfcompp\n\tfstsw\tsosw")
f("\n\tand\tsosw,4500h")
f("\n\tcmp\tsosw,0000h\n\tje")
goto lab;
case BRAV:f("\n\tfcompp\n\tfstsw\tsosw")
f("\n\tand\tsosw,4500h")
f("\n\tcmp\tsosw,0000h\n\tjne")
goto lab;
case NERAVN: f("\n\tfcompp\n\tfstsw\tsosw")
f("\n\tand\tsosw,4500h")
f("\n\tcmp\tsosw,4000h\n\tjne")
goto lab;
case Scanf: f("\n\tcall\tscanf") f("\n\tfistp\t") f(p->v->str) break;
case Printf:f("\n\tcall\tprintf") break;
case DIEZ: goto kones;
default: Osch=24;
fclose(a);
return;
}
else{ if (s.kol==0) break;
p=s.pop();
}
p=p->r;
}
kones:
f("\n\n\tretf\nS_CODE\tends")
if (ioc) f("\n\ninclude\tlibio.as")
f("\n\n\tend\tMAIN")
fclose(a);
if (ioc)
if ((a=fopen("libio.as","r"))==NULL)
strcpy(Komment,"\n Нет библиотечного файла libio.as");
else {fclose(a);}
}
// ********** Освобождение выделенной памяти **********
int urov=0;
void ProgaDestroy(Tree *b)
{ Tree *tmp;
do{
int u=urov;
while(u>0) { fprintf(a,"¦ "); u--;}
fprintf(a,"+---");
if (b->kod!=PODDEREVO && b->kod!=PODWHILE)
{
fprintf(a,"%d-- %s\n",b->kod,b->op);
}
else{ fprintf(a,"+\n");
urov++;
if (b->v!=NULL)ProgaDestroy((Tree *)b->v);
urov--;
int u=urov;
while(u>=0) { fprintf(a,"¦ "); u--;}
fprintf(a,"\n");
}
tmp=b->r;
delete b;
b=tmp;
}while(b!=NULL);
}
void MemoryDestroy()
{
fprintf(a,"\n\nПрограмма\n");
fprintf(a,"¦\n");
if (Pr!=NULL) ProgaDestroy(Pr);
fprintf(a,"\n\nИдентификаторы с числовой константой");
if (TV!=NULL)
{ Peremen *tmp;
do{ fprintf(a,"\n%d %s",TV->type,TV->str);
tmp=TV->r;
delete TV;
TV=tmp;
}while(TV!=NULL);
}
}