| INSTITUTO POLITÉCNICO NACIONAL ESCUELA SUPERIOR DE CÓMPUTO |

Introducción | Contenido | Bibliografía

Introducción
Contenido
UNIDAD I
UNIDAD II
UNIDAD III
UNIDAD IV
UNIDAD V Introducción 5.1 Estructura de un programa en YACC 5.2 Definición del tipo de la pila de YACC 5.3 Terminales y no terminales en YACC

5.4 Precedencia y asociatividad en YACC

5.5 Manejo de Errores en YACC

5.6 Desarrollo de una aplicación utilizando LEX y YACC

UNIDAD VI
UNIDAD VII
UNIDAD VIII
UNIDAD IX
PROBLEMARIO
Bibliografía

5.4 Precedencia y asociatividad en YACC

> Hay una situación común donde las reglas dadas anteriormente para resolver conflictos no son suficientes; esto es en el reconocimiento de expresiones aritméticas. La mayoría de las construcciones comúnmente usadas para expresiones aritméticas se pueden describir por la noción de niveles de precedencia para los operadores, junto con la información sobre asociatividad izquierda o derecha. Resulta que las gramáticas ambiguas con las reglas desambiguantes apropiadas se pueden usar para crear parsers que son más rápidos y fáciles de escribir que los parsers construidos partiendo de gramáticas no ambiguas. La idea básica es escribir reglas gramaticales de la forma

> expr : expr OP expr
> y
> expr : UNARY expr

> Para todos los operadores binarios y unarios deseados. Esto crea una gramática muy ambigua, con muchos conflictos. Como reglas desambiguantes, el usuario especifica la prioridad, de todos los operadores, u la asociatividad de los operadores binarios. Esta información es suficiente para permitir al yacc resolver los conflictos del parser de acuerdo con estas reglas, y construir un parser que acepte las precedencias y asociatividad deseadas.

> La precedencia y asociatividad están unidas a tokens en la sección de declaraciones. Esto se hace por medio de una serie de líneas que comienzan con la palabra reservada del yacc: %left, %rigth, o %nonassoc, seguido de una lista de tokens.

> Todos los tokens de una misma línea se supone que tienen el mimo nivel de precedencia y asociatividad; las líneas están listadas en reglas de precedencia creciente. Por lo tanto,

> %left ‘+’ ‘-‘
> %left ‘*’ ‘/’

> Describe la precedencia y asociatividad de los cuatro operadores aritméticos. Los signos más y menos son asociativos a la izquierda, y tienen menor precedencia que el asterisco y que la barra, los cuales son también asociativos a la izquierda.

> La palabra reservada %right se usa para describir operadores asociativos a la derecha, y la palabra reservada %nonassoc se usa para describir operadores, como el operador .LT. En el lenguaje FORTRAN, que no puede asociarse con ellos mismos; por lo tanto, A .LT. B .LT. C es ilegal en FORTRAN, y tal operador será descrito con la palabra reservada %nonassoc de yacc.

> Como un ejemplo del comportamiento de estas declaraciones, la descripción

> %right ‘=’
> %left ‘+’ ‘-‘
> %left ‘*’ ‘/‘
> %%
> expr : expr ‘=’ expr
> | expr ‘+’ expr
> | expr ‘-’ expr
> | expr ‘*’ expr
> | expr ‘/’ expr
> | NAME
> ;

> Se podría usar para estructurar la entrada:

> a = b = c*d - e - f*g

> Como sigue:

> a = ( b = ( ( (c*d) - e) - (f*g) ) )

> Cuando se usa este mecanismo, los operadores unitarios deben, en general recibir una precedencia. A veces un operador unitario y un operador binario tienen la misma representación simbólica, pero precedencias diferentes. Un ejemplo es unitario y binario ‘-‘; el signo menos unitario puede recibir la misma prioridad que la multiplicación, o incluso más alta, mientras que el signo menos binario tiene una prioridad menor que la multiplicación. La palabra reservada %prec, cambia el nivel de prioridad relacionado con una regla gramatical determinada. El %prec aparece inmediatamente después del cuerpo de la regla gramatical, antes de la acción o del punto y coma de cierre, y va seguido de un nombre de token o de literal. Esto produce que la precedencia de la regla gramatical sea la del nombre de token o lit eral siguiente. Por ejemplo, para hacer que el signo menos unitario tenga la misma prioridad que la multiplicación, las reglas deberán ser:

> %left ‘+’ ‘-‘
> %left ‘*’ ‘/‘
> %%
> expr : expr ‘+’ expr
> | expr ‘-’ expr
> | expr ‘*’ expr
> | expr ‘/’ expr
> | ‘-‘ expr %prec ‘*’
> | NAME
> ;

> Un token declarado por medio de %left, %right, y %nonassoc no necesitan ser, pero pueden ser, declarados también por medio de %token.

> Las precedencias y asociatividades las usa el yacc para resolver conflictos del analizador; éstos dan cabida a las reglas desambiguantes. Formalmente, las reglas funcionan de la siguiente forma:

> 1. La precedencia y asociatividad se registra para esos tokens y literales que los tienen.

> 2. Una precedencia y asociatividad está asociada con cada regla gramatical; es la precedencia y asociatividad del último token o literal del cuerpo de la regla. Si se usa la construcción %prec, ésta contrarresta esta regla estándar. Algunas reglas gramaticales pueden no tener precedencias o asociatividad relacionadas con ellas.

> 3. Cuando hay un conflicto reduce/reduce, o hay un conflicto desplazamiento/reduce o bien el símbolo de entrada o la regla gramatical no tiene precedencia y asociatividad, entonces se usan las dos reglas desambiguantes especificadas al principio de la sección y se informa de los conflictos.

> 4. Si hay un conflicto desplazamiento/reduce, y ambas reglas gramaticales y el carácter de entrada tienen prioridad y asociatividad relacionada con ellos, entonces el conflicto se resuelve en favor de la acción (desplazamiento o reduce) relacionada con la prioridad más alta.

> Si las precedencias son las mismas, entonces se usa la asociatividad; la asociatividad izquierda implicimplica reduce, la asociatividad derecha implica desplazamiento, y la no asociatividad implica error.

> Los conflictos resueltos por precedencia no se cuentan en el número de conflictos de desplazamiento/reduce y reduce/reduce que informa yacc. Esto quiere decir que los errores en la especificación de precedencia puede ocultar errores en la gramática de entrada; es un buena idea ahorrar precedencias, y usarlas esencialmente a modo de libro de cocina, hasta que se haya obtenido alguna experiencia. El archivo y.output es muy útil para decir si el parser está realmente haciendo lo que se suponía tenía que hacer.

> Atrás Siguiente

##### Introducción / Contenido / Unidad I / Unidad II / Unidad III / Unidad IV / Unidad V / Unidad VI / Unidad VII / Unidad VIII / Unidad IX / Problemario / Bibliografía

##### Inicio

##### Créditos

José Sánchez Juárez, Andrés Ortigoza Campos, Fabiola Ocampo Botello