Proiectarea unui analizor 
sintactic LALR(1)Tabela de simboluri. Analiza de domeniu

Generatorul de analizoare sintactice BISON




Principiul de functionare a programului Bison

Bison este un generator de analizoare sintactice pentru gramatici LALR(1) si constituie unul dintre utilitarele standard ale sistemelor de operare Unix. Se mentioneaza ca prezentul document se bazeaza pe versiunea 1.28 a programului Bison.

Programul Bison primeste la intrare un fisier continand o specificatie a gramaticii pe care urmeaza sa o recunoasca si genereaza un program C ce contine codul de analiza sintactica. Sintaxa de specificare a gramaticii este o varianta a formei BNF (Backus-Naur Form). Functia de analiza din codul generat se numeste yyparse( )

Fisierul ce contine specificatia gramaticii este un fisier text care poate avea orice nume acceptat de sistemul de operare. Din considerente istorice se recomanda ca fisierul de specificatie sa aiba extensia .y (bison este succesorul utilitarului yacc).

Programul C rezultat este memorat intr-un fisier care are implicit acelasi nume cu fisierul de specificare (mai putin extensia .y) la care se adauga sufixul .tab.c (utilizatorul poate solicita explicit un alt nume). In afara de codul generat automat, utilizatorul mai trebuie sa prevada cel putin trei functii C:

In continuare se compileaza programul obtinut, rezultand astfel analizorul sintactic executabil.

Lansarea in executie a programului Bison

Lansarea in executie a programului Bison se realizeaza cu comanda

bison [optiuni] [nume_fisier_specificatii]

Cateva dintre optiunile liniei de comanda mai des utilizate sunt:  

Structura programului de specificatie


Programul de specificatie este format din patru mari sectiuni:

%{
declaratii C
%}
declaratii Bison
%%
reguli gramaticale 
%%
cod C (definit de utilizator)

 

Sectiunea de declaratii C

Sectiunea de declaratii C poate contine directive, macrodefinitii si declaratii de functii si variabile care sunt folosite in actiunile semantice din regulile gramaticii. Aceste declaratii sunt copiate la inceputul codului generat, inainte de definitia functiei yyparse. Daca nu este nevoie de declaratii C, atunci intreaga sectiune poate lipsi (inclusiv delimitatorii "%{" si "%}").

 

Sectiunea de declaratii Bison

Aici se declara atomii lexicali (simbolurile terminale), tipurile asociate atributelor simbolurilor terminale si neterminale, precedenta si asociativitetea operatorilor, etc.

Principalele declaratii Bison sunt:

 

Sectiunea de reguli gramaticale
Sectiunea de reguli gramaticale contine una sau mai multe reguli gramaticale. Implicit, prima regula din sectiune este cea care descrie derivarile posibile pentru simbolul de start al gramaticii.

Sintaxa de scriere a regulilor gramaticale este urmatoarea:

rezultat:    alternativa1

                |    alternativa2

                ...

                ;

unde 

 

Sectiunea de cod C (definit de utilizator)
Sectiunea de cod C definit de utilizator este copiata, fara modificari, la sfarsitul fisierului in care se afla codul generat automat. Aici este locul potrivit pentru definirea functiilor main, yyerror si eventual yylex.

 

Tratarea erorilor in Bison

 Analizorul sintactic generat de Bison sesizeaza, in mod implicit, o eroare sintactica atunci cind atomul lexical care urmeaza nu poate fi prelucrat conform regulilor sintactice si in contextul creat (continutul stivei analizorului). Utilizatorul poate genera o situatie de eroare sintactica si in mod explicit, in cadrul unei actiuni, prin invocarea macroului YYERROR. Semnalarea erorii se realizeaza prin apelarea functiei yyerror() cu un argument reprezentand mesajul de eroare. Apelul functiei yyerror() se face fie automat, din functia yyparse(), fie imediat inainte de invocarea lui YYERROR. Mesajul implicit, in cazul erorilor sintactice depistate automat, este parse error, dar utilizatorul poate obtine si mesaje “mult mai sugestive” daca defineste simbolul YYERROR_VERBOSE in sectiunea de declaratii (nu conteaza valoarea asociata acestuia).

 

