Yacc ( Yet Another Compiler-Compiler ) es un programa informático para el sistema operativo Unix desarrollado por Stephen C. Johnson . Es un generador de analizadores sintácticos LALR (izquierda a derecha, derivación más a la derecha) con lookahead , que genera un analizador sintáctico LALR (la parte de un compilador que intenta dar sentido sintáctico al código fuente ) basado en una gramática formal , escrita en una notación similar a la forma Backus–Naur (BNF). [1] Yacc se suministra como una utilidad estándar en BSD y AT&T Unix. [2] Las distribuciones Linux basadas en GNU incluyen Bison , un reemplazo de Yacc compatible con versiones posteriores . [3]
A principios de los años 1970, Stephen C. Johnson , un científico informático de Bell Labs / AT&T , desarrolló Yacc porque quería insertar un operador or exclusivo en un compilador de lenguaje B [4] (desarrollado utilizando el compilador-compilador TMG de McIlroy [5] ), pero resultó ser una tarea difícil. Como resultado, su colega de Bell Labs Al Aho le indicó el trabajo de Donald Knuth sobre análisis sintáctico LR , que sirvió como base para Yacc. [4] Yacc fue influenciado por [6] y recibió su nombre en referencia al compilador-compilador TMG. [7]
Yacc fue escrito originalmente en el lenguaje de programación B , pero pronto fue reescrito en C por Alan Snyder. [5] Apareció como parte de la versión 3 de Unix , [8] y una descripción completa de Yacc se publicó en 1975. [6]
Johnson utilizó Yacc para crear el compilador Portable C. [ 8] Bjarne Stroustrup también intentó utilizar Yacc para crear una especificación formal de C++ , pero "fue derrotado por la sintaxis de C". [9] Aunque lo consideró inadecuado para una especificación formal del lenguaje, Stroustrup procedió a utilizar Yacc para implementar Cfront , la primera implementación de C++. [10]
En una entrevista de 2008, Johnson reflexionó que "la contribución que Yacc hizo a la difusión de Unix y C es de lo que estoy más orgulloso". [11]
La entrada a Yacc es una gramática con fragmentos de código C (llamados "acciones") adjuntos a sus reglas. Su salida es un analizador de desplazamiento-reducción en C que ejecuta los fragmentos de C asociados con cada regla tan pronto como se reconoce la regla. Las acciones típicas implican la construcción de árboles de análisis . Usando un ejemplo de Johnson, si la llamada node(label, left, right) construye un nodo de árbol de análisis binario con la etiqueta y los hijos especificados, entonces la regla
expr : expr '+' expr { $$ = nodo ( '+' , $1 , $3 ); } reconoce expresiones de suma y construye nodos para ellas. Los identificadores especiales $$ , $1 y $3 hacen referencia a elementos en la pila del analizador . [6]
Yacc produce únicamente un analizador sintáctico (analizador de frases) que puede utilizarse solo en el caso del análisis sintáctico sin escáner. Sin embargo, el análisis sintáctico completo normalmente requiere un analizador léxico externo para realizar primero una etapa de tokenización (análisis de palabras), a la que luego le sigue la etapa de análisis propiamente dicha. [6] Los generadores de analizadores léxicos, como Lex o Flex , están ampliamente disponibles para este propósito. El estándar IEEE POSIX P1003.2 define la funcionalidad y los requisitos tanto para Lex como para Yacc. [12]
Algunas versiones de AT&T Yacc se han convertido en código abierto . Por ejemplo, el código fuente está disponible con las distribuciones estándar de Plan 9. [ 13]
Yacc y otros programas similares (que en su mayoría son reimplementaciones) han sido muy populares. El propio Yacc solía estar disponible como generador de analizadores por defecto en la mayoría de los sistemas Unix, aunque desde entonces ha sido reemplazado por programas más recientes, en gran medida compatibles, como Berkeley Yacc , GNU Bison , MKS Yacc y Abraxas PCYACC. Una versión actualizada del AT&T Yacc original se incluye como parte del proyecto OpenSolaris de Sun. Cada uno ofrece ligeras mejoras y características adicionales con respecto al Yacc original, pero el concepto y la sintaxis básica siguen siendo los mismos. [14]
Yacc también fue una de varias herramientas UNIX disponibles para el sistema operativo UNOS de Charles River Data Systems bajo la licencia de Bell Laboratories . [15]
Entre los lenguajes que se implementaron por primera vez con Yacc se encuentran AWK , C++ , [10] eqn y Pic . [16] Yacc también se utilizó en Unix para implementar el Portable C Compiler , así como analizadores para lenguajes de programación como FORTRAN 77 , Ratfor , APL , bc , m4 , etc. [8] [17]
Yacc también ha sido reescrito para otros lenguajes, incluidos OCaml , [18] Ratfor , ML , Ada , Pascal , Java , PHP , Python , Ruby , Go , [19] Common Lisp, [20] y Erlang . [21]
Después de que la versión TMG de B estuvo funcionando, Thompson reescribió B en sí misma (un paso de arranque)… Cuando Johnson regresó a Bell Labs en 1973, se desconcertó al descubrir que el lenguaje cuyas semillas había traído a Canadá había evolucionado en casa; incluso su propio programa yacc había sido reescrito en C, por Alan Snyder.
