c++ - recursividad - Analizador de Descensos Recursivos

recursividad java

Question

El libro ''Modern Compiler Design'' es el buen libro sobre compiladores. En su código fuente, algo que me molesta es AST o Abstract Syntax Tree. Supongamos que queremos escribir un analizador de expresiones en paréntesis que analiza algo como: ((2+3)*4) * 2 ! El libro dice que tenemos un AST como:

        ((2+3)*4) * 2
          /   |     /
       (2+3)  *4    * 2
        /     | /
     (2+3)    *  4
     / | /
    2  + 3

Así que debería guardar un árbol en la memoria o simplemente usar llamadas recursivas; Nota: si no lo guardo en la memoria, ¿cómo puedo convertirlo en código de máquina?

Código del analizador:

int parse(Expression &expr)
{
  if(token.class==''D'')
  { 
    expr.type=''D'';
    expr.value=token.val-''0'';
    get_next_token();
    return 1;
  }
  if(token.class==''('') 
  {
    expr.type=''P'';
    get_next_token();
    parse(&expr->left);
    parse_operator(&expr->op);
    parse(&expr->right);
    if(token.class!='')'')
      Error("missing )");
    get_next_token();
    return 1;
  }
  return 0;
}

La gramática es:

expr -> expr | (expr op expr)
digit   -> 0|1|2....|9
op  -> +|*

Answer 1

Así que debería guardar un árbol en la memoria o simplemente usar llamadas recursivas;

Utilizará llamadas recursivas en su analizador para construir el árbol en la memoria.

Y, por supuesto, desea mantener el árbol en la memoria para procesarlo.

Un compilador de optimización mantiene varias representaciones del código en la memoria (y las transforma).

Answer 2

La respuesta a la pregunta depende de si desea un compilador, un intérprete o algo intermedio (un intérprete envuelto alrededor de un idioma intermedio). Si desea un intérprete, un analizador de descenso recursivo evaluará la expresión al mismo tiempo, por lo que no es necesario mantenerlo en la memoria. Si desea un compilador, entonces una expresión constante como el ejemplo puede y debe ser optimizada, pero la mayoría de las expresiones operarán en variables, y usted necesita convertirse a la forma de árbol como un paso intermedio antes de convertirse a una forma lineal.

Un compilador / intérprete híbrido usualmente compilará expresiones, pero no tiene que hacerlo. A menudo es una forma barata de escribir un programa que genera un ejecutable para simplemente envolver al intérprete con el código fuente. Matlab usa esta técnica: el código solía ser compilado genuinamente pero había problemas con la consistencia con la versión interactiva. Sin embargo, no permitiría que la dificultad de generar un árbol de análisis de expresiones determine el problema.

Answer 3

Nueve veces de cada diez guardará el AST en la memoria para lo que esté haciendo después de realizar el análisis y el análisis.

Una vez que tienes un AST puedes hacer una serie de cosas:

• Evalúelo directamente (tal vez usando la recursión, quizás usando su propia pila personalizada)
• Conviértalo en otra salida, como el código en otro idioma o algún otro tipo de traducción.
• Compílalo al conjunto de instrucciones preferido
• etc.

Answer 4

Puede almacenar el árbol en la memoria o puede producir directamente el código de salida requerido. El almacenamiento de la forma intermedia normalmente se realiza para poder realizar algún procesamiento en el código a un nivel superior antes de generar la salida.

En su caso, por ejemplo, sería sencillo descubrir que su expresión no contiene variables y, por lo tanto, el resultado es un número fijo. Sin embargo, si solo se observa un nodo a la vez, esto no es posible. Para ser más explícitos, si después de ver "2 *" genera código de máquina para calcular el doble de algo, este código se desperdicia cuando la otra parte es, por ejemplo, "3" porque su programa computará "3" y luego computará duplicar eso cada vez que solo cargar "6" sería equivalente pero más corto y más rápido.

Si desea generar el código de la máquina, primero debe saber para qué tipo de máquina se generará el código ... el modelo más simple utiliza un enfoque basado en la pila. En este caso, no necesita lógica de asignación de registros y es fácil compilar directamente en código de máquina sin la representación intermedia. Considere este pequeño ejemplo que maneja solo números enteros, cuatro operaciones, negación unaria y variables ... notará que no se utiliza ninguna estructura de datos: se leen los caracteres del código fuente y se escriben las instrucciones de la máquina en la salida ...

