Использование LEX/YACC
Приведенные ниже тексты демонстрируют использование программ LEX/YACC
или их свободно распространяемых аналогов FLEX/BISON для создания лексического
и синтаксического анализаторов. Входной язык такой же как и в примере из
первой части . Синтаксическое дерево и кодогенератор
такие же как в примере из второй части .
Язык реализации - C, поскольку LEX/YACC создают текст на этом языке. Пример
короче двух предыдущих, но для его понимания надо разобраться с LEX/YACC.
Или только с YACC, а лексический анализатор написать вручную. YACC по описанию
создает анализатор, который в процессе работы считывает лексемы,
помещает их в стек (в отличие от ранее рассмотренных примеров сканер должен
возвращать не только слово, но и соотвествующий идентификатор) и постоянно
проверяет вершину стека на предмет возможности применения одного из перечисленных
в задании синтаксических правил. Если найдено правило, правая часть которого
совпадает с вершиной стека, соотвествующие символы из стека удаляются, символ
из левой части правила помещается в стек и выполняется связанный с правилом код.
Здесь под символами понимаются не символы алфавита, а лексемы (терминальные символы)
и левые части правил (нетерминальные символы). Процесс заканчивается если
в стеке останется один стартовый символ (в данном случае это program) или если фиксируется
ошибка. На самом деле все сложнее, анализатор еще должен уметь разрешать конфликты.
Например, появление на вершине стека символа IDENTIFIER еще не означает, что его можно
преобразовать в нетерминальный символ (неоднозначность, для выбора подходящего
варианта нужно использовать информацию о предшествующих символах). Преобразование символа identifier также
неоднозначно, но этот конфликт может быть разрешен путем надлежащего упорядочивания
правил (сначала identifiers identifier , затем identifier , но правильнее также использовать информацию о предшествующих символах). Могут быть ситуации, когда надо также учитывать последующий символ.
Автоматически сгенерированный анализатор хорош тем, что при его создании явно используется
формальное описание синтаксиса языка. При ручном написании анализатора оно только имеется
ввиду. Тем не менее ответ на вопрос о сравнении сложности этих методик не очевиден.
Пример может содержать неточности и ошибки.
Некоторое представление о принципах синтаксически-управляемого разбора может дать следующий
текст .
<![CDATA[
/* Файл l - Описание лексического анализатора */
/* Командная строка: flex.exe l */
/* Результат: lexyy.c */
%{
#include <string.h> /* strdup */
#include <stdlib.h> /* atoi */
%}
DIGIT [0-9]
ID [A-Za-z][A-Za-z0-9]*
%%
"<=" { return(LE); }
"!=" { return(NE); }
">=" { return(GE); }
word { return(WORD); }
begin { return(BLOCK); } /* Слово BEGIN используется FLEX */
if { return(IF); }
then { return(THEN); }
while { return(WHILE); }
do { return(DO); }
write { return(WRITE); }
blank { return(BLANK); }
end { return(END); }
{ID} { yylval.ID = (char *) strdup(yytext); return(IDENTIFIER); }
{DIGIT}+ { yylval.Value = atoi(yytext); return(NUMBER); }
[ \t\n]+ /* Пропуск пробелов и переводов строки */
. { return(yytext[0]); }
%%
int yywrap()
{
return 1; /* Конец файла - завершение */
}
]]>
<![CDATA[
/* Файл s - Описание синтаксиса и кодогенератор */
/* Командная строка: bison.exe s */
/* Результат: s_tab.c */
%{
#include <stdlib.h> /* malloc */
#include <string.h> /* strcmp */
#include <stdio.h> /* Ввод/вывод */
#include <io.h>
#define YYDEBUG 0 /* Отладка отключена, включение - 1 */
#define idEMPTY 0
#define idNUMBER 1
#define idVAR 2
#define idOR 3
#define idAND 4
#define idLT 5
#define idLE 6
#define idEQ 7
#define idNE 8
#define idGE 9
#define idGT 10
#define idBIT_OR 11
#define idBIT_AND 12
#define idADD 13
#define idSUB 14
#define idMUL 15
#define idDIV 16
#define idIF 17
#define idWHILE 18
#define idWRITE 19
#define idBLANK 20
#define idASSIGN 21
int errors; /* Счетчик ошибок */
typedef unsigned int word;
struct DICT
{
char *Name; /* Имя переменной */
word Ofs; /* Смещение переменной */
word Size; /* Длина массива, 0 - простая переменная */
struct DICT *Next; /* Следующая переменная */
};
typedef struct DICT DICT;
DICT *Dict = 0; /* Словарь */
word Ofs=0;
DICT *Find(char *Name);
DICT *Add (char *Name, word Size);
DICT *Test(DICT *Dict, word Array);
struct NODE
{
word ID;
word Value;
DICT *Var;
struct NODE *Left;
struct NODE *Right;
};
typedef struct NODE NODE;
NODE *Tree=0;
NODE *Node(word ID, word Value, DICT *Var, NODE *Left, NODE *Right);
void yyerror(char *s) /* Вызывается yyparse при ошибке */
{
errors++;
printf("%s\n", s);
}
%}
%no_lines /* Не включать директивы #line */
%union /* Элемент стека */
{
word Value; /* Число */
char *ID; /* Идентификатор */
NODE *Node; /* Элемент синтаксического дерева */
}
%start program /* Начальный символ */
%token <Value> NUMBER /* Число */
%token <ID> IDENTIFIER /* Идентификатор */
%token WORD BLOCK IF THEN WHILE DO WRITE BLANK END
%left '|' '&'
%left '<' LE '=' NE GE '>'
%left '-' '+'
%left '*' '/'
%type <Node> operators operator list expr cond
%%
/* Синтаксические правила */
program : declarations
BLOCK
operators
END
{
/*$3->Left = NULL;
Tree = $3;*/
Tree = $3->Right;
}
;
declarations : declaration
| declarations declaration
;
declaration : WORD identifiers ';'
;
identifiers : identifier
| identifiers ',' identifier
;
identifier : IDENTIFIER
{
Add($1, 0);
}
| IDENTIFIER '[' NUMBER ']'
{
Add($1, $3);
}
;
operators : operator
{
/*Дополнительный узел используется для построения списка */
$$ = Node(idEMPTY, 0, NULL, NULL, $1);
$$->Left = $$->Right;
}
| operators operator
{
$1->Left->Right = $2;
$1->Left = $1->Left->Right;
}
;
operator : IF cond THEN operators END
{
$$ = Node(idIF, 0, NULL, Node(idEMPTY, 0, NULL, $2, $4->Right), NULL);
}
| WHILE cond DO operators END
{
$$ = Node(idWHILE, 0, NULL, Node(idEMPTY, 0, NULL, Node(idEMPTY, 0, NULL, NULL, $2), $4->Right), NULL);
}
| WRITE list ';'
{
$$ = $2;
$2->ID = idWRITE;
$2->Right = NULL;
}
| BLANK
{
$$ = Node(idBLANK, 0, NULL, NULL, NULL);
}
| IDENTIFIER '=' expr ';'
{
$$ = Node(idASSIGN, 0, NULL, Node(idEMPTY, 0, Test(Find($1), 0), NULL, $3), NULL);
}
| IDENTIFIER '[' expr ']' '=' expr ';'
{
$$ = Node(idASSIGN, 0, NULL, Node(idEMPTY, 0, Test(Find($1), 1), $3, $6), NULL);
}
;
list : expr
{
$$ = Node(idEMPTY, 0, NULL, Node(idEMPTY, 0, NULL, $1, NULL), NULL);
$$->Right = $$->Left;
}
| list ',' expr
{
$1->Right->Right = Node(idEMPTY, 0, NULL, $3, NULL);
$1->Right = $1->Right->Right;
}
;
expr : NUMBER
{
$$ = Node(idNUMBER, $1, NULL, NULL, NULL);
}
| IDENTIFIER
{
$$ = Node(idVAR, 0, Test(Find($1), 0), NULL, NULL);
}
| IDENTIFIER '[' expr ']'
{
$$ = Node(idVAR, 0, Test(Find($1), 1), $3, NULL);
}
| expr '|' expr
{
$$ = Node(idBIT_OR, 0, NULL, $1, $3);
}
| expr '&' expr
{
$$ = Node(idBIT_AND, 0, NULL, $1, $3);
}
| expr '+' expr
{
$$ = Node(idADD, 0, NULL, $1, $3);
}
| expr '-' expr
{
$$ = Node(idSUB, 0, NULL, $1, $3);
}
| expr '*' expr
{
$$ = Node(idMUL, 0, NULL, $1, $3);
}
| expr '/' expr
{
$$ = Node(idDIV, 0, NULL, $1, $3);
}
| '(' expr ')'
{
$$ = $2;
}
;
cond : expr '<' expr
{
$$ = Node(idLT, 0, NULL, $1, $3);
}
| expr LE expr
{
$$ = Node(idLE, 0, NULL, $1, $3);
}
| expr '=' expr
{
$$ = Node(idEQ, 0, NULL, $1, $3);
}
| expr NE expr
{
$$ = Node(idNE, 0, NULL, $1, $3);
}
| expr GE expr
{
$$ = Node(idGE, 0, NULL, $1, $3);
}
| expr '>' expr
{
$$ = Node(idGT, 0, NULL, $1, $3);
}
| cond '|' cond
{
$$ = Node(idOR, 0, NULL, $1, $3);
}
| cond '&' cond
{
$$ = Node(idAND, 0, NULL, $1, $3);
}
| '(' cond ')'
{
$$ = $2;
}
;
%%
/* Программный код */
char *str(word N, word S)
{
static char *Digit="0123456789";
static char Buff [11];
word I;
word J;
word K;
if (S==0)
{
S=1;
}
I=0;
while (N>0 || S>0)
{
Buff[I++]=Digit[N%10];
if (S>0)
{
S--;
}
N/=10;
}
Buff[I]=0;
J=0;
K=I-1;
while (J<K)
{
char C =Buff[J];
Buff[J++]=Buff[K];
Buff[K--]=C;
}
return Buff;
}
DICT *Find(char *Name)
{
DICT *Ptr;
for (Ptr=Dict; Ptr!=NULL; Ptr=Ptr->Next)
{
if (strcmp(Ptr->Name, Name)==0)
{
break;
}
}
return Ptr;
}
DICT *Add (char *Name, word Size)
{
DICT *Ptr=Find(Name);
if (Ptr==NULL)
{
Ptr =(DICT *) malloc(sizeof(DICT));
Ptr->Name = strdup(Name);
Ptr->Ofs = Ofs; Ofs+=(Size>0)?2*Size:2;
Ptr->Size = Size;
Ptr->Next = Dict;
Dict = Ptr;
}
else
{
errors++;
printf("Переменная %s уже определена\n", Name);
}
return Ptr;
}
DICT *Test(DICT *Dict, word Array)
{
if (Dict!=NULL)
{
if (Dict->Size==0 && Array!=0)
{
errors++;
printf("Индексация переменной %s недопустима\n", Dict->Name);
}
else if (Dict->Size!=0 && Array==0)
{
errors++;
printf("Пропущен индекс массива %s\n", Dict->Name);
}
}
else
{
errors++;
printf("Переменная не определена\n");
}
return Dict;
}
NODE *Node(word ID, word Value, DICT *Var, NODE *Left, NODE *Right)
{
NODE *Ptr =(NODE *) malloc(sizeof(NODE));
Ptr->ID = ID;
Ptr->Value= Value;
Ptr->Var = Var;
Ptr->Left = Left;
Ptr->Right= Right;
return Ptr;
}
char Text[4096];
word pText;
FILE *out;
void Save(char Ch)
{
if (pText>=sizeof(Text))
{
fwrite(Text, 1, pText, out);
pText=0;
}
Text[pText++]=Ch;
}
void Decl(char *Inst)
{
word I=0;
while (Inst[I]!=0)
{
Save(Inst[I++]);
}
Save('\n');
}
void Emit(word L, char *Inst)
{
if (L!=0)
{
char *P=str(L, 5);
word I=0;
Save ('@');
while (P[I]!=0)
{
Save(P[I++]);
}
Save(':');
Save(' ');
}
else
{
word I=0;
while (I<8)
{
Save(' ');
I++;
}
}
Decl(Inst);
}
word Lbl (word ID)
{
switch (ID)
{
case idNUMBER:
case idVAR:
case idADD:
case idSUB:
case idMUL:
case idDIV:
case idASSIGN:
{
return 0;
}
}
return 1;
}
void Enum(NODE *P, word *L)
{
if (P==NULL)
{
return;
}
Enum(P->Left, L);
if (Lbl(P->ID)!=0)
{
P->Value=(*L)++;
}
Enum(P->Right, L);
}
void Code(NODE *P, word F, word T, word M)
{
char Buff [128];
if (P->ID==idNUMBER)
{
Emit(0, strcat(strcpy(Buff, "mov AX,"), str(P->Value, 0)));
}
else if (P->ID==idVAR)
{
if (P->Left)
{
Code(P->Left, 0, 0, 0);
Emit(0, "shl AX,1");
Emit(0, "mov DI,AX");
Emit(0, strcat(strcat(strcpy(Buff, "mov AX,DS:[DI+"), str(P->Var->Ofs, 0)), "]"));
}
else
{
Emit(0, strcat(strcat(strcpy(Buff, "mov AX,DS:["), str(P->Var->Ofs, 0)), "]"));
}
}
else if (P->ID==idOR)
{
if (T==0)
{
Code(P->Left, 0, M, P->Value);
Emit(P->Value,"nop");
Code(P->Right, F, 0, M);
}
else
{
Code(P->Left, 0, T, P->Value);
Emit(P->Value,"nop");
Code(P->Right, 0, T, M);
}
}
else if (P->ID==idAND)
{
if (T==0)
{
Code(P->Left, F, 0, P->Value);
Emit(P->Value,"nop");
Code(P->Right, F, 0, M);
}
else
{
Code(P->Left, M, 0, P->Value);
Emit(P->Value,"nop");
Code(P->Right, 0, T, M);
}
}
else if (idLT<=P->ID && P->ID<=idDIV)
{
Code(P->Right, 0, 0, 0);
Emit(0, "push AX");
Code(P->Left, 0, 0, 0);
Emit(0, "pop BX");
if (idLT<=P->ID && P->ID<=idGT)
{
word ID=P->ID;
Emit(0,"cmp AX, BX");
if (T==0)
{
if (ID==idLT)
{
ID=idGE;
}
else if (ID==idLE)
{
ID=idGT;
}
else if (ID==idEQ)
{
ID=idNE;
}
else if (ID==idNE)
{
ID=idEQ;
}
else if (ID==idGE)
{
ID=idLT;
}
else if (ID==idGT)
{
ID=idLE;
}
T=F;
F=0;
}
if (ID==idLT)
{
Emit(0, strcat(strcpy(Buff, "jae @"), str(P->Value, 5)));
}
else if (ID==idLE)
{
Emit(0, strcat(strcpy(Buff, "ja @"), str(P->Value, 5)));
}
else if (ID==idEQ)
{
Emit(0, strcat(strcpy(Buff, "jne @"), str(P->Value, 5)));
}
else if (ID==idNE)
{
Emit(0, strcat(strcpy(Buff, "je @"), str(P->Value, 5)));
}
else if (ID==idGE)
{
Emit(0, strcat(strcpy(Buff, "jb @"), str(P->Value, 5)));
}
else if (ID==idGT)
{
Emit(0, strcat(strcpy(Buff, "jbe @"), str(P->Value, 5)));
}
Emit(0, strcat(strcpy(Buff, "jmp @"), str(T, 5)));
Emit(P->Value, "nop");
}
else if (P->ID==idBIT_OR)
{
Emit(0,"or AX,BX");
}
else if (P->ID==idBIT_AND)
{
Emit(0,"and AX,BX");
}
else if (P->ID==idADD)
{
Emit(0,"add AX,BX");
}
else if (P->ID==idSUB)
{
Emit(0,"sub AX,BX");
}
else if (P->ID==idMUL)
{
Emit(0,"mul BX");
}
else if (P->ID==idDIV)
{
Emit(0,"xor DX,DX");
Emit(0,"div BX");
}
}
else if (P->ID==idIF)
{
F=P->Value;
P=P->Left;
Code(P->Left, F, 0, P->Value);
Emit(P->Value,"nop");
P=P->Right;
while (P!=NULL)
{
Code(P, 0, 0, 0);
P=P->Right;
}
Emit(F, "nop");
}
else if (P->ID==idWHILE)
{
word L;
F=P->Value;
P=P->Left;
T=P->Value;
L=P->Left->Value;
Emit(L, "nop");
Code(P ->Left->Right, F, 0, T);
Emit(T, "nop");
P=P->Right;
while (P!=NULL)
{
Code(P, 0, 0, 0);
P=P->Right;
}
Emit(0, strcat(strcpy(Buff, "jmp @"), str(L, 5)));
Emit(F,"nop");
}
else if (P->ID==idWRITE)
{
P=P->Left;
while (P!=NULL)
{
Code(P->Left, 0, 0, 0);
Emit(0, "mov CX,8");
Emit(0, "call @WRITE");
P=P->Right;
}
Emit(0,"mov AH, 2");
Emit(0,"mov DL,13");
Emit(0,"int 21H");
Emit(0,"mov AH, 2");
Emit(0,"mov DL,10");
Emit(0,"int 21H");
}
else if (P->ID==idBLANK)
{
Emit(0,"mov AH, 2");
Emit(0,"mov DL,13");
Emit(0,"int 21H");
Emit(0,"mov AH, 2");
Emit(0,"mov DL,10");
Emit(0,"int 21H");
}
else if (P->ID==idASSIGN)
{
P=P->Left;
Code(P->Right, 0, 0, 0);
if (P->Left)
{
Emit(0, "push AX");
Code(P->Left, 0, 0, 0);
Emit(0, "shl AX,1");
Emit(0, "mov DI,AX");
Emit(0, "pop AX");
Emit(0, strcat(strcat(strcpy(Buff, "mov DS:[DI+"), str(P->Var->Ofs, 0)), "],AX"));
}
else
{
Emit(0, strcat(strcat(strcpy(Buff, "mov DS:["), str(P->Var->Ofs, 0)), "],AX"));
}
}
}
void main(int argc, char *argv[])
{
extern FILE *yyin;
yyin=fopen(argv[1], "r");
/*yydebug=1;*/
errors =0;
yyparse();
if (errors==0)
{
NODE *P;
word L;
L=1;
Enum(Tree, &L);
out=fopen(argv[2], "w");
Emit(0,"mov AX,DS");
Emit(0,"add AX,4096");
Emit(0,"mov DS,AX");
P=Tree;
while (P!=NULL)
{
Code(P, 0, 0, 0);
P=P->Right;
}
Emit(0,"mov AX,4C00H");
Emit(0,"int 21H");
Decl("@WRITE: dec CX");
Decl(" xor DX,DX");
Decl(" mov BX,10");
Decl(" div BX");
Decl(" push DX");
Decl(" or AX,AX");
Decl(" jz @SPACE");
Decl(" call @WRITE");
Decl(" jmp @DIGIT");
Decl("@SPACE: mov AH, 2");
Decl(" mov DL,32");
Decl(" int 21H");
Decl(" dec CX");
Decl(" jnz @SPACE");
Decl("@DIGIT: mov AH, 2");
Decl(" pop DX");
Decl(" add DL,48");
Decl(" int 21H");
Decl(" retn");
if (pText>0)
{
fwrite(Text, 1, pText, out);
}
fclose(out);
}
}
#include "lexyy.c" /* Сканер */
]]>
Сайт создан в системе
uCoz