yacc

yacc (acrônimo para Yet Another Compiler Compiler) é um gerador de analisador sintático desenvolvido por Stephen C. Johnson da AT&T para o sistema operacional Unix. Ele gera um analisador sintático, parte do compilador responsável por fornecer sentido sintático a um determinado código fonte, baseado numa gramática formal escrita numa forma similar ao formalismo de Backus-Naur. O resultado é um código para o analisador sintático em C.

O yacc costumava ser o gerador de analisador sintático padrão na maioria dos sistemas Unix, mas acabou sendo suplantado por versões mais modernas ainda que compatíveis, como Berkeley Yacc, GNU bison, MKS yacc e Abraxas pcyacc. Uma versão atualizada do código original da AT&T é incluída no OpenSolaris. O yacc também já foi reescrito para outras linguagens, incluindo Ratfor, EFL, ML, Ada, Java e Limbo.

O analisador sintático gerado pelo yacc requer um analisador léxico, que pode ser fornecido externamente através e geradores de analisador léxicos como o lex ou o flex. A norma POSIX define a funcionalidade e os requisitos tanto para lex quanto para yacc.

Relacionamento com lex

O yacc e o gerador de analisador léxico lex são geralmente usados em conjunto. O Yacc usa uma gramática formal para analisar sintaticamente uma entrada, algo que o lex não consegue fazer somente com expressões regulares (o lex é limitado a simples máquinas de estado finito). Entretanto, o yacc não consegue ler a partir duma simples entrada de dados, ele requer uma série de tokens, que são geralmente fornecidos pelo lex. O lex age como um pré-processador do yacc. Segue abaixo dois diagramas do relacionamento entre lex e yacc:

Diagrama 1

		regras léxicas		regras gramaticais
		↓		↓
		lex		yacc
		↓		↓
entrada	→	yylex()	→	yyparse()	→	saída

Diagrama 2

main()	→	yyparse()	→	yylex()	→	Fluxo de entrada
	←		←		←

A partir do diagrama 1, percebe-se que o lex gera a subrotina yylex() a partir de regras léxicas, e que o yacc gera a subrotina yyparse() a partir de regras gramaticais. A partir do diagrama 2, percebe-se que um programa qualquer invoca o analisador sintático para uma fluxo de entrada. O analisador sintático não consegue analisar entradas, mas sim tokens. Portanto, cada vez que ele precisa dum token, ele invoca o analisador léxico. O analisador léxico processa o fluxo de entrada e retorna o primeiro token que encontrar. Esse processo de requisição é contínuo e só termina quando o analisador léxico identifica o fim o fluxo de entrada ou quando o analisador sintático identifica uma falha gramatical.

Referências

• Stephen C. Johnson (1979). «Yacc: Yet Another Compiler-Compiler» (PDF). Consultado em 22 de julho de 2008. Arquivado do original (PDF) em 6 de março de 2009 
• M. E. Lesk e E. Schmidt. «Lex - A Lexical Analyzer Generator». The Lex & Yacc Page (em inglês). Consultado em 22 de julho de 2008 
• Ivan L. M. Ricarte (14 de fevereiro de 2003). «Desenvolvimento de uma aplicação». Programação de Sistemas: Uma Introdução. Universidade Estadual de Campinas. Consultado em 22 de julho de 2008 

Ver também

• Analisador sintático LALR, o algoritmo de análise sintática gerado pelo yacc
• Bison, versão GNU do yacc
• lex, analisador léxico usado em conjunto do yacc
• Formalismo de Backus-Naur, uma meta sintaxe para gramáticas livres de contexto