Algoritmo de construcción de tabla de precedencia para CFGs independientemente de ser OPGs
Autores: Lizcano, Leonardo; Angulo, Eduardo; Márquez, José
Idioma: Inglés
Editor: MDPI
Año: 2024
Acceso abierto
Artículo científico
2024
Algoritmo de construcción de tabla de precedencia para CFGs independientemente de ser OPGs
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Gramáticas de precedencia de operadores
Gramáticas libres de contexto
Lenguajes de precedencia de operadores
Relaciones de precedencia
Conjuntos izquierdos y derechos
Algoritmos
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 27
Citaciones: Sin citaciones
Las gramáticas de precedencia de operadores (OPG) son gramáticas libres de contexto (CFG) que se caracterizan por la ausencia de dos símbolos no terminales adyacentes en el cuerpo de cada producción (lado derecho). Los lenguajes de precedencia de operadores (OPL) son deterministas y libres de contexto. Se establecen tres posibles relaciones de precedencia entre pares de símbolos terminales para estos lenguajes. Muchas CFG no son OPG porque la precedencia de operadores no se puede aplicar a ellas al no cumplir con la regla básica. Para resolver este problema, hemos realizado una redefinición exhaustiva de los conjuntos de terminales Izquierdo y Derecho que son la base para calcular las relaciones de precedencia, y hemos definido un nuevo conjunto Izquierdo más a la izquierda. Los algoritmos para calcularlos también se describen en detalle. La contribución más significativa de nuestro trabajo es que establecemos relaciones de precedencia entre terminales superando la regla básica de no tener dos no terminales consecutivos mediante un algoritmo que permite construir la tabla de precedencia de operadores para una CFG independientemente de si es un OPG. El documento muestra las complejidades de los algoritmos propuestos y posibles excepciones a las reglas propuestas. Presentamos ejemplos utilizando un OPG y dos no-OPGs para ilustrar el funcionamiento de los algoritmos propuestos. Con estos, se construye la tabla de precedencia de operadores y se realiza el análisis ascendente correctamente.
Descripción
Las gramáticas de precedencia de operadores (OPG) son gramáticas libres de contexto (CFG) que se caracterizan por la ausencia de dos símbolos no terminales adyacentes en el cuerpo de cada producción (lado derecho). Los lenguajes de precedencia de operadores (OPL) son deterministas y libres de contexto. Se establecen tres posibles relaciones de precedencia entre pares de símbolos terminales para estos lenguajes. Muchas CFG no son OPG porque la precedencia de operadores no se puede aplicar a ellas al no cumplir con la regla básica. Para resolver este problema, hemos realizado una redefinición exhaustiva de los conjuntos de terminales Izquierdo y Derecho que son la base para calcular las relaciones de precedencia, y hemos definido un nuevo conjunto Izquierdo más a la izquierda. Los algoritmos para calcularlos también se describen en detalle. La contribución más significativa de nuestro trabajo es que establecemos relaciones de precedencia entre terminales superando la regla básica de no tener dos no terminales consecutivos mediante un algoritmo que permite construir la tabla de precedencia de operadores para una CFG independientemente de si es un OPG. El documento muestra las complejidades de los algoritmos propuestos y posibles excepciones a las reglas propuestas. Presentamos ejemplos utilizando un OPG y dos no-OPGs para ilustrar el funcionamiento de los algoritmos propuestos. Con estos, se construye la tabla de precedencia de operadores y se realiza el análisis ascendente correctamente.