Yacc

Yacc (Yet Another Compiler-Compiler) es un programa informático para el sistema operativo Unix desarrollado por Stephen C. Johnson. Es un generador de analizador de Derivación más a la derecha de izquierda a derecha (LALR) que genera un analizador 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). Yacc se proporciona como una utilidad estándar en BSD y AT&T Unix. Las distribuciones de Linux basadas en GNU incluyen Bison, un reemplazo de Yacc compatible con versiones posteriores.

Historia

A principios de la década de 1970, Stephen C. Johnson, científico informático de Bell Labs / AT&T, desarrolló Yacc porque quería insertar un operador exclusivo o en un compilador de lenguaje B (desarrollado con el compilador TMG de McIlroy -compilador), pero resultó ser una tarea difícil. Como resultado, su colega de Bell Labs Al Aho lo dirigió al trabajo de Donald Knuth sobre el análisis de LR, que sirvió como base para Yacc. Yacc fue influenciado y recibió su nombre en referencia al compilador-compilador TMG.

Yacc se escribió originalmente en el lenguaje de programación B, pero pronto Alan Snyder lo reescribió en C. Apareció como parte de la Versión 3 de Unix, y en 1975 se publicó una descripción completa de Yacc.

Johnson usó Yacc para crear el Compilador C portátil. Bjarne Stroustrup también intentó usar Yacc para crear una especificación formal de C++, pero "fue derrotado por la sintaxis de C". Si bien lo encontró inadecuado para una especificación formal del lenguaje, Stroustrup procedió a utilizar Yacc para implementar Cfront, la primera implementación de C++.

En una entrevista de 2008, Johnson reflexionó que "la contribución que hizo Yacc a la difusión de Unix y C es de lo que 'estoy más orgulloso".

Descripción

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 shift-reduce 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 niños, 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 los elementos de la la pila del analizador.

Yacc produce solo un analizador (analizador de frases); para un análisis sintáctico completo, esto requiere un analizador léxico externo para realizar la primera etapa de tokenización (análisis de palabras), que luego es seguida por la etapa de análisis sintáctico propiamente dicha. Los generadores de analizadores léxicos, como Lex o Flex, están ampliamente disponibles. El estándar IEEE POSIX P1003.2 define la funcionalidad y los requisitos para Lex y Yacc.

Algunas versiones de AT&T Yacc se han vuelto de código abierto. Por ejemplo, el código fuente está disponible con las distribuciones estándar de Plan 9.

Impacto

Yacc y programas similares (en su mayoría reimplementaciones) han sido muy populares. El propio Yacc solía estar disponible como generador de analizador predeterminado 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. Se incluye una versión actualizada del AT&T Yacc original como parte del proyecto OpenSolaris de Sun. Cada uno ofrece ligeras mejoras y características adicionales sobre el Yacc original, pero el concepto y la sintaxis básica siguen siendo los mismos.

Entre los lenguajes que se implementaron por primera vez con Yacc están AWK, C++, eqn y Pic. Yacc también se usó en Unix para implementar el compilador Portable C, así como analizadores para lenguajes de programación como FORTRAN 77, Ratfor, APL, bc, m4, etc.

Yacc también se ha reescrito para otros lenguajes, incluidos OCaml, Ratfor, ML, Ada, Pascal, Java, Python, Ruby, Go, Common Lisp y Erlang.

• Berkeley Yacc: La implementación de Berkeley de Yacc rápidamente se hizo más popular que el propio ATT Yacc debido a su rendimiento y falta de restricciones de reutilización.
• Parser LALR: El algoritmo subyacente de persing en los persianas generados por Yacc.
• Bison: La versión GNU de Yacc.
• Lex (y Analizador Lexical Flex), un analizador token comúnmente utilizado en conjunción con Yacc (y Bison).
• BNF es una metásintax utilizada para expresar gramáticas sin contexto: es una forma formal de describir lenguajes sin contexto.
• PLY (Python Lex-Yacc) es una aplicación alternativa de Lex y Yacc en Python.