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 analizadores sintácticos LALR (lookahead left-to-right rightmost derivation) , 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). ^{[ 1 ]} Yacc se suministra como 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 futuras . ^{[ 3 ]}

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 OR exclusivo en un compilador de lenguaje B ^{[ 4 ]} (desarrollado usando el compilador-compilador TMG de McIlroy ^{[ 5 ]} ), 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 sintáctico LR , que sirvió de 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 fue publicada en 1975. ^{[ 6 ]}

Johnson utilizó Yacc para crear el compilador C portátil . ^{[ 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 ]} Si bien 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 de Yacc es una gramática con fragmentos de código C (llamados "acciones") adjuntos a sus reglas. Su salida es un analizador sintáctico de desplazamiento-reducción en C que ejecuta los fragmentos de C asociados a 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 la llamada node(label, left, right) construye un nodo de árbol de análisis sintáctico binario con la etiqueta y los hijos especificados, entonces la regla

expr : expr '+' expr { $$ = nodo ( '+' , $1 , $3 ); }

reconoce expresiones de sumatoria y construye nodos para ellas. Los identificadores especiales $$ , $1 y $3 se refieren 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 generalmente requiere un analizador léxico externo para realizar primero una etapa de tokenización (análisis de palabras), seguida de la etapa de análisis sintáctico propiamente dicha. ^{[ 6 ]} Existen numerosos generadores de analizadores léxicos, como Lex o Flex , 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 programas similares (en su mayoría reimplementaciones) han sido muy populares. Yacc solía estar disponible como generador de analizadores sintácticos predeterminado en la mayoría de los sistemas Unix, aunque desde entonces ha sido reemplazado por programas más recientes y en gran medida compatibles, como Berkeley Yacc , GNU Bison , MKS Yacc y Abraxas PCYACC. Una versión actualizada del Yacc original de AT&T se incluye como parte del proyecto OpenSolaris de Sun. Cada una ofrece ligeras mejoras y características adicionales con respecto al Yacc original, pero el concepto y la sintaxis básica se han mantenido iguales. ^{[ 14 ]}

Yacc también fue una de las varias herramientas UNIX disponibles para el sistema operativo UNOS de Charles River Data Systems bajo 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 ] [ 11 ]} Yacc también se utilizó en Unix para implementar el Compilador C portátil , así como analizadores para lenguajes de programación como FORTRAN 77 , Ratfor , APL , bc , m4 , etc. ^{[ 8 ] [ 17 ]}

Yacc también se ha reescrito para otros lenguajes, incluidos OCaml , ^{[ 18 ]} Ratfor , ML , Ada , Pascal , Java , PHP , Python , Ruby , Go , ^{[ 19 ]} Common Lisp ^{[ 20 ]} y Erlang . ^{[ 21 ]}

• Berkeley Yacc : La implementación de Yacc de Berkeley rápidamente se hizo más popular que el propio Yacc de AT&T debido a su rendimiento y la falta de restricciones de reutilización. ^{[ 22 ]}
• Analizador LALR : El algoritmo de análisis subyacente en los analizadores generados por Yacc.
• Bison : La versión GNU de Yacc.
• Lex (y el analizador léxico Flex ), un analizador de tokens que se usa comúnmente junto con Yacc (y Bison).
• BNF es una metasintaxis que se utiliza para expresar gramáticas libres de contexto : es decir, una forma formal de describir lenguajes libres de contexto.
• PLY (Python Lex-Yacc) es una implementación alternativa de Lex y Yacc en Python.

• Compilador-compilador
• hoc (lenguaje de programación)

• Entorno de pruebas para aprender y probar la sintaxis.

• yacc – Referencia de shell y utilidades, Especificación única de UNIX , Versión 5 de The Open Group 
• yacc(1) – Manual del programador de Plan 9 , Volumen 1 
• yacc(1) – Manual de comandos generales de Inferno 
• yacc(1) – Manual de comandos generales de Linux de ManKier.com