Вопросы парсера рекурсивного спуска

Question

У меня два вопроса о том, как написать парсер рекурсивного спуска:

Первый: что, когда у вас есть нетерминал, который может соответствовать одному из нескольких разных нетерминалов? Как вы проверяете, какой путь правильный?

Во-вторых, как вы строите AST? Используя YACC, я могу просто написать кусок кода, который будет выполняться для каждого экземпляра нетерминала, и он имеет специальные переменные, которые ссылаются на «значения» правил. Как вы делаете подобное в парсере рекурсивного спуска?

Answer 1

1. Вы пробуете их по порядку, затем возвращаетесь при неудаче.Или вы доказываете, что ваш язык находится в LL ( k ) и смотрите не более k символов впереди.
2. Для каждого успешного анализаКак правило, вы создаете объект из результата подправил.

Например,

class ASTNode {
  public:
    virtual int eval() = 0;
    virtual ~ASTNode() = 0;
};

// construct this when parsing an integer literal
class Value : ASTNode {
    int v;
  public:
    Value(int v_) : v(v_) {}
    virtual int eval() { return v; }
    virtual ~Value() {}
};

// construct this when parsing "x+y"
class Addition : ASTNode {
    ASTNode *left, *right;
  public:
    Addition(ASTNode *l, ASTNode *r) : left(l), right(r) {}
    virtual int eval() { return l->eval() + r->eval(); }
    virtual ~Addition() { delete left; delete right; }
};

Answer 2

Или урок о том, как сделать себе удар одним легким уроком.

Во-первых, когда у вас нетерминал, который может соответствовать одному из нескольких разных нетерминалов?Как вы проверяете, какой путь правильный?

Вам нужно заглянуть в поток и принять решение.На RDC трудно выполнить возврат.

Более простое решение состоит в том, чтобы спроектировать грамматику так, чтобы ей не нужно было смотреть вперед (усердно).построить AST?

Возвращаемое значение из вызова функции является деревом для всего, что было проанализировано вызовом.Вы помещаете все вложенные вызовы в другой динамически распределенный объект и возвращаете его.