Revenirea din erori

 Dupa revenirea din functia yyerror(), in functia yyparse(), analizorul sintactic va incerca “revenirea din eroare”. Revenirea din eroare si continuarea compilarii este posibila doar daca in sectiunea de reguli sunt prevazute si productii de eroare corespunzatoare. In absenta acestor productii de eroare, analizorul sintactic isi termina executia si genereaza un cod de retur diferit de zero.

 

Productii de eroare

 In tentativa de revenire din eroare, analizorul sintactic introduce, in mod fortat, in sirul de intrare un simbol special cu numele error. Simbolul error este predefinit in limbajul recunoscut de Bison si este considerat simbol terminal (token, atom) cu destinatie speciala pentru tratarea erorilor. Utilizatorul poate prevedea cateva reguli speciale, numite productii de eroare, in sectiunea de reguli, care sa contina pseudo-atomul error. Daca una din aceste reguli speciale se “potriveste” cu situatia nou creata (prin introducerea fortata a lui error in sirul de intrare), procesul de analza (functia yyparse) poate continua. “Potrivirea” regulilor, care reprezinta productii de eroare, este interpretata de catre Bison intr-o maniera foarte larga, in sensul ca daca “potrivirea stricta” nu este aplicabila, atunci se fac noi tentative de “aranjara a unei potriviri” dupa cum urmeaza. Mai intai se deruleaza inapoi contextele, prin scoaterea succesiva a starilor din stiva analizorului, pana cand se ajunge intr-o stare care sa permita deplasarea simbolului error. In continuare se incearca deplasarea, conform regulii date de productia de eroare, a atomului aflat in sirul de intrare la momentul sesizarii erorii (atomul care a declansat eroarea). Daca acest lucru nu este posibil, se abandoneaza atomul si se citesc noi atomi pana cand se va realiza potrivirea cu regula. Atomii care nu s-au potrivit regulii sunt si ei abandonati.

 Modul de construire a productiilor de eroare determina, in final, strategia de revenire din erori. O strategie simpla si eficienta este ca simbolul error sa apara la sfarsitul productiilor de eroare, intercalat intre doua simboluri terminale. Astfel se incerca reducerea intregii constructii sintactice, in care apare eroarea, fara a mai semnala alte erori in lant. Binenteles, aceasta schema functioneaza doar daca atomul care incheie constructia apare corect in textul sursa. In caz contrar revenirea din eroare va trebui sa se faca cu o alta productie de eroare, la un nivel mai sus in ierarhia regulilor sintactice (mai aproape de simbolui de start al gramaticii). Totusi, pentru a preveni semnalarea erorilor sintactice in lant, cauzate de o singura gresala in textul sursa, analizorul generat de Bison emite un mesaj de eroare dupa care suspenda emiterea celorlalte mesaje. Reluarea semnalarii mesajelor de eroare se realizeaza fie prin apelul macroului yyerrok (in cadrul unei actiuni semantice asociate unei reguli), fie in mod automat dupa prelucrarea cu succes a trei atomi consecutivi.

 

Descrierea regulilor semantice in Bison

Semantica limbajului este data de actiunile pe care le executa compilatorul in momentul in care recunoaste anumite constructii sintactice. Rezultatul actiunilor semantice depinde in mare masura de valorile care intra in calcul si care, de regula, reprezinta atributele asociate simbolurilor (terminale sau neterminale). Pentru aceasta, programul Bison permite atasarea la oricare simbol al gramaticii a unei valori semantice, pe post de atribut. Tipul implicit pentru atribute este int. Pentru a preciza alt tip pentru atributele tuturor simbolurilor se introduce definitia:

#define YYSTYPE tip_explicit

in sectiunea de declaratii C. Pentru a preciza tipuri distincte pentru atributele diferitelor simboluri sunt necesare doua etape:

Actiunile semantice se pot intercala printre simbolurile productiilor din sectiunea de reguli si au forma:

{ instructiuni C }

De regula, productiile au o singura actiune semantica plasata la sfarsitul productiei. Actiunea tipica este cea care calculeaza valoarea atributului pentru simbolul rezultat (din partea stanga a productiei) in functie de atributele simbolurilor care compun alternativa regulii sintactice (din partea dreapta a productiei). Codul C din cadrul actiunii semantice poate referi atributul pentru simbolul rezultat prin constructia $$ iar atributele simbolurilor care compun alternativa prin constructii de forma $n, unde n este numarul de ordine al simbolului din cadrul alternativei (eventualele actiuni semantice intercalate printre simboluri intra si ele la numar).


 

