Software didáctico para la construcción de analizadores sintácticos descendentes no recursivos predictivos

Software didáctico para la construcción de analizadores sintacticos descendentes no recursivos predictivos. Ing. Francisco Ríos Acosta Instituto Tecnológico de la Laguna, a 25 de agosto del 2008. pag. 1 de 44 Software didáctico para la construcción de analizadores sintacticos descendentes no recursivos predictivos.

FRANCISCO RÍOS ACOSTA Instituto Tecnológico de la Laguna Blvd. Revolución y calzada Cuauhtémoc s/n Colonia centro Torreón, Coah; México Contacto : [email protected]

Resúmen. Se presenta un software didáctico denominado RD-NRP cuyo objetivo es ayudar en el proceso de enseñanza-aprendizaje del tema “análisis sintactico” dentro del curso de Programación de Sistemas. Además, permite la generación de código de una clase denominada SintDescNRP que es usada para definir objetos cuyo fin es analizar sintacticamente un grupo de sentencias. El software ofrece las facilidades : (1) Ingreso de una gramática de contexto libre no ambigua, (2) Transformación de la gramática : eliminación de la recursividad a la izquierda y factorización a la izquierda, (3) Obtención de los conjuntos : PRIMEROS y SIGUIENTES, (4) Construcción de la tabla M de reconocimiento, (5) Simulación del reconocedor descendente, y (6) generación de código en C# para la clase SintDescNRP. La teoría de base para la construcción del software fue tomada del libro “del dragón” de Aho, Sethi y Ullman. El trabajo termina mostrando la construcción de un analizador sintactico no recursivo predictivo escrito en C#, que usa el código producido por los sofware’s didácticos SP-PS1 y RD-NRP.

Software didáctico para la construcción de analizadores sintacticos descendentes no recursivos predictivos. Instituto Tecnológico de la Laguna, a 25 de agosto del 2008. pag. 3 de 44 Ing. Francisco Ríos Acosta 1 Introducción. El software didáctico RD-NRP es un ejecutable en ambiente Windows, escrito en C# de Visual Studio 2005 de MicroSoft. Su uso se suscribe a la materia de Programación de Sistemas en su tema Análisis Sintactico-Reconocedores Descendentes. El usuario de este software tiene acceso a las siguientes utilidades : • • • • • •

•

• Ingreso de una gramática de contexto libre no ambigua. Transformación de la gramática eliminando la recursividad a la izquierda E.R.I., haciendo no recursivo al reconocedor. Transformación de la gramática factorizando a la izquierda, haciendo predictivo al reconocedor. Obtención del conjunto PRIMERO para cada no terminal de la gramática transformada. Obtención del conjunto SIGUIENTE para cada no terminal de la gramática transformada. Construcción de la tabla M de reconocimiento, usada por el algoritmo del reconocedor descendente no recursivo predictivo. Simulación del reconocimiento de una sentencia, visualizando la derivación a la izquierda producida por el reconocedor descendente. Generación del código para la clase SintDescNRP, que permite definir objetos dentro de una aplicación C#, que analizan sintacticamente un grupo de sentencias que cumplen con la sintaxis descrita por una gramática de contexto libre.

Durante la exposición de este trabajo, veremos cómo se usa, la utilidad del RD-NRP, además de terminar explicando la construcción de un anañizador sintactico descendente no recursivo predictivo, que utiliza el código generado por este software didáctico. 2 Ingreso de una gramática de contexto libre no ambigua. Esta característica representa el punto de inicio para la construcción del reconocedor descendente. Proporciona al usuario las funciones : • • • • • • • Ingreso de la gramática desagrupada. Configuración del número de yes. Inserción de renglones para una edición mas amigable. Limpieza o inicialización de la rejilla de ingreso de la gramática, para iniciar en 0 producciones. Carga de una gramática previamente tecleada y salvada. Salvar la gramática que se ha tecleado en la rejilla de ingreso. Análisis de la gramática, visualizando sus producciones, los símbolos no terminales y los terminales. Si hay errores son comunicados al usuario, permaneciendo la gramática en un estado denominado DEFICIENTE. Si no existieron errores en el análisis, la gramática tiene un estado OK.

La figura #2.1 muestra la interfase para una gramática de asignación, analizada y con estado OK. El resultado del análisis indica 10 producciones, 10 símbolos terminales y 4 símbolos no terminales. Las producciones agrupadas de la gramática son :

A -> id = E ; E -> E + T

T -> T * F |

| E – T

T / F |

| T

F F -> id | num | ( E ) Para llegar a la interfase mostrada en la figura 2.1 debemos ingresar a cada producción de la gramática utilizando un renglón de la rejilla de entrada, para cada componente de la producción. Es decir, primero ingresamos al miembro izquierdo de la producción que será invariablemente un no terminal, debido a que manejamos sólo gramáticas de contexto libre. Los símbolos no terminales las denotamos con una letra mayúscula. En la columna siguiente debemos ingresar el número de yes de la producción. Las Y’s son los símbolos terminales o no terminales que conforman al miembro derecho de la producción. Por último debemos ingresar a cada Y del miembro derecho de la producción : Y1, Y2, Y3, …, Yn.

La figura #2.2 muestra la interfase que contiene el estado de la gramática después de haber ingresado a cada producción de la gramática.

Software didáctico para la construcción de analizadores sintacticos descendentes no recursivos predictivos. Ing. Francisco Ríos Acosta Instituto Tecnológico de la Laguna, a 25 de agosto del 2008. pag. 4 de 44 Fig. No. 2.1 Interfase de