Yacc (Yet Another Compiler-Compiler)

 

O yacc (Yet Another Compiler-Compiler) completa com o lex o conjunto de ferramentas do UNIX para a construção de compiladores. Foi desenvolvido em 1975 nos Laboratórios Bell e gera analisadores sintáticos com algoritmo LALR.

Um programa yacc contém três seções, também separadas por %%: declarações, regras de tradução e funções auxiliares. Na seção de declarações devem ser especificados todos os tokens que o parser deve tratar. O token identificador, por exemplo, deve ser declarado na forma

%token identificador
Na seção de regras de tradução, a mais importante da especificação, colocamos a gramática da linguagem do compilador a ser gerado e a correspondente ação semântica para cada possível conjunto de tokens e expressões regulares associadas a cada símbolo não-terminal.

Como exemplo, vamos retornar à gramática dada anteriormente para definição de expressões aritméticas.

E -> E + E | E * E | ( E ) | - E | ID
Para criarmos um parser para esta gramática é necessário primeiro, na seção de declarações, se definir o token ID , relativo a um identificador. Isso é feito na forma
%token ID
O próximo passo é definir a gramática na especificação yacc escrever as ações semânticas para cada conjunto de símbolos reconhecidos. É o que faz o trecho seguinte.
E: E `+` E { $$ = $1 + $3; } |
E `*` E { $$ = $1 * $3; } |
`(` E `)` { $$ = $2; } |
`-` E { $$ = -$2; } |
ID { $$ = tabsimb(yylval); }
;
Essa definição especifica que o nó sintático cujos filhos forem E + E irá retornar como valor o resultado do valor do primeiro token, que é a primeira expressão, somado com o valor da segunda expressão. Dentro do bloco de ação semântica, isso é feito com um comando C simples de soma e atribuição, e os valores dos tokens são avaliados com o símbolo $ seguido da ordem do token correspondente na expressão gramatical. No caso, as duas expressões são $1 e $3, já que $2 é o token de sinal de soma `+'; o valor de retorno é simbolizado por $$. Esta mesma regra é seguida pelas demais alternativas gramaticais, com a diferença de que quando é encontrado um token ID, o valor retornado é o valor do identificador na tabela de símbolos, retornado pela função tabsimb(yylval), onde yylval contém o atributo do token, que no caso é o nome do identificador. A especificação final yacc ficará como mostrado a seguir.
/* definições de tokens */
%token ID
%%
/* regras */
E: E `+` E { $$ = $1 + $3; } |
E `*` E { $$ = $1 * $3; } |
`(` E `)` { $$ = $2; } |
`-` E { $$ = -$2; } |
ID { $$ = tabsimb(yylval); }
;
%%
/* funções auxiliares */
tabsimb(char[] id){
/* definição da função */
}
/* implementação do analisador léxico */
O lex e o yacc foram projetados para trabalharem um com o outro. Podemos optar por implementar nosso próprio analisador léxico dentro do programa yacc, mas é trivial faze-lo com a ajuda do lex. O yacc espera como analisador léxico a ser definido a função yylex(), que tem o mesmo nome do analisador gerador pelo lex, bastando incluir do programa yacc, na seção de funções, o arquivo "lex.yy.c" que contém a implementação do analisador léxico gerado.

Um grande problema na análise sintática é o tratamento e recuperação de erros. O yacc permite tratar erros com a utilização de um token especial chamado error, com o qual é casado um erro sintático. Na sua respectiva ação semântica realizamos o tratamento de erros correspondente, por exemplo, emitindo uma mensagem de erros. No final da ação semântica de erro é necessário chamar a rotina yacc yyerrok, que restabelece o yacc no seu modo normal de operação.

Veja exemplo

VoltarHomePróximoe-mail