INTRODUCCIÓN
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.
¿QUÉ ES YACC?
YACC es un analizador sintactico que nos permitira averiguar si un fichero
de entrada cualquiera respeta las reglas de una gramática concreta. Yacc es escrito en C. portátil
que La clase de especificaciones aceptada es una muy general: LALR(1) las gramáticas con las reglas
del disambiguating.
Además de los recopiladores para el C, APL,
Pascal, RATFOR, etc., que Yacc también se ha usado para los idiomas menos
convencionales, incluso un idioma del phototypesetter,
varios idiomas de calculadora de escritorio, un sistema de recuperación de
documento, y un Fortran que
ponen a punto el sistema.
Igual que sucedía con lex, YACC no es
directamente un analizador sino un generador de analizadores. A partir de un
fichero fuente en YACC, se genera un fichero fuente
en C que contiene el analizador sintáctico.
Sin embargo, un analizador sintáctico de YACC no puede funcionar por sí solo, sino que necesita un analizador
léxico externo para funcionar.
Dicho de otra manera, el fuente en C que genera YACC contiene llamadas a una función yylex() que debe estar definida y debe devolver el tipo de
lexema encontrado.
Además, es necesario incorporar también una función yyerror(), que será invocada cuando el
analizador sintáctico encuentre un símbolo que no encaja en la gramática.
¿CÓMO SE COMPONE YACC?
Un programa fuente en YACC
tiene tres secciones:
Ø
La parte de declaraciones.
Hay dos secciones opcionales en la parte de declaraciones de un programa en YACC:
En la primera sección, se ponen
declaraciones ordinarias en C, delimitadas por %{
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.
Ø
La parte de las reglas de
traducción. En la parte de la especificación en YACC
después del primer par %% se escriben las reglas de traducción. Cada regla
consta de una producción de la gramática y la acción semántica asociada. Un
conjunto de producciones como: < 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;}.
Ø
La parte de las rutinas de apoyo
en C. La tercera parte de una especificación en YACC
consta de rutinas de apoyo escritas en C. Para que el analizador sintáctico
funcione, se debe proporcionar un análisis léxico de nombre 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.
REGLAS DE YACC
Una regla de YACC es parecida a
una de lex, pero en vez de
un patrón regular, especifica una regla de la gramática. Las reglas deben estar
dadas de forma que la parte izquierda conste de un único símbolo no terminal, y la parte derecha indique la combinación de
terminales y no terminales de que puede estar compuesto.
Además, toda regla debe incluir una acción en C que se
ejecutará en cuanto YACC consiga encontrar los
componentes del símbolo resultado: símbolo_result:
componentes acción_en_C
Ø
El símbolo resultado debe estar situado en la primera posición de la
línea; es decir, que no puede haber espacios antes del símbolo resultado.
Ø
Los componentes son una combinación de terminales y no terminales
separados por espacios en blanco.
Ø
La acción puede ser una sola sentencia de C, o una sentencia compuesta,
encerrada entre llaves { }.
¿CÓMO
SE USA YACC?
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 '-'.
¿CÓMO FUNCIONA YACC?
Yacc mantiene una herramienta general
describiendo la entrada a un programa de la computadora.
El
usuario de Yacc especifica
las estructuras de su entrada, junto con el código ser invocado como cada tal
estructura se reconoce.
Yacc convierte tal una especificación
en un subprograma que el han - el dles
el proceso de la entrada; frecuentemente, es conveniente y apropiado tener la
mayoría del flujo de mando en la aplicación del usuario manejó por este
subprograma