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 : friosam@prodigy.net.mx
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
Página siguiente |