Parser SQL w C – Flex, Bison czyli YACC problem

Ktoś by pewnie spytał się po co generować własny parser plików zapytań SQL, skoro są one walidowane w każdym silniku bazodanowym. Jedne z możliwych odpowiedzi to: hobbistycznie, lub też dla celów akademickich, czyli aby pokazać zasadę działania uniksowych parserów.

Bison (generator utworzony w ramach projektu GNU) zazwyczaj jest używany razem z programem flex (program podobny do lex, też wolny). Te dwa narzędzia pozwolą również na napisanie pretty-printera, a w zasadzie nieograniczona ilość na kod C w instrukcji main() pozwala pisać całkiem przyzwoite programy.

Pliki z gramatyką, które będziemy tworzyć, są to pliki tekstowe składające się z trzech części oddzielonych od siebie podwójnym znakiem procentu (“%%”) w kolejności: deklaracje, reguły gramatyczne, kod w języku C. Plik z rozszerzeniem .y jest to program dla bisona, natomiast plik z rozszerzeniem .l jest to program flex’a.

Pisanie parserów w C++ jest dużo trudniejsze (z wykorzystaniem g++ a nawet flex++), tutaj można znaleźć przykładowy tutorial:
http://tldp.org/HOWTO/Lex-YACC-HOWTO-5.html

sql.l:

%{
#include “sql.tab.h” //<>
#include <stdlib.h>
#include <string.h>

/*prototypy funkcji*/
void lexError(const char *);
static int getToken(const char *);

%}

%option yylineno

single_line_comment        “//”.*|”///”.*
white_space                [ \t\n\r]

%%

“select” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext));  return SELECT;}
“from” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext));  return FROM;}
“where” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext));  return WHERE;}
“order” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext));  return ORDER;}
“group” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext));  return GROUP;}
“by” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return BY;}
“like” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return LIKE;}
“as” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return AS;}
“insert” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return INSERT;}
“update” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return UPDATE;}
“delete” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return DELETE;}
“set” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return SET;}
“into” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return INTO;}
“values” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return VALUES;}
“join” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return JOIN;}
“on” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return ON;}

“primary” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return PRIMARY;}
“foreign” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return FOREIGN;}
“references” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return REFERENCES;}
“key” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return KEY;}
“grant” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return GRANT;}
“create” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return CREATE;}
“alter” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return ALTER;}
“to” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return TO;}
“with grant option” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return WITHGRANT;}

“table” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return TABLE;}
“database” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return DATABASE;}

“–” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return SC;}

“(” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext));  return START;}
“)” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext));  return END;}

=|==|=!|<=|>=|<|> {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext));  return ZNAK;}

“;” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext));  return SR;}
“*” {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext));  return AST;}

[0-9]+ {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext));  return LICZBA;}
[0-9A-Za-z”‘,]+ {yylval=(char*) malloc (strlen(yytext)); strncpy(yylval, yytext, strlen(yytext)); return TEXT;}

[:space:]+    ;
[ \n|\t]+     ;
“/*”(.|\n)*”*/”  ;

%%

/*metoda zwraca opis bledu leksykalnego*/
void lexError(const char *msg)
{
fprintf(stderr,”LINE:%d:lexical error (%s) [TEXT: %s]\n”, yylineno, msg, yytext);
}

sql.y:

%{
#include <stdio.h>
#include <stdlib.h>
#include “lex.yy.c”

typedef char* string;

int test = 1;
char* beg;

int yyerror(char *s){
printf(“Linia nr %d\nBlad %s\n”, yylineno, s);
fprintf(yyout, “Linia nr %d\nBlad %s\n”, yylineno, s);
test = 0;
};

int yylex(void);

#define YYERROR_VERBOSE
#define FALSE 0
#define TRUE 1

/*Numer linii parsera.*/
extern int yylineno;

/*Plik wejscia i wyjscia.*/
extern FILE *yyin, *yyout;

struct Intern{
string pl;
string en;
};

%}

%token SELECT
%token FROM
%token WHERE
%token ORDER
%token GROUP
%token BY
%token LIKE
%token AS
%token INSERT
%token UPDATE
%token DELETE
%token SET
%token INTO
%token VALUES
%token JOIN
%token ON

%token PRIMARY
%token FOREIGN
%token KEY
%token GRANT
%token CREATE
%token DROP
%token ALTER
%token REFERENCES
%token TO
%token WITHGRANT

%token DATABASE
%token TABLE

%token START
%token END
%token SR
%token AST
%token ZNAK
%token LICZBA
%token TEXT

