nodos en el árbol de análisis sintáctico que no deberían estar allí

Question

Estoy escribiendo un programa de análisis de una lengua, y el escáner está diseñado para

1. sea también vuelven terminales que no sean necesarios (por ejemplo whitespacing) O
2. no para hacerlo

según una bandera booleana.

Ahora, en el analizador sintáctico, no quiero saturar la gramática con todos esos terminales, deberían ser tragados de alguna manera "automágicamente" por el árbol de análisis sintáctico que estoy construyendo.

Para hacer esto "mágico", pensé que encadenaría los terminales (simplemente vinculados a la lista circular) para poder iterarlos y "completar los espacios en blanco" a medida que ocurre la reducción (estoy usando un LALR (1)) generador de analizador).

Parece una idea sensata, aunque hay un problema. ¿Recuerdas que dije "regresar ... o no"? En el escenario (2), liberaría la terminal, porque ¿quién sabe qué viene después? Y no quiero ninguna pérdida de memoria.

Pero en el escenario (1), no puedo liberar el terminal, porque basándome en ellos decidiré en reducciones adicionales donde el proceso de "rellenar los espacios en blanco" debería detenerse.

No puedo liberarlo condicional tampoco, por la misma razón: no sé lo que viene a continuación. ¿Qué ocurre si no se activa ningún proceso de "rellenar espacios en blanco"? ¿Qué pasa si no habrá más reducción en absoluto?

¿Has tenido problemas similares? ¿Cómo lo has resuelto?

Nota: esto es todo en mi mente y es posible que no lo haya explicado con suficiente claridad, por favor pregunte y voy a editar mi pregunta. El escenario es en realidad un poco más complejo, no estoy escribiendo esto desde cero, donde podría usar mi imaginación, lo estoy integrando en otra cosa, así que bien podría ser que responda con "No puedo hacer eso debido a las limitaciones del entorno ".

---

Adición

La única muy buena idea que viene a la mente es que tenedor y mejorar el generador de análisis, que ya he hecho en algunos lugares menores aquí y allá, para superar algunos de los limitaciones que mencioné arriba.

Answer 1

Su vocabulario es un poco extraño. La mayoría de los analizadores están diseñados para reconocer la sintaxis del idioma. por lo general, la definición de idioma define una noción de terminales y excluye explícitamente el "espacio en blanco", que consiste en secuencias de texto poco interesantes entre el texto de los terminales, que a menudo incluyen espacios en blanco, pestañas y varios tipos de comentarios independientes. Entonces, la palabra "terminal" usada en el análisis generalmente significa "aquellos átomos del lenguaje que no son espacios en blanco". Lo has definido implícitamente para incluir espacios en blanco, y creo que eso está causando tu dolor.

Desde este punto de vista, la forma más fácil de evitar la definición de gramática utilizada por su analizador con espacios en blanco es simplemente hacer que el lexer no pase espacios en blanco al analizador. Entonces tu gramática no necesita indicar cómo se manejan (y sí, las gramáticas que lo hacen son realmente desordenadas), el analizador no tiene que preocuparse por ellas y no se muestran en el árbol.

Si está compilando un compilador o un intérprete, ignorar los espacios en blanco es más fácil.

Si usted está construyendo un analizador de reingeniería (ver nuestra DMS Software Reengineering Toolkit, a continuación, la captura de los comentarios (al menos) en el AST es importante, ya que con el tiempo uno desea volver a generar el texto de AST consturcted, y es muy útil si el regenerado el texto contiene los comentarios también. [Puede hacerlo de otra forma, pero no es tan fácil].

El DMS lexer produce tokens "micro" que son su concepto de tokens de idioma, espacios en blanco y comentarios, internamente. Elimina micro-tokens de espacio en blanco porque simplemente no agregan nada (ver la discusión anterior). Transmite tokens convencionales al analizador sintáctico, como era de esperar. Pega los tokens de comentario al token de idioma anterior o siguiente, dependiendo de la tipo de token y wher e encontrado para C, a/* ... */visto antes de que se le anexe un token, y un // ... comentario se adjunta al token anterior (con algunos detalles más sutiles no discutidos aquí). Luego, el análisis solo ve tokens de idioma, por lo que la gramática no es innecesariamente complicada, y si toda la información adjunta al token se coloca en el árbol, los comentarios se completan durante el viaje.

Ahora, la gente a menudo quiere árboles de sintaxis "abstractos"; quieren dejar de lado cosas como "(" y ")". El esquema que describo arriba adjunta comentarios incluso a tokens concretos como estos. Ahora hay una complicación: si deja las fichas (..) fuera del árbol, desaparecen los comentarios adjuntos. Oops. Así que los analizadores DMS hacen algo complicado: los comentarios adjuntos a los tokens que tienen un lugar lógico en el árbol pero no están realmente allí ("terminales eliminados") se levantan al nodo padre del árbol con una anotación que dice que pertenecen al token secundario perdido . Sí, implementar esto es realmente un PITA. La buena noticia es que solo tuvimos que hacerlo una vez en la maquinaria de análisis general de DMS, y funciona para muchos idiomas. Pero esto significa que tiene que estar dispuesto a construir un analizador inusual ("reingeniería"), y tuvimos una motivación comercial para hacerlo.

EDITAR: No está claro por qué OP lo quiere, pero insiste en capturar espacios en blanco en el árbol. Como él no nos ha dicho por qué, voy a adivinar: quiere información precisa de la columna para los tokens/nodos de árbol. Eso no es difícil de hacer: enseñarle al lexer a hacer un seguimiento de la posición (línea/columna) y estampar cada token (micro-tokens como los comentarios, también) con la posición de inicio/final, y dejar que el análisis almacene esa información en el árbol. De esta manera evita mantener espacios en blanco en el árbol, también. (DMS también lo hace, porque al informar problemas, la información precisa es útil, y cuando se regenera el código, a menudo es deseable volver a colocar el código en su posición original (al menos la misma columna)).

EDIT2: Si OP insiste en capturar espacios en blanco, podría considerar explorar scannerless GLR parsing. Esto mantiene cada caracteres en la secuencia de entrada, incluido el espacio en blanco.