| 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
UNIDAD VI 6.1 Atributos Heredados 6.2 Atributos Sintetizados 6.3 Conversión de Atributos Heredados a Sintetizados 6.4 Desarrollo de una aplicación con LEX y YACC (Calculadora, Derivador, Graficador, etc.)
UNIDAD VII
UNIDAD VIII
UNIDAD IX
PROBLEMARIO
Bibliografía

6.4 Desarrollo de una aplicación con LEX y YACC (Calculadora, Derivador, Graficador, etc.)

> El ejemplo de la calculadora de escritorio se modifica para proporcionar una calculadora de escritorio que hace aritmética de intervalos de punto flotante. La calculadora entiende las constantes de punto flotante, las operaciones aritméticas +, -, *, /, y signo menos unitario -, y = (asignación), y tiene 26 variables de punto flotante, desde a hasta z. Además, también entiende intervalos, escritos.

> ( x , y )

> Donde x es menor o igual a y. Hay 26 variables de valores de intervalos A hasta Z que también se pueden usar. Las asignaciones no devuelve ningún valor, y no imprimen nada, mientras que las expresiones imprimen el valor (flotante o intervalo).

> Este ejemplo explora un gran número de dispositivos muy interesantes del yacc y del C. los intervalos están representados por una estructura, consistente en los valores de final del punto de la izquierda y de la derecha, almacenados como valores de precisión doble. A esta estructura se le dá un nombre de tipo, INTERVAL, usando typedef. El valor de la pila de yacc también puede contener escalares de punto flotante, y enteros (usados para indexar dentro de matrices que contienen los valores de las variables). Nótese que esta estrategia completa depende grandemente de que sea posible asignar estructuras y uniones en C. En efecto, muchas de las acciones llaman a funciones que también devuelven estructuras.

> También hay que señalar el uso de YYERROR para manejar condiciones de error: división de un intervalo que contiene 0, y un intervalo presentado en la regla errónea. En efecto, el mecanismo de yacc de recuperación de un error se usa para desechar el resto de la línea que contiene el error.

> Además de la mezcla de tipos de la pila, esta gramática también demuestra un interesante uso de la sintaxis para controlar el tipo (escalar o intervalo) de expresiones intermedias. Se nota que un escalar se puede ascender automáticamente a un intervalo si el contexto demanda un valor intervalo. Esto produce un gran número de conflictos cuando se ejecuta la gramática a través de yacc: 18 Desplazamiento/Reducción y 26 Reducción/Reducción. El problema se puede ver mirando a las dos líneas de entrada:

> 2.5 + ( 3.5 - 4. )
> y
> 2.5 + ( 3.5 , 4. )

> Se tiene en cuenta que el 2.5 se va a usar en una expresión de valor intervalo en el segundo ejemplo, pero este hecho no se conoce hasta que se lee la coma (,); para entonces, 2.5 ha terminado, y el analizador no puede volver a atrás y cambiar de idea. Más generalmente, podría ser necesario buscar un número arbitrario de tokens para decidir si convertir un escalar en un intervalo. Este problema se salva teniendo dos reglas para cada operador de valor intervalo binario; uno cuando el operando izquierdo es un escalar, y uno cuando el operando izquierdo es un intervalo. En este segundo caso, el operando de la derecha tiene que ser un intervalo, por lo tanto la conversión se aplicará automáticamente.

> Pero de todos modos, hay todavía muchos casos donde la conversión puede o no puede ser aplicada, llegando a los conflictos anteriores. Estos se resuelven listando las reglas que producen escalares primero en el fichero de especificación; de esta forma, los conflictos se resolverán en la dirección de mantener expresiones de valores escalares como valores escalares hasta que sea necesario convertirlos en intervalos.
> Esta forma de manejar diversos tipos es muy instructiva, pero no muy general. Si hubiera muchos tipos de expresiones, en vez de sólo dos, el número de reglas necesarias, aumentaría dramáticamente, y los conflictos aun más dramáticamente, por lo tanto, mientras que este ejemplo es instructivo, es una práctica mejor en un entorno de lenguaje de programación el mantener el tipo de información como parte del valor, y no como parte de la gramática.

> Finalmente, una palabra acerca de los analizadores léxicos. La única característica no usual es el tratamiento de constantes de punto flotante. La rutina de librería C atof se usa para hacer la conversión de un literal de caracteres a un valor de doble precisión. Si el analizador léxico detecta un error, éste responde devolviendo un token que es ilegal en la gramática, provocando un error sintáctico en el parser, y por supuesto la recuperación de errores.

