Рекурсивный спускный анализатор

Ответ 1

Вы можете сохранить дерево в памяти или вы можете напрямую создать требуемый код вывода. Хранение промежуточной формы обычно выполняется, чтобы выполнить некоторую обработку кода на более высоком уровне перед генерированием вывода.

В вашем случае, например, было бы просто обнаружить, что ваше выражение не содержит переменных, и поэтому результат является фиксированным числом. Глядя только на один node за один раз, это, однако, невозможно. Чтобы быть более явным, если после просмотра "2 *" вы создаете машинный код для вычисления двойного значения чего-то, что этот код в какой-то степени теряется, когда другая часть, например, "3", потому что ваша программа будет вычислять "3", а затем вычислить дважды каждый раз, тогда как загрузка "6" будет эквивалентной, но короче и быстрее.

Если вы хотите сгенерировать машинный код, вам нужно сначала узнать, для какой машины будет генерироваться код... простейшая модель - это стековый подход. В этом случае вам не нужна логика распределения регистров и легко компилируется непосредственно в машинный код без промежуточного представления. Рассмотрим этот небольшой пример, который обрабатывает только целые числа, четыре операции, унарное отрицание и переменные... вы заметите, что никакой структуры данных не используется вообще: символы исходного кода считываются и машинные инструкции записываются для вывода...

#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;
}

Например, запуск компилятора с 1+y*(-3+x) в качестве ввода вы получаете как вывод

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

Однако этот подход написания компиляторов не очень хорошо масштабируется для оптимизирующего компилятора.

В то время как можно получить некоторую оптимизацию, добавив оптимизатор "глазок" на выходном каскаде, многие полезные оптимизации возможны только для просмотра кода с более высокой точки зрения.

Также даже генерация голого машинного кода может выиграть, увидев больше кода, например, чтобы решить, какой регистр назначить для того, что или решить, какая из возможных реализаций ассемблера будет удобна для определенного кода кода.

Например, одно и то же выражение может быть скомпилировано оптимизирующим компилятором на

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

Ответ 2

Девять раз из десяти вы сохраните AST в памяти за все, что вы делаете после того, как лексирование и разбор сделаны.

Как только у вас есть АСТ, вы можете сделать несколько вещей:

• Оцените его напрямую (возможно, используя рекурсию, возможно, используя собственный собственный стек)
• Преобразуйте его в какой-то другой вывод, например, код на другом языке или какой-либо другой тип перевода.
• Скомпилируйте его в предпочтительный набор команд
• и др.

Ответ 3

Вы можете создать АСТ с Dijkstra алгоритм Shunting-yard.

В какой-то момент у вас будет все выражение или AST в памяти, хотя, если вы не вычислите немедленные результаты при разборе. Это работает с (суб) выражениями, содержащими только литералы или константы времени компиляции, но не с любыми переменными, вычисленными во время выполнения.

Ответ 4

Так что я должен сохранить дерево в памяти или просто использовать рекурсивные вызовы,

Вы будете использовать рекурсивные вызовы в вашем парсере для создания дерева в памяти.

И, конечно же, вы хотите сохранить дерево в памяти для его обработки.

Оптимизирующий компилятор сохраняет несколько представлений кода в памяти (и преобразует их).

Ответ 5

Ответ на вопрос зависит от того, хотите ли вы компилятор, интерпретатор или что-то среднее между ними (интерпретатор, обернутый вокруг промежуточного языка). Если вам нужен интерпретатор, парсер с рекурсивным спусками одновременно оценит выражение, поэтому нет необходимости хранить его в памяти. Если вы хотите компилятор, то константное выражение, подобное этому примеру, может и должно быть оптимизировано, но большинство выражений будут работать с переменными, и вам нужно преобразовать в древовидную форму как промежуточный шаг перед преобразованием в линейную форму.

Гибридный компилятор/интерпретатор обычно компилирует выражения, но это не обязательно. Это часто дешевый способ написания программы, которая выводит исполняемый файл, чтобы просто перевести интерпретатор с исходным кодом. Matlab использует эту технику - код, который действительно был скомпилирован, но были проблемы с согласованностью с интерактивной версией. Однако я бы не допустил сложность генерации дерева разбора для выражений, определяющих проблему.