domingo, febrero 27, 2005
Un mar de configuraciones
Ates: link a la version en MSWord de este blog:
http://www.geocities.com/jahazhn/cmpl/un_mar_de_configuraciones.doc
La plataforma eclipse puede ser un poco confusa. Son muy agradables toda la gama de posibilidades y facilidades que posee, sin embargo, por ser un IDE muy apartado de lo común requiere bastante tiempo para adaptarse a él.
Uno de los prejuicios más grandes que tengo, es por no tener obvio el comando “compilar”, eso es lo que opina un fanático de DEV C++ 4, donde en el centro de la barra de herramientas aparecen los tres botones: “Compilar”, “Correr”, o para ir de un solo al mandado, “Compilar y correr”.
Hasta hace unos días encontré el comando “Construir” (Build).
El otro detalle que me ha llevado hasta el borde de la desesperación, es el casi infinito mar de configuraciones, un cuadro de diálogo tras otro, y en cada cuadro , “ene” posibilidades... hablando concretamente, en las configuraciones para el comando “Run...”, olvidé ese paso, por eso, no importaba cuantas veces creara un nuevo proyecto, o incluso un nuevo espacio de trabajo, el dichoso IDE seguía buscando el método main de la primera cosa que hice con eclipse, de modo que nunca encontraba los nuevos archivos.
Ese es el tipo de cosas que deja la sensación de no saber si el de ‘la falla’ es el usuario o el que diseñó el programa. Por convención, suele ser el usuario, ¿verdad?.
Una vez superadas esas dificultades con el IDE, el proyecto se pone en marcha luego de un poco de observación de la gramática en la definición de micro-C.
Aquí muestro el código del lexer
class lexico extends Lexer;
options{ k=4; }
TOK_IF: "if";
TOK_ELSE: "else";
TOK_RETURN: "return";
TOK_WHILE: "while";
TOK_BREAK: "break";
TOK_CONTINUE: "continue";
TOK_TYPE_INT: "int";
TOK_TYPE_CHAR: "char" ;
TOK_VOID: "void";
ASSIGN:('=');
ADD_OP:('+''-');
MUL_OP:('*''/');
EQ_OP:("==""!=");
REL_OP:("<="">=");
REL_OP2:("<"">");
OPEN_PAR:('(');
CLOSE_PAR: (')');
OPEN_BRACE:('{');
CLOSE_BRACE: ('}');
COMMA: (',');
SEMICOLON: (';');
SUSPENSIVE: "...";
SPACE: (' ''\r''\n'){$setType(Token.SKIP); } ;
IDENTIFIER:
(LETTER)(LETTERDIGIT)*
;
INTEGER_CONSTANT:
(ZERO)(NONZERO)(DIGIT)*
;
protected ZERO:'0';
protected NONZERO:('1'..'9');
protected DIGIT:(ZERONONZERO);
protected LETTER:('a'..'z''A'..'Z''_') ;
CHAR_CONSTANT: ('\'')(LETTERDIGIT)('\''); //aun falta
STRING_CONSTANT: ('\"')()('\"'); //aun falta
protected COMMENT: "/*"()"*/";
Las definiciones de los operadores y palabras reservadas no dan mayor problema, solamente hay que fijarse de definirlas antes que los identificadores, para que el “no-determinismo” no sea una dificultad extra.
Los elementos más complejos han resultado ser la constante de caracter y la constate de cadena. En realidad, solamente se trata de analizar con calma elcaso en particular.
Continuamos con el Parser
El parser es sin duda la parte más emocionante d este proyecto, hasta ahora. Resulta sorprendente que la “Teoría de la computación” sirva para algo, (al cursar esa clase, esa es la interrogante más popular, pero la única que el maestro no contesta... ¿porqué nos hace eso? ).
Al definir la gramática del lenguaje a nivel de tokens, se logra ver con toda claridad la estructura del programa, y como es de esperar, hay que tener ciertas delicadezas con esa gramática.
El primer problema que se detecta al introducir una gramática y compilar el código de ANTLR para el parser es el de “Infinite recursion...”. La recursión izquierda, como la conocemos en español, es el primer detalle a tratar.
Eliminando recursión izquierda
A continuación muestro las transformaciones que realicé a algunas de las producciones de la gramática provista por el profesor:
( léase el signo ‘&’ como ‘lamda’)
translation_unit -> external_declaration translation_unit external_declaration
--------------------------------------------------------------------------------
translation_unit -> external_declaration translation_item
translation_item -> external_declaration translation_item &
parameter_def_list -> type identifier parameter_def_list "," type identifier;
-------------------------------------------------------------------------------
parameter_def_list -> type identifier parameter_item
parameter_item -> "," type identifier parameter_item &
declarations -> declarations declaration &
---------------------------------------------
declarations -> declarative
declarative -> declaration declarative &
parameter_decl_list -> parameter_decl_list "," parameter_decl_spec parameter_decl_spec
----------------------------------------------------------------------------------------
parameter_decl_list -> parameter_decl_spec parameter_declarative
parameter_declarative -> "," parameter_decl_spec parameter_declarative &
statement_list -> statement_list statement statement
------------------------------------------------------
statement_list -> statement statement_item
statement_item -> statement statement_item &
simple_expression -> simple_expression add_op term term
---------------------------------------------------------
simple_expression -> term simple_expression_
simple_expression_ -> add_op term simple_expression_ &
term -> term mul_op factor factor
-----------------------------------
term -> factor term_
term_ -> mul_op factor term_ &
expression_list -> expression_list "," expression expression
--------------------------------------------------------------
expression_list -> expression expression_list_
expression_list_ -> "," expression expression_list_ &
identifier_list -> identifier_list "," identifier identifier
---------------------------------------------------------------
identifier_list -> identifier identifier_list_
identifier_list_ -> "," identifier identifier_list_ &
Este procedimiento resulta relativamente sencillo, ya que la transformación implica solamente aplicar una fórmula de dos pasos.
Producciones no deterministas
Un segundo problema resulta el no-determinismo de algunas de las producciones, generalmente las de la forma A -> B BC. En algunos casos, no basta para ANTLR aplicar factorización izquierda, por ejemplo, si hacemos A -> BH, H -> C ‘lambda’, ANTLR reportará no-determinismo en la producción H.
Todavía no he encontrado la manera de solucionar este problema; mencionando que para estos casos estoy utilizando el operador ‘?’, que significa “cero o una vez”, es decir H -> C?.
A continuación muestro la gramática para el Parser, en formato de ANTLR, encontrará marcadas con un ‘!!’ al inicio d la línea, aquellas producciones en las cuales he encontrado el problema arriba descrito.
class parsico extends Parser;
startRule: translation_unit;
translation_unit : external_declaration translation_item;
translation_item : (external_declaration translation_item)?;
!!external_declaration : function_definition declaration;
function_definition : function_def_header function_body;
function_def_header : return_type IDENTIFIER (OPEN_PAR) parameters_def (CLOSE_PAR);
return_type : type (TOK_VOID);
parameters_def : parameter_def_list (TOK_VOID);
parameter_def_list : type IDENTIFIER parameter_item;
parameter_item : ((COMMA) type IDENTIFIER parameter_item)?;
function_body : (OPEN_BRACE) declarations statement_list (CLOSE_BRACE);
declarations : declarative;
declarative : (declaration declarative)?;
!!declaration : variable_declaration function_declaration;
variable_declaration : type identifier_list (SEMICOLON);
function_declaration : return_type IDENTIFIER (OPEN_PAR)
!!parameters_decl (CLOSE_PAR) (SEMICOLON);
parameters_decl : parameter_decl_list parameter_decl_list (COMMA) (SUSPENSIVE) (TOK_VOID);
parameter_decl_list : parameter_decl_spec parameter_declarative;
!!parameter_declarative : (COMMA parameter_decl_spec parameter_declarative)?;
parameter_decl_spec : type IDENTIFIER;
statement_list : statement statement_item;
statement_item : (statement statement_item)?;
!!statement : expression (SEMICOLON)
(TOK_RETURN) statement_
(TOK_WHILE) (OPEN_PAR) expression (CLOSE_PAR) statement
(TOK_IF) (OPEN_PAR) expression (CLOSE_PAR) statement //else_statement
(TOK_IF) (OPEN_PAR) expression (CLOSE_PAR) statement (TOK_ELSE) statement
(OPEN_BRACE) statement_list (CLOSE_BRACE)
// (TOK_RETURN) (SEMICOLON)
(TOK_BREAK) (SEMICOLON)
(TOK_CONTINUE) (SEMICOLON);
statement_: expression SEMICOLON SEMICOLON;
//else_statement : (TOK_ELSE statement)?;
expression : equality_expression ((ASSIGN) equality_expression)?;
equality_expression : relational_expression ((EQ_OP) relational_expression)?;
relational_expression : simple_expression ((REL_OP) simple_expression)?;
simple_expression : term simple_expression_;
simple_expression_ : ((ADD_OP) term simple_expression_)?;
term : factor term_;
term_ : (MUL_OP factor term_)?;
factor :
constant
(ADD_OP) factor
IDENTIFIER ((OPEN_PAR) factor_)?
(OPEN_PAR) expression (CLOSE_PAR);
factor_ : (CLOSE_PAR) expression_list (CLOSE_PAR);
constant : STRING_CONSTANT numeric_constant CHAR_CONSTANT;
numeric_constant : INTEGER_CONSTANT;
expression_list : expression expression_list_;
expression_list_ : ((COMMA) expression expression_list_)?;
identifier_list : IDENTIFIER identifier_list_;
identifier_list_ : ((COMMA) IDENTIFIER identifier_list_)?;
type : (TOK_TYPE_INT) (TOK_TYPE_CHAR);
La mente se consuela con un clásico “un poco más de análisis bastará para hallar la solución...”
Este es el contenido de uno de los archivos que he probado con el “compilador”:
int uno(int x, char c){
int y, z, w;
char r, c;
if(c == c){break;}
return x + 3;
}
A estas alturas del proyecto, me siento más realizado si el código generado “acepta” el input, que si le encuentra errores, porque mientras no corrija el no-determinismo de la gramática, no se logra reconocer código válido, como en:
if(c == c){break;}else{continue;}.
Este tipo de input no es aceptada aún por la gramática expuesta más arriba.
Ahora viene la etapa de reportar errores. Aquí es donde “la mula botó a Genaro”.
http://www.geocities.com/jahazhn/cmpl/un_mar_de_configuraciones.doc
La plataforma eclipse puede ser un poco confusa. Son muy agradables toda la gama de posibilidades y facilidades que posee, sin embargo, por ser un IDE muy apartado de lo común requiere bastante tiempo para adaptarse a él.
Uno de los prejuicios más grandes que tengo, es por no tener obvio el comando “compilar”, eso es lo que opina un fanático de DEV C++ 4, donde en el centro de la barra de herramientas aparecen los tres botones: “Compilar”, “Correr”, o para ir de un solo al mandado, “Compilar y correr”.
Hasta hace unos días encontré el comando “Construir” (Build).
El otro detalle que me ha llevado hasta el borde de la desesperación, es el casi infinito mar de configuraciones, un cuadro de diálogo tras otro, y en cada cuadro , “ene” posibilidades... hablando concretamente, en las configuraciones para el comando “Run...”, olvidé ese paso, por eso, no importaba cuantas veces creara un nuevo proyecto, o incluso un nuevo espacio de trabajo, el dichoso IDE seguía buscando el método main de la primera cosa que hice con eclipse, de modo que nunca encontraba los nuevos archivos.
Ese es el tipo de cosas que deja la sensación de no saber si el de ‘la falla’ es el usuario o el que diseñó el programa. Por convención, suele ser el usuario, ¿verdad?.
Una vez superadas esas dificultades con el IDE, el proyecto se pone en marcha luego de un poco de observación de la gramática en la definición de micro-C.
Aquí muestro el código del lexer
class lexico extends Lexer;
options{ k=4; }
TOK_IF: "if";
TOK_ELSE: "else";
TOK_RETURN: "return";
TOK_WHILE: "while";
TOK_BREAK: "break";
TOK_CONTINUE: "continue";
TOK_TYPE_INT: "int";
TOK_TYPE_CHAR: "char" ;
TOK_VOID: "void";
ASSIGN:('=');
ADD_OP:('+''-');
MUL_OP:('*''/');
EQ_OP:("==""!=");
REL_OP:("<="">=");
REL_OP2:("<"">");
OPEN_PAR:('(');
CLOSE_PAR: (')');
OPEN_BRACE:('{');
CLOSE_BRACE: ('}');
COMMA: (',');
SEMICOLON: (';');
SUSPENSIVE: "...";
SPACE: (' ''\r''\n'){$setType(Token.SKIP); } ;
IDENTIFIER:
(LETTER)(LETTERDIGIT)*
;
INTEGER_CONSTANT:
(ZERO)(NONZERO)(DIGIT)*
;
protected ZERO:'0';
protected NONZERO:('1'..'9');
protected DIGIT:(ZERONONZERO);
protected LETTER:('a'..'z''A'..'Z''_') ;
CHAR_CONSTANT: ('\'')(LETTERDIGIT)('\''); //aun falta
STRING_CONSTANT: ('\"')()('\"'); //aun falta
protected COMMENT: "/*"()"*/";
Las definiciones de los operadores y palabras reservadas no dan mayor problema, solamente hay que fijarse de definirlas antes que los identificadores, para que el “no-determinismo” no sea una dificultad extra.
Los elementos más complejos han resultado ser la constante de caracter y la constate de cadena. En realidad, solamente se trata de analizar con calma elcaso en particular.
Continuamos con el Parser
El parser es sin duda la parte más emocionante d este proyecto, hasta ahora. Resulta sorprendente que la “Teoría de la computación” sirva para algo, (al cursar esa clase, esa es la interrogante más popular, pero la única que el maestro no contesta... ¿porqué nos hace eso? ).
Al definir la gramática del lenguaje a nivel de tokens, se logra ver con toda claridad la estructura del programa, y como es de esperar, hay que tener ciertas delicadezas con esa gramática.
El primer problema que se detecta al introducir una gramática y compilar el código de ANTLR para el parser es el de “Infinite recursion...”. La recursión izquierda, como la conocemos en español, es el primer detalle a tratar.
Eliminando recursión izquierda
A continuación muestro las transformaciones que realicé a algunas de las producciones de la gramática provista por el profesor:
( léase el signo ‘&’ como ‘lamda’)
translation_unit -> external_declaration translation_unit external_declaration
--------------------------------------------------------------------------------
translation_unit -> external_declaration translation_item
translation_item -> external_declaration translation_item &
parameter_def_list -> type identifier parameter_def_list "," type identifier;
-------------------------------------------------------------------------------
parameter_def_list -> type identifier parameter_item
parameter_item -> "," type identifier parameter_item &
declarations -> declarations declaration &
---------------------------------------------
declarations -> declarative
declarative -> declaration declarative &
parameter_decl_list -> parameter_decl_list "," parameter_decl_spec parameter_decl_spec
----------------------------------------------------------------------------------------
parameter_decl_list -> parameter_decl_spec parameter_declarative
parameter_declarative -> "," parameter_decl_spec parameter_declarative &
statement_list -> statement_list statement statement
------------------------------------------------------
statement_list -> statement statement_item
statement_item -> statement statement_item &
simple_expression -> simple_expression add_op term term
---------------------------------------------------------
simple_expression -> term simple_expression_
simple_expression_ -> add_op term simple_expression_ &
term -> term mul_op factor factor
-----------------------------------
term -> factor term_
term_ -> mul_op factor term_ &
expression_list -> expression_list "," expression expression
--------------------------------------------------------------
expression_list -> expression expression_list_
expression_list_ -> "," expression expression_list_ &
identifier_list -> identifier_list "," identifier identifier
---------------------------------------------------------------
identifier_list -> identifier identifier_list_
identifier_list_ -> "," identifier identifier_list_ &
Este procedimiento resulta relativamente sencillo, ya que la transformación implica solamente aplicar una fórmula de dos pasos.
Producciones no deterministas
Un segundo problema resulta el no-determinismo de algunas de las producciones, generalmente las de la forma A -> B BC. En algunos casos, no basta para ANTLR aplicar factorización izquierda, por ejemplo, si hacemos A -> BH, H -> C ‘lambda’, ANTLR reportará no-determinismo en la producción H.
Todavía no he encontrado la manera de solucionar este problema; mencionando que para estos casos estoy utilizando el operador ‘?’, que significa “cero o una vez”, es decir H -> C?.
A continuación muestro la gramática para el Parser, en formato de ANTLR, encontrará marcadas con un ‘!!’ al inicio d la línea, aquellas producciones en las cuales he encontrado el problema arriba descrito.
class parsico extends Parser;
startRule: translation_unit;
translation_unit : external_declaration translation_item;
translation_item : (external_declaration translation_item)?;
!!external_declaration : function_definition declaration;
function_definition : function_def_header function_body;
function_def_header : return_type IDENTIFIER (OPEN_PAR) parameters_def (CLOSE_PAR);
return_type : type (TOK_VOID);
parameters_def : parameter_def_list (TOK_VOID);
parameter_def_list : type IDENTIFIER parameter_item;
parameter_item : ((COMMA) type IDENTIFIER parameter_item)?;
function_body : (OPEN_BRACE) declarations statement_list (CLOSE_BRACE);
declarations : declarative;
declarative : (declaration declarative)?;
!!declaration : variable_declaration function_declaration;
variable_declaration : type identifier_list (SEMICOLON);
function_declaration : return_type IDENTIFIER (OPEN_PAR)
!!parameters_decl (CLOSE_PAR) (SEMICOLON);
parameters_decl : parameter_decl_list parameter_decl_list (COMMA) (SUSPENSIVE) (TOK_VOID);
parameter_decl_list : parameter_decl_spec parameter_declarative;
!!parameter_declarative : (COMMA parameter_decl_spec parameter_declarative)?;
parameter_decl_spec : type IDENTIFIER;
statement_list : statement statement_item;
statement_item : (statement statement_item)?;
!!statement : expression (SEMICOLON)
(TOK_RETURN) statement_
(TOK_WHILE) (OPEN_PAR) expression (CLOSE_PAR) statement
(TOK_IF) (OPEN_PAR) expression (CLOSE_PAR) statement //else_statement
(TOK_IF) (OPEN_PAR) expression (CLOSE_PAR) statement (TOK_ELSE) statement
(OPEN_BRACE) statement_list (CLOSE_BRACE)
// (TOK_RETURN) (SEMICOLON)
(TOK_BREAK) (SEMICOLON)
(TOK_CONTINUE) (SEMICOLON);
statement_: expression SEMICOLON SEMICOLON;
//else_statement : (TOK_ELSE statement)?;
expression : equality_expression ((ASSIGN) equality_expression)?;
equality_expression : relational_expression ((EQ_OP) relational_expression)?;
relational_expression : simple_expression ((REL_OP) simple_expression)?;
simple_expression : term simple_expression_;
simple_expression_ : ((ADD_OP) term simple_expression_)?;
term : factor term_;
term_ : (MUL_OP factor term_)?;
factor :
constant
(ADD_OP) factor
IDENTIFIER ((OPEN_PAR) factor_)?
(OPEN_PAR) expression (CLOSE_PAR);
factor_ : (CLOSE_PAR) expression_list (CLOSE_PAR);
constant : STRING_CONSTANT numeric_constant CHAR_CONSTANT;
numeric_constant : INTEGER_CONSTANT;
expression_list : expression expression_list_;
expression_list_ : ((COMMA) expression expression_list_)?;
identifier_list : IDENTIFIER identifier_list_;
identifier_list_ : ((COMMA) IDENTIFIER identifier_list_)?;
type : (TOK_TYPE_INT) (TOK_TYPE_CHAR);
La mente se consuela con un clásico “un poco más de análisis bastará para hallar la solución...”
Este es el contenido de uno de los archivos que he probado con el “compilador”:
int uno(int x, char c){
int y, z, w;
char r, c;
if(c == c){break;}
return x + 3;
}
A estas alturas del proyecto, me siento más realizado si el código generado “acepta” el input, que si le encuentra errores, porque mientras no corrija el no-determinismo de la gramática, no se logra reconocer código válido, como en:
if(c == c){break;}else{continue;}.
Este tipo de input no es aceptada aún por la gramática expuesta más arriba.
Ahora viene la etapa de reportar errores. Aquí es donde “la mula botó a Genaro”.
Comments:
Publicar un comentario
<< Home
<< Home