> %{
> #include <stdio.h>
> #include <ctype.h>
> typedef struct interval {
> double lo, hi;

> } INTERVAL;
> INTERVAL vmul ( ), vdiv ( );
> double atof ();
> double dreg[26];
> INTERVAL verg[26];
> %}
> %start lines
> %union {
> int ival;
> double dval;
> INTERVAL vval;
> }
> %token <ival> DREG VREG
> /* indica dentro de dreg, matrices vreg */
> %token <dval> CONST
> /* constante de punto flotante */
> %type <vval> dexp
> /* expresión */
> %type <dval> vexp
> /* expresión intervalo*/
> /* Información de precedencia de los operadores */
> %left ‘+’ ‘-‘
> %left ‘*’ ‘/‘
> %left UMINUS /* precedencia para el signo menos unitario */
> %%
> lines : /* vacío */
> | lines line
> ;
> line : dexp ‘\n’
> {printf ( “%15.8f\n”, $1);}
> | vexp ‘\n’
> {printf ( “( %15.8f, %15.8f )\n”, $1.lo, $1.hi);}
> | DREG ‘=’ dexp ‘\n’
> { dreg[$1] = $3 ; }
> | VREG ‘=’ vexp ‘\n’
> { vreg[$1] = $3 ; }
> | error ‘\n’
> {yyerrok;}
> ;
> dexp : CONST
> | DREG
> { $$ = dreg [$1];}
> | dexp ‘+’ dexp
> { $$ = $1 + $3;}
> | dexp ‘-’ dexp
> { $$ = $1 - $3;}
> | dexp ‘*’ dexp
> { $$ = $1 * $3;}
> | dexp ‘/’ dexp
> { $$ = $1 / $3;}
> | ‘-’ dexp % prec UMINUS
> { $$ = - $2;}
> | ‘(’ dexp ‘)’
> { $$ = $2;}
> ;

> vexp : dexp
> { $$.hi = $$.lo = $1;}
> | ‘(‘ dexp ‘,’ dexp ‘)’
> {
> $$.lo = $2;

> $$.hi = $4
> If ($$.lo > $$.hi) {
> printf (“interval out order\n”);
> YYERROR;
> }
> }
> | VREG
> { $$ = vreg[$1] ;}
> |vexp ‘+’ vexp
> { $$.hi = $1.hi + $3.hi;
> $$.lo = $1.lo + $3.lo;}
> |vexp ‘+’ vexp
> { $$.hi = $1 + $3.hi;
> $$.lo = $1 + $3.lo;}

> |vexp ‘-’ vexp
> { $$.hi = $1.hi - $3.lo;
> $$.lo = $1.lo - $3.hi;}
> |vexp ‘-’ vexp
> { $$.hi = $1 - $3.lo;
> $$.lo = $1 - $3.hi;}
> |vexp ‘*’ vexp
> { $$ = vmul ( $1.lo, $1.hi, $3);}
> |vexp ‘*’ vexp
> { $$ = vmul ( $1, $1, $3);}
> |vexp ‘/’ vexp
> { if(dcheck ( $3 ) ) YYERROR;
> $$ = vdiv ( $1.lo, $1.hi, $3);}
> |vexp ‘/’ vexp
> { if(dcheck ( $3 ) ) YYERROR;
> $$ = vdiv ( $1, $1, $3);}

> | ‘-‘ vexp %prec UMINUS
> { $$.hi = .$2.lo; $$.lo = -$2.hi;}
> | ‘(‘ vexp ‘)’
> { $$ = $2;}
> ;
> %%
> #define BSZ 50
> /* tamaño del buffer para fp números */
> /* análisis léxico */
> yylex(){register c;
> /* salta los espacios en blanco */
> while ( (c = getchar( )) == ‘ ’ )
> If ( isupper ( c ) ) {
> yylval,ival = c- ‘A’;
> return ( VREG);
> }
> If ( islower ( c ) ) {
> yylval,ival = c- ‘a’;
> return ( DREG);
> }

> If ( isdigit ( c ) || c== ‘.’ ) {
> /* engulle dígitos, puntos, exponentes */
> char buf[BSZ+1], *cp = buf;
> int dot = 0, exp = 0;
> for( ; (cp-buf)<BSZ ; ++cp, c=getchar( ) ){
> *cp = c;
> if ( isdigit ( c ) ) continue;
> if ( c == ‘.’ ) {
> if (dot++ || exp) return (‘.’);
> /* lo anterior produce un error de sintaxis */
> continue;
> }
> if ( c == ‘e’) {
> if (exp++) return (‘e’);
> /* lo anterior causa error de sintaxis */
> continue;
> }
> /* final del número*/
> break;
> }
> *cp = ‘\0';
> if ( (cp- buf) >= BSZ )
> printf(“constante demasiado larga: truncada\n”);
> else ungetc (c, stdin);
> /* lo anterior ‘push’ el último carácter que se ha leído*/
> yylval.dval = atof (buf);
> return ( CONST);
> }
> return (c);
> }
> INTERVAL hilo ( a, b, c, d) double a, b, c, d;\
> /* devuelve el menor intervalo que contiene */
> /* a, b, c y d usados por *, / rutinas*/
> INTERVAL v;
> if( a>b) {v.hi = a; v.lo = b;}
> else {v.hi = b; v.lo = a;}
> if ( c>d) {
> if (c>v.hi) v.hi = c;
> if (d<v.lo) v.lo = d;
> }
> else {
> if (d>v.hi) v.hi = d;
> if (c<v.lo) v.lo = c;
> }
> return (v);
> }
> INTERVAL vmul (a, b, v) double a, b,; \
> INTERVAL V; {
> return ( hilo (a*v.hi, a*v.lo, b*v.hi, b*v.lo));
> }
> dcheck ( v) INTERVAL v ; {
> if (v.hi >= 0. && v.lo <= 0. ){
> printf (“divisor interval contains 0. \n);
> return (1);
> }
> return(0);
> }
> INTERVAL vdiv (a, b, v )double a, b; \
> INTERVAL v ; {
> return (hilo (a/v.hi, a/v.lo, b/v.hi,b/v.lo));

> 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