Criando um simples parser usando Bison e Flex

Finalmente andei testando e integrando o Bison e o Flex. Apesar de já ter uma experiência no uso do Bison, não sabia os primeiros passos, nem mesmo como integrá-lo com o Flex. A princípio venho testando com o Flex, mas pretendo pular para o re2c.

Para quem não conhece o Flex, eu vos apresento:
Flex is a tool for generating scanners. A scanner, sometimes called a tokenizer, is a program which recognizes lexical patterns in text. The flex program reads user-specified input files, or its standard input if no file names are given, for a description of a scanner to generate. [1]

E o Bison:
Bison is a general-purpose parser generator that converts an annotated context-free grammar into an LALR(1) or GLR parser for that grammar. Once you are proficient with Bison, you can use it to develop a wide range of language parsers, from those used in simple desk calculators to complex programming languages. [2]

Enfim, primeiro começamos com o arquivo que o Flex irá analisar.

%{
#include "common.h"
#include "parser.h"
%}
 
/* Definições */
STRING [a-z][a-z0-9]*
WHITESPACE [ \n\r\t]+
DIGITS [0-9]+
ANY_CHAR .
 
%option case-insensitive
 
%% /* Regras */
 
{WHITESPACE} /* Ignore */ ;
 
"SELECT" { return T_SELECT; }
"FROM" { return T_FROM; }
 
{STRING} { return T_STRING; }
{DIGITS} { return T_DIGIT; }
 
"," { return ','; }
 
{ANY_CHAR} {
	printf("Unexpected character in input: '%c' (ASCII=%d)\n", yytext[0], yytext[0]);
}

A integração com o Bison acontece neste arquivo, incluindo o arquivo .h que o Bison irá gerar, no caso do exemplo, o "parser.h".

Todo esse 'return PALAVRA' está indicando que o que a expressão regular (que vem antes no bloco) casar, representa um token, que é chamado pelo que é retornado, a convenção é usar sempre tudo em maiúsculo.

E agora, o arquivo que o Bison usará para gerar o código do parser.

%{
#include "common.h"
#include <stdio.h>
%}
 
%token T_STRING
%token T_DIGIT
%token T_SELECT
%token T_FROM
 
%error-verbose
 
%%
 
stmt:
	select_stmt
;
 
field_list:
		field
	|	field_list ',' field
;
 
field:
		T_STRING
	|	'`' T_STRING '`'
;
 
select_stmt:
		T_SELECT field_list T_FROM
;
 
%%
 
void yyerror(const char* errmsg)
{
	printf("\n*** Erro: %s\n", errmsg);
}
 
int yywrap(void) { return 1; }
 
int main(int argc, char** argv)
{
     yyparse();
     return 0;
}

Como podem ver, os '%%' dividem o arquivo em 3 partes, assim como acontece no arquivo que o Flex usa, ambos são para: definição, regra e códigos C. Há vários detalhes do que pode ter entre essas partes, até mesmo lugar certo para os comentários.

O %token é bem intuitivo, o que vem após ele é o nome dos tokens a serem usados nas regras da gramática, o %error-verbose é a opção para termos uma mensagem de erro mais detalhada (ele diz o que ele esperava, quando recebe algo inesperado, como aquelas mensagens de parser error vistas no PHP, por exemplo). E como stmt é a primeira regra, o Bison irá usá-lo pra ditar a ordem da gramática, embora essa ordem possa ser sobreescrita usando a opção %start. Há muitas opções, tanto no Flex, como no Bison!

A gramática usada acima é simples de perceber... Ela espera uma entrada:
SELECT campo[, ...] FROM

Onde 'campo' também pode estar entre backticks (`), como é aceito no MySQL, por exemplo.

Perceba que eu usei um common.h em ambos os arquivos, nele eu coloquei o protótipo de funções que estarão presente nos arquivos gerados. Ele é o seguinte:

#ifndef __COMMON_H__
#define __COMMON_H__
 
extern int yylex(); 
extern int yyparse(); 
extern void yyerror(const char* s);
 
#endif

Prosseguindo, para gerar os arquivos, um Makefile seria legal, então segue um exemplo:

CFLAGS=-g
BISON=bison
FLEX=flex
 
parser: parser.o scanner.o
	$(CC) -o parser scanner.o parser.o
 
parser.c: parser.y
	$(BISON) -d -oparser.c parser.y
 
scanner.c: scanner.l
	$(FLEX) -oscanner.c scanner.l
 
clean:
	rm -f scanner.c scanner.o parser.c parser.o parser.h parser

O argumento -d para o Bison, fará com que ele gere o .h (parser.h), que será o referenciado pelo código gerado pelo Flex (scanner.c). No fim, teremos então o executável parser, que espera dados na entrada padrão, e analisá-os segundo a gramática usado nos arquivos que foram usados para gerá-lo.

Agora, vamos testar o parser com umas entradas.

$ echo "select 1" | ./parser 
*** Erro: syntax error, unexpected T_DIGIT, expecting T_STRING or '`'
 
$ echo "select a1, from" | ./parser 
*** Erro: syntax error, unexpected T_FROM, expecting T_STRING or '`'
 
$ echo "from" | ./parser 
*** Erro: syntax error, unexpected T_FROM, expecting T_SELECT
 
$ echo "select a, b, c from" | ./parser 

Feito! A última entrada não reporta qualquer erro, foi aceita segundo a gramática.

Fica aí um exemplo de como usar o Bison e Flex (diferente da maioria dos exemplos, não foi uma calculadora! :D), sem muitos detalhes; e sim, eu sei, não é um material ideal para quem nunca mexeu com ambos.

[1] - http://flex.sourceforge.net/
[2] - http://www.gnu.org/software/bison/

Muito bom! Sempre achei

Muito bom! Sempre achei maneiro esse assunto mas não fazia idéia de por onde começar.

Vou testar qualquer hora dessas :D

ahuahuehahuea morri de

ahuahuehahuea
morri de susto
pensei que você estava mechendo com o adobe flex
já ia pensar que vc tava virando esses carinhas das hypes
ehhehehe
isso aí por a caso tem a ver com o pl/asm??
abraço ae ecl

Bom demais! Anos a fio

Bom demais!

Anos a fio tentando achar alguma coisa prática e imediata, eis.
O conceito eu entendo só queria algo objetivo, achei aqui.

Mantenha esta página. Simplicidade e conteúdo sempre vão fazer a diferença.

{}'s
MaRZ

T_DIGIT não foi usado no

T_DIGIT não foi usado no parser né.

É verdade, bem observado.

É verdade, bem observado. Fica então para quem estiver testando o código, usá-lo. :D

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Post new comment

The content of this field is kept private and will not be shown publicly.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Lines and paragraphs break automatically.

More information about formatting options