Un generador de evaluadores de gramáticas de atributos NC(1) de máximo paralelismo sin sincronización entre procesos

Abstract

En éste trabajo se presenta el desarrollo de un generador de evaluadores de gramáticas de atributos no circulares −NC(1)−. Este generador computa estáticamente toda la información necesaria para que el evaluador generado construya, en tiempo proporcional a la longitud del árbol, procesos concurrentes independientes capaces de producir la evaluación. Esto permite evaluar aprovechando el máximo paralelismo posible sin ningún tipo de sincronización. En éste trabajo se aprovechan dos enfoques: el clásico enfoque secuencial, que determina un orden lineal de evaluación, con el enfoque recientemente propuesto por Wuu Yang para el particionado de mayor refinamiento del grafo de dependencias en regiones disjuntas. El algoritmo desarrollado evita un recorrido adicional sobre el árbol sintáctico y completa el estudio de los detalles para la implementación del evaluador. Este desarrollo se integrará como evaluador alternativo de un generador de procesadores de lenguajes