RESUMEN DE YACC
YACC significa "otro compilador de compiladores más" (del inglés Yet Another Compilers-Compiler), lo que refleja la popularidad de los generadores de analizadores sintácticos al principio de los años setenta, cuando S. C. Johnson creó la primera versión de YACC. Este generador se encuentra disponible como una orden del sistema UNIX, y se ha utilizado para facilitar la implantación de cientos de compiladores.
Para construir un traductor utilizando YACC primero se
prepara un archivo, por ejemplo traduce.y, que contiene una
especificación en YACC del traductor. La orden del sistema UNIX
yacc traduce.y
transforma al archivo
traduce.y en un programa
escrito en C llamado y.tab.c, que implementa un analizador
sintáctico escrito en C, junto con otras rutinas en C que el usuario pudo haber
preparado en el fichero traduce.y. Posteriormente, se compila el
fichero y.tab.c y se obtiene el programa objeto deseado que realiza
la traducción especificada por el programa original en YACC. Si se necesitan
otros procedimientos, se pueden compilar o cargar con
y.tab.c,
igual que en cualquier programa en C.
Un programa fuente en YACC tiene tres secciones:
declaraciones
%%
reglas de traducción
%%rutinas en C de apoyo
%{ y
%}. Aquí se sitúan las
declaraciones de todas las variables temporales usadas por las reglas de
traducción o los procedimientos de la segunda y tercera secciones. Por
ejemplo: %{ #include <string.h> %}
También en la parte de declaraciones hay declaraciones de los componentes léxicos de la gramática. Por ejemplo:
%token DIGITO
declara que DIGITO es un componente léxico o token. Los
componentes léxicos que se declaran en esta sección se pueden utilizar
después en la segunda y tercera partes de la especificación en YACC.
< lado izquierdo > -> < alt1 > | < alt2 > ... | < altn >
En YACC se escribiría:
< lado izquierdo > : < alt1 > { acción semántica 1 } | < alt2 > { acción semántica 2 } .... | < altn > { acción semántica n } ;
En una producción en YACC, un carácter simple
entrecomillado 'c' se considera como el símbolo terminal
c, y las cadenas sin comillas de letras y dígitos no declarados como
componentes léxicos se consideran símbolos no terminales. Los lados derechos
alternativos de las reglas se pueden separar con una barra vertical, y un
símbolo de punto y coma sigue a cada lado izquierdo con sus alternativas y
sus acciones semánticas. El primer lado izquierdo se considera, por defecto,
como el símbolo inicial.
Una acción semántica en YACC es una secuencia de
sentencias en C. En una acción semántica, el símbolo
$$ se
refiere al valor del atributo asociado con el no terminal del lado
izquierdo, mientras que $i se refiere al valor asociado con el
i-ésimo símbolo gramatical (terminal o no terminal) del lado derecho. La
acción semántica se realiza siempre que se reduzca por la producción
asociada, por lo que normalmente la acción semántica calcula un valor para
$$ en función de los
$i. Si la regla no especifica
ninguna acción semántica, la acción semántica por omisión es
{$$ =
$1;}.
yylex(). En caso necesario se pueden agregar otros
procedimientos, como rutinas de recuperación de errores.
El analizador léxico
yylex() produce pares
formados por un componente léxico y su valor de atributo asociado. Si se
devuelve un componente léxico como DIGITO, el componente léxico
se debe declarar en la primera sección de la especificación en YACC. El valor
del atributo asociado a un componente léxico se comunica al analizador
sintáctico mediante una variable especial que se denomina
yylval.
Uso de YACC con gramáticas ambiguas. Si la gramática
de la especificación en YACC es ambigua se producen conflictos en las acciones
del analizador sintáctico. YACC informará del número de conflictos en las
acciones del análisis sintáctico que se produzcan. Se puede obtener una
descripción de los conjuntos de elementos y de los conflictos en las acciones de
análisis sintáctico invocando a YACC con la opción -v. Esta opción
generará un archivo adicional llamado y.output que contiene los
núcleos de los conjuntos de elementos encontrados por el analizador sintáctico,
una descripción de los conflictos en las acciones del análisis, y una
representación legible de la tabla de análisis sintáctico LR que muestra
cómo se resolvieron los conflictos de las acciones del análisis sintáctico.
A menos que se ordene lo contrario, YACC resolverá todos los conflictos en las acciones del análisis sintáctico utilizando las dos reglas siguientes:
Como estas reglas que se siguen por omisión, no siempre reflejan lo que quiere el escritor del compilador, YACC proporciona un mecanismo general para resolver los conflictos de desplazamiento/reducción. En la parte de declaraciones, se pueden asignar precedencias y asociatividades a los terminales. La declaración
%left '+' '-'
hace que '+' y
'-' tengan la misma
precedencia y que sean asociativos por la izquierda. Se puede declarar que un
operador es asociativo por la derecha diciendo
%right '^'
y se puede obligar a un operador a ser un operador binario no asociativo (por ejemplo, dos casos del operador no se pueden combinar en absoluto) diciendo:
%nonassoc '<'
A los componentes léxicos se les dan precedencias en el orden en que aparecen en la parte de declaraciones, siendo los primeros los de menor precedencia. Los componentes léxicos de una misma declaración tienen la misma precedencia. Así, la declaración
%right MENOSU
daría al componente léxico MENOSU un nivel de precedencia mayor que a los terminales declarados anteriormente.
YACC resuelve los conflictos de desplazamiento/reducción
asociando una precedencia y asociatividad a cada producción implicada en un
conflicto, así como a cada terminal implicado en un conflicto. Si debe elegir
entre desplazar el símbolo de entrada a y reducir por
la producción A->a, YACC reduce si la precedencia de la producción
es mayor que la de a o si las precedencias son las mismas y la
asociatividad de la regla es %left. De lo contrario se elige la
acción de desplazar.
Generalmente, la precedencia de una producción se considera igual a la del símbolo terminal situado más a la derecha. En la mayoría de los casos, esta es la decisión sensata. En las situaciones en que el símbolo terminal situado más a la derecha no proporcione la precedencia adecuada a una producción, se puede forzar una precedencia añadiendo al final a la regla la etiqueta
%prec < terminal >
Entonces, la precedencia y asociatividad de la producción
serán las mismas que las de terminal, que se define seguramente en
la sección de declaraciones. YACC no informa de los conflictos de
desplazamiento/reducción que se resuelven utilizando este mecanismo de
precedencia y asociatividad.
Este "terminal" puede ser simplemente un
marcador. Es decir, el terminal no es devuelto por el analizador léxico, sino
que se declara tan sólo para definir una precedencia para una producción. Por
ejemplo,
expr : '-' expr %prec MENOSU
hace que la regla anterior tenga la precedencia
correspondiente al token MENOSU, en lugar de la del token
'-'.