description Resumen problema:Unparse AST <O (exp (n))?
El modo de ver, medios unparsing para crear una corriente de contadores de un AST, que cuando se analiza de nuevo produce un AST iguales.
So parse(unparse(AST)) = AST mantiene.
Esto es lo mismo que encontrar un árbol de análisis válido que produzca el mismo AST.
El lenguaje está descrito por una gramática context freeS-attributed utilizando una variante eBNF.
Por lo tanto, el analizador tiene que encontrar una 'ruta' válida a través de los nodos atravesados en los que se mantienen todas las restricciones gramaticales. Esto básicamente significa encontrar una asignación válida de nodos AST a las reglas de producción de gramática. Este es un constraint satisfaction problem (CSP) en general y podría ser resuelto, como el análisis sintáctico, por backtracking en O (exp (n)).
Afortunadamente para el análisis, esto se puede hacer en O (n³) usando GLR (o restringiendo la gramática). Debido a que la estructura AST está muy cerca de la estructura de reglas de producción de gramática, realmente me sorprendió ver una implementación donde el tiempo de ejecución es peor que el análisis: XText usa ANTLR para analizar y retroceder para analizar.
Preguntas
- es un S-atributo de contexto libre de gramática todo lo que un programa de análisis y necesidad de compartir unparser o existen restricciones adicionales, por ejemplo en la técnica de análisis/implementación del analizador?
- Tengo la sensación de que este problema no es O (exp (n)) en general, ¿algún genio podría ayudarme con esto?
- ¿Es básicamente una gramática sensible al contexto?
Ejemplo 1:
Area returns AnyObject -> Pedestrian | Highway
Highway returns AnyObject -> "Foo" Car
Pedestrian returns AnyObject -> "Bar" Bike
Car returns Vehicle -> anyObjectInstance.name="Car"
Bike returns Vehicle -> anyObjectInstance.name="Bike"
Así que si tengo un AST contiene
AnyObject -> AnyObject -> Vehicle [name="Car"] y sé que la raíz puede ser la zona, pude resolverla a
Area -> Highway -> Car
Entonces la decisión (Carretera | Peatonal) depende de las decisiones del subárbol. El problema empeora cuando una hoja puede ser, a primera vista, de varios tipos, pero tiene que ser una específica para formar una ruta válida más adelante.
Ejemplo 2:
Así que si tengo reglas S-atributos devolver los objetos sin tipo, simplemente asignando algunos atributos, por ejemplo,
A -> B C {Obj, Obj}
X -> Y Z {Obj, Obj}
B -> "somekeyword" {0}
Y -> "otherkeyword" {0}
C -> "C" {C}
Z -> "Z" {Z}
Así que si un AST contiene
Obj
/\
"0" "C"
puedo unparse a
A
/\
B C
justo después de que podía resolver "C" a C.
Mientras que atraviesa la AST , todas las restricciones que puedo generar desde la gramática están satisfechas para ambas reglas, A y X, hasta que toco "C". Esto significa que para
A -> B | C
B -> "map" {MagicNumber_42}
C -> "foreach" {MagicNumber_42}
ambas soluciones para el árbol
Obj
|
MagicNumber_42
son válidos y se considera que tienen los mismos semántica, por ejemplo. azúcar sintáctica.
información:
Supongo que no entiendo. Un recorrido de profundidad en primer plano de un árbol de análisis debe visitar las hojas de token en su orden original. ¿Es el AST demasiado diferente del árbol de análisis sintáctico para hacer un cruce de este tipo? – phs
sí, el árbol de análisis sintáctico está 'fuertemente tipado', por lo que básicamente se sabe qué regla de gramática particular se utilizaron para producir un determinado nodo. Con un AST general, esta información se pierde y necesita ser reconstruida. Entonces, para analizar el AST, es suficiente construir un árbol de análisis válido que produzca este AST. Tenga en cuenta que puede haber varios árboles de análisis sintáctico, pero esto no importa porque cualquier valor válido de ellos tiene el mismo significado (azúcar sintáctico). El problema no radica en atravesar el AST, sino en etiquetar los nodos visitados con una secuencia válida de reglas de producción de gramática. –
La transformación que toma un árbol de análisis sintáctico para un AST depende de la aplicación; ya que parece que este es el paso que desea invertir, tendrá que informarnos sobre la aplicación específica (idioma). – phs