#include <stdio.h>
#include <stdlib.h>

void error(const char *what) {
    fprintf(stderr, "ERROR: %s/n", what);
    exit(1);
}

void compileLiteral(const char *& s) {
    int v = 0;
    while (*s >= ''0'' && *s <= ''9'') {
        v = v*10 + *s++ - ''0'';
    }
    printf("    mov  eax, %i/n", v);
}

void compileSymbol(const char *& s) {
    printf("    mov  eax, dword ptr ");
    while ((*s >= ''a'' && *s <= ''z'') ||
           (*s >= ''A'' && *s <= ''Z'') ||
           (*s >= ''0'' && *s <= ''9'') ||
           (*s == ''_'')) {
        putchar(*s++);
    }
    printf("/n");
}

void compileExpression(const char *&);

void compileTerm(const char *& s) {
    if (*s >= ''0'' && *s <= ''9'') {
        // Number
        compileLiteral(s);
    } else if ((*s >= ''a'' && *s <= ''z'') ||
               (*s >= ''A'' && *s <= ''Z'') ||
               (*s == ''_'')) {
        // Variable
        compileSymbol(s);
    } else if (*s == ''-'') {
        // Unary negation
        s++;
        compileTerm(s);
        printf("    neg  eax/n");
    } else if (*s == ''('') {
        // Parenthesized sub-expression
        s++;
        compileExpression(s);
        if (*s != '')'')
            error("'')'' expected");
        s++;
    } else {
        error("Syntax error");
    }
}

void compileMulDiv(const char *& s) {
    compileTerm(s);
    for (;;) {
        if (*s == ''*'') {
            s++;
            printf("    push eax/n");
            compileTerm(s);
            printf("    mov  ebx, eax/n");
            printf("    pop  eax/n");
            printf("    imul ebx/n");
        } else if (*s == ''/'') {
            s++;
            printf("    push eax/n");
            compileTerm(s);
            printf("    mov  ebx, eax/n");
            printf("    pop  eax/n");
            printf("    idiv ebx/n");
        } else break;
    }
}

void compileAddSub(const char *& s) {
    compileMulDiv(s);
    for (;;) {
        if (*s == ''+'') {
            s++;
            printf("    push eax/n");
            compileMulDiv(s);
            printf("    mov  ebx, eax/n");
            printf("    pop  eax/n");
            printf("    add  eax, ebx/n");
        } else if (*s == ''-'') {
            s++;
            printf("    push eax/n");
            compileMulDiv(s);
            printf("    mov  ebx, eax/n");
            printf("    pop  eax/n");
            printf("    sub  eax, ebx/n");
        } else break;
    }
}

void compileExpression(const char *& s) {
    compileAddSub(s);
}

int main(int argc, const char *argv[]) {
    if (argc != 2) error("Syntax: simple-compiler <expr>/n");
    compileExpression(argv[1]);
    return 0;
}

Por ejemplo, ejecutando el compilador con 1+y*(-3+x) como entrada se obtiene como salida

mov  eax, 1
push eax
mov  eax, dword ptr y
push eax
mov  eax, 3
neg  eax
push eax
mov  eax, dword ptr x
mov  ebx, eax
pop  eax
add  eax, ebx
mov  ebx, eax
pop  eax
imul ebx
mov  ebx, eax
pop  eax
add  eax, ebx

Sin embargo, este enfoque de escribir compiladores no se adapta bien a un compilador optimizado.

Si bien es posible obtener una optimización agregando un optimizador de "mirilla" en la etapa de salida, muchas optimizaciones útiles son posibles solo mirando el código desde un punto de vista más alto.

También incluso la generación de código de máquina simple podría beneficiarse al ver más código, por ejemplo, para decidir qué registro asignar a qué o decidir cuál de las posibles implementaciones de ensamblador sería conveniente para un patrón de código específico.

Por ejemplo, un compilador optimizador podría compilar la misma expresión para

mov  eax, dword ptr x
sub  eax, 3
imul dword ptr y
inc  eax

Answer 5

Puedes crear un AST con el algoritmo Shunting-yard de Dijkstra.

Sin embargo, en algún momento tendrá la expresión completa o AST en la memoria, a menos que calcule resultados inmediatos mientras analiza. Esto funciona con (sub) expresiones que contienen solo literales o constantes de tiempo de compilación, pero no con ninguna variable calculada en tiempo de ejecución.