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 Look Ahead Left-to-Right (LALR) , que genera un analizador LALR (la parte de un compilador que intenta darle sentido sintáctico al código fuente ) basado en una gramática formal , escrita en una notación similar a Backus –Forma Naur (BNF) . [1] Yacc se suministra como una utilidad estándar en BSD y AT&T Unix. [2] Las distribuciones de Linux basadas en GNU incluyenBison , un reemplazo de Yacc compatible con versiones anteriores . [3]
Autor (es) original (es) | Stephen C. Johnson |
---|---|
Repositorio | |
Sistema operativo | Unix , similar a Unix , Plan 9 , Inferno |
Plataforma | Multiplataforma |
Tipo | Mando |
Historia
A principios de la década de 1970, Stephen C. Johnson , un científico informático de Bell Labs / AT&T , desarrolló Yacc porque quería insertar un operador exclusivo u en un compilador de lenguaje B (desarrollado utilizando el compilador-compilador TMG de McIlroy [4] ), pero resultó ser una tarea difícil. Como resultado, el colega de Bell Labs, Al Aho , lo dirigió al trabajo de Donald Knuth sobre análisis sintáctico LR , que sirvió de base para Yacc. [5] Yacc fue influenciado por [6] y recibió su nombre en referencia al compilador-compilador TMG. [7]
Yacc fue originalmente escrito en el lenguaje de programación B , pero pronto se volvió a escribir en C . [4] Apareció como parte de la versión 3 de Unix , [8] y en 1975 se publicó una descripción completa de Yacc. [6]
Johnson usó Yacc para crear el compilador de C portátil . [8] Bjarne Stroustrup , por otro lado, intentó usar Yacc para su trabajo inicial en C ++ , pero "fue derrotado por la sintaxis de C" (por ejemplo, teniendo operadores de declaración de prefijo y sufijo). [9]
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". [10]
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 de reducción de cambios 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 sintáctico . Usando un ejemplo de Johnson, si el nodo de llamada (etiqueta, izquierda, derecha) construye un nodo de árbol de análisis binario con el especificado etiqueta e hijos, luego la regla
expr: expr '+' expr {$$ = nodo ('+', $ 1, $ 3); }
reconoce expresiones de suma y construye nodos para ellas. Los identificadores especiales $$ , $ 1 y $ 3 se refieren a elementos en la pila del analizador . [6]
Yacc produce solo un analizador sintáctico (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 propiamente dicho. [6] 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. [11]
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 del Plan 9 . [12]
Impacto
Yacc y programas similares (en gran parte reimplementaciones) han sido muy populares. Yacc mismo solía estar disponible como el generador de analizador predeterminado en la mayoría de los sistemas Unix, aunque desde entonces ha sido suplantado por programas más recientes, en gran parte compatibles, como Berkeley Yacc , GNU Bison , MKS Yacc y Abraxas PCYACC. Se incluye una versión actualizada de la versión original de AT&T 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. [13]
Entre los lenguajes que se implementaron por primera vez con Yacc se encuentran AWK , eqn y Pic . [14] Yacc también se usó en Unix para implementar el compilador portátil de C , así como analizadores para lenguajes de programación como FORTRAN 77 , Ratfor , APL , bc , m4 , etc. [8] [15]
Yacc también ha sido reescrito para otros lenguajes, incluyendo OCaml , [16] Ratfor , ML , Ada , Pascal , Java , Python , Ruby , Go , [17] Common Lisp [18] y Erlang . [19]
- Berkeley Yacc : La implementación de Berkeley de Yacc rápidamente se hizo más popular que el propio Yacc de AT&T debido a su desempeño y la falta de restricciones de reutilización. [20]
- Analizador LALR : el algoritmo de análisis subyacente en analizadores generados por Yacc.
- Bison : la versión GNU de Yacc.
- Lex (y analizador léxico Flex ), un analizador de tokens comúnmente utilizado junto con Yacc (y Bison).
- BNF es una metasintaxis utilizada para expresar gramáticas libres de contexto : es una forma formal de describir lenguajes libres de contexto.
- PLY (Python Lex-Yacc) es una implementación alternativa de Lex y Yacc en Python.
Ver también
- Compilador-compilador
- hoc (lenguaje de programación)
Referencias
- ^ "La AZ de los lenguajes de programación: YACC" . Computerworld . Consultado el 30 de noviembre de 2012 .
- ^ Levine, John (1992). Lex y yacc . Sebastopol, CA: O'Reilly & Associates. pag. xx. ISBN 1-56592-000-7.
- ^ Levine, John (2009). Flex y bison . Sebastopol, California: O'Reilly Media. pag. xv. ISBN 978-0-596-15597-1.
- ^ a b Ritchie, Dennis M. (abril de 1993). El desarrollo del lenguaje C (PDF) . Asociación de Maquinaria de Computación, Inc.
- ^ Morris, Richard (1 de octubre de 2009). "Stephen Curtis Johnson: Geek de la semana" . Software Red Gate . Consultado el 19 de enero de 2018 .
- ^ a b c d Johnson, Stephen C. (1975). Yacc: Yet Another Compiler-Compiler (Informe técnico). Murray Hill, Nueva Jersey: AT&T Bell Laboratories. 32 . Consultado el 31 de enero de 2020 .
- ^ "Sistemas de escritura para traductores tempranos" . Laboratorio de Computación Atlas.
- ^ a b c McIlroy, MD (1987). Un lector de investigación Unix: extractos comentados del Manual del programador, 1971–1986 (PDF) (Informe técnico). CSTR. Bell Labs. 139.
- ^ Stroustrup, Bjarne . "Una historia de C ++: 1979-1991" (PDF) .
- ^ Hamilton, Naomi (9 de julio de 2008). "Yacc, Unix y consejos de ex alumnos de Bell Labs Stephen Johnson" . www.computerworld.com . Archivado desde el original el 22 de agosto de 2020 . Consultado el 10 de noviembre de 2020 .
- ^ - Referencia de comandos y utilidades, Especificación UNIX única , Número 7 de The Open Group , - Referencia de comandos y utilidades, Especificación UNIX única , Número 7 de The Open Group .
- ^ "plan9: lanzamiento de UC Berkeley del Plan 9 bajo la GPLv2" . 26 de diciembre de 2017 . Consultado el 2 de enero de 2018 .
- ^ Manual de bisonte: Historia
- ^ "Especial de UNIX: Profs Kernighan & Brailsford" . Computerphile . 30 de septiembre de 2015.
- ^ Kernighan, Brian W .; Pike, Rob (1984). El entorno de programación Unix . Prentice Hall. ISBN 0-13-937681-X.
- ^ "Manual del usuario de OCaml: Capítulo 12 Generadores de Lexer y analizador (ocamllex, ocamlyacc)" . Consultado el 25 de noviembre de 2013 .
- ^ "Yacc.go: una versión de Yacc para el lenguaje de programación Go" . Consultado el 15 de julio de 2017 .
- ^ "CL-Yacc: una versión Common Lisp de Yacc" .
- ^ "yecc: una implementación de Erlang de Yacc" .
- ^ John Levine (agosto de 2009), flex & bison , O'Reilly Media
enlaces externos
- - Referencia de comandos y utilidades, la especificación única de UNIX , número 7 de The Open Group
- - Manual del programador de Plan 9 , Volumen 1
- - Manual de comandos generales de Inferno