%token SC

/*poczatek programu*/

%%

/* SQL 1992 */

statement_sql92: statement_sql92 SELECT TEXT FROM TEXT SR {
printf(“select %s from %s;\n”, $3, $5);
fprintf(yyout, “select %s from %s;\n”, $3, $5);
}
| statement_sql92 select_ast_st
| statement_sql92 select_where_st
| statement_sql92 delete_st
| statement_sql92 insert_st
| statement_sql92 update_st
| statement_sql92 statement_ddl
| statement_sql92 grant_st
| statement_sql92 other_statement {printf(“\n”);}
| ‘\n’
|
;

select_ast_st: SELECT AST FROM TEXT
{
printf(“select * from %s;\n”, $4);
fprintf(yyout, “select * from %s;\n”, $4);
}
| select_ast_st WHERE TEXT ZNAK TEXT
| select_ast_st ORDER BY TEXT
| select_ast_st SR
;

select_where_st: SELECT TEXT FROM TEXT WHERE TEXT ZNAK TEXT {
printf(“select %s from %s where %s %s %s”, $2, $4, $6, $7, $8);
fprintf(yyout, “select %s from %s where %s %s %s”, $2, $4, $6, $7, $8);
}
| select_where_st ORDER BY TEXT {
printf(” order by %s”, $4);
fprintf(yyout, ” order by %s”, $4);
}
| select_where_st SR {
printf(“;\n”);
fprintf(yyout, “;\n”);
}
;

delete_st: DELETE FROM TEXT SR {
printf(“delete from %s;\n”, $3);
fprintf(yyout, “delete from %s;\n”, $3);
}
| DELETE FROM TEXT WHERE TEXT ZNAK TEXT SR {
printf(“delete from %s where %s %s %s;\n”, $3, $5, $6, $7);
fprintf(yyout, “delete from %s where %s %s %s;\n”, $3, $5, $6, $7);
}
;

insert_st: INSERT INTO TEXT START TEXT END VALUES START TEXT END SR {
printf(“insert into %s (%s) values (%s);\n”, $3, $5, $9);
fprintf(yyout, “insert into %s (%s) values (%s);\n”, $3, $5, $9);
}
;

update_st: UPDATE TEXT SET TEXT ZNAK TEXT WHERE TEXT ZNAK TEXT SR {
printf(“update %s set %s %s %s where %s %s %s;\n”, $2, $4, $5, $6, $8, $9, $10);
fprintf(yyout, “update %s set %s %s %s where %s %s %s;\n”, $2, $4, $5, $6, $8, $9, $10);
}
;

/* DATABASE DESIGN LANGUAGE – DLL */

statement_ddl: drop_st
| create_st
| alter_st
;

drop_st: DROP TABLE TEXT SR {
printf(“drop table %s;\n”, $3);
fprintf(yyout, “drop table %s;\n”, $3);
}
;

create_st: CREATE create_table
| CREATE create_database
;

create_table: TABLE TEXT START TEXT {
printf(“create table %s(%s”, $2, $4);
fprintf(yyout, “create table %s(%s”, $2, $4);
}
| create_table TEXT {
printf(” %s”, $2);
fprintf(yyout, ” %s”, $2);
}
| create_table END SR {
printf(“);\n”);
fprintf(yyout, “);\n”);
}
;

create_database: DATABASE TEXT SR {
printf(“create database %s;\n”, $2);
fprintf(yyout, “create database %s;\n”, $2);
}
;

alter_st: ALTER TEXT START TEXT END SR {
printf(“alter %s (%s);\n”, $2, $3);
fprintf(yyout, “alter %s (%s);\n”, $2, $3);
}
;

/* STATEMENTS DATA CONTROL LANGUAGE */

grant_st: GRANT TEXT ON TEXT TO TEXT WITHGRANT SR {
printf(“grant %s on %s to %s with grant option;\n”, $2, $4, $6);
//fprintf(yyout, ” on %s to %s with grant option;”, $3, $5);
}
;

/* OTHER STATEMENTS LIKE SINGLE LINE COMMENTS AND BLOCK COMMENTS */

other_statement: SC {
printf(“– “);
fprintf(yyout, “– “);
}
| other_statement TEXT {
printf(” %s”, $2);
fprintf(yyout, ” %s”, $2);
}
;

%%

