Sig: El Analizador Ascendente Parse::Yapp Sup: Análisis Sintáctico Ascendente en Ant: Práctica: Un C simplificado Con:
Ind:
Ind:
Parse::Yapp,
usando la propia notación yapp para describir el lenguaje.
Un programa yapp consta de tres partes:
la cabeza, el cuerpo y la cola. Cada una de las partes
va separada de las otras por el símbolo %% en una
línea aparte.
yapp: head body tail
head: headsec '%%'
headsec: #empty
| decls
decls: decls decl | decl
body: rulesec '%%'
rulesec: rulesec rules | rules
rules: IDENT ':' rhss ';'
tail: /*empty*/
| TAILCODE
decl: '\n'
| TOKEN typedecl symlist '\n'
| ASSOC typedecl symlist '\n'
| START ident '\n'
| HEADCODE '\n'
| UNION CODE '\n'
| TYPE typedecl identlist '\n'
| EXPECT NUMBER '\n'
typedecl: # empty
| '<' IDENT '>'
El terminal START se corresponde con una declaración
%start indicando cual es el símbolo de arranque de la gramática.
Por defecto, el símbolo de arranque es el primero de la gramática.
El terminal ASSOC está por los terminales que indican
precedencia y asociatividad.
Esto se ve claro si se analiza el contenido del fichero
YappParse.yp (![[*]](crossref.png)
)
en el que se puede encontrar
el código del analizador léxico del módulo
Parse::Yapp.
El código dice:
...
if($lexlevel == 0) {# In head section
$$input=~/\G%(left|right|nonassoc)/gc
and return('ASSOC',[ uc($1), $lineno[0] ]);
$$input=~/\G%(start)/gc
and return('START',[ undef, $lineno[0] ]);
$$input=~/\G%(expect)/gc
and return('EXPECT',[ undef, $lineno[0] ]);
$$input=~/\G%{/gc
...
La variable $lexlevel indica en que sección nos encontramos:
cabecera, cuerpo o cola. El terminal EXPECT
indica la presencia de una declaración %expect en el fuente,
la cual cuando es seguida de un número indica el numero de
conflictos shift-reduce que cabe esperar. Use EXPECT
si quiere silenciar las advertencias de yapp sobre la presencia
de conflictos cuya resolución automática considere correcta.
%union y a las especificaciones de
tipo entre símbolos menor mayor (<tipo>) en declaraciones token y
%type no son usadas por yapp. Estas declaraciones son
necesarias cuando el código de las acciones semánticas
se escribe en C como es el caso de yacc y bison.
Sigue un ejemplo de programa yacc/bison que usa declaraciones %union
y de tipo para los atributos:
1 %{
2 #include <stdio.h>
3
4 #define CLASE(x) ((x == 1)?"global":"local")
5 #define TIPO(x) ((x == 1)?"float":"integer")
6 %}
7
8 %union {
9 int n; /* enumerado */
10 char *s; /* cadena */
11 }
12
13 %token <n> FLOAT INTEGER
14 %token <n> GLOBAL
15 %token <n> LOCAL
16 %token <s> NAME
17 %type <n> class type
18
19 %%
La declaración %union de la línea 8 indica que los atributos
son de dos tipos: enteros y punteros a caracteres.
El nombre del campo es posteriormente usado en las
declaraciones de las líneas 13-17 para indicar el tipo
del atributo asociado con la variable o con el terminal.
Así, la declaración de la línea 13 indica
que los terminales FLOAT e INTEGER
son de tipo entero, mientras que la declaración de la línea 16 nos
dice que el terminal NAME es de tipo cadena.
29 class
30 : GLOBAL { $$ = 1; }
31 | LOCAL { $$ = 2; }
32 ;
33
34 type
35 : FLOAT { $$ = 1; }
36 | INTEGER { $$ = 2; }
37 ;
La información proveída sobre los tipos permite a yacc
introducir automáticamente en el código C producido
los typecasting o ahormados
para las asignaciones de las líneas 30-31 y 35-36. Obsérve que
en yacc el atributo de la variable en la parte izquierda
se denota por $$.
Otra diferencia entre yacc y yapp es que en yacc los
atributos de la parte derecha no constituyen un vector, denotándose
por $1, $2, $3 ...
En ocasiones yacc no puede determinar el tipo de un atributo.
En particular cuando se habla del atributo asociado con una acción
intermedia, ya que esta no tiene variable sintáctica asociada
explícitamente o bien cuando se habla de los atributos
de símbolos que están a la izquierda de la reducción actual
(véase la sección 35.13). Los atributos de símbolos
a la izquierda de la producción actual se denotan en yacc por números
no positivos $0, $-1, $-2 ....
En estos casos
el programador deberá especificar explícitamente el tipo del
atributo usando la notación $<tipo>#. Donde tipo es
uno de los campos de la union y # es el numeral
del símbolo correspondiente:
39 namelist
40 : NAME { printf("%s de clase %s, tipo %s\n",$1,CLASE($<n>-1),TIPO($<n>0)); }
41 | namelist ',' NAME
42 { printf("%s de clase %s, tipo %s\n",$3,CLASE($<n>-1),TIPO($<n>0)); }
43 ;
44 %%
yapp contiene la gramática
y las acciones
rhss: rhss '|' rule | rule
rule: rhs prec epscode | rhs
rhs: #empty
| rhselts
rhselts: rhselts rhselt | rhselt
rhselt: symbol | code
prec: PREC symbol
epscode: # vacio
| code
code: CODE
Las acciones semánticas (variable sintáctica code y terminal CODE)
se ejecutan siempre que ocurre una reducción por una regla y, en general, devuelven
un valor semántico. El código de la acción se copia verbatim
en el analizador. La estrategia usada por el analizador léxico
es contar las llaves abrir y cerrar en
el texto. Véase el correspondiente fragmento del analizador
léxico:
....
$lineno[0]=$lineno[1];
....
$$input=~/\G{/gc
and do {
my($level,$from,$code);
$from=pos($$input);
$level=1;
while($$input=~/([{}])/gc) {
substr($$input,pos($$input)-1,1) eq '\\' #Quoted
and next;
$level += ($1 eq '{' ? 1 : -1) or last;
}
$level and _SyntaxError(2,"Unmatched { opened line $lineno[0]",-1);
$code = substr($$input,$from,pos($$input)-$from-1);
$lineno[1]+= $code=~tr/\n//;
return('CODE',[ $code, $lineno[0] ]);
};
Las llaves dentro de cadenas y comentarios no son significativas en la cuenta.
El problema es que el reconocimiento de cadenas en Perl es mas difícil que
en otros lenguajes: existe toda una variedad de formas de denotar una cadena.
Por tanto, si el programador usuario de yapp necesita
escribir una llave dentro de una cadena de doble comilla, deberá escaparla.
Si la cadena es de simple comilla escaparla no es solución, pues
aparecería el símbolo de escape en la cadena. En ese caso se deberá añadir
un comentario con la correspondiente falsa llave. Siguen
algunos ejemplos tomadados de la documentación de Parse::Yapp
"{ My string block }"
"\{ My other string block \}"
qq/ My unmatched brace \} /
# Casamos con el siguiente: {
q/ for my closing brace } / #
q/ My opening brace { /
# debe cerrarse: }
yapp con cadenas que produzcan confusión
en el analizador y observe el comportamiento. Pruébelas en las diferentes
secciones en las que puede ocurrir código: en la cabecera, en el cuerpo
y en la cola.
yapp contiene las rutinas de soporte.
tail: /*empty*/
| TAILCODE
el terminal TAILCODE al igual que los terminales
CODE y HEADCODE indican que en ese punto se puede encontrar
código Perl. La detección de TAILCODE y HEADCODE son mas sencillas
que las de CODE.
La cola de un programa yacc es similar.
Para el programa yacc cuya cabecera y cuerpo
se mostraron en la sección
35.19.2
la cola es:
1 %%
2
3 extern FILE * yyin;
4
5 main(int argc, char **argv) {
6 if (argc > 1) yyin = fopen(argv[1],"r");
7 /* yydebug = 1;
8 */
9 yyparse();
10 }
11
12 yyerror(char *s) {
13 printf("%s\n",s);
14 }
La declaración del manejador de fichero yyin en la línea 14
referencia el archivo
de entrada para el analizador. La variable (comentada, línea 7)
yydebug controla la información para la depuración de la gramática.
Para que sea realmente efectiva, el programa deberá además compilarse
definiendo la macro YYDEBUG. Sigue un ejemplo
de Makefile:
1 inherited: y.tab.c lex.yy.c 2 gcc -DYYDEBUG=1 -g -o inherited1 y.tab.c lex.yy.c 3 y.tab.c y.tab.h: inherited1.y 4 yacc -d -v inherited1.y 5 lex.yy.c: inherited1.l y.tab.h 6 flex -l inherited1.l 7 clean: 8 - rm -f y.tab.c lex.yy.c *.o core inherited1
Al compilar tenemos:
pl@nereida:~/src/inherited$ make yacc -d -v inherited1.y flex -l inherited1.l gcc -DYYDEBUG=1 -g -o inherited1 y.tab.c lex.yy.c pl@nereida:~/src/inherited$ ls -ltr total 232 -rw-r----- 1 pl users 242 Dec 10 2003 Makefile -rw-r----- 1 pl users 404 Dec 10 2003 inherited1.l -rw-r----- 1 pl users 878 Dec 10 2003 inherited1.y -rw-rw---- 1 pl users 1891 Jan 26 15:41 y.tab.h -rw-rw---- 1 pl users 30930 Jan 26 15:41 y.tab.c -rw-rw---- 1 pl users 2365 Jan 26 15:41 y.output -rw-rw---- 1 pl users 44909 Jan 26 15:41 lex.yy.c -rwxrwx--x 1 pl users 56336 Jan 26 15:41 inherited1
yacc desarrollado
en las secciones anteriores ha sido escrito
usando la variante flex del lenguaje LEX. Un programa
flex tiene una estructura similar a la
de un program yacc con tres partes: cabeza, cuerpo
y cola separados por %%. Veamos como ejemplo de manejo de
flex, los contenidos
del fichero flex inherited1.l utilizado en las secciones
anteriores:
1 %{
2 #include <string.h>
3 #include "y.tab.h"
4 %}
5 id [A-Za-z_][A-Za-z_0-9]*
6 white [ \t\n]+
7 %%
8 global { return GLOBAL; }
9 local { return LOCAL; }
10 float { return FLOAT; }
11 int { return INTEGER; }
12 {id} { yylval.s = strdup(yytext); return NAME; }
13 {white} { ; }
14 , { return yytext[0]; }
15 . { fprintf(stderr,"Error. carácter inesperado.\n"); }
16 %%
17 int yywrap() { return 1; }
La cabeza contiene declaraciones C asi como definiciones
regulares. El fichero y.tab.h que es incluído en la línea
3, fué generado
por yacc y contiene, entre otras cosas,
la información recolectada
por yacc sobre los tipos de los atributos
(declaración %union) y la enumeración de los terminales.
Es, por tanto, necesario que la compilación con yacc
preceda a la compilación con flex.
La información en y.tab.h es usada por el analizador léxico
para ``sincronizarse'' con el analizador sintáctico.
Se definen en las líneas 5 y 6 las
macros para el reconocimiento de identificadores (id)
y blancos (white). Estas macros son llamadas en el cuerpo
en las líneas 12 y 13.
La estructura del cuerpo
consiste en parejas formadas por una definición
regular seguidas de una acción.
La variable yylval contiene el atributo asociado
con el terminal actual. Puesto que el token NAME
fué declarado del tipo cadena (véase 35.19.2),
se usa el correspondiente
nombre de campo yylval.s.
La cadena que acaba de casar queda guardada en la variable
yytext, y su longitud queda en la
variable entera global yyleng.
Una vez compilado con flex el fuente,
obtenemos un fichero denominado lex.yy.c.
Este fichero contiene la rutina yylex() que realiza el análisis
léxico del lenguaje descrito.
La función yylex() analiza las entradas, buscando la
secuencia mas larga que casa con alguna de las expresiones regulares
y ejecuta la correspondiente acción.
Si no se encuentra ningun emparejamiento se ejecuta la regla ``por defecto'', que es:
(.|\n) { printf("%s",yytext); }
Si encuentran dos expresiones regulares con las que la cadena mas larga
casa, elige la que figura primera en el programa flex.
Una vez que se ha ejecutado la correspondiente acción, yylex()
continúa con el resto de la entrada, buscando por subsiguientes
emparejamientos. Asi continúa hasta encontrar un final de fichero
en cuyo caso termina, retornando un cero o bien hasta que una de las
acciones explicitamente ejecuta una sentencia return.
Cuando el analizador léxico alcanza el final del fichero, el
comportamiento en las subsiguientes llamadas a yylex
resulta indefinido. En el momento en que yylex
alcanza el final del fichero llama a la función yywrap, la cual retorna un
valor de 0 o 1 según haya mas entrada o no. Si el valor es 0,
la función yylex asume que la propia yywrap
se ha encargado de abrir el nuevo fichero y asignarselo
a yyin.
yacc y flex para
completar los analizadores sintáctico y léxico descritos en las secciones
35.19.2,
35.19.4 y
35.19.5.
La gramática en cuestión es similar a la descrita
en la sección 35.13.
Usando la variable yydebug y la macro YYDEBUG
analize el comportamiento para la entrada
global float x,y.