0
428
Vistas¿Cómo dejar de lado los nodos sin importancia?
Estoy usando ANTLR 4.9.2 para analizar una gramática que representa instrucciones de ensamblaje.
grammar IrohAsm; main: line* | EOF; line: (rangedec | instruction | comment)? EOL; instruction: MNEMONIC firstoperand COMMA secondoperand; rangedec : range assignment?; firstoperand : range | mem | REGISTER; secondoperand : range | mem | IMM | REGISTER; range : IDENTIFIER OPENBRACKETS IMM CLOSEDBRACKETS; assignment : EQUALS OPENCURL IMM (COMMA IMM)* CLOSECURL; mem : AT IMM; comment : '#' ~EOL*; WHITESPACE : (' ') -> skip ; // remember to append \n to input EOL : '\n'; OPENCURL : '{'; CLOSECURL : '}'; OPENBRACKETS : '['; CLOSEDBRACKETS : ']'; COMMA : ','; EQUALS : '='; AT : '@'; MNEMONIC : ('jmp' | 'add' | 'sub' | 'jez' | 'mov' | 'wrt' | 'get'); REGISTER: ('ab' | 'bb' | 'cb' | 'db'); IMM : DIGITS RADIX?; RADIX : ('d' | 'b' | 'h'); DIGITS : [0-9]+; IDENTIFIER: ([a-zA-Z0-9] | '$' | '_' | '\u00C0'..'\uFFFF')+ ;La gramática funciona bien, pero genera árboles como el siguiente;
cuando se le da la siguiente entrada:
mov ab,abComo puede ver, COMMA se incluye como uno de los elementos secundarios de la instrucción. Su ubicación es importante para el idioma, pero realmente no me importa después del análisis. ¿Hay alguna manera de que pueda dejarlo fuera del árbol final por completo? Y si es así, ¿sería esto un cambio en la gramática o en mi código para analizar el árbol?
Mi código actual para obtener el árbol:
CharStream inputStream = CharStreams.fromFileName("src/test/assembly/cool.asm"); IrohAsmLexer lexer = new IrohAsmLexer(inputStream); IrohAsmParser parser = new IrohAsmParser(new CommonTokenStream(lexer)); ParseTree parseTree = parser.main();3 Respuestas
Responde la pregunta0
Su pregunta se reduce a: "¿cómo puedo convertir mi árbol de análisis en un árbol de sintaxis abstracta?". La respuesta simple a eso es: "no puedes" :). Al menos, no usar un mecanismo ANTLR incorporado. Tendrá que recorrer el árbol de análisis (utilizando el mecanismo de visitante o oyente de ANTLR) y construir su AST manualmente.
La función para crear AST más fácilmente a partir de un árbol de análisis a menudo aparece en el repositorio de Github de ANTLR:
así como en stackoverflow:
0
Para ANTLR, como dice Bart, no puedes hacerlo sin hacerlo tú mismo. Esencialmente, debe escribir un código personalizado para recorrer el CST y construir un AST personalizado.
No tiene que ser de esta manera. Puede construir generadores de analizadores que construyan automáticamente árboles que:
- Omita los nodos que no tengan ningún valor (p. ej., "coma", EOL)
- Elimine cadenas de producciones unarias (p. ej., "primer operando" y "segundo operando; estas son cadenas cortas en su ejemplo, pero los árboles de expresión tienden a tener cadenas largas)
- Construya listas de nodos siempre que se generen árboles inclinados hacia la derecha o hacia la izquierda a partir de reglas gramaticales que representan listas, reemplazando los nodos de "columna vertebral" y el nodo final de la lista, si corresponde, con un solo nodo de lista. (Tu ejemplo no tiene ninguno de estos). Esto hace que las listas sean más pequeñas y fáciles de manipular.
El resultado da algo muy parecido a los AST clásicos sin ningún esfuerzo manual; los árboles resultantes suelen tener entre un 30 y un 50 % del tamaño de los CST de los que se derivan automáticamente.
Esto importa cuando
- trabajando con gramáticas grandes (no desea tener que definir el mapeo de cada nodo a mano para 3500 reglas)
- trabajar con gramáticas que cambian rápidamente (mientras intenta obtener un primer borrador correcto)
- herramientas de construcción que procesan árboles muy grandes (que representan [sistemas] muy grandes de código fuente, digamos el árbol fuente de Linux) que tienen que tocar miles de millones de nodos para calcular la respuesta, evitando muchos accesos a líneas de caché que contendrían nodos concretos o lista de espinas.
Proporcionaría el nombre de la herramienta que hace esto que diseñé y construí, pero algunas personas odian cuando lo hago. Puedes consultar mi perfil.
0
Para cualquiera que esté atascado en esto, la respuesta de Bart Kiers es un gran punto de partida, algunos recursos que encontré que explican bien los patrones de Oyente/Visitante son:
- Esta presentación del departamento de informática de la Universidad de Taylor y el ejemplo adjunto de GitHub (específicamente las partes sobre el patrón de visitante)
- El ejemplo de la referencia definitiva de ANTLR4 "4.3 Construyendo un traductor con un oyente"