main(int argc, char *argv[]) {

int revokeL = TRUE;

struct Intern lang[] = { {“1) Wybierz standard jezyka zapytan\n”, “1) Choose SQL standard\n”},
{“2) Wybierz jezyk\n”, “2) Choose language\n”},
{“3) Waliduj skrypt SQL\n”, “3) Validate SQL file\n”},
{“4) Formatuj skrypt SQL\n”, “4) Pretty-print SQL script\n”},
{“5) Wyjscie\n”, “5) Exit from program\n” }
};

FILE *fp = NULL;
fpos_t dlugosc;
char stringInput;
if(argc != 3) {
printf(“Uzycie: %s <nazwa pliku wejscia> <nazwa pliku wyjscia>\n”, argv[0]);
do{
printf(“Czy chcesz przejsc do trybu interaktywnego (menu programu) ? [T/N]”);
stringInput = getchar();
__fpurge(stdin);
}while(stringInput != ‘T’ && stringInput != ‘N’);
if(stringInput == ‘N’)
return 1;
}
int choice = 0;

yyin = stdin;
yyout = stdout;

/* Jezeli zostal zdefiniowany plik wejscia i/lub wyjscia */
if (argc >= 2)
{
/* Otworz plik do czytania */
yyin = fopen(argv[1], “r”);

/* Jezeli nie udalo sie otworzyc pliku */
if(yyin == NULL)
{
fprintf(stderr, “ERROR: Input file not exists.\n”);
return 1;
}

/* Jezeli zostal zdefiniowany plik wyjscia */
if(argc >= 3)
{
/* Otworz plik do zapisu */
yyout = fopen(argv[2], “w”);
}

/* Jezeli nie udalo sie otworzy pliku wyjscia */
if(yyout == NULL)
{
fprintf(stderr, “ERROR: Output file not exists.\n”);

return 1;
}
}

while(choice != 4)
{
printf(“\nSQL miniStudio:\n”);
if(revokeL) printf(lang[0].pl); else printf(lang[0].en);
if(revokeL) printf(lang[1].pl); else printf(lang[1].en);
if(revokeL) printf(lang[2].pl); else printf(lang[2].en);
if(revokeL) printf(lang[3].pl); else printf(lang[3].en);
if(revokeL) printf(lang[4].pl); else printf(lang[4].en);

scanf(“%d”,&choice);

switch(choice)
{
case 1:
{ // wybierz standard
break; }

case 2:
{ // wybierz jezyk
if(revokeL){
revokeL = FALSE;
printf(“\nLanguage changed to ENGLISH!\n”);
} else{
revokeL = TRUE;
printf(“\nZmieniono jezyk na POLSKI!\n”);
}

break; }

case 3:
{ // waliduj skrypt

yyparse();
if(test){
printf(“Test OK!\n”);
fprintf(yyout, “Test OK!\n”);
}

break; }

case 4:
{ // formatuj
break; }

case 5:
{ // wyjscie
exit(0);
break; }

default:
{ break; }
}

}

}

dane wejściowe:

select fadsiouuwaruwf from ffsadfadsfasdfasfs;
select fadsiouuwaruwf from ffsadfadsfasdfasfs;
select
fasdfagtergddfa49384934
from ffsadfadsfasdfasfs;
select fadsiouuwaruwf from ffsadfadsfasdfasfs;
select fadsiouuwaruwf from ffsadfadsfasdfasfs;
select fadsiouuwaruwf from ffsadfadsfasdfasfs;
select * from tabelka;

select kolumna
from tabela;

select dsfy87dsayfsadf7 from ffsadfadsfasdfasfs;
select kjfds8ay7f8as8f    from ffsadfadsfasdfasfs;
delete from pracownicy;
select fadsiouuwaruwf from ffsadfadsfasdfasfs;

update tabelka set umowa = ‘OK’ where umowa = NULL;

delete from pracownicy where imie = ‘andrzej’;

insert into tabelka(kol1,kol2) values(‘JaN’,’Kowalski’);

select TYTUL from BOOK WHERE   autor = ‘Profesor’   ORDER BY tytul;

select fadsiouuwaruwf from ffsadfadsfasdfasfs;
select fadsiouuwaruwf from ffsadfadsfasdfasfs;
delete from zamowienia;
select fadsiouuwaruwf from ffsadfadsfasdfasfs;

— komentarz, ponizej instrukcje ddl czyli tworzenia baz

create database testowa;
create database drugabazka;

create table waznedane (kol1 int, wartosc varchar);

create table fjdskfjkldsfkl (kol2 int, kol4 int, kol3 bool);

grant uprawnienie on employee to piotr with grant option;

wyjście:

