Solución:
Bueno, primero que nada, la gramática se usa para construir un árbol de análisis a partir de una expresión. Entonces, si ya tiene un árbol de análisis, no necesita la gramática.
Dependiendo de cuánto trabajo haga su analizador, el árbol resultante que se forma al analizar una expresión ya podría ser un árbol de sintaxis abstracto. O podría ser un árbol de análisis simple que requiere una segunda pasada para construir el ast.
Para construir el árbol de análisis a partir de una gramática y una expresión, primero tendría que convertir su gramática en código de trabajo. Normalmente, dividiría el trabajo en un tokenizador que divide el flujo de entrada que representa la expresión en una lista de tokens y un analizador que toma la lista de tokens y construye un árbol de análisis ast a partir de él.
Entonces la expresión 1 + 2*(3+4) podría dividirse en una lista de tokens como este:
1 - int
+ - add_operator
2 - int
* - mul_operator
( - lparen
3 - int
+ - add_operator
4 - int
) - rparen
La primera columna es el valor de texto real. El segundo representa el tipo de token. Estos tokens se introducen en el analizador, que se crea a partir de su gramática, reconoce los tokens y crea el árbol de análisis.
Entonces, ¿cómo se escribe el tokenizador léxico y el analizador real? Podrías enrollar el tuyo a mano. O, más comúnmente, use un generador de analizador como coco o antlr o lex / yacc. Estas herramientas toman una descripción de su gramática y generan el código para un tokenzier y un analizador. (Existen generadores de código para la mayoría de los lenguajes populares y también para algunos impopulares).
La forma en que construya su analizador depende en gran medida del idioma que utilice. Cómo escribirías un analizador sintáctico en Haskell es completamente diferente de cómo lo harías en, digamos, C.
-
Aquí hay un tutorial que le muestra cómo construir su propio analizador de descenso recursivo.
-
Coco es un generador de analizadores sintácticos para varios idiomas, que también incluye documentación sobre cómo empezar.
-
Si Python es lo tuyo, entonces pyparsing tal vez sea para ti.
Responderé a esto desde una perspectiva general, sin intentar hablar de lexers y analizadores sintácticos.
Un árbol de análisis contiene símbolos no terminales que forman parte de una gramática libre de contexto y muestran la cadena de producciones para obtener una cadena que consta de símbolos terminales, ya sea de forma recursiva o no. Entonces, cuando tiene el árbol de análisis sintáctico, no necesita la gramática; puede derivar la gramática del árbol de análisis sintáctico.
Un AST no contiene ningún símbolo no terminal. Solo contiene símbolos.
Ejemplo:
E
|
E + T
| |
T M * M
| | |
M a b
|
a
Que es una versión muy rápida de mostrar a+a*b. Tenga en cuenta que la forma en que se interpreta el árbol de sintaxis abstracta depende de la precedencia del árbol, del tipo de recorrido que realice (en orden, preorden, posorden). Esta sería una función general que codificará en su árbol de búsqueda. Sin embargo, en general, el AST para ese árbol de análisis podría verse así:
+
| |
a *
| |
a b