Exemplu

In exemplul urmator este prezentat un fisier de specificatii Bison pentru un subset foarte restrans al limbajului Pascal si fisierul de specificatii Flex corespunzator. Exemplul ilustreaza principalele aspecte enuntate in paragrafele de mai sus. Presupunand ca numele acestor fisiere sunt sspascal.y si respectiv sspascal.lxi, comenzile necesare pentru a genera analizorul corespunzator si pentru a-l lansa in executie sunt:

$ bison -d sspascal.y

$ flex sspascal.lxi

$ gcc sspascal.tab.c lex.yy.c -o cpascal

$ ./cpascal nume_fisier_sursa

In ultima comanda nume_fisier_sursa poate lipsi, caz in care se va astepta introducerea textului sursa de la stdin (tastatura).

Fisierul sspascal.y

%{
#include <stdio.h>
#include <stdlib.h>
#define YYDEBUG 1
#define TIP_INT 1
#define TIP_REAL 2
#define TIP_CAR 3
double stiva[20];
int sp;
void push(double x)
{ stiva[sp++]=x; }
double pop()
{ return stiva[--sp]; }
%}
%union {
  	int l_val;
	char *p_val;
}
%token BEGINN
%token CONST
%token DO
%token ELSE
%token END
%token IF
%token PRINT
%token PROGRAM
%token READ
%token THEN
%token VAR
%token WHILE
%token ID
%token <p_val> CONST_INT
%token <p_val> CONST_REAL
%token <p_val> CONST_CAR
%token CONST_SIR
%token CHAR
%token INTEGER
%token REAL
%token ATRIB
%token NE
%token LE
%token GE
%left '+' '-'
%left DIV MOD '*' '/'
%left OR
%left AND
%left NOT
%type <l_val> expr_stat factor_stat constanta
%%
prog_sursa:	PROGRAM ID ';' bloc '.'
		;
bloc:		sect_const sect_var instr_comp
		;
sect_const:	/* empty */
		| CONST lista_const
		;
lista_const:	decl_const
		| lista_const decl_const
		;
sect_var:	/* empty */
		| VAR lista_var
		;
lista_var:	decl_var
		| lista_var decl_var
		;
decl_const:	ID '=' {sp=0;} expr_stat ';'	{
		printf("*** %d %g ***\n", $4, pop());
					}
		;
decl_var:	lista_id ':' tip ';'
		;
lista_id:	ID
		| lista_id ',' ID
		;
tip:		tip_simplu
		;
tip_simplu:	INTEGER
		| REAL
		| CHAR
		;
expr_stat:	factor_stat
		| expr_stat '+' expr_stat	{
			if($1==TIP_REAL || $3==TIP_REAL) $$=TIP_REAL;
			else if($1==TIP_CAR) $$=TIP_CAR;
				else $$=TIP_INT;
			push(pop()+pop());
						}
		| expr_stat '-' expr_stat	{
			if($1==TIP_REAL || $3==TIP_REAL) $$=TIP_REAL;
			else if($1==TIP_CAR) $$=TIP_CAR;
				else $$=TIP_INT;
			push(-pop()+pop());
						}
		| expr_stat '*' expr_stat	{
			if($1==TIP_REAL || $3==TIP_REAL) $$=TIP_REAL;
			else if($1==TIP_CAR) $$=TIP_CAR;
				else $$=TIP_INT;
			push(pop()*pop());
						}
		| expr_stat '/' expr_stat	
		| expr_stat DIV expr_stat
		| expr_stat MOD expr_stat
		;
factor_stat:	ID		{}
		| constanta
		| '(' expr_stat ')'	{$$ = $2;}
		;
constanta:	CONST_INT	{
			$$ = TIP_INT;
			push(atof($1));
				}
		| CONST_REAL	{
			$$ = TIP_REAL;
			push(atof($1));
				}
		| CONST_CAR	{
			$$ = TIP_CAR;
			push((double)$1[0]);
				}
		;
instr_comp:	BEGINN lista_instr END
		;
lista_instr:	instr
		| lista_instr ';' instr
		;
instr:		/* empty */
		| instr_atrib
		| instr_if
		| instr_while
		| instr_comp
		| instr_read
		| instr_print
		;