select fadsiouuwaruwf from ffsadfadsfasdfasfs;
select fadsiouuwaruwf from ffsadfadsfasdfasfs;
select fasdfagtergddfa49384934 from ffsadfadsfasdfasfs;
select fadsiouuwaruwf from ffsadfadsfasdfasfs;
select fadsiouuwaruwf from ffsadfadsfasdfasfs;
select fadsiouuwaruwf from ffsadfadsfasdfasfs;
select * from tabelka;
select kolumna from tabela;
select dsfy87dsayfsadf7 from ffsadfadsfasdfasfs;
select kjfds8ay7f8as8f from ffsadfadsfasdfasfs;
delete from pracownicy;
select fadsiouuwaruwf from ffsadfadsfasdfasfs;
update tabelka set umowa = ‘OK’ where umowa = NULL;
delete from pracownicy where imie = ‘andrzej’;
insert into tabelka (kol1,kol2) values (‘JaN’,’Kowalski’);
select TYTUL from BOOK where autor = ‘Profesor’ order by tytul;
select fadsiouuwaruwf from ffsadfadsfasdfasfs;
select fadsiouuwaruwf from ffsadfadsfasdfasfs;
delete from zamowienia;
select fadsiouuwaruwf from ffsadfadsfasdfasfs;
—  komentarz, ponizej instrukcje ddl czyli tworzenia bazcreate database testowa;
create database drugabazka;
create table waznedane(kol1 int, wartosc varchar);
create table fjdskfjkldsfkl(kol2 int, kol4 int, kol3 bool);
Test OK!

Dzięki programowi w flexie możemy skopiować string dla każdego tokena (zamiast alokować pamięć i używać strcpy wystarczy użyć instrukcji yylval=text; , jednak kopiowanie stringów jest bezpieczniejsze jeżeli mamy zamysł pisania pretty-printera kodu), natomiast w bisonie każda instrukcja jest przetwarzana pod kątem naszej gramatyki i jeżeli w pliku wejściowym wpiszemy nieprawidłową instrukcję (niezgodną z nasza gramatyką), otrzymamy komunikat o błędzie.

Program kompiluje się w następujący sposób:

#!/bin/bash
flex -i sql.l
bison -d sql.y
gcc -o sql sql.tab.c -lfl

Regexp – vc++

Niesamowite możliwości udostępniają wyrażenia regularne. Istnieje narzędzie, które nazywa się Regex Builder w wersji 2.05, za jego pomocą można w wygodny sposób testować wyrażenia na dowolnym łańcuchu znaków, aby te prawidłowe móc potem użyć we własnym programie.

I tak na przykład, aby wyciągnąć wartości i wykładniki z wielomianów za pomocą wyrażenia regularnego, możemy użyć następująco:

Regex ^expression = gcnew Regex(“x\\^(\\d+)”);
// wielomian jest dzielony wyrażeniem regularnym na poszczególne wykładniki (n>1)
expression = gcnew Regex(“[+-]*(\\d)*x[^^]|[+-][x]”);
// wielomian jest dzielony wyrażeniem regularnym na poszczególne wykładniki (n==1)
expression = gcnew Regex(“(.?)((\\d)+).”);
// wielomian jest dzielony wyrażeniem regularnym na poszczególne wykładniki (n==0)
MatchCollection ^polyMatch = expression->Matches(text);

5x+54+4784x^5+x+389x^2+5x+4x+3x+89x^3+2x^2+4+8x^8+5345+85x+4+x

Składowe wpisanego wielomianu:
współczynnik: 4784 wykładnik: 5
współczynnik: 389 wykładnik: 2
współczynnik: 89 wykładnik: 3
współczynnik: 2 wykładnik: 2
dodawanie współczynników: (389 + 2) x^2
współczynnik: 8 wykładnik: 8
współczynnik: 5 wykładnik: 1
współczynnik: 1 wykładnik: 1
(5 + 1) x^1
współczynnik: 5 wykładnik: 1
(6 + 5) x^1
współczynnik: 4 wykładnik: 1
(11 + 4) x^1
współczynnik: 3 wykładnik: 1
(15 + 3) x^1
współczynnik: 85 wykładnik: 1
(18 + 85) x^1
współczynnik: 1 wykładnik: 1
(103 + 1) x^1
współczynnik: 54 wykładnik: 0
współczynnik: 4 wykładnik: 0
(54 + 4) x^0
współczynnik: 5345 wykładnik: 0
(58 + 5345) x^0
współczynnik: 4 wykładnik: 0
(5403 + 4) x^0
ostatecznie w2: 8x^8 +4784x^5 +89x^3 +391x^2 +104x^1 +5407