Разбор синтаксического и рекурсивного спуска деревьев

Question

Разбор синтаксического и рекурсивного спуска деревьев

Итак, я много месяцев изучал и экспериментировал с языковым дизайном, и у меня гораздо лучшее понимание, чем пару месяцев назад. Я все еще смущен некоторыми вещами, хотя …
Я взломал несколько плохих парсеров без исследований, но мне нужно что-то лучше.
Поэтому я пытаюсь написать синтаксический анализатор рекурсивного спуска, поскольку я прочитал, что наиболее логичным является написать вручную. Насколько я понимаю, каждое правило реализовано в своей собственной функции. Поэтому я думаю, что понимаю, как бы написать об этом, но только о первой половине … Работа синтаксического анализатора заключается в создании синтаксического дерева или чего-то подобного, верно? Я также пытался исследовать эту тему, но мне не удалось найти каких-либо примеров того, как дерево представлено в языке. Я пишу на D, потому что это мой любимый язык, но он очень похож на C / C ++, поэтому я буду понимать любые примеры, написанные на этих языках или псевдокоде.

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

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

4

abstract-syntax-tree c++d parsing recursion

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Дерево, как правило, представляется в виде структуры, содержащей указатели на своих дочерних элементов и node член, который хранит свой тип узла или он принадлежит к определенному классу, так что вы можете получить его фактический тип (то есть, если он содержит арифметическое выражение, оператор if, цикл и т. д.).

Простой пример действительно был бы if Скажите, как вы упомянули. Для этого вы должны сделать что-то вроде этого (псевдо-C следует):

enum AST_Node {
Node_if,
Node_and,
Node_or,
Node_not,
Node_equal,
Node_less,
// etc., other node types follow
};

struct AST {
struct AST *children[MAX_CHILDREN]; // don't do this
enum AST_Node node;
};

struct AST *parse_if_statement()
{
// expect tokens in order
expect("if");

// parse condition
expect("(");
struct AST *condition = parse_expression();
expect(")");

// parse two child statements
struct AST *then_branch = parse_statement();
struct AST *else_branch = NULL;
if (accept("else")) {
else_branch = parse_statement();
}

// create AST, fill in children
struct AST *if_statement = new_AST_node(Node_if);
if_statement->children[0] = condition;
if_statement->children[1] = then_branch;
if_statement->children[2] = else_branch;

return if_statement;
}

Таким образом, в основном вы просто ожидаете / принимаете постоянные лексические элементы («если», круглые скобки вокруг условия и т. Д.), Затем вы передаете разбор поддеревьев (условие и две ветви) соответствующим функциям синтаксического анализатора.

И вот как вы ходите по дереву: вы в основном делаете прогулка вглубь, составление или интерпретация каждого ребенка по порядку. Затем вы добавляете дополнительную семантику, которую подразумевает тип узла поддерева, который в настоящее время интерпретируется / компилируется.

Value *interpret_if_statement(struct AST *ast)
{
assert(ast->node == Node_if);

struct AST *condition = ast->children[0];
struct AST *then_branch = ast->children[1];
struct AST *else_branch = ast->children[2];

// evaluate condition
Value *condval = interpret_expression(condition);

if (condval->bool_value == TRUE) {
// if condition is true, interpret "then" branch
return interpret_statement(then_branch);
} else if (else_branch != NULL) {
// otherwise interpret "else" branch, if any
return interpret_statement(else_branch);
} else {
return NULL;
}
}

9