instr_atrib:	variabila ATRIB expresie
		;
variabila:	ID
		| ID '[' expresie ']'
		| ID '.' ID
		;
expresie:	factor
		| expresie '+' expresie
		| expresie '-' expresie
		| expresie '*' expresie
		| expresie '/' expresie
		| expresie DIV expresie
		| expresie MOD expresie
		;
factor:		ID
		| constanta {}
		| ID '(' lista_expr ')'
		| '(' expresie ')'
		| ID '[' expresie ']'
		| ID '.' ID
		;
lista_expr:	expresie
		| lista_expr ',' expresie
		;
instr_if:	IF conditie THEN instr ramura_else
		;
ramura_else:	/* empty */
		ELSE instr
		;
conditie:	expr_logica
		| expresie op_rel expresie
		;
expr_logica:	factor_logic
		| expr_logica AND expr_logica
		| expr_logica OR expr_logica
		;
factor_logic:	'(' conditie ')'
		| NOT factor_logic
		;
op_rel:		'='
		| '<'
		| '>'
		| NE
		| LE
		| GE
		;
instr_while:	WHILE conditie DO instr
		;
instr_print:	PRINT '(' lista_elem ')'
		;
lista_elem:	element
		| lista_elem ',' element
		;
element:	expresie
		| CONST_SIR
		;
instr_read:	READ '(' lista_variab ')'
		;
lista_variab:	variabila
		| lista_variab ',' variabila
		;
%%
yyerror(char *s)
{
  printf("%s\n", s);
}
extern FILE *yyin;
main(int argc, char **argv)
{
  if(argc>1) yyin = fopen(argv[1], "r");
  if((argc>2)&&(!strcmp(argv[2],"-d"))) yydebug = 1;
  if(!yyparse()) fprintf(stderr,"\tO.K.\n");
}

Fisierul sspascal.y poate fi accesat aici.

 

Fisierul sspascal.lex

%{
#include "sspascal.tab.h"
%}
%option noyywrap
%option caseless
LITERA		[A-Za-z_]
CIFRA		[0-9A-Fa-f]
CIFRA_ZEC	[0-9]
IDENTIFICATOR	{LITERA}({LITERA}|{CIFRA_ZEC})*
NR_BAZA10	{CIFRA_ZEC}+
EXPON		(E|e)("+"?|"-"){CIFRA_ZEC}{1,2}
NR_REAL		{NR_BAZA10}"."{NR_BAZA10}{EXPON}?
DELIMIT_1	[;.,:]
OPERATOR_1	[+*/()<>=]|"-"|"["|"]"
COMENT		"{"[^}]*"}"
SIR_CAR		["][^\n"]*["]
CARACTER	"'"[^\n]"'"
%%
[ \t\n]
{COMENT}
begin		{return BEGINN;}
const		{return CONST;}
do		{return DO;}
else		{return ELSE;}
end		{return END;}
if		{return IF;}
print		{return PRINT;}
program		{return PROGRAM;}
read		{return READ;}
then		{return THEN;}
var		{return VAR;}
while		{return WHILE;}
char		{return CHAR;}
integer		{return INTEGER;}
real		{return REAL;}
":="		{return ATRIB;}
"<>"		{return NE;}
"<="		{return LE;}
">="		{return GE;}
div		{return DIV;}
mod		{return MOD;}
or		{return OR;}
and		{return AND;}
not		{return NOT;}
{IDENTIFICATOR}	{return ID;}
{NR_BAZA10}	{
	yylval.p_val = yytext;
	return CONST_INT;
		}
{NR_REAL}	{
	yylval.p_val = yytext;
	return CONST_REAL;
		}
{CARACTER}	{
	yylval.p_val = yytext;
	return CONST_CAR;
		}
{SIR_CAR}	{return CONST_SIR;}
{DELIMIT_1}	{return yytext[0];}
{OPERATOR_1}	{return yytext[0];}
%%
Fisierul sspascal.lxi poate fi accesat aici.

Desfasurarea lucrarii

Se va dezvolta si modifica exemplul de mai sus asfel incat sa corespunda gramaticii descrise in Anexa A si Anexa B.

 

Proiectarea
unui analizor sintactic LALR(1)Tabela de simboluri. Analiza de domeniu